Пример 22

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

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

КС-грамматика является грамматикой простого предшествования, если она однозначна, на содержит ε-продукций и для любой пары ее символов (терминальных и нетеринальных) выполняется не более одного отношения предшествования.

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

Отношения предшествования зависят от порядка, в котором стоят символы.

Грамматики, у которых нет продукций, правые части которых представляют собой или имеют два соседних нетерминала называются операторными.

Следующая грамматика для выражений

E→ ЕАЕ | (E) | -E | id

А→ + | - | * | / | ↑

не является операторной, поскольку правая часть ЕАЕ имеет два (на самом деле — даже три) последовательных нетерминала. Однако если заменить А каждой из его альтер­натив, то получаем операторную грамматику

E→ E+E | E-E | E*E | E/E | E↑E | (E) | -E| id

При синтаксическом анализе приоритета операторов определяются три непересе­кающихся отношения приоритетов — <•, и •> — между тер­миналами. Эти отношения приоритетов управляют выбором основ и имеют следующее содержание.

Отношение	Значение
а < • b a b а • > b	а "уступает приоритет" b а имеет тот же приоритет, что и b а "забирает приоритет у" b

Хотя эти отношения и выглядят похожими на арифметические отношения "меньше", "равно" и "больше", они имеют совершенно иные свойства. Например, в одном и том же языке может быть так, что и а< • b, и а •> b, или для некоторых терминалов а и b не выполняется ни одно из отношений а< • b, а •> b и а b.

Имеется два способа определения отношений приоритетов, которые должны выполняться между терминалами.

Первый способ — интуитивный. Он основан на традиционных понятиях ассоциативности и приоритета операторов. Например, если * имеет приоритет выше, чем +, то * •> + и + <• *. Такой подход раз­решает неоднозначности грамматик позволяет написать для нее синтаксиче­ский анализатор приоритета операторов.

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

Дата добавления: 2014-12-27