c# - C# 和 Java 语法是 LALR(x) 吗？

Question

我想知道 C# 和 Java 语法是否是 LALR(x)？如果是，x 的值是多少？

编辑：

接受了真实答案后，我觉得这样改Q比较好：

是否有任何 LALR(x) 解析器可以解析当前版本的 Java（版本 7）或 C#（版本 4）？如果是，x 的值是多少？

Answer 1

你不能在没有首先为语言指定特定语法的情况下提出这个问题，因为有些语法可能是，有些可能不是。

也许您指的是最近 Java 规范中发布的 Java 语法。你的意思是Java 7？

我不确定您是否可以为 C# 指定特定的语法，至少不能来自 Microsoft，尤其是对于 C# 4.0；我不相信他们已经发表了语法。

我可以告诉你，我不认为 C# 可以是 LALR(x)，因为它有一些看起来像标识符的元素，但在某些上下文中可以是关键字。这要求词法分析器知道解析器期望什么来确定类似标识符的标记是关键字还是仅仅是标识符。因此必须有从解析器到词法分析器的反馈，或者词法分析器必须产生两个标记并将它们传递给解析器以决定它想要哪个。LALR 解析器是在没有任何反馈的令牌流上定义的，并且每个输入令牌只有一种解释。

我认为 Java 也不是 Java 1.5 及更高版本，当时enum是作为具有自己关键字的特殊类型引入的。这是因为，对于 Java 1.5 编译器要处理使用enum作为变量名的现有 Java 1.4 程序，enum在某些上下文中必须被视为关键字，而在其他上下文中则必须被视为变量名。因此，Java 1.5 解析器与 C# 存在相同的问题。

实际上，没有真正的语言是 LALR(1) [第一版 Java 可能是一个例外]，任何构建真正的解析器 (尤其是 LALR) 的人都必须做出某种破解来解决这个问题。（GCC 用 LALR 解析器解析 C++ 很着名，而且很长一段时间都被一个糟糕的符号表破解，所以它可以区分作为变量的标识符和作为 typedef 实例的标识符。它现在有某种手工实现递归下降解析器，但我认为可怕的黑客仍然存在）。所以我不确定回答你的问题的价值。

我们的语言前端家族的 C# 4.0 和 Java 7 成员都使用 GLR 解析器解析语言，并扩展了反馈功能和处理同一标记的两种解释的能力。GLR 使 LALR(x) 的问题变得毫无意义，反馈和多种解释让我们也可以处理许多超出纯 GLR 能力范围的语言。

编辑：经过一番思考，可能有一种非常丑陋的方法可以让两种语法在上下文中处理它们的关键字。让我们以 Java 的枚举为例。实际上必须有语法规则：

  type = 'enum' '{'  enum_members '}' ;

但我们还需要允许“枚举”作为标识符。我们可以通过用非终结符替换终端令牌 标识符来做到这一点：

  identifier = IDENTIFIER | 'enum' ;

并坚持 IDENTIFIER 是词法分析器产生的终端。现在至少词法分析器不必决定如何处理enum；解析器会。但是您指定的语法必须形成这样的形状，才能有机会成为 LALR(x)。

我们的解析器曾经这样做是为了允许某些关键字有时用作标识符。如前所述，我们更改了解析引擎，不再这样做。

Answer 2

Java 语法（1.0 版）被称为 LALR(1)；这个网站提供了一个语法，并以通知开头

语法已经过机械检查以确保它是 LALR(1)。

我不确定 C# 是否为 LALR(1)，但这里有一个可用的C# 解析器bison，这表明它可能是 LALR(1)（假设您允许优先声明）。

对于它的价值，通常 LALR(1) 是唯一使用的 LALR 解析器。如果您需要对语法使用 LALR(2) 之类的东西，通常最好使用具有显式优先消除歧义的 LALR(1) 解析器，或者像 GLR 解析器这样功能更强大的解析器。

希望这可以帮助！

Answer 3

至少对于 Java（1.0 版）来说，它是：http: //java.sun.com/docs/books/jls/first_edition/html/19.doc.html