Shift-Reduce Parsers There are two main categories of shift-reduce parsers 1.Operator-Precedence Parser simple,but only a small class of grammars. CFG LR LALR 2.LR-Parsers SLR covers wide range of grammars. ·SLR-simple LR parser LR-most general LR parser LALR-intermediate LR parser(lookhead LR parser) SLR,LR and LALR work same,only their parsing tables are different. CS308 Compiler Theory
Shift-Reduce Parsers • There are two main categories of shift-reduce parsers 1. Operator-Precedence Parser – simple, but only a small class of grammars. CFG LR 2. LR-Parsers SLR LALR – covers wide range of grammars. • SLR – simple LR parser • LR – most general LR parse r • LALR – intermediate LR parser (lookhead LR parser) SLR LR and LALR work same only their parsing tables are different CS308 Compiler Theory 11 – SLR, LR and LALR work same, only their parsing tables are different
LR Parsers The most powerful shift-reduce parsing (yet efficient)is: LR(k)parsing left to right right-most k lookhead scanning derivation (k is omitted→it is 1) LR parsing is attractive because: -LR parsing is most general non-backtracking shift-reduce parsing,yet it is still efficient. The class of grammars that can be parsed using LR methods is a proper superset of the class of grammars that can be parsed with predictive parsers. LL(1)-Grammars C LR(1)-Grammars -An LR-parser can detect a syntactic error as soon as it is possible to do so a left-to-right scan of the input. CS308 Compiler Theory 12
LR Parsers • Th f l hif he most powerful shift-red i ( ffi i ) i duce parsing (yet efficient) is: LR(k) parsing. left to right right-most k lookhead scanning derivation (k is omitted Î it is 1) • LR parsing is attractive because: – LR parsing is most general non-backtracking shift-reduce parsing, yet it is still efficient. – The class of grammars that can be parsed using LR methods is a proper superset of the class of g p pp rammars that can be parsed with predictive parsers. LL(1)-Grammars ⊂ LR(1)-Grammars – An LR-parser can detect a syntactic error as soon as it is possible to do so a left-to-right scan of the input CS308 Compiler Theory 12 scan of the input
LR Parsers ·LR-Parsers covers wide range of grammars. SLR-simple LR parser LR-most general LR parser -LALR-intermediate LR parser (look-head LR parser) - SLR,LR and LALR work same (they used the same algorithm). only their parsing tables are different. CS308 Compiler Theory 13
LR Parsers • LR-Parsers – covers wide range of grammars. – SLR – simple LR parser – LR – most general LR parser – LALR – intermediate LR parser (look-head LR parser) – SLR, LR and LALR work same (they used the same algorithm), only their parsing tables are different. CS308 Compiler Theory 13
LR Parsing Algorithm input a a 3 $ stack Xm LR Parsing Algorithm +output Sm-1 Xm-l Action Table Goto Table Si terminals and non-terminal X t four different t each item is S a actions a a state number t t e e CS308 Compiler Theory 14
LR Parsing Algorithm a1 ... ai ... a inpu t n $ S m 1 i n stack pu X m Sm-1 LR Parsing Algorithm output Xm-1 . . S1 X Action Table terminals and $ s Goto Table non-terminal X s 1 S 0 s t four different a actions t s t each item is a a state number t CS308 Compiler Theory 14 e s e s
A Configuration of LR Parsing Algorithm A configuration of a LR parsing is: (SoX,S1…XmSm,aa+1…an$) Stack Rest of Input Sm and a;decides the parser action by consulting the parsing action table.(Initial Stack contains just S) A configuration of a LR parsing represents the right sentential form: X1...Xm ai aiti...an S CS308 Compiler Theory 5
A Configuration of LR Parsing Algorithm • A configuration of a LR parsing is: ( S o X1 S1 ... X m S m, ai ai+1 ... a n $ ) Stack Rest of Input • S m and ai decides the parser action by consulting the parsing action table. (Initial Stack contains just S o table. (Initial Stack contains just S ) o ) • A configuration of a LR parsing represents the right sentential form: A configuration of a LR parsing represents the right sentential form: X1 ... X m ai ai+1 ... a n $ CS308 Compiler Theory 15