左图将语法纳入LL（1）

Question

我有一个家庭作业，需要将语法转换为LL（1）。我已经删除了左侧递归，但是我在左图上遇到了麻烦。我发现的所有示例都很简单，看起来像这样：

A -> aX | aY
变成：
A -> aZ
Z -> X | Y

我明白那个。但是，我的语法看起来更像是这样：

X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

我不确定如何将更简单的示例应用于此。我已经尝试了至少几个小时了，我已经失去了我尝试过的所有事情。通常，我的尝试看起来像这样：

X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

然后，我尝试将E规则转换为只有一个以 +或 - ：：

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

接着...

X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

等等。但是我不断地获得了许多额外的非终端，以及一些很长的制作 /链制作，而实际上没有左手。我不确定如何处理 - 我似乎无法消除 一些 非末端具有多个生产以a +和a - 。

Answer 1

让我们看一下您的语法：

$ qquad begin {align} x＆ to ae mid ixe mid（X） text { - } b＆ to text {+} mid text { - } mid varepsilon end end end {align} $

请注意，$ x $不需要左键：所有规则都不相交第一组¹。如果您想让这个明显，可以丢弃$ i $并将其插入：

美元 mid text { - }

同样，我们可以在线$ b $：

美元 mid text { - }

现在，我们看到我们实际上必须在$ e $上进行左撇子：我们有明显的冲突，并且通过$ XE $获得了其他冲突。因此，让我们在$ xe $上进行内联$ x $：

美元 mid text { - } ）ee mid varepsilon end {align} $

现在，我们可以像您的示例一样轻松地左图：

美元中 text { - } m mid aee mid（x）ee mid varepsilon p＆ to text {+} e mid xe mid xe mid mid text {+} xee m＆ text { - } e mid xe mid text { - } xee end {align} $

到目前为止，我们可以看到我们还没有到达任何地方：通过将$ text {+} $或$ text { - } $从替代品中分解，我们挖出了另一个$ x $，它又有$ text {+text {+text { } $和$ text { - } $在其第一组中。

因此，让我们看一下您的语言。通过

美元

和

美元

你有 任意长 表单$+^+$的前缀 结束不同, ，语义上：ll（1）解析器无法决定是否有任何给定（下一个）$ text {+} $属于一个 一对 - 这意味着选择替代性$ IE $ - 或单独出现 - 这意味着选择$ bxe $。

结果，看起来不像您 语 可以用 任何 LL（1）语法，因此试图将其转换为一种是徒劳的。

更糟糕的是：作为$ bxe rightarrow bixee rightarrow^* bi^n xe^n e $，您无法决定使用$ bxe $ 任何 有限的外观。这不是正式的证据，但强烈表明您的语言甚至都不是LL。

如果您想到自己在做什么 - 将波兰语符号与单一操作员混合在一起，那么解析应该很难就不足为奇了。基本上，您必须从左边计算 和 从$ text {+} $的长链中识别单个$ b $ - $ text {+} $的权利。如果我想到链条中的多个$ b $ - $ text {+} $，我什至不确定语言（有两个语言 语义上不同 但是句法等于$ text {+} $）可以确定性地解析（无需回溯）。

---

1. 那将是可以在非终端/规则替代方案的推导中首先出现的一组终端。