所以我有这个语法(如下)，我需要建立一个解析表。我需要使它适合预测解析器。我知道第一个想法是让它无歧义，但对我来说它已经是明确的(因为我找不到可以绘制 2 个不同解析树的字符串)。其次，我需要将其考虑在内。我把我的猜测放在原始语法下面，我感觉我遗漏了一些东西，如果我遗漏了什么，有人可以指出。
S -> m G | m K p
G -> n G | n
K -> q K r | m n
我猜:
S -> m A
A -> G | K p
G -> n G'
G' -> n G' | emptyString
K -> q K r | m n
最佳答案
你所拥有的看起来是正确的!下面是一步一步地了解如何达到目标的方法，以及为什么每次转换都是必要的。
首先，让我们看看我们的 S 非终结符。这个非终结符有两个以 m 开头的产生式，这意味着我们在这些产生式之间存在 FIRST/FIRST 冲突。对产生式 S → mG 和 S → mKp 进行左分解得到我们
现在，这样做是否暴露了以前不存在的任何问题？幸运的是，没有。非终结符 G 只能产生以 n 开头的字符串，非终结符 K 只能产生以 q 或 m 开头的字符串。这意味着我们没有在这里引入任何 FIRST/FIRST 冲突，所以没有必要进一步接触任何东西——至少现在还没有。
接下来，让我们看看 G 非终结符，它有产生式 G → nG 和 G → n。换句话说，这会生成一串包含一个或多个字母 n 副本的字符串。正如目前所写，存在第一个/第一个冲突。我们有很多方法可以重写它。您提出的方案基本上是将其分成两部分 - 一部分生成单个 n ，以及生成零个或多个 n 副本的后续部分。我将在这里跟随您的脚步，它引入了一个新的非终结符，我将称之为 H 以将其与 G 区分开来:
现在，我们不得不问 - 这个 ε 产生式是否引入了任何 FIRST/FOLLOW 冲突？为了回答这个问题，我们需要确定 FOLLOW(H) 是什么。我们看到 H 只出现在产生式 H → nH(它没有给我们任何新东西)和 G → nH 的末尾，这告诉我们 FOLLOW(G) 中的所有内容也将在 FOLLOW(H) 中. FOLLOW(G) 中有什么？ G 出现在产生式 A → G 的末尾，它告诉我们 FOLLOW(A) 中的所有内容都将在 FOLLOW(H) 中。而 A 只出现在 S → mA 中，这意味着 FOLLOW(A) 中唯一的标记是输入结束标记 $。呼!所以 FOLLOW(H) = { $ }。这是个好消息，因为这与 H → nH 产生不冲突。
这留下了 K 的产生式规则，幸运的是它们没有任何问题。
把所有这些放在一起，我们得到网络转换的语法是
这恰好是 LL(1)。这是解析表:
m n q r $
+------+------+------+------+------+
S | mA | | | | |
+------+------+------+------+------+
A | Kp G Kp | | |
+------+------+------+------+------+
G | | nH | | | |
+------+------+------+------+------+
H | | nH | | | eps |
+------+------+------+------+------+
K | mn | | qKr | | |
+------+------+------+------+------+
关于parsing - 左因子分解语法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33332505/