问题标签 [lr]

我有这样的规则语法

有没有办法把这个语法变成 LALR(1)？据我所知，如果解析器p在块内看到，则存在移位/导出冲突。

如果通过查看给我一个 CFG，我可以决定它是 LL 类语法还是 LR 类语法？当我在谷歌上搜索这个问题时，我得到的是这些语法的解析器是如何工作的，但这不是我想要的。任何帮助将不胜感激。

我在 yacc 中有这个语法：

在 flex 中：

我想做一个有效的解析，例如：

其中第一行是“Directivas”，然后是一个空白行，然后是“Conceitos”，其中一个 Conceito 是一个单词，后面是几行以“-”开头的文本行。那些 'Conceitos 由一个空行分隔

但它发现了一个转变/减少冲突..我是新来的，我不知道为什么

对不起我的英语不好

谢谢

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

我想我了解它对 LR(0) 的工作原理：

• 图的节点是LR 项，例如A → B • C
• 边缘是从A → B • C到的“过渡”C → • D

问题是，LR(1) 需要计算前瞻，我不知道如何将它们合并到算法中。
在我看来，即使我知道任何给定 LR 项目的传递闭包，我仍然需要通过所有相同的计算来确定每个项目的前瞻集是什么。

甚至可以使用 Warshall 的算法来计算规范的 LR(1) 闭包，还是仅适用于更受限制的情况（如 LR(0)、SLR(1) 等）？

我有一个无法解决的 LR(1) 冲突的语法；然而，语法应该是明确的。我将首先用五个标记的简化语法来演示这个问题：(、)、{}和。,id

EBNF 看起来像这样：

语法是明确的，最多需要两个前瞻标记。当(移位时，只有五种可能：

1. (→ 重复。
2. )→ 减少为'(' args ')'。
3. id )不{}→ 减少为'(' expression ')'。
4. id ) {}→ 减少为'(' args ')' '{}'
5. id ,→ 减少为'(' args ')' '{}'（最终）。

天真的翻译会产生以下结果（和冲突）：

因此，语法最多需要三个前瞻标记来决定。我知道 LR(3) 语法可以转换为 LR(1) 语法。

但是，我不太明白在这种特殊情况下如何进行转换。请注意，上面的简化语法是从大量代码中提取的；primary特别是，是否有可能在不触摸和上述所有内容的情况下进行转换 expr？

我对 lr(0) 解析器有疑问。例如，我有以下语法：

如果我尝试构造 lr0 自动机的第一个状态，我会得到以下第一个状态：

所以在我看来，这是一个愚蠢的怀疑。因为我有“S ->”。在第一种状态下，这是 lr0 解析器中移位/减少的情况吗？导致解析器可以通过非终结符 S 转移动作，或者通过空转换减少动作（我认为）。

我已经在网上搜索了一个带有空转换的示例，但我没有找到。

我正在尝试为以下语法创建一个 LALR(1) 解析器并找到一些移位/减少冲突。

所以解析器无法正确解析字符串“ID[ID]”。我的问题是，

1. 是否有任何通用方法可以将此类非 LALR(1) 语法转换为 LALR(1) 语法？
2. 如果两个文法生成完全相同的语言，并且我们知道其中一个不是 LALR(1)，我们能否知道另一个是否是 LALR(1)？

上面提到的语法只是一个例子，我真正想知道的是解决这些语法问题的一般方法。欢迎任何建议或阅读建议。

提前致谢。

我们找到 follow(A) 以防我们找到类型的产生式

A → α

这里的 α 可以是 ε 吗？

就像在下面的例子中：

P → aPa | 铅 ε

如果 α 可以是 ε，则它不是 LR(1)

我已经开始阅读有关 LR(k) 解析表构造的内容，所有解释 k > 0 算法的文本都建议在生成项目集之前为每个符号计算前瞻，然后在生成所有项目集时，应该合并多余的以生成最小的解析表。

考虑以下伪状态/项集构造例程：

1. 首先假设可以在没有前瞻的情况下确定状态转换（k = 0）
2. 计算当前状态的整个项目集
3. 尝试确定当前状态动作：
   • 如果集合中只有一个项目并且它已经消耗了所有输入（rhs 右侧的标记，则操作减少到项目的 lhs。
   • 如果集合中的每个项目都需要输入，则动作是转移并进入下一个状态
   • 如果有些项目需要输入而有些则没有，这是一个移位/减少冲突
   • 如果两个或多个具有不同 lhs 的项目到达输入末尾，这是一个减少/减少冲突。如果发生了最后两种情况之一，这意味着我们需要在决定状态动作之前先看一下。将 k 增加 1 并返回步骤 2。
4. 如果动作要转移，则通过模拟输入组合（如果 k > 0 则为前瞻）继续创建后续状态，并为每个新状态返回步骤 1。

使用上述步骤为任意 LR(k) 语法构建表是否可能/可行？如果没有，我错过了什么？

我知道 LR 和 LALR 都是自下而上的解析算法，但两者有什么区别？

LR(0)、LALR(1) 和 LR(1) 解析有什么区别？如何判断语法是 LR(0)、LALR(1) 还是 LR(1)？