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

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

Однако при заполнении матрицы операторного предшествования возникает проблема: символ) стоит рядом с символом 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, то можно заметить, что противоречий в ней не будет.

Во-вторых, можно, не изменяя языка, попытаться преобразовать грамматику 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<b) then if(a<c) then a:=c else a:=b;);

• во-вторых, конец логического выражения в условии после ключевых слов 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).

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