Attribute evaluation (9-27 and 10-2, 2007) Reminders: A2 due Monday 10-1, 11:59pm Scheme assignment will be on the web on Tuesday. It has trivia due on 10-4, and a main due date of Monday 10-15. Midterm exam will be Thursday 10-18, in class Keep checking the web for reading assignments Feedback on A1: will restore points for prime-is-not-itself-a-partition undocumented size limitations are not acceptable nobody seems to have really done iterators no sets needed! ======================= Following parsing, the next two phases of the "typical" compiler are semantic analysis and (intermediate) code generation. We'll talk about code generation briefly later. The principal job of the semantic analyzer is to enforce static semantic rules. It also commonly constructs a syntax tree (usually first), and much of the information it gathers is needed by the code generator. There is considerable variety in the extent to which parsing, semantic analysis, and intermediate code generation are interleaved. A common approach interleaves construction of a syntax tree with parsing (eliminating the need to build an explicit parse tree), then follows with separate, sequential phases for semantic analysis and code generation. ----------------- 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. loop 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 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 ----------------- Both semantic analysis and (intermediate) code generation can be described in terms of annotation, or "decoration" of a parse or syntax tree. ATTRIBUTE GRAMMARS provide a formal framework for decorating such a tree. The notes below discuss attribute grammars and their ad-hoc cousins, ACTION ROUTINES. We'll start with decoration of parse trees, then consider syntax trees. ----------------- | Book presents an LR AG for evaluation of constant arithmetic | expressions, with precedence and associativity: | | E => E + T E1.val = E2.val + T.val | E => E - T E1.val = E2.val - T.val | E => T E.val = T.val | T => T * F T1.val = T2.val * F.val | T => T / F T1.val = T2.val / F.val | T => F T.val = F.val | F => - F F1.val = - F2.val | F => (E) F.val = E.val | F => const F.val = C.val | | << show how this handles, for example, (1 + 2) * 3 >> Here's another example. It 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 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 The attribute grammar serves to define the semantics of the input program. Attribute rules are best thought of as definitions, not assignments. They are not necessarily meant to be evaluated at any particular time, or in any particular order, though they do define their left-hand side in terms of the right-hand side. 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) ] When a parse tree under this grammar is fully decorated, the value of the string will be in the 'val' attribute of the root. << show how this handles, for example, 10.01 >> This is a fairly simple attribute grammar. Each symbol has at most two attributes (the period has no attributes). Moreover, these attributes are all so-called SYNTESIZED attributes -- they are calculated only from the attributes of things below them in the parse tree. In general, we are allowed both synthesized and INHERITED attributes. Inherited attributes may depend on things above or to the side of them in the parse tree. Tokens have only synthesized attributes, initialized by the scanner (name of an identifier, value of a constant, etc.). Inherited attributes of the start symbol constitute run-time parameters of the compiler. The grammar above is called S-ATTRIBUTED because it uses only synthesized attributes. Its ATTRIBUTE FLOW (attribute dependence graph) is purely bottom-up. | Book also presents an L-attributed LL AG for constant expressions. | | E => T TT E.v = TT.v | TT.st = T.v | TT => + T TT TT1.v = TT2.v | TT2.st = TT1.st + T.v | TT => - T TT TT1.v = TT2.v | TT2.st = TT1.st - T.v | TT => TT.v = TT.st | T => F FT T.v = FT.v | FT.st = F.v | FT => * F FT FT1.v = FT2.v | FT2.st = FT1.st * F.v | FT => / F FT FT1.v = FT2.v | FT2.st = FT1.st / F.v | FT => FT.v = FT.st | F => - F F1.v = - F2.v | F => ( E ) F.v = E.v | F => const F.v = C.v | | << show how this handles, for example, (1 + 2) * 3 >> | | Because its structure isn't left-associative, it can't be decorated | using an S-attributed AG. It's still L-ATTRIBUTED, which means that the | attributes can be evaluated in a single left-to-right pass over the | parse tree, which can if desired be interleaved with an LL 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 the most general class of attribute grammars that can be evaluated _during_ an LL parse. (They are _more_ general than what can be evaluated during an LR parse.) 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: 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, 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. ------------- Our second binary number example won't work with action routines. Here's a simple action routine example based on an LL(1) grammar for constant expressions. E => T { TT.st := T.v } TT { E.v := TT.v } TT => + T { TT2.st := TT1.st + T.v } TT { TT1.v := TT2.v } TT => - T { TT2.st := TT1.st - T.v } TT { TT1.v := TT2.v } TT => { TT.v := TT.st } T => F { FT.st := F.v } FT { T.v := FT.v } FT => * F { FT2.st := FT1.st * F.v } FT { FT1.v := FT2.v } FT => / F { FT2.st := FT1.st / F.v } FT { FT1.v := FT2.v } FT => { FT.v := FT.st } F => - F { F1.v := - F2.v } F => ( E ) { F.v := E.v } F => const { F.v := C.v } This is what most compilers do. ===================================================================== SPACE MANAGEMENT Any attribute evaluation method requires space for the attributes of the grammar symbols. We can follow the formalism closely, and associate storage with every symbol in the grammar (or at least every symbol that *has* attributes), or manage our storage in a more ad-hoc fashion. Consider first the more formal approach, for a context-free grammar (tree grammars will be discussed below). If we are building an explicit parse tree we can simply store attributes in the nodes of the tree themselves. If we are not building a parse tree, there still exist reasonable techniques for both top-down and bottom-up parsers to *automatically* allocate and deallocate space for the symbols we have seen but not yet finished with. The top-down approach is kind of messy, but only for whoever writes the driver for the parser, NOT for whoever writes the action routines. It keeps a stack that contains all the symbols in all the productions between the root of the (hypothetical) parse tree and the current point in the parse. All the RHS symbols of a given production are adjacent in the stack; the LHS is buried in the RHS of a deeper (closer to the root) production. The key ideas: parse stack used only by parser; contains future symbols augmented to also contain end-of-production markers and action routine numbers attribute stack used for semantic analysis; contains "current" symbols as stated above three pointers into attribute stack: lhs, rhs, and ntp (next to parse) when predict: push end-of-production marker on parse stack before RHS symbols save lhs and rhs pointers onto another stack push RHS symbols onto attribute stack update lhs := ntp ntp := rhs := new symbols on AS when see action routine number pop and call when match token: advance ntp at end of production pop everything from rhs up off the attribute stack ntp := lhs + 1 restore lhs and rhs -------- | Problem with the attribute-oriented approach with automatic space | management in top-down parsers: LOTS of (unnecessary) copy rules. | Even if we copy *pointers* to attributes (to save time) it's still a | nuissance to write all those action routines. | | Alternative: ad-hoc space management. For the above grammar, we have: | | E => T TT | TT => + T {add} TT | TT => - T {sub} TT | TT => | T => F FT | FT => * F {mul} FT | FT => / F {div} FT | FT => | F => - F {neg} | F => ( E ) | F => const {push const.val} | | This uses an LL SEMANTIC STACK. It's just a stack of SEMANTIC RECORDS | (a lot like the more formal attribute records) of our own design under | our own control. Note the lack of copy rules. Also note the explicit | management. Action routines have to take responsibility for pushing | and popping things at appropriate times. You need to be aware of what | is near the top of the stack. | | Suppose we are interested in expressions made out of *variables*, not | constants. It is straightforward (but messy) to write an attribute grammar | that accumulates into the root of the tree the code necessary to calculate | the expression. With explicit action routines (with either automatic or | ad-hoc management of storage) we know exactly what order things will happen | in, and we can spit the code out into a file: | | E => T TT | TT => + T {gen_op(+)} TT | TT => - T {gen_op(-)} TT | TT => | T => F FT | FT => * F {gen_op(*)} FT | FT => / F {gen_op(/)} FT | FT => | F => - F {reg := tos; gen(neg reg)} | F => ( E ) | F => id {find free register; gen(ld id,reg); push reg} | | where | gen_op(op) = func { | pop Lreg, Rreg | gen (op Lreg,Rreg) | push Lreg | make Rreg free | } | | Another example of the ad-hoc approach: you get easier handling of lists. | Consider variable declarations: | D => IL : T | IL => I ILT | ILT => , IL | ILT => | | The attribute grammar approach (with explicit action routines) goes | like this: | D => IL : T {declare_types (IL.chain, T)} | IL => I ILT {IL.chain = (I, ILT.chain)} | ILT => , IL {ILT.chain = IL.chain} | ILT => {ILT.chain = nil} | | The ad-hoc approach goes like this: | D => {push marker} IL : T {push T; declare_types()} | IL => I {push I} ILT | ILT => , IL | ILT => | | The choice between automatic and ad-hoc space management is again a matter | of taste. The PL/0 compiler uses automatic space management. If you look | at the 'grammar' file, you'll see that the code to build a syntax tree is | very simple. -------- | For bottom-up parsing we keep an attribute stack that mirrors the parse | stack; next to every state number on the parse stack is an attribute record | for the symbol we shifted when we entered that state. Evaluation of | S-attributed grammars is then easy. Evaluation of L-attributed grammars is | messy, though usually (but not always) possible. This messiness is | arguably the principal disadvantage of bottom-up parsing. (A more minor | disadvantage is that you have to have a parser generator; there is no | obvious analogue of recursive descent.) The basic problem is that because | you are recognizing, not predicting, you don't know what production you're | in until very late, and there is therefore no obvious place in which to | store inherited attributes -- you don't know what you're inheriting from! | The basic solution is to create dummy symbols that generate epsilon, and to | insert them into the grammar in *all* the places you might be inheriting | from, so that you can always assume that *one* of them is at a known depth | below you in the parse stack. | | Example: | | dec --> type id_list | id_list --> id | --> id_list , id | | Want to pass type into list. | | dec --> type id_list | id_list --> id declare_id ($1.name, $0.tp) | --> id_list , id declare_id ($3.name, $0.tp) | | Problem (1): suppose the buried symbol isn't always at the same depth? | Solution: marker symbols. Example: | | stmt --> id := expr | --> | --> if expr then stmt | expr --> ... | | Want expr to have inherited attribute with "context" -- what type do we | expect? | | stmt --> id := A expr | --> | --> if B expr then stmt | A --> $$.tp := $-1.tp | B --> $$.tp := Boolean | expr --> ... if $0.tp = Boolean then... | | Problem (2): Inserting a marker may break LR-ness: | | S --> LC TP1 | S --> LC TP2 | | You can put a marker in the TRAILING PART, but not in the LEFT CORNER. ===================================================================== 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.