编译原理编译原理编译原理 (35).ppt

CompilerS1Top-Down ParsingoExample:Grammar:S (S)S|String:()accept$6S$S5Match )$S)4S )$S)S3Match()$S)S(2S (S)S()$S1ActionInput Parsing stackCompilerS2Which Rule to Use?oWhen a nonterminal A is at the top of 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).S S S (S)SS$)(MN,TCompilerS3Rules1.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 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,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.CompilerS4ExampleoS (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 added to MS,)and MS,$S S S (S)SS$)(MN,T1.A ,=*a 2.A ,=*,S$=*A a CompilerS5ExampleoExample: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 。