Книга: Системное программное обеспечение. Лабораторный практикум

Описание лексического анализатора

Описание лексического анализатора

Для построения лексического анализатора воспользуемся подходом, использованном в лабораторной работе № 2.

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

• двенадцать ключевых слов языка (prog, end., if, else, begin, end, while, end, not, or, xor и and);

• разделители: открывающая и закрывающая круглые скобки, точка с запятой;

• знаки операций: присваивание, сравнение (четыре знака), сложение, вычитание и унарный минус;

• идентификаторы;

• целые десятичные константы без знака.

Можно заметить, что end и end. – это разные лексемы.

Кроме перечисленных лексем распознаватель должен уметь определять и исключать из входного текста комментарии, принцип построения которых описан выше. Для выделения комментариев ключевыми символами должны быть открывающая и закрывающая фигурные скобки.

Отдельного внимания заслуживает знак «унарный минус», который не случайно был взят в качестве иллюстрации для этого примера.

Если не делать различий между унарным минусом и бинарным, то правила грамматики G для символов E, T и F имели бы следующий вид:

E ? E—T | E+T | T

T ? —T | F

F ? (E) | a | c

Однако такая грамматика будет очень сложна для синтаксического анализа, поскольку в ней возникает проблема выбора правила между E—T и – T при выполнении свертки (можно проверить и прийти к выводу, что она, например, не является грамматикой операторного предшествования). Преобразования для этой грамматики неочевидны.

Но возможно более простое решение, если понять, как различить две операции (унарный и бинарный знаки «минус») на этапе лексического анализа. Различие можно сделать, если заметить, что бинарный минус всегда следует после операнда (переменной или константы) или после закрывающей круглой скобки, в то время как унарный минус – или после знака операции, или после открывающей круглой скобки. Такой анализ вполне по силам КА, если в него добавить еще одно состояние, которое будет определять, какую лексему (унарный или бинарный минус) сопоставлять с входным символом «—». Поскольку перед унарным минусом, как и перед любыми другими лексемами, может быть комментарий, то придется добавить два состояния (чтобы различать, в каком месте КА встретилось начало комментария, и после завершения комментария вернуться в то же место).

Таким образом, незначительное усложнение КА лексического анализатора позволит избежать серьезных проблем на этапе синтаксического анализа.

Данный пример иллюстрирует, как важно рационально провести границу между лексическим и синтаксическим анализом.

Другой пример из заданного входного языка еще более очевиден, хотя он и не ведет к столь серьезным осложнениям при лексическом разборе: это знак операции «не равно» – «<>». Его можно рассматривать как две лексемы или как одну. В первом случае проверка правильности этой операции будет идти на этапе синтаксического анализа, во втором случае – на этапе лексического анализа. Оба варианта могут быть без проблем реализованы, но второй из них представляется все же более логичным.

Как правило, если есть возможность выявления ошибки на более ранних стадиях компиляции, лучше такой возможностью воспользоваться. Из этой рекомендации есть исключения – ей лучше не следовать в тех случаях, когда ранний анализ не дает существенных преимуществ, но может нарушить логическую стройность языка или грамматики, затруднит их восприятие человеком.

Например, в том же входном языке сочетания if(и while(могут быть рассмотрены как единые лексемы (обозначим их if_ и w_l) и выявлены на этапе лексического анализа. При этом синтаксический анализатор не получает никаких преимуществ, но правила грамматики для нетерминального символа будут иметь вид:

О ? if_ В) О else О | if_ В) О | begin L end | w_l B)do О | а:=Е

Логическая целостность и структура правил нарушены, так как человеку трудно воспринимать закрывающую скобку при отсутствии открывающей, а потому от такого варианта лучше отказаться (хотя окончательное решение, конечно, всегда остается за разработчиком компилятора).

В данном языке лексический анализатор всегда может однозначно определить границы лексемы, поэтому нет необходимости в его взаимодействии с синтаксическим анализатором и другими элементами компилятора.

Приняв во внимание правила и соглашения, рассмотренные для КА в лабораторной работе № 2, полностью КА можно описать следующим образом:

M(Q,?,?,q₀,F):

