X 总控程序 分析表 分析栈
# 其中:
①分析表,实现相应的分析动作,即对[Ai,aj],设Ai示当前分析工作栈顶为Ai,输入字符为aj时,应选用Ai推导。
②分析工作栈,用于存放分析过程中的文法符号。分析工作栈初始化时,在工作栈顶写入一个“#”,再写入文法开始符号。
③总控程序,依据分析工作栈和分析表联合控制输入串的识别和分析。
2、分析程序的工作原理
⑴把“#”和文法开始符号推入分析工作栈;设置指示器的初始值,用第一个输入符号(终结符号)与分析工作栈顶文法符号进行匹配。
⑵设在某一步的分析工作栈与输入串的当前工作状态: X1X2
Xm-1Xm为分析工作栈中的当前状态;aiai+1
#为输入
表进行
串的当前状态。
①若Xm
VN,则以Xm及ai组成符号对(Xm,ai)查分
析表M[Xm,ai],设XmUVW,将Xm从分析工作栈顶退出,
并将UVW按反向写入分析工作栈中。若M[Xm,ai]=“Error”,则调用出错处理程序。
②若Xm
VT并且Xm=ai,则表明分析工作栈顶的符号与当
前输入符号相匹配,将工作栈顶的符号Xm退出,输入符号指针向右移一位。
③若Xm=#,则表明输入符号串已完全匹配,分析成功结束分析工作。
3、分析程序的算法(P77)
例:对输入串 # i*i+i #的预测分析过程
P78
第四节 递归下降分析程序的构造
一、递归下降分析程序的构造方法
对文法的每个非终结符号,根据各侯选式的结构,编写一个对应的子程序,完成非终结符相应的语法成分的识别和分析任务。 二、递归下降分析程序的功能
对某个非终结符,用产生式规则的右部符号进行匹配。 三、递归下降分析程序的特点
1、程序结构清晰,易于手工操作。
2、对语义处理灵活。 四、递归下降分析法的必要条件
必须是不包含左递归和回溯的上下文无关文法。 五、递归下降分析程序的设计
P74
第五节 预测分析法的错误处理 一、出错情况
1、工作栈顶终结符与输入符号不匹配。
2、对应M[A,a]中为空(Error)。 二、出错处理
1、报告出错(出错位置,出错性质)。 2、处理出错情况,使语法分析继续下去:
⑴若M[A,a]中为空(Error),跳过输入符号a,若该项为同步(synch),则退出工作栈顶的非终结符A。
⑵工作栈顶的终结符无法与输入符号匹配,则弹出该符号。
第六节 学习与理解
一、填空题
⑴自上而下语法分析方法的基本思想是:从文法的开始符号出发。不断建立最左直接推导,试图构造一个推导序列,最终由它推导出与输入符号串相同的符号串。
⑵自上而下分析方法会遇到的主要问题有回溯和左递归。 ⑶在语法分析中,最常见的两种方法一定是自上而下分析法,
另一种是自下而上分析法。 二、选择题
⑴编译过程中,语法分析器的任务是B,C,D。
A、分析单词是怎样构成的 B、分析单词串是如何构成语句的 C、分析语句是如何构成程序的 D、分析程序结构
⑵高级语言编译程序常用的语法分析方法中,递归下降分析法属于B分析方法。
A、自左至右 B、自上而下 C、自下而上 D、自右至左
三、解答题
⑴已知文法G: A
aAa
①该文法是LL(1)文法吗?为什么?
②若采用LL(1)方法进行分析,如何得到该文法的LL(1)分析表。
③若输入串“aaaa”,请给出语法分析过程。 解:
①因为FOLLOW(A)=FOLLOW(A)#},造成FOLLOW(A)
FIRST(A)={a,
}
,
FIRST(A)={a,#}{a,
所以该文法不是LL(1)文法。
②若采用LL(1)方法进行语法分析,必须修改该文法。因该文法产生偶数(可以为0)个a,所以得到文法G`:A
。
此时 FOLLOW(A)={#},因此
FOLLOW(A)
FIRST(A)={#}{a,
}=
aaA
所以文法G`是LL(1)文法。该文法的LL(1)分析表:
VT a # VN A AaaA A③对符号串“aaaa”的分析过程:
步骤 1 2 3 4 5 6 7 8 分析栈 输入串 产生式/动作 aaA #A aaaa# A#Aaa aaaa# 匹配 #Aa aaa# 匹配 #A aa# AaaA #Aaa aa# 匹配 #Aa a# 匹配 #A # A # # 接受 ⑵设文法G(A):
AB
aABcBb
d aA
①试给出文法G(A)等价的LL(1)文法G`(A)。
②构造G`(A)的LL(1)分析表,给出输入串aadc#的分析过程。
语法分析-自上而下分析
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)