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

Во-вторых, можно, не изменяя языка, попытаться преобразовать грамматику G к такому виду, чтобы она удовлетворяла требованиям грамматик операторного предшествования (как уже отмечалось ранее, а также как сказано в [1, 3, 7], известно, что формальных рекомендаций по выполнению таких преобразований не существует).

Например, если добавить во входной язык только ключевое слово then, то для нетерминального символа O получим правила:

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

В этом случае в матрице операторного предшествования для ключевых слов then и else возникнет противоречие, аналогичное рассмотренному ранее противоречию для лексем (и else. Добавив в грамматику G еще один нетерминальный символ R, получим правила, аналогичные правилам, приведенным в задании по лабораторной работе № 3:

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

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

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

Допустимы оба рассмотренных варианта, а также их комбинации. Первый из них требует добавления нового ключевого слова – а значит, усложняется лексический анализатор, второй ведет к созданию новых нетерминальных символов и новых правил в грамматике – это усложняет синтаксический анализатор и генератор кода. К тому же второй вариант требует неформальных преобразований правил грамматики, которые не всегда могут быть найдены (например, автору не известны такие преобразования, которые могли бы привести рассматриваемую здесь грамматику G к виду операторного предшествования – читатели могут попробовать в этом свои силы самостоятельно). Если других препятствий нет, то, с точки зрения автора, первый вариант предпочтительнее (лучше изменить синтаксис входного языка и упростить свою работу). [9]

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

Если посмотреть, к чему ведет размещение в одной клетке матрицы операторного предшествования двух знаков – «=·» и «·>», то можно заметить, что это означает конфликт между выполнением свертки и выполнением переноса при разборе условного оператора. Почему такой конфликт возникает? Этому есть две причины:

• во-первых, распознаватель не может определить, к какому оператору 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).

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