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

Рис. 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).

Для построения синтаксического анализатора будем использовать анализатор на основе грамматик операторного предшествования. Этот анализатор является линейным распознавателем (время анализа линейно зависит от длины входной цепочки), для него существует простой и эффективный алгоритм построения распознавателя на основе матрицы предшествования [1–3, 7]. К тому же алгоритм «сдвиг-свертка» для данного типа анализатора был разработан при выполнении лабораторной работы № 3, а поскольку он не зависит от входного языка, он может быть без модификаций использован в данной работе.

Для построения анализатора на основе грамматики операторного предшествования необходимо построить матрицу операторного предшествования (порядок ее построения был детально рассмотрен при выполнении лабораторной работы № 3).

Построим множества крайних левых и крайних правых символов грамматики G. На первом шаге получим множества, приведенные в табл. 5.3.

После завершения построения мы получим множества, представленные в табл. 5.4 (детальное построение множеств крайних левых и крайних правых символов описано при выполнении лабораторной работы № 3).

После этого необходимо построить множества крайних левых и крайних правых терминальных символов. На первом шаге возьмем все крайние левые и крайние правые терминальные символы из правил грамматики G. Получим множества, представленные в табл. 5.5.

Дополним множества, представленные в табл. 5.5, на основе ранее построенных множеств крайних левых и крайних правых символов, представленных в табл. 5.4 (алгоритм выполнения этого действия подробно рассмотрен при выполнении лабораторной работы № 3). Получим множества крайних левых и крайних правых терминальных символов, которые представлены в табл. 5.6.

После построения множеств, представленных в табл. 5.6, можно заполнять матрицу операторного предшествования.

Однако при заполнении матрицы операторного предшествования возникает проблема: символ) стоит рядом с символом else в правиле О → if(B) О else О (между ними один нетерминальный символ О). Значит, в клетке матрицы операторного предшествования на пересечении столбца, помеченного else, и строки, помеченной), должен стоять знак «=.» («составляют основу»). Но в то же время символ else стоит справа от нетерминального символа О в том же правиле О → if(B) О else О, а в множество крайних правых терминальных символов R t(0) входит символ). Тогда в клетке матрицы операторного предшествования на пересечении столбца, помеченного else, и строки, помеченной), должен стоять знак «.>» («следует»). Получаем противоречие (в одну и ту же клетку матрицы предшествования должны быть помещены два знака – «=.» и «>»), которое говорит о том, что исходная грамматика G не является грамматикой операторного предшествования.

Как избежать этого противоречия?

Во-первых, можно изменить входной язык так, чтобы он удовлетворял требованиям задания на курсовую работу, но не содержал операторов, приводящих к таким неоднозначностям. Например, добавив во входной язык ключевые слова then и endif, для нетерминального символа О получим правила:

O → if B then O else O endif | if B then O endif | begin L end | while(B)do O | a:=E

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