CFGs for Syntax Definition and Language Design

CS 536 CFGs for Syntax Definition

Announcements Hw 2 due Thursday Proj 2 underway Screencast posted Who s seen it? Who likes it? Gone Thursday New office hours posted

Roadmap Last time CFG basics This time CFGs for syntax design Language membership List grammars Resolving ambiguity

CFG Review G = (N, ,P,S) Example: Nested parens N = { Q } = { (, )} P = Q ( Q ) | S = Q means derives or more steps CFG generates a string by applying productions until no non-terminals remain +means derives in 1

Formal CFG Language Definition Let G= (N, ,P,S) be a CFG. Then +? where L(G) = ? ? S is the start nonterminal of G w is a sequence of terminals or ?

CFGs as Language Definition CFG productions define the syntax of a language 1. Prog beginStmtsend 2. Stmts Stmtssemicolon Stmt 3. | Stmt 4. Stmt idassignExpr 5. Expr id 6. | Exprplusid We call this notation BNF or enhanced BNF HTML Grammar using BNF http://bioinfo2.ugr.es/OReillyReferenceLibrary/web/html/appa_02.html

List Grammars Useful to repeat a structure arbitrarily often Stmts Stmtssemicolon Stmt | Stmt Stmts Stmts ; Stmt Stmts ; Stmt List skews left Stmts Stmts ; Stmt Stmts Stmts ; Stmt

List Grammars Useful to repeat a structure arbitrarily often Stmts Stmtsemicolon Stmts | Stmt Stmts Stmts ; Stmt List skews right Stmt ; Stmts Stmts Stmt ; Stmts Stmts Stmt ; Stmts

List Grammars What if we allowed both skews ? Stmts Stmtssemicolon Stmts | Stmt Stmts ; Stmts Stmts Stmts ; Stmts Stmts ; Stmts Stmts ; Stmts Stmt

Derivation Order Leftmost Derivation: always expand the leftmost nonterminal Rightmost Derivation: always expand the rightmost nonterminal Prog 1. Prog beginStmtsend begin Stmts end 2. Stmts Stmtssemicolon Stmt 3. | Stmt Stmts semicolon Stmt 4. Stmt idassignExpr 5. Expr id 6. | Exprplusid Rightmost expands this nonterminal Leftmost expands this nonterminal

Ambiguity Even with a fixed derivation order, it is possible to derive the same string in multiple ways For Grammar G and string w G is ambiguous if >1 leftmost derivation of w >1 rightmost derivation of w > 1 parse tree for w

Example: Ambiguous Grammars Expr intlit Derive the string 4 - 7 * 3 | Exprminus Expr (assume tokenization) | ExprtimesExpr | lparenExpr rparen Parse Tree 1 Parse Tree 2 Expr Expr Expr times Expr Expr minus Expr Expr minus Expr intlit intlit Expr times Expr 4 3 intlit intlit 7 intlit intlit 7 3 4

Why is Ambiguity Bad? Eventually, we ll be using CFGs as the basis for our parser Parsing is much easier when there is no ambiguity in the grammar The parse tree may mismatch user understanding! Operator precedence 4 - 7 * 3 Expr Expr Expr times Expr Expr minus Expr Expr minus Expr intlit intlit Expr times Expr 4 3 intlit intlit 7 intlit intlit 7 3 4

Resolving Grammar Ambiguity: Precedence Intuitive problem Context-freeness Nonterminals are the same for both operators To fix precedence 1 nonterminal per precedence level Parse lowest level first Expr intlit | Exprminus Expr | ExprtimesExpr | lparenExpr rparen

Resolving Grammar Ambiguity: Precedence lowest precedence level first 1 nonterm per precedence level Expr intlit | Exprminus Expr Derive the string 4 - 7 * 3 | ExprtimesExpr | lparenExpr rparen Expr Expr minus Expr Term Expr Expr minus Expr Term | Term Term times Term Factor Term TermtimesTerm intlit Factor Factor | Factor 4 Factor intlit intlit intlit | lparenExpr rparen 7 3

Resolving Grammar Ambiguity: Precedence Fixed Grammar Expr expr minus expr Derive the string 4 - 7 * 3 | Term Let s try to re-build the wrong parse tree Term TermtimesTerm | Factor Expr Factor intlit Term | lparenExpr rparen Term times Term Expr Factor Expr minus Expr intlit 3 Term Term We ll never be able to derive minus without parens Term times Term Factor Factor Factor intlit 4 intlit 7 intlit 3

Did we fix all ambiguity? Derive the string 4 - 7 - 3 Fixed Grammar Expr Expr minus Expr Expr | Term Term TermtimesTerm Expr minus Expr | Factor Expr minus Expr Term Factor intlit Term Factor Term | lparenExpr rparen Factor Factor intlit intlit intlit NO! These subtrees could have been swapped!

Where we are so far Precedence We want correct behavior on 4 7 * 9 A new nonterminal for each precedence level Associativity We want correct behavior on 4 7 9 Minus should be left associative: a b c = (a b) c Problem: the recursion in a rule like Expr Expr minus Expr

Definition: Recursion in Grammars A grammar is recursive in (nonterminal) X if + ? for non-empty strings of symbols and A grammar is left-recursive in X if +? for non-empty string of symbols A grammar is right-recursive in X if + ? for non-empty string of symbols ? ? ?

Resolving Grammar Ambiguity: Associativity We ll recognize left-associative operators with left-associative productions We ll recognize right-associative operators with right-associative productions Example: 4 7 9 Term E Expr Expr minus Expr E - T | Term Factor T F - E Term TermtimesTerm F T intlit | Factor 9 F intlit Factor intlit | lparenExpr rparen 7 intlit 4

Resolving Grammar Ambiguity: Associativity Expr Expr minus Term Example: 4 7 9 | Term Let s try to re-build the wrong parse tree again Term TermtimesFactor | Factor Factor intlit | lparenExpr rparen E E - T T F We ll never be able to derive minus without parens intlit 4