Pup*_*ppy 17 parsing ll-grammar lr-grammar
所有LL语法都是LR语法,但不是相反,但我仍然很难处理这种区别.我很好奇LR示例中没有等效LL表示的小例子(如果有的话).
Chr*_*odd 19
好吧,就语法而言,它很简单 - 任何简单的左递归语法都是LR(可能是LR(1))而不是LL.所以列表语法如:
list ::= list ',' element | element
是LR(1)(假设元素的生产是)但不是LL.这样的语法可以通过左因子等相当容易地转换成LL语法,所以这不是太有趣.
更感兴趣的是LR而不是LL的语言 - 这是一种语言,对于任何k,存在LR(1)语法但没有LL(k)语法.一个例子是需要可选的尾随匹配的东西.例如,任意数量的a符号的语言后跟相同数量或更少的b符号,但不是更多的bs - {a ^ ib ^ j | i> = j}.有一个简单的LR(1)语法:
S ::= a S | P
P ::= a P b | \epsilon
但没有LL(k)语法.原因是LL语法需要在查看a时决定是匹配a + b对还是奇数a,而LR语法可以推迟该决定直到它看到b或输入结束.
这篇关于cs.stackechange.com的帖子有很多关于此的参考资料