编译原理文法详解_编译原理为什么存在递归文法

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

引言

学完了词法分析，我们知道词法分析器将正则表达式转换成词法单元流，但对于这个记号流我们不知道是否能由正确的文法产生，因此我们需要通过语法分析器来检测其合法性。语法分析器的输出是一棵语法分析树（无论显性还是隐性），并且进行一些语法纠错处理。语法分析的整个过程大概就是我们先定义一个语法，再用相应的算法来检测我们的词法单元流是否符合该语法。这里主要讨论上下文无关文法构成的语法和自顶向下、自底向上的语法分析。

上下文无关文法

定义为一个四元组（V_T,V_N,S,P）

• V_T:终结符的有限集合
• V_N:非终结符的有限集合，与V_T无交集
• S:开始符号
• P:产生式的有限集合。形如A->α，α∈(V_N∪V_T）^*

类似自动机的定义，不过是语法的产生式。
为什么要叫上下文无关文法呢？因为产生式的左边只有一个符号，也就是说只要满足了右侧的串就可以直接归约到左边的符号，不需要查看上下文。与此相对的上下文有关文法例如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α₁ | Aα₂ | … | Aα_m| β₁ | β₂ | … | β_n
(转化)
A → β₁ A’ | β₂ A’ | … | β_n A’
A’ → α₁A’ | α₂A’| … | α_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
然后就可以使用公式了。

总结

这一节的主要内容应该是自顶向下分析，为了构建这一棵语法树，我们使用上下文无关文法，定义了推导的概念，发现我们要使用左推导，并且解决了二义性，顺便消除了左递归，这才成功构建出这样一棵语法树。