是否有LL(0)解析器这样的东西？

Question

我在某个地方看到了一个问题,询问LL(0)和LR(0)解析器之间的区别.是否有LL(0)解析器这样的东西？如果是这样,他们如何在不查看任何令牌的情况下进行解析？

Answer 1

LL(0)解析器会查看标记,但它们不会决定应用哪些生成.他们只是确定序列是否属于该语言.这意味着每个非终端符号必须具有单个右侧,并且可能没有递归.

G == ID name lastname
name == STRING
lastname == STRING

# lexer rules
# -----------
ID == [0-9]+
STRING == <unicode>+

请注意,正如@ 280Z28所提到的,需要一个单独的词法分析器来处理可变长度部分(ID和STRING),或者语法不会LL(0).

应用于解析具有该语法的输入的生成序列需要零预测.

如果在解析了部分给定输入序列之后可以应用多个生产,则确定性需要前瞻.

从理论上讲,语法会产生一种语言,并且在这种情况下,歧义(具有多种方法来推导给定的短语)很好.在解析中,只有一种方式是语义(意义),这就是我们想要的.

在解析编程语言时,前瞻是了解下一个要使用的语法生成所需的信息.

在LL(0)语言中,没有选择,因此输入序列可以被接受和解析,也可以被拒绝.