文档介绍：

语义分析、生成中间代码
生成目标程序
代码优化
语法分析程序
词法分析程序
错
误
处
理
符
号
表
管
理
第4章语法分析
要求明确语法分析在编译过程所处的阶段和作用。
明确语法分析的基本分析方法。
掌握句柄、最左素短语、活前缀和项目等基本概念。
掌握消除文法左递归的方法。
掌握构造LL(1)分析表的方法,会使用LL(1)分析法分析句子。
掌握构造优先关系表的方法,会使用算符优先分析法分析句子。
掌握构造LR(0)、SLR(1)分析表的方法,会使用LR分析法分析句子。
教学目标
语法分析的任务
自顶向下分析法
自底向上分析法
算符优先分析法
LR分析法

PL/0编译程序的语法分析
教学内容
任务:根据文法规则,从源程序单词符号串中识别出语法
成分,并进行语法检查。
两大类分析方法:
自顶向下分析
自底向上分析
语法分析的任务
+
若xS 则xL(G[S]) 否则xL(G[S])
G[S]
存在主要问题: 回溯问题,左递归问题
主要方法:递归子程序法、 LL分析法
自顶向下分析算法的基本思想为:
自底向上分析算法的基本思想为:
+
若xS 则xL(G[S]) 否则xL(G[S])
G[S]
存在主要问题:“可归约串”的识别问题
主要方法:算符优先分析法、 LR分析法
自顶向下分析法
自顶向下分析的一般过程
从S出发采用最左推导,试图逐步推出输入串α,αL(G[S])?
S作为语法树的根,试图自上而下地为α构造一棵语法树
若叶结点从左向右排列恰好α,则表示α是文法的句子,而这棵语法树就是句子α的语法结构
若构造不出语法树,则α不是文法的句子
【】
α=acb
G[S]:
S→aAb
A→cd|c
分析过程是设法建立一
棵语法树,使语法树的末端结
点与给定符号串相匹配.
:令S为根结点·
S
,符号串去匹配输入串
·
S
a
A
b
完成一步推导SaAb
检查 a-a匹配
A是非终结符,将匹配任务交给A

A有两个右部,选第一个
·
a
A
b
c
d
S
完成进一步推导Acd
检查,c-c匹配,b-d不匹配(失败)
但是还不能冒然宣布αL(G[S])

改选A的第二右部
·
S
a
A
b
c
Ac 检查 c-c匹配
b-b匹配
建立语法树,末端结点为acb与输入acb相匹配,
建立了推导序列 SaAbacb
∴acbL(G[S])
α=acb
G[S]:
S→aAb
A→cd|c
自顶向下分析方法分类
确定的
不确定的
回溯

什么是回溯(backtracking)?
分析工作要部分地或全部地退回去重做叫回溯
造成回溯的条件:
文法中,对于某个非终结符号的规则其右部
有多个选择,并根据所面临的输入符号不能准确
的确定所要选择时,就可能出现回溯。
回溯带来的问题:
严重的低效率,只有在理论上的意义而无实际意义
自顶向下分析存在的主要问题