smw*_*dia 15 compiler-construction ll-grammar formal-languages
(我正在度假时间谈论一些语言理论.如果这是一个天真的问题,请原谅.)
根据这里:
LL语法,特别是LL(1)语法,具有很大的实际意义,因为这些语法的解析器易于构造,并且由于这个原因,许多计算机语言被设计为LL(1).
那么,出于好奇,当代计算机语言是LL(1)？C,Java,C#或Python是否属于这一类？
我想我很想用[引证需要]标记维基百科的引用; 这些假设至少是值得怀疑的.例如,有大量基于yacc的编译器构造工具,这使得在实践中使用更强大(同样快速)的LALR算法构建解析器非常容易,有些还实现了更强大的功能(并且几乎同样快,在大多数实际语法中)GLR算法.几十年来,手写解析器一直没有必要.[注1]
通过尝试回答问题:
大多数计算机语言在技术上都不是LL,因为它们甚至没有上下文.那将包括需要声明标识符的语言(C,C++,C#,Java等),以及具有预处理器和/或宏设施的语言(C和C++等),含有歧义的语言只能是使用语义信息解决(Perl将是这里最糟糕的攻击者,但C和C++也在那里).而且,为了传播更多的乐趣,它还包括具有类似Python的布局感知的语言(当然还有Python,还有Haskell).
我在"技术上"引用了恐慌的引用,因为有很多人会说这些例外"不计算".这是他们的意见,他们有权获得它(无论如何,我已经放弃了争论,尽管我不赞同这种观点).例如,您可以通过在应用语法之前预处理文本来消除C/C++中的预处理器,或者通过插入INDENT,NEWLINE和DEDENT令牌而不是空白来预处理空白感知语言,之后您可以进行某种声明关于神秘的"核心语言".(这很难应用于C++模板,只能通过解析文本来消除,因此您不能声称可以在解析之前完成扩展.)
声称语言不是无上下文因为它需要声明标识符的说法可能更具争议性.在某些语言中(不是C/C++,其中需要语义分析以避免歧义),您可以认为可以在不验证声明规则的情况下构造解析树,这使得该规则"不是语法".但仍然可以在语法上强制执行声明规则; 你不能用无上下文语法(例如,你可以使用Van Wijngaarden语法).
在任何情况下,常见的解析策略是识别语言的超集,然后通过对得到的解析树的后续分析来拒绝不合格的程序; 在这种情况下,问题是超集是否是LL.在我看来,为了使其有意义,有必要将每个有效的程序解析为正确的语法树,这消除了使用语义分析来消除歧义.
解析的目的是生成语法树,而不仅仅是识别文本是否有效.(你可能会错过这个重要的事实,如果你浏览那些倾向于关注识别的正式语言教科书,可能是因为语法树的结构不那么有趣.)因此,坚持提出的语法实际上代表句法结构似乎是合理的.的语言.
例如,您可以使用简单的常规语言识别代数表达式:
(PREFIX* OPERAND POSTFIX*) (INFIX PREFIX* OPERAND POSTFIX*)*
其中PREFIX是前缀运算符(的集合,POSTFIX是后缀运算符的集合(如果有的话)以及),INFIX是中缀运算符的集合(加法,减法,乘法等),而OPERAND是一个标识符或不变的.
那个正则表达式不会正确地拒绝带有不平衡括号的表达式,但是我们已经同意识别该语言的超集是对的,对吧？:-)
如果需要,我们可以从PREFIX和POSTFIX集中删除括号,并使OPERAND成为递归生成.得到的语法通常是LL(1)[注2]:
operand => IDENTIFIER | CONSTANT | '(' expression ')'
term => operand | PREFIX operand | operand POSTFIX
expression => term | term INFIX expression
然而,问题是该语法不捕获运算符优先级.它甚至没有尝试识别a+b*c并且a*b+c都是和的事实,因此+在这两种情况下都是顶层运算符,而不是在表达式中首先出现的操作符.(如果您正在解析APL,这不会成为问题.但是大多数语言都符合关于运算符优先级的通常预期.)
这一点很重要,因为LL语法不能处理左递归生成,并且您需要左递归生成才能正确解析左关联运算符.(也就是说,要正确地解析a-b-c为((a-b)-c),而不是(a-(b-c)),这将有不同的值).同样,你可以说,这是一种狡辩,因为你可以后期处理解析树,以纠正关联.这当然是正确的,但结果是您用来解析的语法与用于解释语言语法的语法不同.这可能会或可能不会打扰你.
这里值得补充的是,有些语言(Haskell,Prolog,可能还有更多)可以在程序文本中定义运算符及其优先级.这显然使得无法在没有语义分析的情况下生成正确的语法树,并且解析这些语言的通常方法是精确使用上面概述的简化的"交替操作数和运算符"语言.一旦运算符优先级全部已知,大概在解析结束时,所有表达式然后使用诸如Shunting Yard算法之类的东西重新分析,以便产生正确的解析.
让我们假设我们抛弃了上述异议,并问"可以使用哪种常用的编程语言LL解析器？"
但是,为了避免作弊,我们应该确实要求LL解析器具有固定的前瞻,而不需要回溯.如果你允许任意前瞻和回溯,那么你大大扩展了可解析语言的领域,但我认为你不再属于LL领域.这将消除,例如,C++的无模板和预处理器的子集,即使常见的编译器实现使用递归下降解析器,因为需要回溯以解决"最令人烦恼的解析"模糊性.(无论如何,你无法真正从C++中删除模板,并且使用模板进行解析非常困难.[注3])
Java和Python都被设计为LL(1)"伪可解析".我相信Haskell也属于这一类.没有语义信息就无法正确解析C(经典歧义:是(x)*(y)演员还是乘法？ - 它取决于是否x已经被typedef或声明为变量)但我很确定它可以用非捕获回溯递归下降解析器.我没有深入研究过C#,但Eric Lippert的这个答案表明它在某些情况下需要回溯.
当然,人们仍然这样做,并且在许多情况下有充分的理由(例如,产生更好的错误消息).但是"构建LALR解析器很困难" 并不是一个好理由,因为事实并非如此.
这不是LL,因为我没有留下因素.但这很容易做到; 我会把它留作练习.
请参阅C++上下文无关或上下文敏感？.Todd Veldhuizen的经典C++模板也是Turing Complete