18-07-2012, 10:08 AM
CPSC 388 – Compiler Design and Construction
Compiler Design and Construction.ppt (Size: 149 KB / Downloads: 211)
Parsing using CFGs
Algorithms can parse using CFGs in O(n3) time (n is the number of characters in input stream) – TOO SLOW
Subclasses of grammars can be parsed in O(n) time
LL(1)
1 token of look ahead
Do a left most derivation
Scan input from left to right
LALR(1)
one token of look-ahead
do a rightmost derivation in reverse
scan the input left-to-right
LA means "look-ahead“(nothing to do with the number of tokens)
LALR(1)
More general than LL(1) grammars
(Every LL(1) grammar is a LALR(1) grammar but not vice versa)
Class of grammars used by java_cup, Bison, YACC
Parsed bottom up
(start with non-terminals and build tree from leaves up to root)
Covered in text section 4.6-4.7
For class need to understand details of just LL(1) grammars
Building Parse Tables
Recall a parse table
Every row is a non-terminal
Every column is an input token
Every cell contains a production body
If any cell contains more than one production body then grammar is not LL(1)
To build parse table need to have FIRST set and FOLLOW set