第四章 语法分析2课件.ppt

1 自顶向下分析;;; 例如G[S],这个文法产生偶数个a的所有串?。?其产生式如下： S→aSa|aa (4.11) 设w=aaaa$，程序从左至右读w，采用试探法，不妨先选择最长的候选式进行推导，如不行，再选用另一个候选式。分析过程如下?：???????????; 步骤 最左推导 和输入串匹配 第1步 S?aSa w=aaaa$ 第2步 ?aaSaa w=aaaa$ 第3步 ?aaaSaaa w=aaaa$ 第4步 ?aaaaSaaaa w=aaaa$ ????至此，发现分析选用的候选式不对，回退到第3步选用S→aa进行分析。  第5步 ?aaaaaaaa w=aaaa$ 回退到第2步 第6步 ?aaaaaa w=aaaa$ 回退到第1步 第7步 ?aaaaaa w=aaaa$ 成功; ; …;;;;;;; 1 向前看符号决定了选择哪个产生式右部的文法符号串与输入符号串匹配，在程序中由向前看符号可以确定一段程序完成与某一产生式右部的匹配。 2 每一个非终结符号对应一个函数，函数的功能是根据向前看符号扩展分析树，同时用该非终结符号的儿子结点匹配输入符号串。例如，用函数type(…)和simple(…)对应上例中的非终结符号type和simple。; Void main( ) { 初始化lookahead； type()； };;; 在实际语言中，每一种 语法成分都有确定的左右界 符，为了研究问题方便，统 一以‘＃’表示;（2）符号栈: 有四种情况; 出错状态;执行程序主要实现如下操作:;(3)若X∈Vn，查分析表M。 a) M[X,a]= X ? UVW 则将X弹出栈，将UVW压入 注：U在栈顶 （最左推导） b) M[X, a] = error 转出错处理 c) M[X, a] = X ? ε 则将X弹出栈,继续分析。 ;;;预测分析控制程序 置 ip指向输入符号串w#的第一个符号； REPEAT 令X为栈顶符号，a是 ip所指向的符号. IF (X?VT?{#}) IF (X= =a) { 弹出X; ip:=ip+1} ELSE error( ) ELSE IF (M[x,a]=x?y1y2…yk ) {pop(st); push(st,yk);…push(st,y1); write(x?y1y2…yk) } ELSE error( ) UNTIL (X= =#) ;;;预测分析 控制程序;栈;三. 计算 FIRST和 FOLLOW集合 ;如何构造FIRST(?) ？ ? ∈（VT∪VN）* ;单个文法符号的FIRST集合构造方法 当? ∈（VT∪VN） FIRST(?) ？ a）如果? ∈VT，则FIRST(?) ={?} b）如果? ∈VN，且有产生式? a…， a? VT 则把a加入到FIRST(?) ；如果? ? ?也是一个产生式则把?加入到FIRST(?) ;2 在单个文法符号的基础上，任一文法符号串的FIRST集合构造方法 当? = X1X2…Xn FIRST(?) ？;