Рекурсивный спуск Parser LL (4) с примером

-3

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

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

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 
+ 
);

источник

2015-03-12 AWA

Рассмотрите возможность включения вопроса в сообщение. –

@MintyFresh Я знаю, как написать реализацию парсера. Но я ищу пример грамматики (любой синтаксис), где синтаксический анализатор должен использовать ровно 4 прожектора для того, чтобы принимать решения о синтаксическом анализе. – AWA

На самом деле подумайте о том, что вы сделали, о чем вы столкнулись и о чем вы спрашиваете. – MSB

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

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

источник

2015-03-12 18:32:38 rici

Ну, это грамматика LL (4), но существует грамматика LL (1), которая описывает один и тот же язык: 's:" x "" x "" x "c | Я БЫ; c: a | б; a: "(" s "," s ")"; b: "[" s "]"; ' – Gunther

@Gunther: True. Но ОП не запрашивал язык LL (4), а только грамматику LL (4). (Кстати, все языки LR (k), которые не являются LR (0), являются LR (1), а также для LALR, но это не всегда помогает, когда вы пишете синтаксический анализатор.) – rici

Parsing Techniques по Grune и Jacobs (также доступно online) на странице 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).

источник

2015-03-12 20:32:59 Gunther

Рекурсивный спуск Parser LL (4) с примером

ответ

Смежные вопросы