parsing - 如何判断一个文法是LL(1)、LR(0)还是SLR(1)?

标签 parsing grammar lr-grammar ll-grammar

如何识别文法是 LL(1)、LR(0) 还是 SLR(1)?

任何人都可以使用这个示例或任何其他示例来解释它吗?

X → Yz | a

Y → bZ | ε

Z → ε

最佳答案

要检查语法是否为 LL(1),一种选择是构造 LL(1) 解析表并检查是否有任何冲突。这些冲突可能是

  • FIRST/FIRST 冲突,其中必须为非终结符/终结符对预测两个不同的产生式。
  • FIRST/FOLLOW 冲突,其中预测了两种不同的产生式,一种表示应采用某些产生式并将其扩展为非零数量的符号,另一种表示应使用一种产生式来表明应最终扩展某些非终结符输出为空字符串。
  • FOLLOW/FOLLOW 冲突,其中指示非终结符最终应扩展为空字符串的两个产生式相互冲突。

让我们通过为每个非终结符构建 FIRST 和 FOLLOW 集来尝试一下您的语法。在这里,我们明白了

FIRST(X) = {a, b, z}
FIRST(Y) = {b, epsilon}
FIRST(Z) = {epsilon} 

我们还知道 FOLLOW 集是

FOLLOW(X) = {$}
FOLLOW(Y) = {z}
FOLLOW(Z) = {z}

据此,我们可以构建如下的LL(1)解析表:

    a    b    z   $
X   a    Yz   Yz  
Y        bZ   eps
Z             eps

由于我们可以构建没有冲突的解析表,因此语法为 LL(1)。

为了检查语法是 LR(0) 还是 SLR(1),我们首先为该语法构建所有 LR(0) 配置集。在这种情况下,假设 X 是您的起始符号,我们得到以下结果:

(1)
X' -> .X
X -> .Yz
X -> .a
Y -> .
Y -> .bZ

(2)
X' -> X.

(3)
X -> Y.z

(4)
X -> Yz.

(5)
X -> a.

(6)
Y -> b.Z
Z -> .

(7)
Y -> bZ.

由此可见,该文法不是LR(0),因为状态(1)存在移位/归约冲突。具体来说,因为我们有移位项 X → .a 和 Y → .,所以我们无法判断是移动 a 还是减少空字符串。更一般地说,没有 ε-产生式的文法是 LR(0)。

但是,这个文法可能是SLR(1)。为了看到这一点,我们使用特定非终结符的前瞻集来增强每次归约。这返回了这组 SLR(1) 配置集:

(1)
X' -> .X
X -> .Yz [$]
X -> .a  [$]
Y -> .   [z]
Y -> .bZ [z]

(2)
X' -> X.

(3)
X -> Y.z [$]

(4)
X -> Yz. [$]

(5)
X -> a.  [$]

(6)
Y -> b.Z [z]
Z -> .   [z]

(7)
Y -> bZ. [z]

状态 (1) 中的移位/归约冲突已被消除,因为我们仅在前瞻为 z 时进行归约,这不会与任何其他项冲突。

关于parsing - 如何判断一个文法是LL(1)、LR(0)还是SLR(1)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8496642/

相关文章:

parsing - 具有 epsilon 转换的左递归 LR(0) 项的闭包是什么?

c - 通过 C 中的 fgets 解析 .txt 文件的参数

java - native Java 文档解析器和转换器库/基于 linux 的文档转换器

parsing - 语法歧义: why?(问题是: "(a)"与 "(a-z)")

visual-studio-2010 - 在VS2010中寻找Antlr Grammar语法高亮

qml - QML 语法是 LALR(1) 吗?

java - 如何为 java/jsf 代码创建自己的解析器?

c++ - 如何从 C++ 标准推断数组 [] 的优先级高于指针?

parsing - 左/右递归、左/最右推导、优先级、结合性等之间的区别

parsing - LR(1) 解析器状态大小仍然是一个问题吗?