COS 320 Compilers David Walker The Front End stream of characters stream of tokens Lexer abstract syntax Parser Type Checker Lexical Analysis Create sequence of tokens from characters Chap 2 Syntax Analysis Create abstract syntax tree from sequence of tokens Chap 3 Type Checking Check program for wellformedness constraints Parsing with CFGs Context free grammars are often given by BNF expressions Backus Naur Form Appel Chap 3 1 More powerful than regular expressions Matching parens Nested comments wait we could do nested comments with ML LEX CFGs are good for describing the overall syntactic structure of programs Context Free Grammars Context free grammars consist of Set of symbols terminals that denotes token types non terminals that denotes a set of strings Start symbol Rules symbol symbol symbol symbol left hand side non terminal right hand side terminals and or non terminals rules explain how to rewrite non terminals beginning with start symbol into terminals Context Free Grammars A string is in the language of the CFG if only if it is possible to derive that string using the following non deterministic procedure 1 begin with the start symbol 2 while any non terminals exist pick a non terminal and rewrite it using a rule 3 stop when all you have left are terminals and check you arrived at the string your were hoping to Parsing is the process of checking that a string is in the CFG for your programming language It is usually coupled with creating an abstract syntax tree non terminals S E Elist terminals ID NUM PRINT rules S S S S ID E S PRINT Elist E ID E NUM E E E E S Elist Elist E Elist Elist E non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist 8 Elist E 9 Elist Elist E Derive me ID NUM PRINT NUM non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S ID E ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S ID E oops can t make progress ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S S S ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S S S ID E S ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist 4 5 6 7 E ID E NUM E E E E S Elist S S S ID E S ID NUM S ID NUM PRINT Elist ID NUM PRINT E ID NUM PRINT NUM 8 Elist E 9 Elist Elist E Derive me non terminals S E Elist terminals ID NUM PRINT rules 1 S S S 2 S ID E 3 S PRINT Elist S S S ID E S ID NUM S ID NUM PRINT Elist ID NUM PRINT E ID NUM PRINT NUM left most derivation 4 5 6 7 E ID E NUM E E E E S Elist 8 Elist E 9 Elist Elist E S S S S PRINT Elist S PRINT E S PRINT NUM ID E PRINT NUM ID NUM PRINT NUM right most derivation Another way to derive the same string Parse Trees Representing derivations as trees useful in compilers Parse trees correspond quite closely but not exactly with abstract syntax trees we re trying to generate difference abstract syntax vs concrete parse syntax each internal node is labeled with a non terminal each leaf note is labeled with a terminal each use of a rule in a derivation explains how to generate children in the parse tree from the parents Parse Trees Example S S S ID E S ID NUM S ID NUM PRINT Elist ID NUM PRINT E ID NUM PRINT NUM S S ID E NUM S PRINT L E NUM Parse Trees Example 2 derivations but 1 tree S S S ID E S ID NUM S ID NUM PRINT Elist ID NUM PRINT E ID NUM PRINT NUM S S S S PRINT Elist S PRINT E S PRINT NUM ID E PRINT NUM ID NUM PRINT NUM S S ID E NUM S PRINT L E NUM Parse Trees parse trees have meaning order of children nesting of subtrees is significant S S S ID E NUM S S PRINT L PRINT S L E E NUM NUM ID E NUM Ambiguous Grammars a grammar is ambiguous if the same sequence of tokens can give rise to two or more parse trees Ambiguous Grammars characters 4 5 6 tokens NUM 4 PLUS NUM 5 MULT NUM 6 E non terminals E terminals ID NUM PLUS MULT E ID NUM E E E E I like using this notation where I avoid repeating E E E E NUM 4 NUM 5 E NUM 6 Ambiguous Grammars characters 4 5 6 tokens NUM 4 PLUS NUM 5 MULT NUM 6 E non terminals E E terminals ID NUM PLUS MULT E E NUM 4 E NUM 6 NUM 5 E E ID NUM E E E E E E NUM 4 E E NUM 6 NUM 5 Ambiguous Grammars problem compilers use parse trees to interpret the meaning of parsed expressions different parse trees have different meanings eg 4 5 6 is not 4 5 6 languages with ambiguous grammars are DISASTROUS The meaning of programs isn t well defined You can t tell what your program might do solution rewrite grammar to eliminate ambiguity fold precedence rules into grammar to disambiguate fold …