 |
Лексический анализатор для поиска строк в исходном тексте программы
|
|
|
|
Имеется исходный текст программы, написанный на языке Pascal, необходимо найти в этом тексте все строковые константы и записать их в отдельный файл. Эта задача является примером практического применения лексических анализаторов, причем в данном случае лексический анализатор не является частью компилятора, а выступает как самостоятельная программная единица.
В данном случае задача лексического анализатора значительно уже, чем задача лексического анализатора компилятора Pascal. Анализатор должен найти только все строковые константы, не обращая никакого внимания на все остальные лексемы. Также нет необходимости заполнять таблицу лексем и таблицу идентификаторов. И, конечно же, нет необходимости проверять синтаксическую правильность исходной программы – это не задача лексического анализатора.
Построение лексического анализатора начнем с построения грамматики исходного языка. Исходным языком является язык строковых констант Pascal. Строковая константа в языке Pascal может состоять из одной и более частей, соединенных между собой знаком +. Каждая часть строковой константы начинается с символа ‘ и заканчивается символом ‘. В состав строковых констант могут входить любые алфавитно-цифровые символы, но если в нее надо включить одинарную кавычку, то она должна быть повторена дважды: ‘’. Также в строку могут быть включены коды символов. В языке Pascal они записываются восьмеричными цифрами, следующими за знаком #. Коды символов включаются в строку либо сразу после завершающей одинарной кавычки, либо с помощью знака +. Для лексического анализатора строковая константа считается законченной, если после очередной ее части он встретил любой алфавитно-цифровой символ, кроме знаков + и #, или конец файла. Все символы, не входящие в строковые константы, анализатором должны игнорироваться.
|
|
|
Будем обозначать символом b все незначащие символы языка (пробелы, знаки табуляции и перевода строки), символом d – все допустимые восьмеричные цифры (от 0 до 7), а символом а – все остальные алфавитно-цифровые символы. Символом 
будем обозначать конец файла.
Тогда грамматику строковых констант можно записать следующим образом: 
, а ее правила P:
Данная грамматика недостаточна для построения лексического анализатора, поскольку не учитывает комментарии, которые могут встречаться в тексте исходной программы. Анализатор должен игнорировать комментарии и все строковые константы, которые могут быть внутри комментариев.
Язык Pascal предусматривает два независимых варианта комментариев. Первый вариант: комментарий начинается последовательностью символов (* и заканчивается последовательностью символов *), второй вариант: комментарий начинается с символа { и заканчивается символом }. Комментарии могут содержать любые алфавитно-цифровые символы.
Грамматику комментариев языка Pascal можно записать следующим образом: 
, а ее правила P:
.
Здесь а обозначает уже все алфавитно-цифровые символы, кроме символов, обозначенных ранее через b и d, а также символов ‘, +, #, (, *,), { и }.
На основе двух построенных грамматик можно реализовать лексический анализатор, решающий задачу в два этапа. На первом этапе из исходной программы исключаются все комментарии анализатором, на основе грамматики G2, и полученный в результате текст записывается в промежуточное хранилище данных (файл). На втором этапе исходный текст из промежуточного хранилища обрабатывается анализатором на основе грамматики G1 и в нем ищутся все строковые константы. Получаем двухпроходный лексический анализатор.
|
|
|
Однако анализатор можно упростить, если построить грамматику языка, который будет включать в себя и строковые константы, и комментарии языка Pascal. Необходимо только учесть, что строки и комментарии могут следовать в тексте исходной программы друг за другом в произвольном порядке, а также то, что символы, ограничивающие комментарии – (, *,), {, } – могут входить в состав строки.
В этом случае грамматику можно записать следующим образом:
, а ее правила P:
На основе этой грамматики можно построить однопроходный лексический анализатор, выполняющий поиск строковых констант в исходной программе на языке Pascal. Данный анализатор игнорирует комментарии, а также весь остальной текст исходной программы, не содержащий строковых констант.
Эта грамматика является автоматной грамматикой, поэтому на ее основе можно построить КА. Он будет иметь 12 состояний. Данный автомат будет детерминированным, поэтому его сразу можно реализовать в программном коде.
Лексический анализатор, моделирующий работу данного КА, начинает свое функционирование с начала просмотра исходного текста программы. При этом КА находится в начальном состоянии. Если символ на входе не относится ни к комментарию, ни к строковой константе, то анализатор просто пропускает его – при этом КА сразу переходит в конечное состояние, а потом анализатор должен вернуть его в начальное состояние. Если символ относится к строковой константе, то КА начинает переходить по всем состояниям, относящимся к строковой константе (все состояния Si и Di). Лексический анализатор должен при этом запоминать все символы константы (строку). При переходе КА в конечное состояние S анализатор записывает строку в результирующий файл, а КА возвращает в начальное состояние. Если встречаются комментарии, то лексический анализатор должен пропустить все символы до конца комментария (КА при этом находится в состояниях Сi).
Таким образом, граф переходов КА лексического анализатора поиска строковых констант языка Pascal должен быть нагружен функциями:
· создания я пустой строки для записи очередной строковой константы;
· добавления символа или подстроки в конец строковой константы;
|
|
|
· записи строковой константы в результирующий файл и очистки строки для следующей строковой константы.
Построенный КА не является полностью определенным. Это вызвано тем, что существуют ошибки, которые могут быть обнаружены с помощью данного лексического анализатора. Примером такой обнаруживаемой ошибки является незакрытый комментарий. Ошибки можно обозначить отдельным нетерминальным символом грамматики Е и соответствующим состоянием КА. Правило обнаружения ошибок можно записать в виде:
Дополнив грамматику G этим правилом, можно построить полностью определенный детерминированный КА. Дуги переходов в состояние Е этого автомата надо нагрузить функцией выдачи пользователю соответствующего сообщения об ошибке.
Содержание работы
В ходе выполнения работы студенты должны выполнить следующие задания:
1. Реализовать лексический анализатор на основе построенной грамматики и проверить его работу на любом исходном тексте программы.
2. Построить сканер, который бы находил и исключал из входного текста все комментарии языка С++. В языке С++ возможны два типа комментариев: обычный комментарий, ограниченный символами /* и */, и строчный комментарий, начинающийся с символов // и заканчивающийся концом строки.
3. Построить сканер, который выделял бы из текста входной программы на языке С все содержащиеся в ней строковые константы и записывал их в отдельный файл. Строковые константы в языке С состоят из строк, одиночных символов и кодов символов. Строки ограничены символами “ ” (двойные кавычки), одиночные символы – символами ‘ ’ (одинарные кавычки), а коды символов начинаются со знака \ и содержат цифры.
5. Контрольные вопросы
1. Сравните восходящий и нисходящий распознаватели. Какими преимуществами и недостатками обладает каждый из этих методов?
2. Какой цели служит преобразование правил КС-грамматик? Всегда ли это преобразование ведет к упрощению правил?
3. На алгоритме какого распознавателя основан метод рекурсивного спуска? Можно ли реализовать распознаватель по методу расширенного рекурсивного спуска для грамматики, содержащей левую рекурсию?
|
|
|
4. За счет сего класс LL(1)-грамматик является более широким, чем класс КС-грамматик?
5. На каком алгоритме основана работа распознавателя для LL(k)-грамматики?
Лабораторная работа № 2
|
|
|
