Attribute evaluation (9-18 and 9-20, 2012) Reminders: T2 due now A2 due Wesnesday 9-26, 11:59pm ======================================== Static Analysis Recall that static semantics are enforced at compile time, and dynamic semantics are enforced at run time. Some things have to be dynamic semantics because of LATE BINDING (discussed in Chap. 3): we lack the necessary info (e.g. input values) at compile time, or inferring what we want is uncomputable. A smart compiler may avoid run-time checks when it *is* able to verify compliance at compile time. This makes programs run faster. array bounds variant record tags dangling references Similarly, a conservative code improver will apply optimizations only when it knows they are safe alias analysis caching in registers computation out of order or in parallel escape analysis limited extent non-synchronized subtype analysis static dispatch of virtual methods An optimistic compiler may generate multiple versions with a dynamic check to dispatch always use the "optimized" version if it's speculative -- always safe and usually fast prefetching trace scheduling Alternatively, language designer may tighten rules type checking in ML v. Lisp (cons: 'a x 'a list -> 'a list) definite assignment in Java/C# v. C ---------------------------------------- As noted in Chap. 1, job of semantic analyzer is to (1) enforce rules (2) connect the syntax of the program (as discovered by the parser) to something else that has semantics (meaning) -- e.g. value for constant expressions code for subroutines Often, though not always, the meaning is captured in the form of an annotated (or "decorated") abstract syntax tree (AST) -- basically a tree with extra information attached its nodes. (Inside the compiler, tree nodes are typically little objects, and the notes are data members [fields].) In the next assignment, you'll be doing part of the job of the semantic analyzer -- specifically, building an AST. This is a straightforward job in most languages. In general, you have every RD routine return a pointer to the AST for its construct. There are sometimes some wrinkles, though -- e.g. term_tail and factor_tail in the current assignment. How do we get the right children on + - * / nodes? Cleanest, most general solution is to pass left argument to term_tail and factor_tail: AST_node expr(): case input_token of id, literal, ( : T := term() return term_tail(T) else error AST_node term_tail(T1): case input_token of +, - : O := add_op() T2 := term() N := new node(O, T1, T2) return term_tail(N) | ), id, read, write, $$ : return T1 // epsilon else error Are there always solutions like this? Can we always build a syntax tree while parsing? Or are there languages in which we must sometimes build a parse tree and then traverse it in some crazy order? How do we tell? It turns out we can formalize these questions using a framework called ATTRIBUTE GRAMMARS. These aren't actually used much in production compilers, but they clarify the discussion. AGs work on trees -- like parse trees or syntax trees. They assume that some nodes start out with interesting annotations: e.g., textual values of tokens for identifiers, strings, and numbers; built-in names and other "environmental" information in a table attached to the root (program) node. The AG then says how the annotations on other nodes depend on those of their children and/or parents. In a well-formed grammar, if you apply all the rules, you can decorate the entire tree. If you can decorate the entire tree in one pass while parsing (that's a big "if"), then the AG can be written in the form of ACTION ROUTINES -- code fragments embedded in the RHSs of productions, with references to the "attributes" of the symbols in the current production. In this case you can actually get away with not building the parse tree explicitly -- you just deal with the local neighborhood while parsing. In principle, you can do all semantic analysis by decorating the parse tree (maybe while parsing; more likely in a separate pass [which would require that you actually build the parse tree]). It's typically a lot easier, though, to write an AG for the parse tree that serves only to build an AST -- to tag the root with a pointer to an AST. Construction of the AST can almost always be done with ARs (during parsing), allowing us to skip actual construction of a parse tree. Then we can use another AG to decorate the AST. We'll consider decoration of parse trees first, then consider syntax trees. ----------------- Book presents an LR AG for evaluation of constant arithmetic expressions, with precedence and associativity. It annotates the root of the parse tree with the value of the overall expression. Here's a variant that labels the root with a pointer to a syntax tree: E => E + T E1.n = new bin_op(+, E2.n, T.n) E => E - T E1.n = new bin_op(-, E2.n, T.n) E => T E.n = T.n T => T * F T1.n = new bin_op(*, T2.n, F.n) T => T / F T1.n = new bin_op(/, T2.n, F.n) T => F T.n = F.n F => - F F1.n = new un_op(-, F2.n) F => (E) F.n = E.n F => const F.n = new num(const.val) F => id F.n = new ident(id.name) << show how this handles, for example, (a + 1) * b >> That's bottom up. All attributes are "synthesized" -- they depend only on things below them in the tree. Here's a top-down version. Uses n again, but also st, which is "inherited" -- doesn't depend only on things below. E => T TT E.n = TT.n TT.st = T.n TT => + T TT TT1.n = TT2.n TT2.st = new bin_op(+, TT1.st, T.n) TT => - T TT TT1.n = TT2.n TT2.st = new bin_op(-, TT1.st, T.n) TT => TT.n = TT.st T => F FT T.n = FT.n FT.st = F.n FT => * F FT FT1.n = FT2.n FT2.st = new bin_op(*, FT1.st, F.n) FT => / F FT FT1.n = FT2.n FT2.st = new bin_op(/, FT1.st, F.n) FT => FT.n = FT.st F => - F F1.n = new un_op(-, F2.n) F => ( E ) F.n = E.n F => const F.n = new num(const.val) F => id F.n = new ident(id.name) << show how this handles, for example, (a + 1) * b >> | Here's another example. It's possible to prove that strings of the form | a^n b^n c^n are not CF. Let's check them with an AG: | | G -> As Bs Cs | As -> a As | -> | Bs -> b Bs | -> | Cs -> c Cs | -> | | This grammar accepts a^i b^j c^k. We can insist that i == j == k: | | G -> As Bs Cs G.ok = (As.count == Bs.count == Cs.count) | As -> a As As1.count = As2.count + 1 | -> As1.count = 0 | Bs -> b Bs Bs1.count = Bs2.count + 1 | -> Bs1.count = 0 | Cs -> c Cs Cs1.count = Cs2.count + 1 | -> Cs1.count = 0 | | All the attributes here are also synthesized. | | Similarly, the following accepts all binary strings with an embedded | binary point: | | G -> ds . ds | ds -> d more_ds | more_ds -> ds | -> | d -> 0 | -> 1 | | This says nothing about what the program MEANS. | We can attach meaning to the program with an AG: | | G -> ds . ds G.val = ds1.val + ds2.val * 2^(-ds2.len) | ds -> d more_ds ds.val = d.val * 2^more_ds.len + more_ds.val; | ds.len = more_ds.len + 1 | more_ds -> ds more_ds.val = ds.val | more_ds.len = ds.len | -> more_ds.val = 0 | more_ds.len = 0 | d -> 0 d.val = 0 | -> 1 d.val = 1 | | << show how this handles, for example, 10.01 >> | | When a parse tree under this grammar is fully decorated, the value of the | string will be in the 'val' attribute of the root. Attribute rules don't explicitly specify the order in which they should be evaluated. The process of evaluating attributes is called annotation, or DECORATION, of the parse tree. The code fragments for the rules are called SEMANTIC FUNCTIONS. [ Strictly speaking, they should be cast as functions, e.g. G.val = combine (ds1.val, ds2.val, ds2.len) ] An S-ATTRIBUTED grammar uses only synthesized attributes. Its ATTRIBUTE FLOW (attribute dependence graph) is purely bottom-up. Parse trees for an S-attributed AG can be evaluated during an LR parse. In an L-ATTRIBUTED grammar, each synthesized attribute of a LHS symbol (by definition of 'synthesized') depends only on attributes of its RHS symbols. Each inherited attribute of a RHS symbol (by definition of 'L-attributed') depends only on inherited attributes of the LHS symbol or on synthesized or inherited attributes of symbols to its left in the RHS. L-attributed grammars are interesting because they are the most general class that can be evaluated during an LL parse. They are a superset of S-attributed grannars. | One possible criticism of the binary number example above is that while it | computes the right value for the root of the tree, it doesn't compute | the value for each subtree in context. For that we need inherited | attributes, and a different base grammar, which you can find in my | lecture notes. | | G -> ids . fds fds.pos = -1 // fractional digits | G.val = ids.val + fds.val // simple add | ids -> d more_ids d.pos = more_ids.len | ids.len = more_ids.len + 1 | ids.val = d.val + more_ids.val // simple add | fds -> d more_fds d.pos = fds.pos | more_fds.pos = fds.pos - 1 | fds.val = d.val + more_fds.val // simple add | more_ids -> ids more_ids.len = ids.len | more_ids.val = ids.val | -> more_ids.len = 0 | more_ids.val = 0 | more_fds -> fds fds.pos = more_fds.pos | more_fds.val = fds.val | -> more_fds.val = 0 | d -> 0 d.val = 0 | -> 1 d.val = 2^d.pos | | << show how this handles, for example, 10.01 >> | | This attribute grammar is a good bit messier than the first one. | Moreover it isn't even L-attributed (d.pos comes from the right), which | means that you need a separate attribute evaluation traversal of the | parse tree. | | There are certain other tasks, such as generation of code for | short-circuit Boolean expression evaluation (more on this later), that | are also easiest to express with non-L-attributed attribute grammars. | Because of the potential cost of complex traversal schemes, however, | most real-world compilers insist that the grammar be L-attributed. ------------- We can tie this discussion back into the earlier issue of separated phases v. on-the-fly semantic analysis and/or code generation. If semantic analysis and/or code generation are interleaved with parsing, then the TRANSLATION SCHEME we use to evaluate attributes MUST be L-attributed. If we break semantic analysis and code generation out into separate phase(s), then the code that builds the parse/syntax tree must still use a left-to-right (L-attributed) translation scheme, but the later phases are free to use a fancier translation scheme if they want. There are automatic tools that generate translation schemes for context-free grammars or tree grammars (which describe the possible structure of a syntax tree). These tools are sometimes used in syntax-based editors and incremental compilers. Most ordinary compilers, however, use ad-hoc techniques. An ad-hoc translation scheme that is interleaved with parsing takes the form of a set of ACTION ROUTINES. An action routine is a semantic function that we tell the compiler to execute at a particular point in the parse. If semantic analysis and code generation are interleaved with parsing, then action routines can be used to perform semantic checks and generate code. If semantic analysis and code generation are broken out as separate phases, then action routines can be used to build a syntax tree. (A parse tree could be built completely automatically; we wouldn't need action routines for that purpose.) Later compilation phases can then consist of ad-hoc tree traversal(s), or (more rarely) can use an automatic tool to generate a translation scheme. ------------- It's easy to turn the AGs above into action routine versions for bottom-up & top-down parsing. Bottom-up is trivial: E => E + T { E1.n = new bin_op(+, E2.n, T.n) } E => E - T { E1.n = new bin_op(-, E2.n, T.n) } E => T { E.n = T.n } T => T * F { T1.n = new bin_op(*, T2.n, F.n) } T => T / F { T1.n = new bin_op(/, T2.n, F.n) } T => F { T.n = F.n } F => - F { F1.n = new un_op(-, F2.n) } F => (E) { F.n = E.n } F => const { F.n = new num(const.val) } F => id { F.n = new ident(id.name) } Top-down is only slightly harder: E => T { TT.st := T.n } TT { E.n := TT.n } TT => + T { TT2.st := new bin_op(+, TT1.st, T.n) } TT { TT1.n := TT2.n } TT => - T { TT2.st := new bin_op(-, TT1.st, T.n) } TT { TT1.n := TT2.n } TT => { TT.n := TT.st } T => F { FT.st := F.n } FT { T.n := FT.n } FT => * F { FT2.st := new bin_op(*, FT1.st, F.n) } FT { FT1.n := FT2.n } FT => / F { FT2.st := new bin_op(/, FT1.st, F.n) } FT { FT1.n := FT2.n } FT => { FT.n := FT.st } F => - F { F1.n := new un_op(-, F2.n) } F => ( E ) { F.n := E.n } F => const { F.n := new num(const.val) } F => id { F.n := new ident(is.name) } ---------------------------------------- Space management is trivial if you build an explcit parse tree: attributes are fields of the structs that constitute tree nodes. Without an explicit parse tree bottom-up is trivial -- embed in parser stack recursive descent is almost trivial -- local variables of RD routines table-driven top-down is a little tricky, but can be automated -- see book ===================================================================== Attribute grammars for syntax trees. Need a "tree grammar". Example: Bottom-up CFG for calculator language with types and declarations: program -> stmt_list $$ stmt_list -> stmt_list decl | stmt_list stmt | epsilon decl -> int id | real id stmt -> id := expr | read id | write expr expr -> term | expr add_op term term -> factor | term mult_op factor factor -> ( expr ) | id | int_const | real_const | float ( expr ) | trunc ( expr ) add_op -> + | - mult_op -> * | / Simple program: int a read a real b read b write (float (a) + b) / 2.0 Fragment of tree grammar needed to handle above program: program -> item int_decl : item -> id item read : item -> id item real_decl : item -> id item write : item -> expr item null : item -> \nothing `/' : expr -> expr expr `+' : expr -> expr expr float : expr -> expr id : expr -> epsilon real_const : expr -> epsilon The A:B syntax on the left means that A is one kind of a B, and may appear wherever a B is expected on a RHS. Note that "program -> item" does NOT mean that a program "is" an item (the way it does in a CFG), but merely that a program node in a syntax tree has one child, which is an item. Tree grammars differ from CFGs. Language for a CFG is the possible *fringes* of parse trees. Language for a tree grammar is the possible *whole trees*. No comparable notion of parsing: structure of tree is self-evident. BUT: semantic rules on tree grammar productions can drive decoration in exactly the same way that they do for parse trees. Example in the book of rules to do type checking for the above. program errors (synthesized) - list of all static semantic errors (type clash, undefined/redefined names) item, expr symtab (inherited) - list with types of all names declared to left item errors_in (inherited) - list of all static semantic errors to left errors_out (synthesized) - list of all SSEs through here expr type (synthesized) errors (synthesized) - list of all SSEs inside everything location (synthesized) A few rules: program -> item item.symtab := nil item.errors_in := nil program.errors := item.errors_out int_decl : item -> id item -- item2 is rest of program if in int_decl.symtab item2.errors_in := item1.errors_in + ["redefinition of" id.name "at" item1.location] item2.symtab := item1.symtab - + else item2.errors_in := item1.errors_in item2.symtab := item1.symtab + item1.errors_out := item2.errors_out id : expr -> epsilon if in expr.symtab expr.errors := nil expr.type := A else expr.errors := [id.name "undefined at" id.location] expr.type := error + : expr -> expr expr expr2.symtab := expr1.symtab expr3.symtab := expr1.symtab if expr2.type = error or expr3.type = error expr1.type := error expr1.errors := expr2.errors + expr3.errors else if expr2.type <> expr3.type expr1.type := error expr1.errors := expr2.errors + expr3.errors + ["type clash at" expr1.location] else expr1.type := expr2.type expr1.errors := expr2.errors + expr3.errors General technique: When something goes wrong, remember to initialize all attributes that would normally have been initialized, but give them special values (such as "error" above) that will suppress cascading messages.