Q = {H, C, C1, G, S, L, V, D, P1, P2, P3, P4, E1, E2, E3, I1, I2, L2, L3, L4, B1, B2, B3, B4,

B5, W1, W2, W3, W4, W5, O1, O2, D1, D2, X1, X2, X3, A1, A2, A3, N1, N2, N3, F};

? = А (все допустимые алфавитно-цифровые символы);

q₀ = H;

F = {F, S}.

Функция переходов (?) для этого КА приведена в приложении 2.

Из начального состояния КА литеры «p», «e», «i», «b», «w», «o», «x», «a» и «n» ведут в начало цепочек состояний, каждая из которых соответствует ключевому слову (цепочка, начинающаяся с «e», соответствует трем ключевым словам):

• состояния P1, P2, P3, P4 – ключевому слову prog;

• состояния E1, E2, E3 – ключевым словам end и end.;

• состояния I1, I2 – ключевому слову if;

• состояния B1, B2, B3, B4, B5 – ключевому слову begin;

• состояния W1, W2, W3, W4, B5 – ключевому слову while;

• состояния E1, L2, L3, L4 – ключевому слову else;

• состояния D1, D2 – ключевому слову do;

• состояния O1, O2 – ключевому слову or;

• состояния X1, X2, X3 – ключевому слову хог;

• состояния A1, A2, A3 – ключевому слову and;

• состояния N1, N2, N3 – ключевому слову not.

Остальные литеры ведут к состоянию, соответствующему переменной (идентификатору) – V. Если в какой-то из цепочек встречается литера, не соответствующая ключевому слову, или цифра, то КА также переходит в состояние V, а если встречается граница лексемы – запоминает уже прочитанную часть ключевого слова как переменную (чтобы правильно выделять такие идентификаторы, как «i» или «els», которые совпадают с началом ключевых слов).

Цифры ведут в состояние, соответствующее входной константе, – D. Открывающая фигурная скобка ведет в состояние C, которое соответствует обнаружению комментария – из этого состояния КА выходит, только если получит на вход закрывающую фигурную скобку. Еще одно состояние – G – соответствует лексеме «знак присваивания». В него КА переходит, получив на вход двоеточие, и ожидает в этом состоянии символа «равенство».

Рис. 5.1. Граф переходов сокращенного КА (без учета ключевых слов).

Знаки арифметических операций («+» и «—»), знаки операций сравнения («<.», «.>» и «=.»), открывающая круглая скобка, а также последние символы ключевых слов переводят КА в состояние S, которое отличается от начального состояния тем, что в этом состоянии КА воспринимает символ «—» как знак унарной операции отрицания, а не как знак операции вычитания. Если в состоянии S на вход КА поступает открывающая фигурная скобка, то он переходит в состояние C1 (а не в состояние C), из которого по закрывающей фигурной скобке опять возвращается в состояние S.

В еще одно состояние – состояние L – КА переходит, когда на его вход поступает знак «<.». В состоянии L автомат проверяет, является ли знак «<.» началом лексемы «<>» («неравно») или же это отдельная лексема «<.» («меньше»).

Состояние H – начальное состояние КА, а состояния F и S – его конечные состояния. Поскольку КА работает с непрерывным потоком лексем, перейдя в конечное состояние H, он тут же должен возвращаться в начальное состояние, чтобы распознавать очередную лексему. Поэтому в моделирующей программе два состояния (H и F) можно объединить в одно.

В функцию переходов КА не входит состояние «ошибка», чтобы не загромождать ее. В это состояние КА переходит всегда, когда получает на вход символ, по которому нет переходов из текущего состояния.

Видно, что граф переходов для данного КА будет слишком громоздким, чтобы его можно было наглядно представить на рисунке. Граф переходов сокращенного КА (без учета распознавания ключевых слов) представлен на рис. 5.1.

Реализация данного КА выполнена аналогично реализации КА, построенного в лабораторной работе № 2. Для описания структур данных лексем, которые не зависят от входного языка, используется модуль LexElem, который был создан при выполнении лабораторной работы № 2 (листинг П3.4, приложение 3). Типы допустимых лексем описаны в модуле LexType (листинг П3.3, приложение 3), а функционирование автомата моделируется в модуле LexAuto (листинг П3.5, приложение 3).

Оглавление книги