(9.2)--Samuel's Ch4_2编译原理与实践英文版.ppt

《(9.2)--Samuel's Ch4_2编译原理与实践英文版.ppt》由会员分享，可在线阅读，更多相关《(9.2)--Samuel's Ch4_2编译原理与实践英文版.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 4 Top-Down ParsingLL(1)ParsingCompilerS2Introduction oNo longer often usedoSimple scheme with explicit stackoPrelude for more powerful and complex bottom-up algorithmsoFirst“L”the input is processed from left to rightoSecond“L”leftmost derivationo1 one lookahead symbolLL(1)ParsingCompilerS3B

2、asic Method1.Push the start symbol onto the stack.2.Generate:Replace a nonterminal on the top of the stack by one of the choices in the grammar rule for that nonterminal.The replacement string from the BNF must be pushed in reverse onto the stack.3.Match:Match a token on the top of the stack with th

3、e next input token(throw both away).4.Repeat steps 2 and 3.Accept if the stack and the input become empty.CompilerS4Top-Down ParsingoExample:Grammar:S (S)S|String:()accept$6S$S5Match )$S)4S )$S)S3Match()$S)S(2S (S)S()$S1ActionInput Parsing stackS (S)S S CompilerS5Parse Tree ConstructionoAs the parse

4、 proceeds,we can add node construction actions as each nonterminal or terminal is pushed onto the stack.oThe root node is constructed at the beginning of the parse.(1)S=(S)S S (S)S(2)=()S S o=()S Leftmost derivationTop-down parsingCompilerS6Problems with Recursive-Descent1.It may be difficult to con

5、vert a grammar into EBNF.2.It may be difficult to distinguish two or more grammar rule options A|,if both and begin with nonterminals.(First set)3.A .It may be necessary to know what token can come after the nonterminal A.(Follow set)CompilerS7Which Rule to Use?oWhen a nonterminal A is at the top of

6、 the parsing stack,a decision must be made based on the current input token(the lookahead).oChoices are expressed by LL(1)parsing table.nThis is a two dimensional array MN,T indexed by nonterminals N and terminals T($is added to terminals).CompilerS8Rules1.If A is production choice,and there is a de

7、rivation =*a,where a is a token,then add A to the table entry MA,a.Given a token a in the input,we select a rule A if can produce an a for matching.2.If A is production choice,and there is a derivations =*and S$=*A a,where S is the start symbol and a is a token(or$),then add A to the table entry MA,

8、a.If A derives an empty string,and if a is a token that can come after A,then we want to select A to make A disappear.CompilerS9ExampleoS (S)S|oThere is one nonterminal S,three tokens(,)and$,and two production choices.oEvery string derivable from S must be either empty or begin with(.oS (S)S is adde

9、d to MS,(oS is added to MS,)and MS,$S S S (S)SS$)(MN,T1.A ,=*a 2.A ,=*,S$=*A a CompilerS10ExampleoExample:Grammar:S (S)S|String:()accept$6S$S5Match )$S)4S )$S)S3Match()$S)S(2S(S)S()$S1ActionInput Parsing stackMN,T()$SS (S)SS S CompilerS11LL(1)GrammaroA grammar is LL(1)grammar if the associated LL(1)

10、parsing table has at most one production rule in each table entry.oAn LL(1)grammar cannot be ambiguous.CompilerS12ExampleoS (S)S|oThere is one nonterminal S,three tokens(,)and$,and two production choices.oEvery string derivable from S must be either empty or begin with(.oS (S)S is added to MS,(oS is

11、 added to MS,)and MS,$S S S (S)SS$)(MN,T1.A ,=*a 2.A ,=*,S$=*A a CompilerS13Problems with Recursive-Descent1.It may be difficult to convert a grammar into EBNF.2.It may be difficult to distinguish two or more grammar rule options A|,if both and begin with nonterminals.(First set)3.A .It may be neces

12、sary to know what token can come after the nonterminal A.(Follow set)CompilerS14First Sets Let X be a grammar symbol(terminal or nonterminal)or.Then the set First(X)consisting of terminals and,is defined as follows.1.If X is terminal or,then First(X)=X.2.If X is nonterminal,then for each production

13、choice XX1 X2 Xn,oFirst(X)contains First(X1).oIf also for some i *.oTheorem:A nonterminal is nullable if and only if First(A)contains.CompilerS17Example 4.9exp exp addop term|termaddop +|-term term mulop factor|factormulop *factor (exp)|number(1)exp exp addop term(2)exp term(3)addop +(4)addop -(5)te

14、rm term mulop factor(6)term factor(7)mulop *(8)factor (exp)(9)factor numberRewrite each choice separately.Note,there is no -productions.CompilerS18Example 4.9(cont)(1)exp exp addop term(2)exp term(3)addop +(4)addop -(5)term term mulop factor(6)term factor(7)mulop *(8)factor (exp)(9)factor numberFirs

15、t(exp)=First(addop)=First(term)=First(mulop)=First(factor)=+,-*（,number（,number（,numberCompilerS19Example 4.10statement if-stmt|otherif-stmt if(exp)statement else-partelse-part else statement|exp 0|1(1)statement if-stmt(2)statement other(3)if-stmt if(exp)statement else-part(4)else-part else statemen

16、t(5)else-part (6)exp 0(7)exp 1CompilerS20Example 4.10(cont)(1)statement if-stmt(2)statement other(3)if-stmt if(exp)statement else-part(4)else-part else statement(5)else-part (6)exp 0(7)exp 1First(statement)=First(if-stmt)=First(else-part)=First(exp)=otherifelse,0,1if,CompilerS21Example 4.11stmt-sequ

17、ence stmt stmt-seqstmt-seq ;stmt-sequence|stmt s(1)stmt-sequence stmt stmt-seq(2)stmt-seq ;stmt-sequence(3)stmt-seq (4)stmt sCompilerS22Example 4.11(1)stmt-sequence stmt stmt-seq(2)stmt-seq ;stmt-sequence(3)stmt-seq (4)stmt sFirst(stmt-sequence)=First(stmt-seq)=First(stmt)=;,ssCompilerS23Problems wi

18、th Recursive-Descent1.It may be difficult to convert a grammar into EBNF.2.It may be difficult to distinguish two or more grammar rule options A|,if both and begin with nonterminals.(First set)3.A .It may be necessary to know what token can come after the nonterminal A.(Follow set)CompilerS24Follow

19、Sets Given a nonterminal A,the set Follow(A),consisting of terminals and$,is defined as follows.1.If A is the start symbol,then$is in Follow(A).2.If there is a production B A,then First()is in Follow(A).3.If there is a production B A such that is in the First(),then Follow(A)contains Follow(B).oIf B

20、 A,Follow(A)contains Follow(B)CompilerS25Example 4.9exp exp addop term|termaddop +|-term term mulop factor|factormulop *factor (exp)|number(1)exp exp addop term(2)exp term(3)addop +(4)addop -(5)term term mulop factor(6)term factor(7)mulop *(8)factor (exp)(9)factor numberRewrite each choice separatel

21、y.Note,there is no -productions.CompilerS26Example 4.12First(exp)=(,numberFirst(addop)=+,-First(term)=(,numberFirst(mulop)=*First(factor)=(,number(1)exp exp addop term(2)exp term(3)addop +(4)addop -(5)term term mulop factor(6)term factor(7)mulop *(8)factor (exp)(9)factor numberFollow(exp)=Follow(add

22、op)=Follow(term)=Follow(factor)=Follow(mulop)=,+,-(,number$,+,-,*(,number$,+,-,*,),),)CompilerS27Example 4.10statement if-stmt|otherif-stmt if(exp)statement else-partelse-part else statement|exp 0|1(1)statement if-stmt(2)statement other(3)if-stmt if(exp)statement else-part(4)else-part else statement

23、(5)else-part (6)exp 0(7)exp 1CompilerS28Example 4.13Follow(statement)=Follow(if-stmt)=Follow(else-part)=Follow(exp)=(1)statement if-stmt(2)statement other(3)if-stmt if(exp)statement else-part(4)else-part else statement(5)else-part (6)exp 0(7)exp 1First(statement)=if,otherFirst(if-stmt)=if First(else

24、-part)=else,First(exp)=0,1$),else$,else,elseCompilerS29Example 4.11stmt-sequence stmt stmt-seqstmt-seq ;stmt-sequence|stmt s(1)stmt-sequence stmt stmt-seq(2)stmt-seq ;stmt-sequence(3)stmt-seq (4)stmt sCompilerS30Example 4.14(1)stmt-sequence stmt stmt-seq(2)stmt-seq ;stmt-sequence(3)stmt-seq (4)stmt

25、sFirst(stmt-sequence)=s First(stmt-seq)=;,First(stmt)=s Follow(stmt-sequence)=Follow(stmt-seq)=Follow(stmt)=$;$,$CompilerS31Constructing LL(1)Parsing Tables1.If A is production choice,and there is a derivation =*a,where a is a token,then add A to the table entry MA,a.Given a token a in the input,we

26、select a rule A-if can produce an a for matching.The token a is in First()2.If A is production choice,and there is a derivations =*and S$=*A a,where S is the start symbol and a is a token(or$),then add A to the table entry MA,a.If A derives an empty string,and if a is a token that can come after A,t

27、hen we want to select A-to make A disappear.The token a is in Follow(A)CompilerS32LL(1)Parsing Table Algorithm Repeat the following two steps for each nonterminal a and production choice A .1.For each token a in First(),add A to the entry MA,a.2.If is in First(),for each element a of Follow(A),add A to MA,a.CompilerS33ExampleoS (S)S|oFirst(S)=oFollow(S)=oS (S)S is added to MS,(oS is added to MS,)and MS,$S S S (S)SS$)(MN,T(,$,)S (S)S S