Главная > Разное > Автоматический синтаксический анализ
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6. ПРЕОБРАЗОВАНИЯ ГРАММАТИК

Нам уже известны различные" причины, по которым может оказаться желательным преобразование заданной грамматики в другой эквивалентный вид. Например, может возникнуть необходимость исключить левую рекурсию, или привести грамматику в нормальную форму, или преобразовать ее в грамматику с предшествованием. Однако применение исходной грамматики, вероятно, определяется в терминах структуры разбора, порождаемой именно этой грамматикой, а не в терминах структуры разбора, порождаемой измененной грамматикой. Поэтому необходимы методы возвращения к разбору в рамках исходной грамматики. Описываемый ниже метод такого возвращения использовался в одной системе построения компиляторов [14].

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

порождает разбор

В соответствующей грамматике с действиями

соответствующий разбор имеет вид

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

не представляет труда построить дерево грамматического разбора.

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

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

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

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

Заметим, что в этом случае мы преобразовали грамматику с левой рекурсией в грамматику без левой рекурсии.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление