CS453 Intro and PA1 1CS453 Lecture Predictive Parsing 1Plan for Today Recursive descent or predictive parsing– example predictive parser– FIRST and FOLLOW sets revisited– constructing a predictive parser table Syntax-directed translationCS453 Lecture Predictive Parsing 2Example Predictive Parser void S() { switch(tok) { case NUM: Mesh(); eat(EOF); break; default: error(); }} void Mesh() { switch(tok) { case NUM: num_nodes = NUM.val; eat(NUM); NodeList(); num_elem = NUM.val; eat(NUM); break; default: error(); }} void NodeList() { switch(tok) { case NUM: break; case NODE: Node(); NodeList(); break; default: error(); }}S -> Mesh EOFMesh -> num NodeList num ElemListNodeList -> ϵ | Node NodeListNode -> node num real real // node_id, x, yElemList -> ϵ | Elem ElemListElem -> tri num num num num // elem_id, 3 node idsElem -> sqr num num num num num // elem_id, 4 node idsCS453 Lecture Predictive Parsing 3FIRST and FOLLOW sets nullable(X)– X is a nonterminal– nullable(X) is true if X can derive the empty string FIRST– FIRST(z) = {z}, where z is a terminal– FIRST(X) = U FIRST( rhsi ), where X is a nonterminal and X -> rhsi– union all of FIRST(sym) on rhs up to and including firstnonnullable FOLLOW(Y), only relevant when Y is a nonterminal– look for Y in rhs of rules (lhs -> rhs) and union all FIRST sets forsymbols after Y up to and including first nonnullable– if all symbols after Y are nullable then also union in FOLLOW(lhs)CS453 Lecture Predictive Parsing 4Constructing the Predictive Parser Table Algorithmfor each X -> gammafor each T in FIRST(gamma)table[X,T] = X->gammaif gamma is nullablefor each T in FOLLOW(X)table[X,T] = X->gammaS -> Mesh EOFMesh -> num NodeList num ElemListNodeList -> ϵ | Node NodeListNode -> node num real real // node_id, x, yElemList -> ϵ | Elem ElemListElem -> tri num num num num // elem id, 3 node idsElem -> sqr num num num num num // elemid, 4 node idsCS453 Intro and PA1 2CS453 Lecture Predictive Parsing 5Syntax-directed translation One-pass versus multi-pass compiler– What do we need for MiniJava? In a predictive, or top-down, parser– do actions in functions for nonterminals– example: storing off the number of nodes and elements in the meshgrammar parser In a shift-reduce, or bottom-up, parser– each reduction leads to an action being performed– example: SableCC builds a parse tree using actions associated with eachgrammar rule– syntax-directed translation is equivalent to performing an action oninternal nodes in the parse tree during an in post-order traversal– example: interpreter you wrote for
View Full Document
Unlocking...