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

• во-первых, распознаватель не может определить, к какому оператору if относить очередную лексему else (такой конфликт можно наглядно проиллюстрировать на примере оператора: if(a

• во-вторых, конец логического выражения в условии после ключевых слов if (определяет лексема) (закрывающая круглая скобка), но точно такая же лексема может стоять и в конце арифметического выражения перед ключевым словом else: распознаватель не может решить, куда относится очередная лексема) – к условному оператору или к арифметическому выражению. Это еще одна причина конфликта.

Первое противоречие можно разрешить на основании правил, общепринятых для многих языков программирования: ключевое слово else должно всегда относиться к ближайшему оператору if. Второе противоречие можно разрешить, если проверять, что предшествует закрывающей круглой скобке – логическое или арифметическое выражение. Тогда конфликт между сверткой и переносом должен решаться в пользу переноса, чтобы анализатор мог выбрать максимально длинный условный оператор и отнести else к ближайшему if, если перед скобкой следует логическое выражение, в противном случае должна выполняться свертка.

Следовательно, из двух знаков, которые могут быть помещены в клетку матрицы операторного предшествования на пересечении столбца, помеченного else, и строки, помеченной), следует выбрать знак «=.» («составляет основу»), имея в виду, что он требует дополнительного анализа второго символа от верхушки стека. Поскольку других конфликтов в исходной грамматике нет, то можно заполнить матрицу операторного предшествования, которая представлена в табл. 5.7 (чтобы сократить размер таблицы, отношения предшествования в ней обозначены символами «<.», «.>» и «=.» без точки «»).

Более подробно о вариантах модификаций алгоритма «сдвиг-свертка» для различных грамматик, в которых присутствуют противоречия между выполнением операций «сдвиг» и «свертка» на этапе синтаксического разбора, можно узнать в [1, 2].

Для проверки условия наличия логического выражения перед закрывающей скобкой и разрешения конфликта между переносом и сверткой для символа else используется функция корректировки отношений предшествования CorrectRul е (модуль SyntRule, листинг П3.6 в приложении 3).

Внимание!

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

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

Например, если бы правила грамматики G для символа O выглядели бы следующим образом (без использования ключевого символа do):

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

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

if (а<0) while (а<10) а:=а+1 else а:=1;

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

Таблица 5.7. Матрица операторного предшествования

В таком случае проблематично выполнить преобразования грамматики и привести ее к виду грамматики операторного предшествования без добавления в язык новых ключевых слов. Поскольку приведенный выше синтаксис оператора while соответствует языкам C и C++, можно проиллюстрировать, как указанная проблема решается в этих языках [13, 25, 32, 39]. Тогда в грамматику надо включить сразу два новых нетерминальных символа (обозначим их Р и R), а блок правил грамматики G для нетерминальных символов L и О будет выглядеть следующим образом:

L → Р| L;P | L;

О → if(B) О; else Р | if(B) R else Р | if(B) Р | while(B) Р | а:=Е

R → begin L end

Р → О | R

И показанный выше оператор будет выглядеть так:

if (а<0) while (а<10) а:=а+1; else а:=1;

В языках C и C++ операторным скобкам begin и end соответствуют лексемы { и }, а оператор присваивания обозначается одним символом: =. Но суть подхода этот пример иллюстрирует верно: в этих языках для условного оператора правила различны в зависимости от того, входит в него составной оператор или одиночный оператор (точка с запятой ставится перед else для одиночных операторов в отличие от языка Pascal, где этой проблемы нет, так как конфликт между then и else может быть разрешен указанным выше способом, как в табл. 5.7). Желающие могут построить для такого языка матрицу операторного предшествования и убедиться, что она строится без конфликтов.

Построение остовной грамматики

После того как заполнена матрица операторного предшествования, на основе исходной грамматики G можно построить остовную грамматику G'({prog,end.,if, else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E},P',E) с правилами P':

E → prog E end. – правило № 1

E → E | E;E | E; – правила № 2, 3 и 4

Е → if(E) Е else Е | if(E) Е | begin Еend | while(£)do Е | а:=Е – правила № 5-9

Е → Е or Е | Е хог Е|Е – правила № 10, 11 и 12

Е → Е andE | Е – правила № 13 и 14

Е → Е<Е | Е>Е | £=.£ | Е<>Е | (Е) | not(E) – правила № 15-20

Е → Е-Е | Е+Е | Е – правила № 21, 22 и 23

Е → urn Е|Е – правила № 24 и 25

Е → (_Е) | а | с – правила № 26, 27 и 28

Всего имеем 28 правил. Жирным шрифтом в грамматике и в правилах выделены терминальные символы.

При внимательном рассмотрении видно, что в остовной грамматике неразличимы правила 2, 12, 14, 23 и 25, а также правила 19 и 26. Но если первая группа правил не имеет значения, то во втором случае у распознавателя могут возникнуть проблемы, связанные с тем, что некоторые ошибочные входные цепочки он будет считать допустимыми (например оператор а:=(а or b);, который во входном языке недопустим). Это связано с тем, что круглые скобки определяют приоритет как логических, так и арифметических операций, и хотя они несут одинаковую синтаксическую нагрузку, распознаватель должен их различать, поскольку семантика этих скобок различна. Для этого дополним остовную грамматику еще одним нетерминальным символом B, который будет обозначать логические выражения. Подставив этот символ в соответствующие правила, получим новую остовную грамматику G»({prog,end.,if,else,begin,end,while,do,or,xor,and,not,<,>,=,<>,(,), – ,+,um,a,c,=}, {E,B},P», E) с правилами P»:

E → prog E end. – правило № 1

E → E | E;E | E; – правила № 2-4

E → if(B) EelseE | if(B) E | begin Eend | while(B)do E | a:=E – правила № 5-9

В → В or В | В хог В | В – правила № 10-12

В → В and В | В – правила № 13 и 14

В → Е<Е | Е>Е | Е=Е | Е<>Е | (В) | not(B) – правила № 15-20

Е → Е-Е | Е+Е | Е – правила № 21-23

Е → urn Е | Е – правила № 24 и 25

Е → (Е) | а | с – правила № 26-28

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

Реализация синтаксического распознавателя

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

Модуль SyntSymb (листинг П3.7, приложение 3), который реализует функционирование алгоритма «сдвиг-свертка» для грамматик операторного предшествования, можно использовать, не внося в него никаких изменений, так как он не зависит от входного языка. Требуется перестроить только модуль SyntRulе, внеся в него новые правила грамматики и новую матрицу операторного предшествования. Полученный в результате программный модуль представлен в листинге П3.6 в приложении 3 (обратите внимание на функцию MakeSymbolStr, которая возвращает имена нетерминальных символов для правил остовной грамматики!).

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