Парсер рекурсивного спуска LL(4) с примером

Question

Я хочу определить грамматику, что для языка, сгенерированного из грамматики, требуется LL(4) парсер рекурсивного спуска. Грамматика не должна быть сложной, если она удовлетворяет требованию?

оператор if для грамматики может быть следующим

if lookahead ∈ FIRST(Something) then
code for Something ...
else if lookahead ∉ FOLLOW(Something
?
) then
ERROR;
Something
*
can be implemented as a while loop:
while lookahead ∈ FIRST(Something) do
code for Something ...
if lookahead ∉ FOLLOW(Something
*
) then
ERROR;
and Something
+
can be implemented as a repeat loop:
repeat
if lookahead ∉ FIRST(Something) then
ERROR;
code for Something ...
until lookahead ∈ FOLLOW(Something
+
);

Answer 1

Пример не совсем вырожденной грамматики (легко разбирается парсером LR(1), кстати):

s: a | b | ID;
a: "x" "x" "x" "(" s "," s ")"
b: "x" "x" "x" "[" s "]"

Answer 2

Методы синтаксического анализа, выполненные Груном и Джейкобсом (также доступны онлайн) на стр. 181, показывают этот пример языка LL(k+1), который не является LL(k):

S ::= a S A 
    | 
A ::= aᵏ b S 
    | c

Соответственно, эта грамматика описывает язык LL (4):

S ::= a S A 
    | 
A ::= a a a b S 
    | c

Грамматика на самом деле является сильной-LL(4) и LALR(4), но ни LL(3), ни LR(3).

Для грамматики LL (4) эта будет делать:

S ::= a a a 
    | A a a a a
A ::=

Также сильны LL (4) и LALR(4), но ни LL(3), ни LR(3).