C# 和 Java Grammars 是 LALR（x）吗？

parsing java c# lalr

2022-09-02 03:31:14

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

编辑：

在接受真实答案后，我认为最好以这种方式更改Q：

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

答案 1

如果不首先为语言指定特定的语法，您就不能问这个问题，因为有些语法可能是，有些可能不是。

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

我不确定你能为C#指定一个特定的语法，至少不能从微软指定一个语法，特别是对于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著名的解析C++与LALR解析器在很长一段时间内都有一个可怕的符号表黑客，因此它可以区分标识符作为变量和标识符作为typedef实例之间的区别。它现在有某种手工实现的递归下降解析器，但我认为可怕的黑客仍然存在）。所以我不确定回答你的问题的价值。

我们的语言前端家族的 C# 4.0 和 Java 7 成员都使用 GLR 解析器解析语言，并通过反馈功能进行了扩展，并能够处理同一令牌的两种解释。GLR使LALR（x）的问题变得毫无意义，反馈和多种解释让我们处理了许多超出纯GLR能力的语言。

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

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

但是我们还需要允许“enum”作为标识器。为此，我们可以将终端令牌标识符替换为非终端：

  identifier = IDENTIFIER | 'enum' ;

并坚持认为识别器是词法分析器生成的终端。现在至少词法分析器不必决定如何处理枚举;解析器可以。但是你指定的语法必须像这样，才能有机会成为LALR（x）。

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

答案 2

Java语法（版本1.0）已知是LALR（1）;该网站提供了一个语法，并以以下通知开头：

语法已经过机械检查，以确保它是 LALR（1）。

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

值得一提的是，通常 LALR（1）是唯一使用的 LALR 解析器。如果你需要使用像 LALR（2）这样的东西来表示语法，通常最好使用具有显式优先消歧的 LALR（1）解析器，或者使用更强大的解析器，如 GLR 解析器。

希望这有帮助！