编译原理第3讲.ppt

第三讲语法分析
语法分析概述
自上而下语法分析
自下而上语法分析
1
CompilerPrinciples
基本思想:从文法的开始符号出发,推
导出句子
回溯→避免条件 First(x),
Follow(u)
基本问题
无限循环→消除左递归
递归子程序法
分析方法
LL(1)分析法
自上而下语法分析
2
CompilerPrinciples
基本思想:从输入串开始逐步归约
基本问题:归约的问题
简单优先
优先分析法算符优先
优先函数的构造
分析方法规范句型活前缀
基础知识 LR(0)项目及项目集
LR(1)项目及项目集
LR分析法 LR分析器分析栈、分析表
分析方法
LR分析表的构造
二义性文法的分析

实现技术——移进归约
自下而上语法分析
3
CompilerPrinciples
§
一、语法分析器的功能
:
:在单词符号的基础上,分析给定语言的句子(程序)的语法结构,看其是否符合语法规则。
源程序
词法分析器
语法分析器
编译程序后续部分
符号表
返单词符号
取单词符号
语法树
4
CompilerPrinciples
二、分析方法
——依据程序语言的语法规则,即文法描述。
☉若能构造出一棵语法树则正确,否则程
序有错
,分为两种:
●自上而下分析法:从文法开始符号出
发,自上而下地构造语法树;
●自下而上分析法:从单词符号串形式的
源程序开始,自下而上地构造语法树;
5
CompilerPrinciples
§
一、方法、问题及其解决
:对任意输入的(单词符号)串,试着从开始符号出发,自上而下地建立起一棵语法分析树,使得该树的叶结点自左而右地排列起来,刚好就是所给的输入串。
☉显然,这种建立语法树的过程应遵照某种规范——通常应与最左推导相对应,即自左向右进行匹配。
例 G[S]:
S→aAb 输入串 a*b
A→**∣*
S
a
A
b
*
*
*
Ip
6
CompilerPrinciples
:
·这是一种自上而下的试探法,有时免不了要走回头路——回溯。
·该方法实现时就是模拟收养儿子的过程—左递归文法会造成死循环。
:
(1)左递归问题:改写产生式,变左递归为右递归。
①直接左递归:直接见诸于产生式的左递归,如
P→Pα,P∈VN, α∈(VT∪VN)*
这种直接左递归可以通过直接扫描产生式发现,也容易解决——改写产生式即可。
7
CompilerPrinciples
如: P→Pα1∣Pα2∣…∣Pαm∣β1∣β2∣…∣βn
其中P∈VN,αi,βj ∈(VT∪VN)* 且α≠є,
β不以P开头
改写成
P→β1 P' ∣β2 P' ∣…∣βn P'
P' →α1 P' ∣α2 P' ∣…∣αm P'∣ε
例:文法G[E]:
E →E+T∣T 改写成 E→TE' E'→+TE'∣ε
T →T*F ∣ F 改写成 T→FT' T'→*FT'∣ε
8
CompilerPrinciples
②消除左递归:通过改写产生式我们可以消除直接左递归,但不能完全消除左递归,因为还存在着间接左递归的问题。
例如文法G[P]: P→Qc∣c Q→Rb∣b R→Pa∣a
表面上并看不出它的左递归性,但是仔细观察时不难发现P,Q,R都是左递归的,因为
P Qc Rbc Pabc,即P +Pabc;
Q +Qcab,R +Rbca亦然。
对这种左递归的消除就稍微麻烦一些。首先,从产生式中找这种形式的左递归。其思想也就是通过推导来寻找左递归、并进一步修改产生式。为此,我们设计以下算法:
9
CompilerPrinciples
消除左递归算法:
Ⅰ.按任一顺序把文法G的所有非终结符排序成P1,P2,…Pn,按此顺序执行:
Ⅱ.FOR i=1 TO n DO
BEGIN
FOR j=1 TO i-1 DO
把形如Pi→Pjγ的产生式改写成
Pi→δ1γ∣δ2γ∣…∣δkγ,其中
Pj →δ1∣δ2∣…∣δk是关于Pj的所
有产生式;
消除关于Pi的直接左递归性
END
Ⅲ.化简由Ⅱ所得的文法——去除无用的非终结符。
10
CompilerPrinciples