代码之家 › 专栏 › 技术社区 › user200783

描述非LL(1)的LL(2)语言的语法,其中没有规则可以产生epsilon?

ll context-free-grammar grammar parsing

0

user200783 · 技术社区 · 5 年前

This answer 示出了描述非LL(1)的LL(2)语言的语法:

S -> a S A | epsilon
A -> a b S | c

在这种语法中 S 是因为它生产 epsilon ,空字符串。是否有任何语法类似地描述了一种不是LL(1)的LL(2)语言,但其中没有规则可以产生 epsilon ?

0 回复 | 直到 5 年前

1

kajigor 5 年前

考虑一下这个语法:

S -> a S A | a c 
A -> a b S | c

它不是LL(1),因为非终结符存在First/First冲突 S 以及终端 a .

它是一种LL(2)语法,因为它不包含任何epsilon规则,并且每个规则的First集都是不同的:

First_2(a S A) = {aa}
First_2(ac) = {ac}
First_2(a b S) = {ab}
First_2(c) = {c}