Properties of ll(1) grammar Definition of ll(1) Grammar a grammar is an ll(1)grammar if the associated ll(1) parsing table has at most on production in each table entry An llodgrammar cannot be ambiguous
Properties of LL(1) Grammar • Definition of LL(1) Grammar – A grammar is an LL(1) grammar if the associated LL(1) parsing table has at most on production in each table entry • An LL(1) grammar cannot be ambiguous
a Parsing algorithm Using the LL(I Parsing Table c assumes S marks the bottom of the stack and the end of the input * push the start symbol onto the top the parsing stack while the top of the parsing stack s and the next input token fs do if the top of the parsing stack is terminal a and the next input token = a then match") pop the parsing stack; advance the input;
A Parsing Algorithm Using the LL(1) Parsing Table (* assumes $ marks the bottom of the stack and the end of the input *) push the start symbol onto the top the parsing stack; while the top of the parsing stack ≠ $ and the next input token ≠ $ do if the top of the parsing stack is terminal a and the next input token = a then (* match *) pop the parsing stack; advance the input;
A Parsing algorithm Using the LL(I Parsing Table else if the top of the parsing stack is non-terminalaA and the next input token is terminal a and parsing table entry M/A, a/ contains production A- XIX2Xn then generate x pop the parsing stack for i: =n downto 1 do push Xi onto the parsing stack; ese error if the top ofthe parsing stack= S and the next input token= s then accept else error
A Parsing Algorithm Using the LL(1) Parsing Table else if the top of the parsing stack is non-terminal A and the next input token is terminal a and parsing table entry M[A,a] contains production A→ X1X2…Xn then (* generate *) pop the parsing stack; for i:=n downto 1 do push Xi onto the parsing stack; else error; if the top of the parsing stack = $ and the next input token = $ then accept else error
Example: If-Statements The ll() parsing table for simplified grammar of if-statements: Statement→→if- stmt other If-stmt ->if(exp) statement else-part Else-part→ else statement|ε Exp→0|1
Example: If-Statements • The LL(1) parsing table for simplified grammar of if-statements: Statement → if-stmt | other If-stmt → if (exp) statement else-part Else-part → else statement | ε Exp → 0 | 1
MIN, T]If Other Else 0 Statement Statement Statement if- stmt other If-stmt If-stmt→ if(exp) stateme t else art Else-part Else-part Else pa state ment Else-pa art Xp Exp→|Exp 0
M[N,T] If Other Else 0 1 $ Statement Statement → ifstmt Statement → other If-stmt If-stmt → if (exp) stateme nt elsepart Else-part Else-part → else state ment Else-part →ε Elsepart →ε Exp Exp → 0 Exp → 1