Методы трансляции.Грамматика.Распознаватель

Грамматика с операторным предшествованием

В компиляторах часто применяют ранний вариант метода предшествования — метод операторного предшествования, предложенный в 1963 г. Р. В. Флойдом. Этот метод применим только к грамматикам с операторным предшествованием.

Пусть и  - терминальные символы,   и   -  нетерминальные символы,  и - любые строки, в том числе пустые. Грамматикой с операторным предшествованием (operatorprecedencegrammar) называют грамматику класса 2 по Хомскому, в которой:

1) Правые части порождающих правил не содержат рядом стоящих нетерминальных символов, то есть, в грамматике нет правил вида:

Грамматику,  обладающую таким  свойством,  называют операторной грамматикой.

2) Для каждой упорядоченной пары терминальных символов  и выполняется не более чем одно из трех отношений предшествования, определяемых так:

А. , если и только если существует правило

или правило

Б. , если и только если существует правило

и вывод или вывод

В. , если и только если существует правило

и вывод или вывод .

3) Различные  порождающие  правила   имеют   разные   правые части.

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

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

Второе и третье требования, как и аналогичные требования к грамматике предшествования, обеспечивают «беступиковость» алгоритма разбора. Строго говоря, перечисленные требования не гарантируют однозначности алгоритма разбора. Это будет видно из дальнейшего. Однако характер возможных неоднозначностей таков, что они без особого труда устраняются семантическими подпрограммами.

Распознаватель

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

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

Пример Сентенциальная форма грамматики ₁

имеет дерево разбора, показанное на рис. 1

U

/      |      \

  B      +      T

                     /     |     \

                    T             M      

Рис. 1 Дерево разбора

Первичная фраза здесь , в то время как основой является самый левый символ Т. Очевидно, выделение вместо основы первичной фразы приводит к неканоническому разбору. Из свойств грамматики с операторным предшествованием следует, что если  - первичная фраза, то либо существует порождающее правило

либо существует порождающее правило

и вывод  в котором применяются только порождающие правила вида , где и - нетерминальные символы.

Алгоритм разбора отыскивает самую левую первичную фразу и состоит в следующем. Символы входной строки поочередно переписываются в стек до тех пор, пока между верхним терминальным символом стека  и очередным терминальным символом входной строки , не появится отношение •> (именно •>). Тогда стек просматривается в направлении от вершины к началу до тех пор, пока между двумя очередными терминальными символами стека  и  не появится отношение <• (именно <•). Часть стека от символа , исключительно, до вершины стека, включительно, есть первичная фраза.

Среди порождающих правил отыскивается правило

(1)

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