第五部分LL1文法及其分析程序教学ppt课件

1、第五章第五章 LL(1)LL(1)文法及其分析程序文法及其分析程序z5.1 5.1 预测分析程序预测分析程序z5.2 LL(1)5.2 LL(1)文法文法z FIRST FIRST和和FOLLOWFOLLOW集定义和计集定义和计 算算z LL(1) LL(1) 文法定义文法定义z LL(1) LL(1)分析程序的生成分析程序的生成z5.3 5.3 非非LL(1)LL(1)文法的改造文法的改造自上而下分析算法自上而下分析算法要点：.由根向下构造语法树.构造最左推导.推导出的终结符能否与当前输入符匹配 S aaab A Ba AS ABA aA | B b | bBaaab.S AB S AB a

2、AB A aA aaAB A aA aaaAB A aA aaa B A aaab B b带回溯的自上而下分析S ABA aA | B b | bBa 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 预测分析程序Predictive parser无回溯的自顶向下分析程序

3、特征根据下一个输入符号为当前要处置 的非终结符选择产生式要求文法是LL(1)的 第一个L 从左到右扫描输入串 第二个L 生成的是最左推导 1 向前看一个输入符号lookahead)预测分析程序的实现技术 1 递归下降子程序 2 表驱动分析程序PL/0PL/0言语的言语的EBNFEBNFv程序程序=分程序分程序. .v分程序分程序=常量阐明部分常量阐明部分变量阐明部变量阐明部 分分过程阐明部分过程阐明部分 语句语句v常量阐明部分常量阐明部分=CONST=CONST常量定义部分常量定义部分 ，常，常量量 定义定义 ；v变量阐明部分变量阐明部分=VAR=VAR标识符标识符 ，标识符，标识符 ；v过程

4、阐明部分过程阐明部分= PROCEDURE = PROCEDURE 标识符分程序标识符分程序 ；过程阐明部分；过程阐明部分 ；v语句语句= = 标识符：标识符：= =表达式表达式 |IF |IF 条件条件 thenthen语句语句|CALL|READ|BEGIN |CALL|READ|BEGIN 语句语句 ；语；语句句 END|WHILE| END|WHILE|begin(*statement*) if sym=ident then (*parsing ass.st.*) begin getsym; if sym=becomes then getsym else error(13); expr

5、ession(fsys); endelse if sym=readsym then(* parsing read st.*)begin getsym; if symlparen then error(34) else repeat getsym; if sym ident then error(35) else getsym until symcomma; if symrparen then error(33);end递归下降子程序递归下降子程序program function_listfunction_list function function_list | function FUNC i

6、dentifier ( parameter_list ) statementvoid ParseFunction()MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();void MatchToken(int expected)if (lookahead != expected) printf(syntax error n);exit(0); else / if match, consume token and mo

7、ve onlookahead = yylex();例：递归子程序实现例：递归子程序实现 表达式的语法分析表达式的语法分析表达式的表达式的EBNF表达式表达式 =+|-项项+|-项项项项 =因子因子*|/因子因子因子因子 =ident|number|表达式表达式zprocedure expr;procedure expr;beginbegin if sym in plus, minus then if sym in plus, minus then begin begin getsym; term; getsym; term; end endelse term;else term; while

8、sym in plus, minus do while sym in plus, minus do begin begin getsym; term; getsym; term; end endend;end; Procedure term;Procedure term; begin factor; begin factor; while sym in times,slash do while sym in times,slash do begin getsym;factor end begin getsym;factor endend;end; Procedure factor;Proced

9、ure factor; begin if sym=ident begin if sym=ident then getsym then getsym else else if sym=number if sym=number then getsym then getsym else else if sym= if sym=( ( then begin then begin getsym; getsym; expr; expr; if sym= if sym=) ) then getsym then getsym else error else error end end else error e

10、lse error end; end; 表驱动予测分析程序模型 Input Input #总控程序总控程序预测分析表预测分析表stack 带带 a0 a1 a2 a3 a4 a5 a6 a7 a8 an-1 an 有限控制器有限控制器磁头磁头识别程序的数学模型下推自动机上下文无关言语句型分析识别程序的数学模型下推自动机下推自动机Pda=(K,f,H,h0,S,Z)Pda=(K,f,H,h0,S,Z) H: H:下推栈符号的有穷字母表下推栈符号的有穷字母表 h0 :H h0 :H中的初始符号中的初始符号 f: K f: K ) ) H K H K H H* * PdaPda的一个组态是的一个组态

