标签: lr-grammar

从这个问题,涉及二进制运算符(+ - */)的表达式的语法不允许使用外括号:

top_level   : expression PLUS term
            | expression MINUS term
            | term TIMES factor
            | term DIVIDE factor
            | NUMBER
expression  : expression PLUS term
            | expression MINUS term
            | term
term        : term TIMES factor
            | term DIVIDE factor
            | factor
factor      : NUMBER
            | LPAREN expression RPAREN

这个语法是LALR(1).因此,我能够使用PLY(yacc的Python实现)为语法创建自下而上的解析器.

为了进行比较,我现在想尝试为同一种语言构建一个自上而下的递归下降解析器.我已经改变了语法,删除了左递归并应用了左因子:

top_level   : expression top_level1
            | term top_level2
            | NUMBER
top_level1  : PLUS term
            | MINUS term
top_level2  : TIMES factor
            | …

LL(1) 解析器需要一个前瞻符号来决定使用哪个产生式。这就是为什么我一直认为使用术语“先行”的原因，当解析器查看下一个输入标记而不“消耗”它时（即它仍然可以通过下一个操作从输入中读取）。然而，LR(0) 解析器让我怀疑这是正确的：

我见过的每个 LR(0) 解析器示例也使用下一个输入标记来决定是移动还是减少。在减少的情况下，不消耗输入令牌。

我使用免费软件工具“ParsingEmu”生成 LR 表并在下面对单词“aab”执行 LR 评估。如您所见，列标题包含标记。从评估中您可以看到解析器正在通过查看下一个输入标记来决定使用哪一列。但是当解析器在步骤 4 - 6 中减少时，输入不会改变（尽管解析器在执行到下一个状态的转换时需要知道下一个输入标记“$”）。

语法：

S -> A
A -> aA
A -> b

桌子：

评估：

现在由于我的困惑，我做了以下假设：

1. 我对“lookahead”定义的假设（lookahead = input token not be used）是错误的。Lookahead 对于 LL 解析器或 LR 解析器意味着两种不同的东西。如果是这样，那么如何定义“前瞻”？

2. LR 解析器具有（从理论的角度来看，当您使用下推自动机时）额外的内部状态，它们通过将输入标记放在堆栈上来消耗输入标记，因此能够通过查看来做出移位减少决策在堆栈上。

3. 上面显示的评估是LR(1)。如果为真，LR(0) 评估会是什么样子？

现在什么是正确的，1、2 或 3 还是完全不同的东西？

在哪里可以找到 LR(1) 解析器生成器的简单（尽可能多，但不能更简单！）实现？

我不是在寻找性能，只是在寻找生成 LR(1) 状态（项目集）的能力。
C++、C#、Java 和 Python 都适合我。

我正在学习ANTLR v4,它是一个基于所谓的自适应LL(*)算法的解析器生成器.它声称是对LL(*)算法的重大改进.但我也听说过像LR这样的算法.

因此,出于好奇而得到一个大局:

• 有多少现代算法可以构建解析器？
• 什么是ANTLR自适应LL(*)算法的优势/局限？

对于一种不是LL(1)or 的语言LR(1)，如何尝试找出某个数字是否n存在使得语法可以是LL(n)or LR(n)？

LR(0)您可以通过查看规范的项目集合来检查语法是否正确LR(0)。然后，假设不是，您可以通过引入先行符号来LR(0)检查它是否是。LR(1)我的简单推理告诉我，要检查它是否LR(2)存在，您可能必须使前瞻包含接下来的两个符号，而不仅仅是一个。因为LR(3)你必须考虑三个符号等。

即使是这种情况，尽管我对此表示怀疑，但我正在努力思考如何尝试识别（甚至暗示）一种n特定的语法，或者它的不存在，LR(n)并且/或LL(n)不从任意LR(m)向上增量检查。

GCC/Clang 是手写解析器。我读到一篇文章说 C++ 不能被 LR(1) 解析器解析（Why can't C++ be parsed with a LR(1) parser?）。如果是这样，当 LR(1) 比递归下降更强大时，为什么 GCC/Clang 是手写的递归下降解析器？