这些语法和最小解析器可以识别它吗？

Question

我正在努力学习如何制作编译器.为了做到这一点,我读了很多关于无上下文的语言.但是有一些我自己无法得到的东西.

因为它是我的第一个编译器,所以有一些我不知道的实践.我的问题是在构建一个解析器生成器,而不是编译器和lexer.有些问题可能很明显..

解析器/语法层次结构

以下是要点:

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

1)模糊语法是具有多个解析树的语法.但是,最左推导或最右推导的选择是否应该导致解析树的单一性？

[编辑:在这里回答]

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

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

2.2)所以一个LR(*)解析器,只要你能想象它,根本就没有模糊的语法,然后可以解析整套无上下文语言？

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

3)根据以前的答案,以下内容可能是自相矛盾的.考虑到LR解析,模糊语法会引发shift-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解析具有非常显着的优势.我已经使用了15年,并且用它做了几十个真正的语言.

对于可能最终来到这里的任何人，请注意：[BRNGLR 算法](http://link.springer.com/article/10.1007%2Fs00236-007-0054-z)，伊丽莎白编写的 GLR 算法的变体Scott 修复了指数行为，对于任何上下文无关语法来说都是最坏情况的三次方。 (2认同)