Курс Основы построения трансляторов


Грамматики класса LL( (LL(-грамматики)


Следующий тип формальных грамматик уже может быть использован для практического применения. В дополнение к Q-грамматикам они могут содержать правила, правая часть которых начинается с нетерминального символа. Общий принцип функционирования МА в этом случае остается прежним. Единственное, что здесь необходимо, это определить выбирающие символы, по которым производится замена. Здесь нужно последовать уже опробованному методу. Если  из правила  A::=U…, начинающегося с нетерминала, можно построить цепочку A >> U... >> ... >> x..., которая начинается с теминального символа x, то такой символ можно считать выбирающим, поскольку он дает основания для применения правила A::=U.... Таким образом, множество выбирающих символов для правила, начинающегося с нетерминального символа, состоит из множества  символов, которые являются первыми во всех возможных цепочках, выводимых из этого правила.

.

ВЫБ(A::=U…) = ПЕРВ(A::=U…)

Естественное требование к выбирающим символам остается прежним: для работоспособности метода необходимо, чтобы множества выбирающих символов для правил с одинаковой левой частью не пересекались. В качестве примера рассмотрим LL(1)-грамматику для четырех действий арифметики и скобок.


.

Правило       Способ выбора      Символы

E ::=TM       ПЕРВ(T)            a,(

M ::=-E       -                  -

M ::=+E       +                  +

M ::=e       СЛЕД(M)             ),#

T ::=FG       ПЕРВ(F)            a,(

G ::=*T       *                  *

G ::=/T       /                  /

G ::=e       СЛЕД(G)             ),+,-,#

F ::=a       A                   a

F ::=(E)     (                   (

 

Множества выбирающих символов для правил, начинающихся с нетерминала и аннулирующих правил строятся в такой несложной грамматике путем простого перебора возможных цепочек синтаксического вывода:

.

Правило  E ::= TM, способ построения ПЕРВ(T):

1.  T >> FG >> a,        выбирающий символ a

2.  T >> FG >> (E),      выбирающий символ (




Начало  Назад  Вперед