Системное программное обеспечение. Лабораторный практикум - Алексей Молчанов

Скачать книгу

– операции присваивания.

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

      Рис. 2.1. Фрагмент графа переходов КА для распознавания всех лексем, кроме ключевых слов.

      Полный граф переходов КА будет очень громоздким и неудобным для просмотра, поэтому проиллюстрируем его несколькими фрагментами. На рис. 2.1 изображен фрагмент графа переходов КА, отвечающий за распознавание разделителей, комментариев, знака присваивания, переменных и констант (всех лексем входного языка, кроме ключевых слов).

      На рис. 2.2 изображен фрагмент графа переходов КА, отвечающий за распознавание ключевых слов if и then (этот фрагмент имеет ссылки на состояния, изображенные на рис. 2.1). Аналогичные фрагменты можно построить и для других ключевых слов.

      Рис. 2.2. Фрагмент графа переходов КА для ключевых слов if и then.

      На фрагментах графа переходов КА, изображенных на рис. 2.1 и 2.2, приняты следующие обозначения:

      • А– любой алфавитно-цифровой символ;

      • А(*) – любой алфавитно-цифровой символ, кроме перечисленных в скобках;

      • П– любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);

      • Б– любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_);

      • Б(*) – любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_), кроме перечисленных в скобках;

      • Ц– любая цифра от 0 до 9;

      • F – функция обработки таблицы лексем, вызываемая при переходе КА из одного состояния в другое. Обозначения ее аргументов:

      – v – переменная, запомненная при работе КА;

      – d – константа, запомненная при работе КА;

      – a – текущий входной символ КА.

      С учетом этих обозначений, полностью КА можно описать следующим образом:

      M(Q,Σ,δ,q0,F):

      Q = {H, C, G, V, D, I1, I2, T1, T2, T3, T4, E1, E2, E3, E4, O1, O2, X1, X2, X3, A1, A2, A3, F}

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

      q 0 = H;

      F = {F}.

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

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

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

      • состояния T1, T2, T3, T4 – ключевому слову then;

      • состояния E1, E2, E3, E4 – ключевому слову else;

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

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

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

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

Скачать книгу