4.2.2 The ll(1 Parsing Table and Algorithm
4.2.2 The LL(1) Parsing Table and Algorithm
Purpose and Example ofll(1) Table Purpose of the ll(1) Parsing Table: To express the possible rule choices for a non-terminala when the a is at the top of parsing stack based on the current input token(the look-ahead). The ll(1) Parsing table for the following simple gl rammar S→(S)S|ε MIN,TI( S→(S)S →)8 s→e
Purpose and Example of LL(1) Table • Purpose of the LL(1) Parsing Table: – To express the possible rule choicesfor a non-terminal A when the A is at the top of parsing stack based on the current input token (the look-ahead). • The LL(1) Parsing table for the following simple grammar: S→(S) S∣ε M[N,T] ( ) $ S S→(S) S S→ε S→ε
The general definition of table The table is a two-dimensional array indexed by non-terminals and terminals Containing production choices to use at the appropriate parsing step called min,t nis the set of non-terminals of the grammar T is the set of terminals or tokens (including s) Any entrances remaining empty Representing potential errors
The General Definition of Table • The table is a two-dimensional array indexed by non-terminals and terminals • Containing production choices to use at the appropriate parsing step called M[N,T] • N is the set of non-terminals of the grammar • T is the set of terminals or tokens (including $) • Any entrances remaining empty • Representing potential errors
Table- Constructing rule The table-constructing rule If aais a production choice, and there is a derivation a=>*aB, where a is a token, then add A→→ ato the table entry M[Aa]; If aais a production choice, and there are derivations a=>* cand S$=> BAay, where S is the start symbol and a is a token(or $) then add a-ato the table entry M[A, al
Table-Constructing Rule • The table-constructing rule – If A→αis a production choice, and there is a derivation α=>*aβ, where a is a token, then add A→αto the table entry M[A,a]; – If A→αis a production choice, and there are derivations α=>*εand S$=>*βAaγ, where S is the start symbol and a is a token (or $), then add A→αto the table entry M[A,a];
A Table-Constructing Case The constructing-process of the following table For the production: SS)S, a=(s), where a=( this choice will be added to the entry ms,a; Since: S=>(S)SE, rule 2 applied witha E, B=GA=S,a ),andy=Ss, so add the choice s→εtoMs,) Since ss→>SS,S→ is also added to ms,S IN,TI( S→(S)S
A Table-Constructing Case • The constructing-process of the following table – For the production : S→(S) S, α=(S)S, where a=(, this choice will be added to the entry M[S, (] ; – Since: S=>(S)Sε，rule 2 applied withα= ε, β=(,A = S, a = ), and γ=S$,so add the choice S→εto M[S, )] – Since S$=>* S$, S→εis also added to M[S, $]. M[N,T] ( ) $ S S→(S) S S→ε S→ε