标签: lr-grammar

我正在尝试实现Warshall的算法来快速计算LR(1)闭包.

我想我理解LR(0)的工作原理:

• 图的节点是LR项,如A ? B • C
• 边缘是"过渡"从开始A ? B • C到C ? • D

问题是,LR(1)需要计算前瞻,我无法弄清楚如何将它们合并到算法中.
在我看来,即使我知道任何给定的LR项目的传递闭包,我仍然需要经历所有相同的计算,只是为了弄清楚每个项目的前瞻设置是什么.

甚至可以使用Warshall的算法来计算规范的LR(1)闭包,还是只能用于更受限制的情况(如LR(0),SLR(1)等)？

我在空闲时间尝试解析，并且我想为一个非常非常简单的语法实现一个 shift-reduce 解析器。我已经阅读了许多在线文章，但我仍然对如何创建解析树感到困惑。这是我想要做的一个例子：

语法：

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

这是一个示例输入：

1 + 1 + 1 + 1

标记化后，变为：

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

我明白那个：

1. 换挡意味着将第一个输入标记压入堆栈并将其从输入中移除
2. 减少意味着用语法元素替换堆栈中的一个或多个元素

所以，基本上，这应该发生：

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num …

我想了解解析器是如何工作的。我了解了 LL、LR(0)、LR(1) 部分、如何构建、NFA、DFA、解析表等。

现在的问题是，我知道词法分析器应该仅在某些情况下根据解析器的需求提取标记，当不可能在一次单独的传递中提取所有标记时。我不太明白这种情况，所以我愿意接受任何解释。

现在的问题是，词法分析器应该如何完成其​​工作？它是否应该将其识别基于当前的“上下文”，即当前应该解析的非终结符？这是完全不同的东西吗？GLR 解析怎么样：这是词法分析器可以尝试不同终端的另一种情况，还是只是一个语法业务？我还想了解它与什么相关，例如它与解析技术的类型（LL、LR 等）相关还是仅与语法相关？

多谢

我正在制作LR(1)解析器,并且我遇到了各个地方的性能瓶颈.

我想尝试优化解析器的数据结构,但为了做到这一点,我需要大致了解有多少状态,规则和终端符号对于(可能很复杂的)计算机语言(如C++)是合理的.

我的猜测是复杂语言的典型语法会:

• ≤100个终端符号
• 每个生产≤50个符号
• ≤2000规则
• ≤10,000个州

但我真的不知道他们有多正确.

请注意,我假设每个规则都是非终结符号  → 符号符号 符号 ...,因此看起来像单个复合"规则" foo: (bar | baz)+实际上可能包含5个规则,而不仅仅是1个规则.

他们合理吗？如果没有,我在哪里找到一些数字？

从历史上看，LALR(1) 解析器优于 LR(1) 解析器，因为 LR(1) 解析器生成的大量状态需要资源。很难相信这在当今的计算环境中仍然是一个问题。情况仍然如此还是现代编译器现在使用规范的 LR 解析器构建，因为 LALR 语法是 LR 语法的适当子集？

我知道每个 LL(1) 也是一个 LR(1)。但是 LL(1) 和 LR(0) 之间的关系呢，LL(1) 也可以是 LR(0) 吗？

我真的很想解开以下关系:

• LR(0)
• LL(0)
• LALR(1)
• SLR(1)
• LR(1)
• LL(1)

我很确定LALR(1)和SLR(1)是LR(1)的子集,但我对其他人的迷失.它们都是独家的吗？LL(0)是LL(1)的子集吗？

谢谢

我熟悉 LR(1) 解析器，它们通常在传统编译器课程中教授。我知道存在 LR(2) 解析器，但我以前从未见过构建过的解析器。

LR(2) 解析器是如何构造的？它与 LR(1) 解析器有何不同？

为 k > 1 制作人工 LR(k) 文法很容易：

Input: A1 B x
Input: A2 B y                   (introduce reduce-reduce conflict for terminal a)
A1   : a
A2   : a
B    : b b b ... b              (terminal b occurs k-1 times)

然而，是否有任何现实世界的非 LR(1) 计算机语言是 LR(k > 1) 可解析的？
或者非 LR(1) 语言也不是 LR(k)？

LR(1)解析器可以解析这种类型的语法吗？

S -> SA  | A
A -> aSb | ab

我正在尝试编写一个实现这种类型解析器的Java程序,但是我只能在没有左递归的语法上得到正确的结果.