Semantic Analysis - University Of Alaska System

2y ago
41 Views
7 Downloads
1.17 MB
21 Pages
Last View : 2d ago
Last Download : 2m ago
Upload by : Mika Lloyd
Transcription

2/4/2013Semantic AnalysisChapter 4Role of Semantic Analysis Following parsing, the next two phases of the"typical" compiler are– semantic analysis– (intermediate) code generation The principal job of the semantic analyzer isto enforce static semantic rules– constructs a syntax tree (usually first)– information gathered is needed by the codegenerator1

2/4/2013Role of Semantic Analysis There is considerable variety in the extentto which parsing, semantic analysis, andintermediate code generation areinterleaved A common approach interleavesconstruction of a syntax tree with parsing(no explicit parse tree), and then followswith separate, sequential phases forsemantic analysis and code generationAttribute Grammars Both semantic analysis and (intermediate) codegeneration can be described in terms ofannotation, or "decoration" of a parse orsyntax tree ATTRIBUTE GRAMMARS provide a formalframework for decorating such a tree Consider the following LR (bottom-up)grammar for arithmetic expressionsmade of constants, with precedence andassociativity:2

2/4/2013Attribute GrammarsEEETTTFFF E TE – TTT * FT / FF- F(E)const This says nothing about what the programMEANSAttribute Grammars We can turn this into an attribute grammar asfollows (similar to Figure 4.1):EEETTTFFF E TE – TTT * FT / FF- .valF.val C.val3

2/4/2013Attribute Grammars The attribute grammar serves to define thesemantics of the input program Attribute rules are best thought of asdefinitions, not assignments They are not necessarily meant to beevaluated at any particular time, or in anyparticular order, though they do define theirleft-hand side in terms of the right-hand sideEvaluating Attributes The process of evaluating attributes is calledannotation, or DECORATION, of the parse tree– When a parse tree under this grammar is fullydecorated, the value of the expression will be inthe val attribute of the root The code fragments for the rules are calledSEMANTIC FUNCTIONS– Strictly speaking, they should be cast as functions,e.g., E1.val sum (E2.val, T.val) but often we willuse the obvious E1.val E2.val T.val4

2/4/2013Evaluating AttributesEEETTTFFF E TE – TTT * FT / FF- .valF.val E2.val E2.val T.valT2.val *T2.val /F.val- F2.valE.valC.valT.valT.valF.valF.valEvaluating Attributes This is a very simple attribute grammar:– Each symbol has at most oneattribute the punctuation marks have no attributes These attributes are all so-called SYNTHESIZEDattributes:– They are calculated only from the attributes ofthings below them in the parse tree5

2/4/2013Evaluating Attributes In general, we are allowed both synthesizedand INHERITED attributes:– Inherited attributes may depend on things above orto the side of them in the parse tree– Tokens have only synthesized attributes, initializedby the scanner (name of an identifier, value of aconstant, etc.).– Inherited attributes of the start symbol constituterun-time parameters of the compilerInherited Attributes LL(1) grammar covering subtraction:Expr const Expr TailExpr Tail - const Expr Tail ε For the expression 9 – 4 – 3:Expr9Expr Tail-4-Expr Tail3Expr Tailε6

2/4/2013Inherited Attributes If we are allowed to pass attribute values not onlybottom-up but also left-to-right then we can pass 9into the Expr Tail node for evaluation, and so on foreach Expr TailExpr9Expr Tail-4-Expr Tail3Expr TailεSimilar to recursion when the result is accumulated as recursive calls madeEvaluating Attributes The grammar for evaluating expressions iscalled S-ATTRIBUTED because it uses onlysynthesized attributes Its ATTRIBUTE FLOW (attribute dependencegraph) is purely bottom-up– It is SLR(1), but not LL(1) An equivalent LL(1) grammar requiresinherited attributes:7

2/4/2013Evaluating Attributes – Example Attribute grammar in Figure 4.3:E T TTE.v TT.vTT.st T.vTT1 T TT2TT1.v TT2.vTT2.st TT1.st T.vTT1 - T TT2TT1.v TT2.vTT2.st TT1.st - T.vTT TT.v TT.stT F FTT.v FT.vFT.st F.vEvaluating Attributes– Example Attribute grammar in Figure 4.3 (continued):FT1 * F FT2FT1.v FT2.vFT2.st FT1.st * F.vFT1 / F FT2FT1.v FT2.vFT2.st FT1.st / F.vFT FT.v FT.stF1 - F2F1.v - F2.vF ( E )F.v E.vF constF.v C.v Figure 4.4 – parse tree for (1 3)*28

