编译原理文法详解_编译原理为什么存在递归文法
引言
学完了词法分析，我们知道词法分析器将正则表达式转换成词法单元流，但对于这个记号流我们不知道是否能由正确的文法产生，因此我们需要通过语法分析器来检测其合法性。语法分析器的输出是一棵语法分析树（无论显性还是隐性），并且进行一些语法纠错处理。语法分析的整个过程大概就是我们先定义一个语法，再用相应的算法来检测我们的词法单元流是否符合该语法。这里主要讨论上下文无关文法构成的语法和自顶向下、自底向上的语法分析。
上下文无关文法
定义为一个四元组（VT,VN,S,P）
- VT:终结符的有限集合
- VN:非终结符的有限集合，与VT无交集
- S:开始符号
- P:产生式的有限集合。形如A->α，α∈(VN∪VT）*
类似自动机的定义，不过是语法的产生式。 为什么要叫上下文无关文法呢？因为产生式的左边只有一个符号，也就是说只要满足了右侧的串就可以直接归约到左边的符号，不需要查看上下文。与此相对的上下文有关文法例如aSb -> abab 就是上下文有关文法。
推导
把产生式看成重写规则，符号串中的非终结符用产生式右部的串（α）代替。 推导具有自反性，传递性。
- 最左/右推导：每次替换都先选择最左/右的串进行推导。
举例: 有以下文法： S->S(S)S|e 如何用最左推导推导出串 (()())？ 法一：S=>S(S)S=>e(S)S=>e(S(S)S)S=>e(S(S)S(S)S)S=>e(e(S)S(S)S)S=>…=>e(e(e)e(e)e)e 法二：S=>S(S)S=>e(S)S=>e(S(S)S)S=>e(e(S)S)S=>e(e(e)S)S=>e(e(e)S(S)S)S=>…=>e(e(e)e(e)e)e 我们每次遵循必须替换掉最左边的S的原则，尝试每一种匹配，如果失败，退回，选择下一匹配，直到成功。这样我们得到了一个串的最左推导。不过以上例子我们得到了两个不同的最左推导，并且都是严格遵照了最左推导的要求来的。因此，我们说这个文法具有二义性。计算机不喜欢二义性，计算机喜欢单刀直入，因此后面我们会看到消除二义性的办法。
语法分析树
语法分析树是推导的图形表示。一个推导对应一棵语法分析树。 我们对上例法一进行语法分析树的构建（e就是空串）：
总之，就是将左推导展开成树的形式。
消除二义性
- 一种是自定义优先级和结合性 例：原文法E->E+E|E*E|(E)|-E|digit 是有二义性的 分析后可得：优先级：digit 和() 最高，/和*其次 ，+和 – 最后。 结合性： + 、-、*、 /都是左结合。 因此先匹配digit和()的文法。 factor->digit | (expr) term->term * factor | term / factor | factor expr->expr + term | expr – term | term 其中factor表示数字和括号表达式，term表示乘除表达式，expr表示加减表达式
- 悬空else文法 stmt → matched_stmt (匹配的if从句) | unmatched_stmt (不匹配的if从句 matched_stmt → if expr then matched_stmt else matched_stmt | other unmatched_stmt → if expr then stm | if expr then matched_stmt else unmatched_stmt
自顶向下分析
所谓自顶向下分析，就是从分析树的顶部向底部构造分析树，也即从开始符号S推出整个串的过程。自顶向下分析采用最左推导，因为分析器是从左到右扫描的。
然而，有的文法不能采用自顶向下分析，因为产生了左递归。
左递归的判定和消除
- 左递归的判定：一个文法G，若存在P经过一次或多次推导得到Pa（即能推导出以P开头的式子）， 则称G是左递归的。 符号如下： 1)A→Aβ，A∈VN，β∈V 2)A→Bβ，B→Aα，A、B∈VN，α、β∈V* 以上两种情况都出现了左递归，即自己推出和自己有关的东西。
- 左递归消除：
1.直接左递归 使用公式: (原始) A → Aα1 | Aα2 | … | Aαm| β1 | β2 | … | βn (转化) A → β1 A’ | β2 A’ | … | βn A’ A’ → α1A’ | α2A’| … | αmA’ | e
2.间接左递归 间接左递归就是要通过多次推导才能看出文法有左递归。如： S→Qc｜c，Q→Rb｜b，R→Sa｜a有S =>Qc =>Rbc =>Sabc 先转变成直接左递归，再使用公式。 把所有关于S的文法带入，并且得到直接左递归的公式，例如上面的文法： Q→(Sa|a)b即Q→Sab|ab|b S→Sabc|abc|c|bc 然后就可以使用公式了。
总结
这一节的主要内容应该是自顶向下分析，为了构建这一棵语法树，我们使用上下文无关文法，定义了推导的概念，发现我们要使用左推导，并且解决了二义性，顺便消除了左递归，这才成功构建出这样一棵语法树。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/219142.html原文链接：https://javaforall.cn