11、是K K * * H H 中的一个中的一个k,w,k,w,) k:) k:当前当前形状，形状，w:w:余留输入串，余留输入串， ：栈中符号，最左边的符号在栈：栈中符号，最左边的符号在栈顶。顶。PdaPda的一次挪动用组态表示的一次挪动用组态表示终止和接受的条件终止和接受的条件: : 1. 1.到达输入串结尾时，处在到达输入串结尾时，处在Z Z中的一个形状中的一个形状或或 2. 2.某个动作序列导致栈空时某个动作序列导致栈空时 例：例：Pda P=(A,B,C),a,b,c),f,h,i,iPda P=(A,B,C),a,b,c),f,h,i,i A, ) A, )f(A,a,i) = (B,h

12、) f(B,a,h) = (B,hh)f(A,a,i) = (B,h) f(B,a,h) = (B,hh) f(C,b,h) = (C, f(C,b,h) = (C, ) f(A,c,i) = (A, ) f(A,c,i) = (A, ) ) f(B,c,h) = (C,h) f(B,c,h) = (C,h) 接受输入串接受输入串aacbbaacbb的过程的过程(A,aacbb,i) (A,aacbb,i) 读读a, pop i, push h, goto Ba, pop i, push h, goto B (B,acbb,h) (B,acbb,h) 读读a, pop h, push hh,

13、goto B a, pop h, push hh, goto B (B,cbb,hh) (B,cbb,hh) 读读c, pop h, push h , goto Cc, pop h, push h , goto C (C,bb,hh) (C,bb,hh) 读读b, pop h, push b, pop h, push , goto C , goto C (C,b,h) (C,b,h) 读读b ,pop h, push b ,pop h, push , goto C , goto C (C, (C, , , ) ) G E: (1) E TE (2) E +TE (3) E (4) T FT (

14、5) T *FT (6) T (7) F (E) (8) F a a + * ( ) # 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 a分析算法分析算法 z BEGINBEGINz 首先把首先把# #然后把文法开场符号推入栈；把第一个输入符然后把文法开场符号推入栈；把第一个输入符号读进号读进b; FLAGb; FLAG：=TRUE=TRUE；z WHILE FLAG DOWHI

15、LE FLAG DO BEGIN BEGINz 把栈顶符号上托出去并放在中；把栈顶符号上托出去并放在中；z IF X IF X Vt THEN IF X=b THEN Vt THEN IF X=b THENz 把下一个输入符号读进把下一个输入符号读进a az ELSE ERROR ELSE ERROR ELSE IF X= ELSE IF X=# # THEN THENz IF X=b THEN FLAG:=FALSE IF X=b THEN FLAG:=FALSEz ELSE ERROR ELSE ERRORz ELSE IF ELSE IF X,b=X X1X2.XKX,b=X X1X2.

