Context-sensitive Analysis, II Ad-hoc syntax-directed translation, Symbol Tables, andTypesRemember the Example from Last Lecture?And Its ExtensionsThe Moral of the StoryAddressing the ProblemRemind ourselves of Compiler PhasesThe Realist’s AlternativeReworking the Example (with load tracking)Slide 9Example — Building an Abstract Syntax TreeRealityTypical UsesSymbol TablesAttribute InformationType SystemsType CheckerType expressionsA simple type checkerType checking exampleType checking expressionsType checking statementsIs This Really “Ad-hoc” ?Context-sensitive Analysis, IIAd-hoc syntax-directed translation, Symbol Tables, andTypesRemember the Example from Last Lecture?Grammar for a basic block (§ 4.3.3) Let’s estimate cycle counts• Each operation has a COST• Add them, bottom up• Assume a load per value• Assume no reuseSimple problem for an AGHey, this looks useful !And Its ExtensionsTracking loads •Introduced Before and After sets to record loads•Added ≥ 2 copy rules per productionSerialized evaluation into execution order•Made the whole attribute grammar large & cumbersomeThe Moral of the Story•Non-local computation needed lots of supporting rules•Complex local computation was relatively easyThe Problems•Copy rules increase complexityHard to understand and maintain•Copy rules increase space requirementsNeed copies of attributesCan use pointers, but harder to understandAddressing the Problem If you gave this problem to a programmer at IBM•Introduce a central repository for facts•Table of namesField in table for loaded/not loaded state•Avoids all the copy rules, allocation & storage headaches•All inter-assignment attribute flow is through tableClean, efficient implementationGood techniques for implementing the table (hashing, § B.3)When its done, information is in the table !Cures most of the problems•Unfortunately, this design violates the functional paradigmDo we care?Remind ourselves of Compiler PhasesDifferent Phases of Project-----------------------Phase I: ScannerPhase II: ParserPhase III: Semantic RoutinesPhase IV: Code GeneratorThe Realist’s AlternativeAd-hoc syntax-directed translation•Associate a snippet of code with each production•At each reduction, the corresponding snippet runs•Allowing arbitrary code provides complete flexibilityIncludes ability to do tasteless & bad thingsTo make this work•Need names for attributes of each symbol on lhs & rhsTypically, one attribute passed through parser + arbitrary code (structures, globals, statics, …)•Need an evaluation schemeFits nicely into LR(1) parsing algorithmReworking the Example (with load tracking)Block0→Block1 Assign⎯AssignAssign→I dent = Expr ;cost← cost + COST(store);Expr0→Expr1 + Termcost← cost + COST(add);⎯Expr1 – Termcost← cost + COST(sub);⎯TermTerm0→Term1 * Factorcost← cost + COST(mult);⎯Term1 / Factorcost← cost + COST(div);⎯FactorFactor→( Expr )⎯Numbercost← cost + COST(loadi);⎯I dentif ier{ i← hash(I dentif ier); if (Ta ble[i].loaded = f alse) then { cost ← cost + COST (load); Ta ble[i].loaded ← true; }}This looks simpler than the Attribute Grammar solution! One missing detail: initializing costReworking the Example (with load tracking)Start→I nit BlockI nit→εcost ← 0;Block0→Block1 Assign⎯AssignAssign→I dent = Expr ;cost← cost + COST(store); … and so on as in the previous version of the example …• Before parser can reach Block, it must reduce Init• Reduction by Init sets cost to zeroThis is an example of splitting a production to create a reduction in the middle — for the sole purpose of hanging an action routine there!Example — Building an Abstract Syntax Tree•Assume constructors for each node•Assume stack holds pointers to nodes Goal → Expr Goal.node = E.node; Expr → Expr + Te rm E0.node= MakeAddNode(E1.node,T.node); | Expr – Term E0.node= MakeSubNode(E1.node,T.node); | Term E.node = T.node; Term → Term * Factor T0.node= MakeMulNode(T1.node,F.node); | Term / Factor T0.node= MakeDivNode(T1.node,F.node); | Factor T.node = F.node; Factor → ( Expr ) F.node = Expr.node; | number F.node= MakeNumNode(token); | id F.node = MakeI dNode(token);RealityMost parsers are based on this ad-hoc style of context-sensitive analysisAdvantages•Addresses shortcomings of Attribute Grammar paradigm•Efficient, flexibleDisadvantages•Must write the code with little assistance•Programmer deals directly with the detailsMost parser generators support a yacc/bison-like notationTypical Uses •Building a symbol tableEnter declaration information as processedAt end of declaration syntax, do some post processingUse table to check errors as parsing progresses•Simple error checking/type checkingDefine before use lookup on referenceDimension, type, ... check as encounteredType conformability of expression bottom-up walkProcedure interfaces are harderBuild a representation for parameter list & typesCreate list of sites to checkCheck offline, or handle the cases for arbitrary orderingsassumes table is globalSymbol Tables•For compile-time efficiency, compilers use symbol tablesAssociates lexical names (symbols) with their attributes•What items go in symbol tables?Variable namesDefined constantsProcedure/function/method namesLiteral constants and stringsSeparate layout for structure layouts Field offsets and lengths•A symbol table is a compile-time structure•More after mid-term!Attribute Information•Attributes are internal representation of declarations•Symbol table associates names with attributes•Names may have different attributes depending on their meaning:Variables: type, procedure levelTypes: type descriptor, data size/alignmentConstants: type, valueProcedures: Signature (arguments/types) , result type, etc.Type Systems•TypesValues that share a set of common propertiesDefined by language (built-ins) and/or programmer (user-defined)•Type SystemSet of types in a programming languageRules that use types to specify program behavior•Example type rulesIf operands of addition are of type integer, then result is of type integerThe result of the unary “&” operator is a pointer to the object referred to by the operand•AdvantagesEnsures run-time safetyProvides
View Full Document