Каждый LL (1) Грамматика также LR (1)?

Question

Каждый LL (1) Грамматика также LR (1)?

Answer 1

Да, поскольку LL и LR разбирают данные слева направо; И поскольку LL (1) выглядит впереди только один токен, он обязательно должен быть LR (1). Это также верно для LR (K), где K> 1, поскольку грамматика LR (K) может быть преобразована в грамматику LR (1).

Разница между LR и LL грамматическими наступает в том, что LR производит самый правый вывод, где оно производит левый вывод. Таким образом, это означает, что анализатор LR может на самом деле анализировать больший набор, чем грамматика LL, поскольку он создает от листьев.

Позвольте сказать, что у нас есть постановки следующим образом:

A -> "(" A ")" | "(" ")"

Тогда LL (1) разобрать строку (()):

(()) -> A
     -> "(" A ")"
     -> "(" "(" ")" ")"

Где в качестве LR (1) разбирается следующим образом:

Input  Stack          Action
(())   0       
())    0 '('
))     0 '(' '(' 
)      0 '(' '(' ')'  Reduce using A -> "(" ")"
)      0 '(' A
-      0 '(' A ')'    Reduce using A -> "(" A ")"
-      0  A           Accept

Для получения дополнительной информации см.: http://en.wikipedia.org/wiki/ll_parsing