Her LL (1) dilbilgisi de bir LR'dir (1)?

Question

her LL (1) dilbilgisi mı ayrıca LR (1)?

Answer 1

Evet, LL ve LR hem Soldan sağa verileri ayrıştırmak beri; ve LL (1) sadece bir jetonu göz önüne aldığından, mutlaka bir LR (1) olmalıdır. Bu aynı zamanda bir LR (k) gramer beri k> 1, bir LR (1) gramer dönüştürülebilir LR (k) için de geçerlidir. bu LR LL soldaki türetme üretir sağdaki türetme üretir içinde

LR ve LL gramerlerin arasındaki fark gelir. Yani bu, bir LR ayrıştırıcısının aslında yapraklardan oluşturulduğu kadar LL dilbilgisinden daha büyük bir seti ayrıştırabileceği anlamına gelir.

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

Sonra LL (1) dizesini (()) ayrıştırmak olacaktır:

aşağıdaki gibi yapımları var Diyelim

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

olarak LR (1) olarak ayrıştırmak izlediğinde:

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

Daha fazla bilgi için bkz: http://en.wikipedia.org/wiki/LL_parsing