LL(1)Parser input buffer our string to be parsed.We will assume that its end is marked with a special symbol $ output a production rule representing a step of the derivation sequence(left-most derivation)of the string in the input buffer. stack contains the grammar symbols at the bottom of the stack,there is a special end marker symbol $ initially the stack contains only the symbol and the starting symbol S. $S←initial stack when the stack is emptied(ie.only left in the stack),the parsing is completed. parsing table a two-dimensional array M[A,a] each row is a non-terminal symbol each column is a terminal symbol or the special symbol -each entry holds a production rule. CS308 Compiler Theory 11
LL(1) Parser input buffer – our string to be parsed We will assume that its end is marked with a special symbol $ our string to be parsed. We will assume that its end is marked with a special symbol $. output – a production rule representing a step of the derivation sequence (left-most derivation) of the string in the input buffer. stack – contains the grammar symbols contains the grammar symbols – at the bottom of the stack, there is a special end marker symbol $. – initially the stack contains only the symbol $ and the starting symbol S. $S Í initial stack – when the stack is emp ( y ), p g p tied (ie. only $ left in the stack), the parsing is completed. parsing table – a two-dimensional array M[A,a] – each i rows a non-termi l bl na symbol – each column is a terminal symbol or the special symbol $ – each entry holds a production rule. CS308 Compiler Theory 11
LL(1)Parser-Parser Actions The symbol at the top of the stack(say X)and the current symbol in the input string (say a)determine the parser action. There are four possible parser actions. 1.If X and a are $parser halts(successful completion) 2.If X and a are the same terminal symbol(different from $ >parser pops X from the stack,and moves the next symbol in the input buffer. 3.IfX is a non-terminal >parser looks at the parsing table entry M[X,a].If M[X,a]holds a production rule X->Y Y2...Yk,it pops X from the stack and pushes YkYk-1,...,Y into the stack.The parser also outputs the production rule X->Y Y2...Yk to represent a step of the derivation. 4.none of the aboveerror all empty entries in the parsing table are errors. -If x is a terminal symbol different from a,this is also an error case. CS308 Compiler Theory 2
LL(1) Parser – Parser Actions • The symbol at the top of the stack (say X) and the current symbol in the input string (say a) determine the parser action (say a) determine the parser action. • There are four possible parser actions. 1. If X and a are $ Î p ( p) arser halts (successful com pletion ) 2. If X and a are the same terminal symbol (different from $) Î parser pops X from the stack, and moves the next symbol in the input buffer. 3. If X is a non-terminal Î parser looks at the parsing table entry M[X,a]. If M[X,a] holds a production rule X → Y1Y 2... Y k, i Xf h k d h Y it pops X from t he stac k an d pus hes Y k,Yk-1,..., Y1 i h k Th into t he stac k. The parser also outputs the production rule X → Y1Y 2...Y k to represent a step of the derivation. 4. none of the above Î error – all empty entries in the parsing table are errors. – If X is a terminal symbol different from a, this is also an error case. CS308 Compiler Theory 12 If X is a terminal symbol different from a, this is also an error case