2/4/2013Evaluating Attributes– ExampleEvaluating Attributes– Example Attribute grammar in Figure 4.3:– This attribute grammar is a good bit messier thanthe first one, but it is still L-ATTRIBUTED, whichmeans that the attributes can be evaluated in asingle left-to-right pass over the input– In fact, they can be evaluated during an LL parse– Each synthetic attribute of a LHS symbol (bydefinition of synthetic) depends only on attributesof its RHS symbols9

2/4/2013Evaluating Attributes – Example Attribute grammar in Figure 4.3:– Each inherited attribute of a RHS symbol (by definitionof L-attributed) depends only on inherited attributes of the LHS symbol, or synthetic or inherited attributes of symbols to its left in theRHS– L-attributed grammars are the most general class ofattribute grammars that can be evaluated during an LLparseEvaluating Attributes There are certain tasks, such as generationof code for short-circuit Boolean expressionevaluation, that are easiest to express withnon-L-attributed attribute grammars Because of the potential cost of complextraversal schemes, however, most realworld compilers insist that the grammar beL-attributed10

2/4/2013Evaluating Attributes - Abstract Syntax The Abstract Syntax defines essential syntacticelements without describing how they areconcretely constructed Consider the following Pascal and C loopsPascalwhile i n do begini: i 1endCwhile (i n) {i i 1;}Small differences in concrete syntax; identical abstract constructAbstract Syntax Format We can define an abstract syntax using rulesof the form– LHS RHS LHS is the name of an abstract syntactic class RHS is a list of essential components that define theclass– Similar to defining a variable. Data type or abstract syntacticclass, and name Recursion naturally occurs among thedefinitions as with BNF– Makes it fairly easy to construct programmatically,similar to what we did for the concrete syntax11

2/4/2013Abstract Syntax Example Loop–Loop Expression test ; Statement bodyThe abstract class Loop has two components, a test which is amember of the abstract class Expression, and a body which is amember of an abstract class Statement Nice by-product: If parsing abstract syntax in a language likeJava, it makes sense to actually define a class for each abstractsyntactic class, e.g.class Loop extends Statement {Expression test;Statement body;}Abstract Syntax of a C-like LanguageProgram Declarations decpart; Statements body;Declarations Declaration*Declaration VariableDecl ArrayDeclVariableDecl Variable v; Type tArrayDecl Variable v; Type t; Integer sizeType int bool float charStatements Statement*Statement Skip Block Assignment Conditional LoopSkip Block StatementsConditional Expression test;Statement thenbranch, elsebranchLoop Expression test; Statement bodyAssignment VariableRef target;Expression sourceExpression VariableRef Value Binary Unary12

