1Concrete and Abstract SyntaxProf. Evan ChangMeeting 4, CSCI 3155, Fall 2009Announcements• Assignment 1 due tonight at 11:55pm– Find a partner• Assignment 2 out tonight– Start early!– PL-Detective User ID sent out by e-mail. Problems?2ReviewLanguages and Grammars• A language is a set of strings over some alphabet (=sentences)• A context-free grammar (=BNF) is a notation for describing languages• A derivation exhibits a sentence in a language• We typically consider an alphabet of tokens rather than of characters4Languages and Grammars• A language is a set of strings over some alphabet (=sentences)• A context-free grammar (=BNF) is a notation for describing languages• A derivation exhibits a sentence in a language• We typically consider an alphabet of tokens rather than of characters5Grammars and Derivations• Formally, a grammar consists of– an alphabet Σ of terminals– a finite set Nof non-terminals– a finite set of productions n ::= s where n ∈ N and s ∈ (Σ∪ N)*• Example:e ::= num | e + e | e * e• Derivation for 1 + 2 + 3?62End of ReviewOn to Concrete and Abstract SyntaxOne-Slide Summary• Concrete syntax is the surface level of a language (think, strings)• Abstract syntax is the deep structure of a language (think, trees/terms)• Parsers convert concrete syntax into abstract syntax and have to deal with ambiguity• Precedence and associativity are some ways to deal with ambiguity8Ambiguity• What does 1 + 2 * 3 evaluate to (i.e., what is the semantics of 1 + 2 * 3)?9e ::= num | e + e | e * ee ::= num | e + e | e * eAmbiguity• The same string can be read in two different ways!• “Need parentheses with ambiguous grammars”10e ::= num | e + e | e * ee ::= num | e + e | e * eDerivations and Parse Trees• Let’s write a derivation and a parse tree for 1 + 2 * 311e ::= num | e + e | e * ee ::= num | e + e | e * eDerivations and Parse Trees• Is there another one?12e ::= num | e + e | e * ee ::= num | e + e | e * e3Derivations and Parse Treesunambiguous grammar=every string has a unique parse tree13e ::= num | e + e | e * ee ::= num | e + e | e * eExample• Is the above grammar ambiguous?14e ::= num | e -ee ::= num | e - eAssociativity• Try rewriting the grammar to get “left associativity”15e ::= num | e -ee ::= num | e - eAssociativity• Try rewriting the grammar to get “right associativity”16e ::= num | e -ee ::= num | e - eAnother Example• Is the above grammar ambiguous?17e ::= num | num + e | num * ee ::= num | num + e | num * eAnother Example• Is it what we want (intuitively for evaluation)?18e ::= num | num + e | num * ee ::= num | num + e | num * e4Another Example19e ::= num | num + e | num * ee ::= num | num + e | num * eAnother Example20e ::= num | num + e | num * ee ::= num | num + e | num * eBetter Idea:Concrete Syntax vs. Abstract Syntax• Use trees directly!• Separate readability concerns (concrete) from structural ones (abstract)• Concrete syntax = strings• Abstract syntax = terms (~parse trees)21Abstract Syntax• e ::= num | plus(e,e) | times(e,e)• We can see the structure immediately• What do the two versions of “1 + 2 * 3” become?22AbstractSyntax Trees• What’s the “parse tree” for ‘plus(1,times(2,3))’?23e ::= num | (e,e) | (e,e)e ::= num | plus(e,e) | times(e,e)Parser• Converts a string into a tree• Maps concrete syntax into abstract syntax• Does syntactic analysis once and for all245Are unambiguous grammars better?• Comparee ::= num | e + e | e * ee ::= t | t + et ::= num | num * t25Are unambiguous grammars better?• Comparee ::= num | e + e | e * ee ::= t | t + et ::= num | num * t26Often write ambiguous grammars Often write ambiguous grammars and view them as abstract syntaxFor Next Time• Reading• Online discussion forum– ≥1 substantive question, comment, or answer each week• Homework assignment 2– Start