Блог

У меня есть грамматика:

 S -> bU | ad | d
U -> Ufab | VSc | bS
V -> fad | f | Ua
 

Чтобы сконструировать анализатор рекурсивного спуска, мне нужна форма LL(1).
Лучшее, что у меня есть, это:

 S -> bU | ad | d
U -> fY | bSX
Y -> adScX | ScX
X -> fabX | aScX | ε
 

Удалил левые рекурсии и выполнил некоторый левый факторинг, но я застрял.
Пытался в течение нескольких часов, но у меня ничего не получается…

Например, допустимой строкой являются:

• bbdfabadc ббдфабадк
• bbdfabfabfabfab
• bfadadcfabfab
• bbadaadc
• bfbbdfabc

Очевидно, что моя грамматическая форма неоднозначна для некоторых, поэтому я не могу создать анализатор рекурсивного спуска…

Из ответа:

 S -> bU | ad | d
U -> fYZ | bSZ
X -> fab | aSc
Y -> adA | bUc | dc
Z -> ε | XZ
A -> Sc | c
 

Все еще не LL(1). Первое и последующее для Z не являются непересекающимися.

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

К левому фактору относится правило

 U -> Ufab | VSc | bS
 

вам нужно сначала заменить V, давая

 U -> Ufab | fadSc | fSc | UaSc | bS
 

который вы затем оставили включенным в

 U -> UX | fY | bS
X -> fab | aSc
Y -> adSc | Sc
 

теперь U достаточно прост, чтобы вы могли устранить левую рекурсию напрямую:

 U -> fYZ | bSZ
Z -> ε | XZ
 

предоставляя вам

 S -> bU | ad | d
U -> fYZ | bSZ
X -> fab | aSc
Y -> adSc | Sc
Z -> ε | XZ
 

Теперь у вас все еще есть проблема с факторингом слева с Y, поэтому вам нужно заменить S:

 Y -> adSc | bUc | adc | dc
 

на который вы оставили фактор

 Y -> adA | bUc | dc
A -> Sc | c
 

предоставление почти LL (1) грамматики:

 S -> bU | ad | d
U -> fYZ | bSZ
X -> fab | aSc
Y -> adA | bUc | dc
Z -> ε | XZ
A -> Sc | c
 

но теперь все застряло, поскольку правило эпсилона для Z означает, что нам нужно, чтобы FIRST (X) и FOLLOW (Z) были непересекающимися (чтобы выбрать между двумя правилами Z). Обычно это указывает на язык, отличный от языка LL, поскольку существует некоторый конечный контекст, который может быть связан с более чем одним правилом (через S -> bU -> bbSZ -> bbbUZ -> bbbbSZZ цепочку exapansion — конечные Zs могут быть распознаны, но либо могут быть пустыми). Часто вы все еще можете распознать этот язык с помощью простого синтаксического анализатора рекурсивного спуска (или таблицы состояний в стиле LL), просто разрешив двусмысленность / конфликт Z в пользу неэпилонского правила.