大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
引言
学完了词法分析，我们知道词法分析器将正则表达式转换成词法单元流，但对于这个记号流我们不知道是否能由正确的文法产生，因此我们需要通过语法分析器来检测其合法性。语法分析器的输出是一棵语法分析树（无论显性还是隐性），并且进行一些语法纠错处理。语法分析的整个过程大概就是我们先定义一个语法，再用相应的算法来检测我们的词法单元流是否符合该语法。这里主要讨论上下文无关文法构成的语法和自顶向下、自底向上的语法分析。
上下文无关文法
定义为一个四元组（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
然后就可以使用公式了。
总结
这一节的主要内容应该是自顶向下分析，为了构建这一棵语法树，我们使用上下文无关文法，定义了推导的概念，发现我们要使用左推导，并且解决了二义性，顺便消除了左递归，这才成功构建出这样一棵语法树。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219142.html原文链接：https://javaforall.net
