1Semantic AnalysisAmer DiwanScanning+Parsing versus semantic analysis• In the syntax section we looked at how to recognize syntactically correct programs• But you need to do more than that!– Check types– Pick overloaded operators– Resolve scopes– Generate code– ...2Type checking example• char *p1, *p2; int i; ...; p1 = p2 + i;expr -> expr op term | termterm -> identifier | numberexprexpr op(+) termidentifier(i)termidentifier(p2)assignidentifier(p1) =char*char*char*intintchar*char*Type checking example (2)• int p1; char *p2; int i; ...; p1 = p2 + i;expr -> expr op term | termterm -> identifier | numberexprexpr op(+) termidentifier(i)termidentifier(p2)assignidentifier(p1) =char*char*char*intintchar*intERROR!int:= char *3Type checking example 3• char *p1, *p2; int i;...; p1 = p2 + i;expr -> term expr’expr’ -> op term expr’ | epsilonterm -> identifier | numberexprassignidentifier(p1) =term expr’op(+) term expr’identifier(i) epsilonintidentifier(p2)char*char*intchar*intchar*Overload resolution example• float f; int i; ...; p1 = p2 + i;expr -> expr op term | termterm -> identifier | numberexprexpr op(+) termidentifier(i)termidentifier(f)floatfloatfloatintintint addition orfloat addition?float additionfloat4Building ASTE-> E1 + T| E1 - T | TT -> T1 * F| FF -> (E)| id| constE.nptr := mknode(‘+’, E1.nptr, T.nptr)E.nptr := mknode(‘-’, E1.nptr, T.nptr)E.nptr := T.nptrT.nptr := mknode(‘*’, T1.nptr, F.nptr)T.nptr := F.nptr;F.nptr := E.nptrF.nptr := mkleaf(id, symtab entry of id)F.nptr := mkleaf(const, value of const)Example continued (4 + 5*6)E1 -> E2 + T1E2 -> T2T2 -> F1 -> const(4)T1 -> T3 * F2F2 -> const(6)T3 -> F3 -> const(5)F2.nptr = 6 T3.nptr= F3.nptr=5T1.nptr= *E2.nptr= T2.nptr= F1.nptr= 4E1=+5Type checking with the ASTchar *p1, *p2; int i; ...; p1 = p2 + i;program -> stmtassign: stmt -> id expr stmt‘+’: expr -> node node‘-’: expr -> node nodeid: expr -> epsilonnum: expr -> epsilonprogramassignid(p1) +id(p2) id(i)ØTypechecking with the AST (cont)programassignid(p1) +id(p2) id(i)Øchar*char*intchar*6Static versus dynamic semantics• Static semantics– Enforced at compile time– Examples in previous slides are that of static semantics• Dynamic semantics– Enforced at run timeExample of dynamic semantics• Array bounds check– for (i = 0; i < 100; ++i) {A[i] = 0;}– In safe languages this translates into– for (i = 0; i < 100; ++i) {if (i in [A’first..A’last]) then A[i] = 0;else error;}The check happens as the program is running!7An aside on dynamic semantics• Compilers try hard to minimize effort to enforce dynamic semantics at run time:– if [0..100) in [A’first..A’last] {for (i = 0; i < 100; ++i) {A[i] = 0;}else {for (i = 0; i < 100; ++i) {if (i in [A’first..A’last]) A[i]=0;else error;}}How to do semantic analysis• Use attribute grammars– A formal system– Can generate code to propagate attributes automatically• Ad-hoc: action routines– Sprinkle pieces of code that are executed when a terminal/non-terminal is matched– More operational than attribute grammars8Attribute grammars• Productions + propagation of attributes– ‘+’: expr1-> expr2expr3op := selectOp(‘+’, expr2.ty, expr3.ty)expr1.ty := op.ty– selectOp: operator x type x type -> type– “ty” is an attribute that the above propagates Attribute grammars: type of rules• Copy– F -> (E)F.val := E.val• Invoke semantic functions– ‘+’: expr1-> expr2expr3op := selectOp(‘+’, expr2.ty, expr3.ty)expr1.ty:= op.tyselectOp: operator x type x type -> type– Semantic functions: primitives specified by the language designer9When to compute the attributes?• ‘+’: expr1-> expr2expr3expr1.ty := op.tyop := selectOp(‘+’, expr2.ty, expr3.ty)• The attribute grammar processor figures out the order in which to compute attributes:– e.g., op.ty before expr1.tyAttribute grammars:Use them on abstract syntax or concrete syntax?• Concrete syntax has many details that are irrelevant to semantics:– e.g., F -> (E) useful for parsing with the correct precedence but otherwise useless...• Abstract syntax– eliminates all the “useless” syntactic details– attribute grammar can be more concise!• Book incorrectly emphasizes AG on concrete syntax10Using action routines• An ad-hoc alternative to attribute grammars– Interleave code (action routines) with parsing– Often used to build AST during a parse• E -> T { EE.arg := T.ptr} EE {E.ptr := EE.ptr}• EE1-> + T { EE2.arg := make_plus(EE1.arg, T.ptr)} EE2{ EE1.ptr := EE2.ptr; }| epsilon { EE1.ptr := EE1.arg; }• T -> (E) { T.ptr := E.ptr; }| number { T.ptr := make_leaf(number.val); }Example• E -> T { EE.arg := T.ptr} EE {E.ptr := EE.ptr}• EE1-> + T { EE2.arg := make_plus(EE1.arg, T.ptr)} EE2{ EE1.ptr := EE2.ptr; }| epsilon { EE1.ptr := EE1.arg; }• T -> (E) { T.ptr := E.ptr; }| number { T.ptr := make_leaf(number.val); }Note that programmer has to specify order of evaluation11Relationship to reading• Reading gives additional/longer examples of both attribute grammars and action routines– Helpful for project 1 and 2• Discusses the differences between different kinds of attribute grammars in more detailRelationship to other classes• CSCI 4555– You will get experience with action routines when you use a parser generator– You will get to use attribute grammars for a compiler generator!12Next topic: Control flow• Read chapter 6 (except 6.5.3 and 6.7)Example building an abstract syntax tree• E1 -> E2 + T [E1.ptr := make_bin_op(“+”, E2.ptr, T.ptr)]E -> T [ E.ptr := T.ptr]T1 -> T2 * F [ T1.ptr := make_bin_op(“*”, T2.ptr, F.ptr)]T -> F [ T.ptr := F.ptr ]F -> (E) [ F.ptr := E.ptr ]F -> const [ F.ptr := make_leaf(const.val)