可以转化为LR解析table的上下文无关文法是否明确？
Is a context-free grammar that can be transformed into a LR parsing table unambiguous?
我知道一般来说上下文无关文法是否无歧义是不可判定的。但是，这并不意味着不能为上下文无关文法的子集决定这一点。
语法用于将输入文本转换为解析树。如果一个语法可以为给定的输入生成多个解析树，那么它就是有歧义的。
LR解析器算法首先将文法转化为LR解析器table。之后，它使用 LR 解析器自动机将给定的输入流处理为使用 LR 解析器 table 的解析树。第一步通常由解析器生成器完成，而第二步针对每个解析操作执行。
考虑LR解析器table构造算法construct(G) = T | error。该算法接收上下文无关文法G。如果 table 构造成功，一个无冲突的 LR 解析器 table T 被 returned。如果 table 构造失败，则会出现 return 错误。这种算法的例子有 SLR、LALR 和 CLR。算法失败的典型示例是 shift-reduce 和 reduce-reduce 冲突。
对于有限的输入流和无冲突的 LR 解析器 table LR 解析器自动机可以确定地从给定的输入流或 return 派生出一个解析树，前提是输入流没有不符合语法。解析步骤可以形式化为parse(T, I) = O | error，其中T是无冲突LR解析table，I是token的输入流，O是单个解析树。如果输入流与语法不匹配，则错误是 returned。
问题
总结以上陈述我的理解是，任何可以以某种方式转换为无冲突 LR 解析器的语法 table 都是明确的。但是，如果算法 return 出错，这并不意味着任何关于语法是否有歧义的声明。因此，LR table 构造算法半决定上下文无关文法的子集是否明确。这是正确的吗？
以下是我的结论可能落空的一些步骤：
- LR table 构造算法可能不会终止
- LR 解析器自动机可能不会终止
- LR table 构造算法不正确，因此 LR 解析器自动机将接受与构造它的文法不完全相同的一组输入流，或者它派生出与文法不同的另一个解析树。
据我所知，上述 none 对于常见的 LR table 构造算法是正确的。
我找不到关于此的明确陈述，因此我将不胜感激解释以及讨论和明确回答此问题的参考。
我认为这个问题在设计编程语言时非常重要，因为如果我的结论是正确的，LR 解析器可以确保用该语言编写的每个程序都能被正确解析。是否有其他方法可以确保语法无歧义？
如果一个文法可以生成LR(k)解析器，那么这个文法肯定是没有歧义的。 LR(k) 算法是确定性的；它总是会因错误或正确的解析自动机而终止。 （类似于 SLR(k) 和 LALR(k) 解析器。）
所以你是对的：如果 LR(k) 解析 table 生成算法成功终止，则语法是明确的，但如果它以错误终止，则语法可能是明确的。
我不明白如何将其推广到 "any" LR table 生成算法，因为声称是这样的算法可能不正确或没有终止。但是对于标准算法来说肯定是正确的。
对于正式证明，您可以参考 S. Sippu 和 E. Soisalon-Soininen 的经典教科书 Parsing Theory 第二卷（Springer-Verlag，1990）。
我知道一般来说上下文无关文法是否无歧义是不可判定的。但是，这并不意味着不能为上下文无关文法的子集决定这一点。
语法用于将输入文本转换为解析树。如果一个语法可以为给定的输入生成多个解析树，那么它就是有歧义的。
LR解析器算法首先将文法转化为LR解析器table。之后，它使用 LR 解析器自动机将给定的输入流处理为使用 LR 解析器 table 的解析树。第一步通常由解析器生成器完成，而第二步针对每个解析操作执行。
考虑LR解析器table构造算法construct(G) = T | error。该算法接收上下文无关文法G。如果 table 构造成功，一个无冲突的 LR 解析器 table T 被 returned。如果 table 构造失败，则会出现 return 错误。这种算法的例子有 SLR、LALR 和 CLR。算法失败的典型示例是 shift-reduce 和 reduce-reduce 冲突。
对于有限的输入流和无冲突的 LR 解析器 table LR 解析器自动机可以确定地从给定的输入流或 return 派生出一个解析树，前提是输入流没有不符合语法。解析步骤可以形式化为parse(T, I) = O | error，其中T是无冲突LR解析table，I是token的输入流，O是单个解析树。如果输入流与语法不匹配，则错误是 returned。
问题
总结以上陈述我的理解是，任何可以以某种方式转换为无冲突 LR 解析器的语法 table 都是明确的。但是，如果算法 return 出错，这并不意味着任何关于语法是否有歧义的声明。因此，LR table 构造算法半决定上下文无关文法的子集是否明确。这是正确的吗？
以下是我的结论可能落空的一些步骤：
- LR table 构造算法可能不会终止
- LR 解析器自动机可能不会终止
- LR table 构造算法不正确，因此 LR 解析器自动机将接受与构造它的文法不完全相同的一组输入流，或者它派生出与文法不同的另一个解析树。
据我所知，上述 none 对于常见的 LR table 构造算法是正确的。
我找不到关于此的明确陈述，因此我将不胜感激解释以及讨论和明确回答此问题的参考。
我认为这个问题在设计编程语言时非常重要，因为如果我的结论是正确的，LR 解析器可以确保用该语言编写的每个程序都能被正确解析。是否有其他方法可以确保语法无歧义？
如果一个文法可以生成LR(k)解析器，那么这个文法肯定是没有歧义的。 LR(k) 算法是确定性的；它总是会因错误或正确的解析自动机而终止。 （类似于 SLR(k) 和 LALR(k) 解析器。）
所以你是对的：如果 LR(k) 解析 table 生成算法成功终止，则语法是明确的，但如果它以错误终止，则语法可能是明确的。
我不明白如何将其推广到 "any" LR table 生成算法，因为声称是这样的算法可能不正确或没有终止。但是对于标准算法来说肯定是正确的。
对于正式证明，您可以参考 S. Sippu 和 E. Soisalon-Soininen 的经典教科书 Parsing Theory 第二卷（Springer-Verlag，1990）。