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

Question

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

编辑:

在接受了真正的答案之后,我认为以这种方式改变Q更好:

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

Answer 1

如果没有首先为语言指定特定的语法,就不能提出这个问题,因为有些语法可能是,有些可能不是.

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

我不确定你能为C#指定一个特定的语法,至少不是微软的一个,特别是对于C#4.0; 我不相信他们已经发表了语法.

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

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

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

我们的语言前端系列的C#4.0和Java 7成员都使用GLR解析器解析语言,扩展了反馈功能,并能够处理同一令牌的两种解释.GLR使得LALR(X)没有实际意义的问题,反馈和多种解释,让我们处理许多语言,这将是纯粹的GLR的能力之外了.

编辑:经过一番思考,可能有一种真正丑陋的方式使两个语法处理他们的关键字在上下文中.我们以Java的枚举为例.实际上必须有语法规则:

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

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

  identifier = IDENTIFIER | 'enum' ;

并坚持认为标识符是词法分析器生成的终端.现在至少lexer不必决定如何处理枚举 ; 解析器.但是你的指定语法必须像这样形成,以便有机会成为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