16、XKz THEN THEN 把把XKXK，X K-1,.,X1X K-1,.,X1一一推进栈一一推进栈 z ELSE ELSEERRORERRORz END OF WHILE; END OF WHILE;z STOP/STOP/* *分析胜利，过程终了分析胜利，过程终了* *z ENDEND分析输入串#a+a#栈内容 栈顶符号 当前输入 余留串 MX,b 1 #E E a +a# E TE2 #ET T a +a# T FT3 #ETF F a +a# F a4 #ETa a a +a#5 # ET T + a# T 6 #E E + a# E +TE7 #ET+ + + a#8 # ET T

17、 a # T FT 9 #ETF F a # F a10 #ETa a a #11 #ET T # T 12 #E E # E 13 # # #FIRSTFIRST集和集和FOLLOWFOLLOW集的定义集的定义 设设G=(VT,VN,PG=(VT,VN,P，S)S)是上下文无关文法是上下文无关文法FIRSTFIRST=a|=a| = =* * a a,aVT, ,aVT, , , VV* * 假设假设 = =* * 那么规定那么规定FRISTFRISTFOLLOWFOLLOWA A=a=aS =S =* * A A 且且a FRISTa FRIST， V V* *， V+ V+ 假设假设S

18、=S =* * u A u A , ,且且 = =* * ，那么，那么#FOLLOW(A)#FOLLOW(A)LL (1) LL (1) 文法文法计算计算FIRSTFIRST集集1.1.假设假设X XV V, ,那么那么FIRST(X)=XFIRST(X)=X2.2.假设假设X XVN,VN,且有产生式且有产生式X Xaa，那么把，那么把a a参与参与到到FIRST(X)FIRST(X)中中; ;假设假设X X也是一条产生式也是一条产生式, ,那那么把么把也加到也加到FIRST(X)FIRST(X)中中. .3.3.假设假设X XYY是一个产生式且是一个产生式且Y YVN,VN,那么把那么把F

19、IRST(Y)FIRST(Y)中的一切非中的一切非元素都加到元素都加到FIRST(X)FIRST(X)中中; ;假设假设X X Y1Y2YK Y1Y2YK 是一个产生是一个产生式式,Y1,Y2,Y(i-1),Y1,Y2,Y(i-1)都是非终结符都是非终结符, ,而且而且, ,对对于任何于任何j,1j i-1, FIRST(Yj)j,1j i-1, FIRST(Yj)都含有都含有 ( (即即Y1.Y(i-1) =Y1.Y(i-1) =* * ), ),那么把那么把FIRST(Yj)FIRST(Yj)中的一切非中的一切非元素都加到元素都加到FIRST(X)FIRST(X)中中; ;特别是特别是,

20、,假设一切的假设一切的FIRST(Yj , j=1,2,K)FIRST(Yj , j=1,2,K)均含有均含有, ,那么把那么把加到加到FRIST(X)FRIST(X)中中. . 计算计算FOLLOWFOLLOW集集1.1.对于文法的开场符号对于文法的开场符号S,S,置置# #于于FOLLOW(S) FOLLOW(S) 中中; ;2.2.假设假设 B B 是一个产生式是一个产生式, ,那么把那么把 FIRST() FIRST() 加至加至FOLLOW(B)FOLLOW(B)中中; ;3.3.假设假设 B B是一个产生式是一个产生式, ,或或 B B是是 一个产生式而一个产生式而 = =* *

21、( (即即FIRST()FIRST()， 那么把那么把FOLLOWFOLLOWA A加至加至FOLLOWFOLLOWB B中中 一个文法一个文法G G是是LLLL1 1的，当且仅当对于的，当且仅当对于G G的每一个的每一个非终结符的任何两个不同产生式非终结符的任何两个不同产生式 ，下面的条件成立：下面的条件成立：FIRSTFIRSTFIRST()=FIRST()=, ,也就是也就是和和推导不出以同一个终结符推导不出以同一个终结符a a为首的符号串；它们为首的符号串；它们不应该都能推出空字不应该都能推出空字. .假假设假假设 = =* * ，那么，那么， FIRST FIRST)FOLLOW)F

22、OLLOWA A. . 也就是，也就是， 假设假设 = =* * . .那么那么所能推出的串的首符号不所能推出的串的首符号不应在应在FOLLOW(AFOLLOW(A中中G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F a各非终结符的FIRST集合如下：FIRST(E)=(,iFIRST(E)=+,FIRST(T)=(,iFIRST(T)=*,FIRST(F)=(,i各非终结符的FOLLOW集合为：FOLLOW(E)=),FOLLOW(E)=)，FOLLOW(T)=，)，FOLLOW(T)=,)，# FO

23、LLOW(F)=*,，),# G E: (1) E TE (2) E +TE (3) E (4) T FT (5) T *FT (6) T (7) F (E) (8) F aE +TE | FIRST(+TE)=+ FOLLOW(E)=)，T *FT | FIRST(*FT)=* FOLLOW(T)=+,)，F (E) | a FIRST( (E)=( FIRST( a)=a所以所以GE是是LL1的的予测分析表构造算法予测分析表构造算法1.1.对文法对文法G G的每个产生式的每个产生式 执行第二步执行第二步 和第三步；和第三步；2.2.对每个终结符对每个终结符a aFIRST(FIRST()

24、)，把，把 加加 至至A,aA,a中，中，3.3.假设假设 FIRST( FIRST() )，那么对任何，那么对任何b bFOLLOW(A) FOLLOW(A) 把把 加加至至A,bA,b中，中，4.4.把一切无定义的把一切无定义的A,aA,a标上标上“出错标志。出错标志。可以证明，一个文法可以证明，一个文法G G的予测分析表不含多重的予测分析表不含多重入口，当且仅当该文法是入口，当且仅当该文法是LL(1)LL(1)的的LL(1)LL(1)文法的性质：文法的性质： LL(1) LL(1)文法是无二义的文法是无二义的 LL(1) LL(1)文法不含左递归文法不含左递归非非LL(1)LL(1)文法

25、的改造文法的改造消除左递归消除左递归提左公因子提左公因子 将产生式将产生式 | 变换为：变换为： B B B B | |EE+TTTT*FFFi(E)FIRST(E)=(,iFIRST(T)=(,iFIRST(F)=(,i消左递归 E TE E +TE E S if C t S |S if C t S | if C t S e S if C t S e SC bC b提左因子提左因子 S if C t S A S if C t S A A e S | A e S | First First集集 Follow Follow集集S if #,eS if #,eA e, A e, #, #, e e

26、C b C b t tMA,e=A e S MA,e=A e S A A LL(1)分析中的一种错误处置方法发现错误发现错误1栈顶的终结符与当前输入符不匹配栈顶的终结符与当前输入符不匹配2非终结符非终结符A于栈顶，面临的输入符为于栈顶，面临的输入符为a，但分析表，但分析表M的的MA,a为为空空“应急恢复战略应急恢复战略跳过输入串中的一些符号直至遇到跳过输入串中的一些符号直至遇到“同步符号为止。同步符号为止。同步符号的选择同步符号的选择1把把FOLLOW(A)中的一切符号作为中的一切符号作为A的同步符号。跳过输入串中的同步符号。跳过输入串中的一些符号直至遇到这些的一些符号直至遇到这些“同步符号，

27、把同步符号，把A从栈中弹出，可使从栈中弹出，可使分析继续分析继续2把把FIRST(A)中的符号加到中的符号加到A的同步符号集，当的同步符号集，当FIRST(A)中的中的符号在输入中出现时，可根据符号在输入中出现时，可根据A恢复分析恢复分析review-parsingThe syntax analysis phase of a compiler verifies that the sequence of tokens returned from the scanner represent valid sentences in the grammar of the programming lang

28、uage. There are two major parsing approaches: top-down and bottom-up. In top-down parsing, you start with the start symbol and apply the productions until you arrive at the desired string. In bottom-up parsing, you start with the string and reduce it to the start symbol by applying the productions b

29、ackwards. In the top-down parsing,we begin with the start symbol and at each step, expand one of the remaining nonterminals by replacing it with the right side of one its productions.We repeat until only terminals remain. The top-down parse prints a leftmost derivation of the sentence.A bottom-up pa

30、rse works in reverse. We begin with the sentence of terminals and each step applies a production in reverse, replacing a substring that matches the right side with the nonterminal on the left. We continue until we have substituted our way back to the start symbol. If you read from the bottom to top,

31、 the bottom-up parse prints out a rightmost derivation of the sentence. lookahead symbol The lookahead symbol is the next symbol coming up in the input. backtracking. Based on the information the parser currently has about the input, a decision is made to go with one particular production. If this c

32、hoice leads to a dead end, the parser would have to backtrack to that decision point, moving backwards through the input, and start again making a different choice and so on until it either found the production that was the appropriate one or ran out of choices.predictive parser and LL(1)grammarPred

33、ictive parser is a non-backtracking top-down parser. A predictive parser is characterized by its ability to choose the production to apply solely on the basis of the next input symbol and the current nonterminal being processed. To enable this, the grammar must take a particular form. We call such a

34、 grammar LL(1). The first “L means we scan the input from left to right; the second “L means we create a leftmost derivation; and the 1 means one input symbol of lookahead.recursive-descentThe first technique for implementing a predictive parser is called recursive-descent. A recursive descent parse

35、r consists of several small functions(procedures), one for each nonterminal in the grammar. As we parse a sentence, we call the functions (procedures) that correspond to the left side nonterminal of the productions we are applying. If these productions are recursive, we end up calling the functions

36、recursively.Table-driven LL(1) parsing In a recursive-descent parser, the production information is embedded in the individual parse functions for each nonterminal and the run-time execution stack is keeping track of our progress through the parse. There is another method for implementing a predicti

37、ve parser that uses a table to store that production along with an explicit stack to keep track of where we are in the parse. How a table-driven predictive parser works We push the start symbol on the stack and read the first input token. As the parser works through the input, there are the followin

38、g possibilities for the top stack symbol X and the input token nonterminal a:1. If X = a and a = end of input (#): parser halts and parse completed successfully2. If X = a and a != #: successful match, pop X and advance to next input token. This is called a match action.3. If X != a and X is a nonte

39、rminal, pop X and consult table at X,a to see which production applies, push right side of production on stack. This is called a predict action.4. If none of the preceding cases applies or the table entry from step 3 is blank, there has been a parse errorThe first set of a sequence of symbols u, wri

40、tten as First(u ) is the set of terminals whichstart all the sequences of symbols derivable from u. A bit more formally, consider allstrings derivable from u by a leftmost derivation. If u =* v , where v begins with someterminal, that terminal is in First(u). If u =* , then is in First(u ).The follo

41、w set of a nonterminal A is the set of terminal symbols that can appear immediately to the right of A in a valid sentence. A bit more formally, for every valid sentence S =*uAv , where v begins with some terminal, that terminal is in Follow(A).Computing first To calculate First(u) where u has the form X1X2.Xn, do the following:1. If X1 is a terminal, then add X1 to First(u), otherwise add First(X1) - to First(u ) .2. If X1 is a nullable nonterminal, i.e., X1 =* , add First(X2) - to First(u). Furthermore, if X2 can also go to , then add First(X3) - and so on, through all Xn until the f