第五章 LL(1)文法及其分析程序z5.1 预测分析程序 z5.2 LL(1)文法 z FIRST和FOLLOW集定义和计 算 z LL(1) 文法定义 z LL(1)分析程序的生成 z5.3 非LL(1)文法的改造1自上而下分析算法要点： .由根向下构造语法树 .构造最左推导 .推导出的终结符是否 与当前输入符匹配S aaabA B a AS AB A aA | B b | bB aaab. SAB S ABaAB A aAaaAB A aAaaaAB A aAaaa B A aaab B b2带回溯的自上而下分析S AB A aA | B b | bB a a a b b. S(1) A. S AB(2) aA. A aA(3) aaA. A aA(4) aaaA. A aA(5) aaa B. A (6) aaab B baaabb. S(1) A. S AB(2) aA. A aA(3) aaA. A aA(4) aaaA. A aA(5) aaa B A (6) aaa b B B bB(7) aaabb B b 3预测分析程序Predictive parser 无回溯的自顶向下分析程序特征根据下一个输入符号为当前要处理的非终结符选择产生式 要求文法是LL(1)的第一个L 从左到右扫描输入串第二个L 生成的是最左推导1 向前看一个输入符号（lookahead) 预测分析程序的实现技术1 递归下降子程序2 表驱动分析程序4PL/0语言的EBNFv程序=分程序. v分程序=常量说明部分变量说明部 分 过程说明部分语句 v常量说明部分=CONST常量定义部分，常 量 定义； v变量说明部分=VAR标识符，标识符； v过程说明部分= PROCEDURE 标识符分程序 ；过程说明部分；v语句= 标识符：=表达式 |IF 条件 then语句|CALL|READ|BEGIN 语句；语 句 END|WHILE|5begin(*statement*)if sym=identthen (*parsing ass.st.*)begingetsym;if sym=becomesthen getsymelse error(13);expression(fsys); end elseif sym=readsymthen (* parsing read st.*)begingetsym;if sym identthen error(35)else getsymuntil symrparenthen error(33); end6递归下降子程序 program function_list function_list function function_list | function FUNC identifier ( parameter_list ) statement void ParseFunction() MatchToken(T_FUNC); ParseIdentifier(); MatchToken(T_LPAREN); ParseParameterList(); MatchToken(T_RPAREN); ParseStatement(); 7void MatchToken(int expected) if (lookahead != expected) printf(“syntax error n“); exit(0); else / if match, consume token and move on lookahead = yylex(); 8例：递归子程序实现 表达式的语法分析表达式的EBNF 表达式=+|-项（+|-）项 项=因子（*|/）因子 因子=ident|number|（表达式 ）9zprocedure expr; beginif sym in plus, minus thenbegingetsym; term; end else term;while sym in plus, minus dobegingetsym; term;end end;10Procedure term;begin factor;while sym in times,slash dobegin getsym;factor end end;11Procedure factor;begin if sym=identthen getsymelseif sym=numberthen getsymelseif sym=(then begin getsym;expr;if sym=)then getsymelse errorendelse errorend; 12表驱动予测分析程序模型Input #总控程序预测分析表stack13带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器磁头识别程序的数学模型下推自 动机14上下文无关语言句型分析（识别）程序的数 学模型下推自动机Pda=(K,f,H,h0,S,Z)H:下推栈符号的有穷字母表h0 :H中的初始符号f: K （) H K H* Pda的一个组态是K * H 中的一个（k,w,) k:当前状 态，w:余留输入串， ：栈中符号，最左边的符号在栈顶。 Pda的一次移动用组态表示 终止和接受的条件:1.到达输入串结尾时，处在Z中的一个状态或 2.某个动作序列导致栈空时 15例：Pda P=(A,B,C),a,b,c),f,h,i,iA, )f(A,a,i) = (B,h) f(B,a,h) = (B,hh)f(C,b,h) = (C, ) f(A,c,i) = (A, )f(B,c,h) = (C,h) 接受输入串aacbb的过程 (A,aacbb,i) 读a, pop i, push h, goto B(B,acbb,h) 读a, pop h, push hh, goto B (B,cbb,hh) 读c, pop h, push h , goto C(C,bb,hh) 读b, pop h, push , goto C(C,b,h) 读b ,pop h, push , goto C (C, , )16G E: (1) E TE(2) E +TE(3) E (4) T FT(5) T *FT(6) T (7) F (E)(8) F a 17a + * ( ) #E (1) (1)E (2) (3) (3)T (4) (4)T (6) (5) (6) (6)F (8) (7)G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a18分析算法 z BEGIN z 首先把#然后把文法开始符号推入栈；把第一个输入符号读进b; FLAG：=TRUE； z WHILE FLAG DOBEGIN z 把栈顶符号上托出去并放在中； z IF X Vt THEN IF X=b THEN z 把下一个输入符号读进a z ELSE ERRORELSE IF X=# THEN z IF X=b THEN FLAG:=FALSE z ELSE ERROR z ELSE IF X,b=X X1X2XK z THEN 把XK，X K-1,X1一一推进栈 z ELSE ERROR z END OF WHILE; z STOP/*分析成功，过程完毕* z END19分析输入串#a+a# 栈内容 栈顶符号 当前输入 余留串 MX,b 1 #E E a +a# E TE2 #ET T a +a# T FT3 #ETF F a +a# F a 4 #ETa a a +a# 5 # ET T + a# T 6 #E E + a# E +TE 7 #ET+ + + a# 8 # ET T a # T FT 9 #ETF F a # F a 10 #ETa a a # 11 #ET T # T 12 #E E # E 13 # # #20FIRST集和FOLLOW集的定义 设G=(VT,VN,P，S)是上下文无关文法 FIRST（）=a| =* a,aVT, , V*若 =* 则规定FRIST（） FOLLOW（A）=aS =* A 且a FRIST（ ）， V*， V+ 若S =* u A ,且 =* ，则 #FOLLOW(A)LL (1) 文法21计算FIRST集1.若XV,则FIRST(X)=X 2.若XVN,且有产生式Xa，则把a加入到 FIRST(X)中;若X也是一条产生式,则把也 加到FIRST(X)中. 3.若XY是一个产生式且YVN,则把FIRST(Y) 中的所有非元素都加到FIRST(X)中;若X Y1Y2YK 是一个产生式,Y1,Y2,Y(i-1)都是非 终结符,而且,对于任何j,1j i-1, FIRST(Yj)都含有 (即Y1Y(i-1) =* ),则 把FIRST(Yj)中的所有非元素都加到 FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,K)均含有,则把加到FRIST(X)中.22计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S) 中; 2.若 B 是一个产生式,则把 FIRST()加至FOLLOW(B)中; 3.若 B是一个产生式,或 B是 一个产生式而 =* (即FIRST()） ， 则把FOLLOW（A）加至FOLLOW（B）中23一个文法G是