2/4/2013Abstract Syntax of a C-like LanguageVariableRef Variable ArrayRefBinary Operator op; Expression term1, term2Unary UnaryOp op; Expression termOperator BooleanOp RelationalOp ArithmeticOpBooleanOp && RelationalOp ! ! ArithmeticOp - * /UnaryOp ! Variable String idArrayRef String id; Expression indexValue IntValue BoolValue FloatValue CharValueIntValue Integer intValueFloatValue Float floatValueBoolValue Boolean boolValueCharValue Character charValueJava Abstract Syntax for C-LikeLanguageclass Loop extends Statement {Expression test;Statement body;}class Assignment extends Statement {// Assignment Variable target; Expression sourceVariable target;Expression source;} 13

2/4/2013Abstract Syntax Tree Just as we can build a parse tree from a BNF grammar, wecan build an abstract syntax tree from an abstract syntax Example for: x 2*yExpression Variable Value BinaryBinary Operator op ; Expression term1, term2Binary nodeExprSample C-Like Program Compute nth fib number14

2/4/2013Abstract Syntax for Loop of C-Like ProgramConcrete and Abstract Syntax Aren’t the two redundant?– A little bit The concrete syntax tells the programmer exactly what towrite to have a valid program The abstract syntax allows valid programs in two differentlanguages to share common abstract representations– It is closer to semantics– We need both! To construct the abstract syntax tree a commonapproach is a bottom-up attribute grammarassociated with the concrete syntax15

2/4/2013Evaluating Attributes – Syntax TreesSkipping Top-Down, butit exists too (with inheritedattributes)EvaluatingAttributes –Syntax Trees(1 3)*216

2/4/2013Action Routines We can tie this discussion back into theearlier issue of separated phases v. on-thefly semantic analysis and/or code generation If semantic analysis and/or code generationare interleaved with parsing, then theTRANSLATION SCHEME we use to evaluateattributes MUST be L-attributedAction Routines If we break semantic analysis and codegeneration out into separate phase(s), thenthe code that builds the parse/syntax tree canstill use a left-to-right (L-attributed)translation scheme However, the later phases are free to use afancier translation scheme if they want17

2/4/2013Action Routines There are automatic tools that generatetranslation schemes for context-freegrammars or tree grammars (which describethe possible structure of a syntax tree)– These tools are heavily used in syntax-basededitors and incremental compilers– Most ordinary compilers, however, use ad-hoctechniquesAction Routines An ad-hoc translation scheme that is interleaved withparsing takes theform of a set of ACTION ROUTINES:– An action routine is a semantic function that we tell thecompiler to execute at a particular point in the parse– Same idea as the previous abstract syntax example (Fig 4.6,4.7), except the action routines are embedded among thesymbols of the right-hand sides; work performed is thesame For our LL(1) attribute grammar, we could put inexplicit action routines as follows:18

2/4/2013Action Routines - Example Action routines (Figure 4.9)Decorating a Syntax Tree Abstract syntax tree for a simple programto print an average of an integer and a real19

2/4/2013Complete AttributeGrammar20

2/4/201321

Semantic Analysis Chapter 4 Role of Semantic Analysis Following parsing, the next two phases of the "typical" compiler are –semantic analysis –(intermediate) code generation The principal job of the semantic analyzer is to enforce static semantic rules –constructs a syntax tree (usua

Related Documents:

tive for patients with semantic impairments, and phono-logical tasks are effective for those with phonological impairments [4,5]. One of the techniques that focus on semantic impair-ments is Semantic Feature Analysis (SFA). SFA helps patients with describing the semantic features which ac-tivate the most distinguishing features of the semantic

Judge Larry Zervos Alaska Superior Court, Sitka Rural Access Subcommittee Judge Dale Curda, co-chair Alaska Superior Court, Bethel Judge Roy Madsen (retired), co-chair Alaska Superior Court, Kodiak Louise Brady Sitka Tribe of Alaska, Sitka James Jackson Alaska Court Magistrate, Galena Judge Michael Jeffery Alaska Superior Court, Barrow

Alaska Airlines Inflight Magazine. Economics 300: Economy of Alaska, Notes-Introduction to Alaska Geography, page 9 Alaska Census Areas For purposes of collecting and reporting economic and social Alaska data, Alaska is divided into 27 “census areas.” These census areas are shown in the map below.

WibKE – Wiki-based Knowledge Engineering @WikiSym2006 Our Goals: Why are we doing this? zWhat is the semantic web? yIntroducing the semantic web to the wiki community zWhere do semantic technologies help? yState of the art in semantic wikis zFrom Wiki to Semantic Wiki yTalk: „Doing Scie

(semantic) properties of objects to place additional constraints on snapping. Semantic snapping also provides more complex lexical feedback which reflects potential semantic consequences of a snap. This paper motivates the use of semantic snapping and describes how this technique has been implemented in a window-based toolkit. This

Wholesale Trade, and Construction. Source: Alaska Department of Labor, . employment pie. 2 ALASKA ECONOMIC TRENDS AUGUST, 1998 Alaska Economic Trends is a monthly . the Employment Security Division and published by the Alaska Department of Labor, P.O. Box 21149, Juneau, Alaska 99802-

Alaska Native Language Materials . in the . Alaska State Library . Historical Collections . Compiled by . James Simard . Alaska State Library - Historical Collections . Alaska Department of Education & Early Development Division of Libraries, Archives & Museums . P.O. Box 110571 Juneau Alaska 99811-0571 (907) 465-2925 Fax: (907) 465-2990

appropriate strategies to solve problems. Mathworld.com Classification: Number Theory Diophantine Equations Coin Problem 02-02. 14 AMC 8 Practice Questions Continued -Ms. Hamilton’s eighth-grade class wants to participate intheannualthree-person-teambasketballtournament. The losing team of each game is eliminated from the tournament. Ifsixteenteamscompete, howmanygames will be played to .