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

Дополним множества, представленные в табл. 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, то можно заметить, что противоречий в ней не будет.

Во-вторых, можно, не изменяя языка, попытаться преобразовать грамматику 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]

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