DOC PREVIEW
UD CISC 672 - Context-sensitive Analysis, II Ad-hoc syntax-directed translation, Symbol Tables, andTypes

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 productionSerialized 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 complexityHard to understand and maintain•Copy rules increase space requirementsNeed copies of attributesCan 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 namesField in table for loaded/not loaded state•Avoids all the copy rules, allocation & storage headaches•All inter-assignment attribute flow is through tableClean, efficient implementationGood 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 paradigmDo 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 flexibilityIncludes ability to do tasteless & bad thingsTo make this work•Need names for attributes of each symbol on lhs & rhsTypically, one attribute passed through parser + arbitrary code (structures, globals, statics, …)•Need an evaluation schemeFits 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 tableEnter declaration information as processedAt end of declaration syntax, do some post processingUse table to check errors as parsing progresses•Simple error checking/type checkingDefine before use  lookup on referenceDimension, type, ...  check as encounteredType conformability of expression  bottom-up walkProcedure interfaces are harderBuild a representation for parameter list & typesCreate list of sites to checkCheck offline, or handle the cases for arbitrary orderingsassumes table is globalSymbol Tables•For compile-time efficiency, compilers use symbol tablesAssociates lexical names (symbols) with their attributes•What items go in symbol tables?Variable namesDefined constantsProcedure/function/method namesLiteral constants and stringsSeparate 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 levelTypes: type descriptor, data size/alignmentConstants: type, valueProcedures: Signature (arguments/types) , result type, etc.Type Systems•TypesValues that share a set of common propertiesDefined by language (built-ins) and/or programmer (user-defined)•Type SystemSet of types in a programming languageRules that use types to specify program behavior•Example type rulesIf operands of addition are of type integer, then result is of type integerThe result of the unary “&” operator is a pointer to the object referred to by the operand•AdvantagesEnsures run-time safetyProvides


View Full Document

UD CISC 672 - Context-sensitive Analysis, II Ad-hoc syntax-directed translation, Symbol Tables, andTypes

Documents in this Course
Syllabus

Syllabus

18 pages

Load more
Download Context-sensitive Analysis, II Ad-hoc syntax-directed translation, Symbol Tables, andTypes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Context-sensitive Analysis, II Ad-hoc syntax-directed translation, Symbol Tables, andTypes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Context-sensitive Analysis, II Ad-hoc syntax-directed translation, Symbol Tables, andTypes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?