parsing - 这些语法和识别它的最小解析器怎么样？

Question

我正在尝试学习如何制作编译器。为了做到这一点，我阅读了很多关于上下文无关语言的内容。但是有些东西我自己还做不到。

因为它是我的第一个编译器，所以有一些我不知道的做法。我的问题是为了构建解析器生成器，而不是编译器和词法分析器。有些问题可能很明显..

我的阅读内容包括:Bottom-Up Parsing , Top-Down Parsing , Formal Grammars .图片来自:Miscellanous Parsing .全部来自斯坦福 CS143 类(class)。



以下是要点:

0)(模糊/明确)和(左递归/右递归)如何影响对一种或另一种算法的需求？还有其他方法来限定语法吗？

1) 歧义文法是具有多个解析树的文法。但是，选择最左派生还是最右派生不应该导致解析树的唯一性吗？

[编辑:回答 here ]

2.1) 但是，语法的歧义是否与 k 相关？我的意思是给出一个 LR(2) 语法，它对于 LR(1) 解析器是不明确的，对于 LR(2) 解析器是不是不明确的？

[编辑:不，不是，LR(2) 语法意味着解析器需要两个前瞻标记来选择要使用的正确规则。另一方面，歧义文法是可能导致多个解析树的文法。 ]

2.2) 所以一个 LR(*) 解析器，只要你能想象，就不会有任何歧义的语法，然后可以解析整个上下文无关语言？

[编辑:由 Ira Baxter 回答，LR(*) 不如 GLR 强大，因为它无法处理多个解析树。 ]

3) 根据之前的答案，接下来的内容可能自相矛盾。考虑到 LR 解析，歧义语法是否会触发 shift-reduce 冲突？一个明确的语法也能触发一个吗？同样，减少减少冲突呢？

[编辑:就是这样，模棱两可的语法会导致 shift-reduce 和 reduce-reduce 冲突。反过来说，如果没有冲突，语法就是单义的。 ]

4)解析左递归语法的能力是LR(k)解析器优于LL(k)的一个优势，这是它们之间的唯一区别吗？

[编辑:是的。 ]

5)给G1:

G1 :
S -> S + S
S -> S - S
S -> a

5.1) G1 既是左递归的，右递归的又是二义性的，对吗？它是 LR(2) 语法吗？一会使其明确:

G2 :
S -> S + a
S -> S - a
S -> a

5.2) G2 还是不明确的吗？ G2 的解析器是否需要两个前瞻？通过因式分解，我们有:

G3 :
S -> S V
V -> + a
V -> - a
S -> a

5.3) 现在，G3 的解析器是否只需要一个前瞻？进行这些转换的对应部分是什么？ LR(1) 是所需的最小解析器吗？

5.4) G1 是左递归的，为了用 LL 解析器解析它，需要将其转换为右递归文法:

G4 :
S -> a + S
S -> a - S
S -> a

然后

G5 :
S -> a V
V -> - V
V -> + V
V -> a

5.5) G4 是否至少需要一个 LL(2) 解析器？ G5 只能由 LL(1) 解析器解析，G1-G5 确实定义了相同的语言，并且这种语言是 ( a (+/- a)^n )。这是真的吗？

5.6) 对于每个语法 G1 到 G5，它所属的最小集合是什么？

6) 最后，由于许多不同的语法可能定义同一种语言，如何选择语法和相关的解析器？生成的解析树是否重要？解析树的影响是什么？

我问了很多，我真的不希望得到一个完整的答案，无论如何，任何帮助都会非常感激。

感谢阅读!

Answer 1

“许多语法可能定义相同的语言，如何选择......”？

通常，您选择满足以下条件的一项:

概念上尽可能简单(暗示:比其他人小)

尽可能跟踪语言引用手册中的术语

满足解析器生成器约束的最小弯曲量

最后一个可能会使您的概念简单性变得一团糟，并且您的各种解析器样式图表显示了您面临的不同问题的数量，具体取决于您选择的生成器。由于选择通常在您实际选择语法之前就已做好，这一事实使情况变得更糟。

最小化语法弯曲的一种方法是选择一个解析器生成器来处理完全上下文无关的语法。 GLR parsing有这个非常显着的优势。我已经使用它 15 年了，并用它完成了几十种真正的语言。