Recursive Predictive Parsing Each non-terminal corresponds to a procedure. Ex:A→aBb (This is only the production rule for A) proc A match the current token with a,and move to the next token; -call‘B'; match the current token with b,and move to the next token; CS308 Compiler Theory 6
Recursive Predictive Parsing • Each non-terminal corresponds to a procedure. Ex: A → aBb (This is only the production rule for A) proc A { - match the current token with a and move to the next token; match the current token with a, and move to the next token; - call ‘B’; - match the current token with b and move to the next token; match the current token with b, and move to the next token; } CS308 Compiler Theory 6
Recursive Predictive Parsing (cont.) A→aBb|bAB proc A{ case of the current token a':-match the current token with a,and move to the next token; -call‘B'; match the current token with b,and move to the next token; b':-match the current token with b,and move to the next token; -call‘A; call B': CS308 Compiler Theory 7
Recursive Predictive Parsing (cont.) A → aBb | bAB proc A { case of th t t k { f the curren t t o ken { ‘a’: - match the current token with a, and move to the next token; - call ‘B ;’ - match the current token with b, and move to the next token; ‘b :’ - match the current token with b and move to the next token; match the current token with b, and move to the next token; - call ‘A’; - call ‘B’ ; } } CS308 Compiler Theory 7
Recursive Predictive Parsing (cont.) When to apply s-productions. A->aA bB 8 If all other productions fail,we should apply an 8-production.For example,if the current token is not a or b,we may apply the 8-production. Most correct choice:We should apply an 8-production for a non- terminal A when the current token is in the follow set of A (which terminals can follow A in the sentential forms). CS308 Compiler Theory 8
Recursive Predictive Parsing (cont.) • When to apply ε-productions. A → aA | bB | ε • If all other productions fail, we should apply an ε-production. For example, if the current token is not a or b, we may apply the ε-production. • M h i W h ld l Most correct c h o ice: We s hould app ly an ε - prodif uct ion for a nonterminal A when the current token is in the follow set of A (which terminals can follow A in the sentential forms) terminals can follow A in the sentential forms). CS308 Compiler Theory 8
Recursive Predictive Parsing (Example) A->aBe cBd C B→bB|8 C→f proc C{match the current token with f, proc A{ and move to the next token;} case of the current token a:-match the current token with a, and move to the next token; proc B call B; case of the current token{ match the current token with e, b:-match the current token with b, and move to the next token; and move to the next token; c:-match the current token with c, call B and move to the next token; e,d:do nothing call B; match the current token with d, and move to the next token; follow set of B f:-call C first set of C CS30 Compiler Theory 9
Recursive Predictive Parsing (Example) A → aBe | cBd | C B → bB | ε C → f proc C { match the current token with f, proc A { and h k} move to t he next to ken; } case of the current token { a: - match the current token with a, and move to the next token; and move to the next token; proc B { proc B { - call B; case of the current token { - match the current token with e, b: - match the current token with b, and move to the next token; and move to the next token; and move to the next token; and move to the next token; c: - match the current token with c, - call B and move to the next token; e,d: do nothing - call B; } - match the current token with d, } and move to the next token; f: - call C follow set of B CS308 Compiler Theory 9 } } first set of C
Non-Recursive Predictive Parsing--LL(1)Parser Non-Recursive predictive parsing is a table-driven parser. It is a top-down parser. It is also known as LL(1)Parser. input buffer stack←→Non-recursiveoutput Predictive Parser Parsing Table CS308 Compiler Theory 10
Non-Recursive Predictive Parsing -- LL(1) Parser • Non-Recursive predictive parsing is a table-driven parser. • It is a top-down parser. • It is also known as LL(1) Parser. input buffer stack Non-recursive output Predictive Parser Parsin g Table CS308 Compiler Theory 10