《(5.1.1)--4.1.1AttributeGrammar.pdf》由会员分享，可在线阅读，更多相关《(5.1.1)--4.1.1AttributeGrammar.pdf（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Compilers TechniquesSyntax-DirectedTranslationThe goal of the compiler is to translate the source programinto a semantically equivalent target program.The popular technology of semantic analysis:The source program and the target program have different grammatical structures,but the express the same
2、results.Syntax-directed translationIntroduction of Semantic AnalysisReview the static semantics of each syntax structureAfter verifying the static semantics,the real translation is performed.e.g.Type,Operation,Dimension,Boundary Crossinge.g.Storage allocation of variablese.g.Evaluation of an express
3、ione.g.Translation of statements(generation of intermediate code)Function of Semantic AnalysisSyntax-directed definitionsSyntax-directed translation schemesA semantic subroutine is compiled for each production.When a production is matched,the corresponding semantic subroutine is called to realize se
4、mantic check and translation.At the appropriate position on the right side of the production,insert the corresponding semantic actions,and execute the encountered semantic actionsaccording to the analysis process.Two Ways of Linking Semantic Rule and Production Example:variables should be defined be
5、fore useThe syntax definition can be written as:L=wcw|w is any string of a and bWhere the first w represents the declaration of the identifier.The latter w represents a reference to an identifier.Question:This grammar is not context-free.What to do?Semantic Information is Context-Sensitive Context-f
6、ree grammarProgram SemanticsInformation necessary for the compiler to translate.Cannot be represented in context-free grammar.It can effectively describe the syntactic structure of the language.It has effective analysis methods,such as LR(1),LALR,etc.How to connect them?Attribute grammarCurrent Situ
7、ation Also known as attribute translation grammar Proposed by Donald Ervin Knuth in 1968.On the basis of context-free grammar,each grammar symbol(terminal or non-terminal)is equipped with several related values(called attributes)Attributes represent information associated with grammar symbols,such a
8、s types,values,code sequences,symbol table,etc.Attributes can be evaluated and passed on.Semantic rules:Attribute computation rules are associated withproductions.Attribute GrammarSyntax-directed definitionsContext-free grammar with attributes and rulesGrammar that uses the syntax-directed definitio
9、ns iscalled basic grammarAttribute GrammarExpression grammarE E+T|E T T T*F|T EF (E)|F digitIn order to evaluate the value of the expression,first add the val attribute to the non-terminal of this grammar.Attribute GrammarSyntax-directed definitions of a simple desk calculatorProductionSemantic rule
10、sL E nprint(E.val)E E1+TE.val:=E1.val+T.valE TE.val:=T.valT T1*FT.val:=T1.val*F.valT FT.val:=F.valF(E)F.val:=E.valF digit F.val:=digit.lexvalAttribute GrammarBasic grammarEach grammar symbol has a set of attributes.Each grammatical production A has a set of semantic rules in the form b:=f(c1,c2,ck),
11、where f is a function,and b,c1,c2,ckare attributes of the grammar symbols of the productionSynthesized attribute:If b is the attribute of A,c1,c2,ckisthe attribute of the right grammar symbol of the production orother attributes of AInherited attribute:If b is the attribute of a grammar symbol Xon t
12、he right of the production,c1,c2,ckare the attribute ofthe grammar symbol on the right of the production or otherattributes of AForm of Syntax-directed DefinitionsBasic grammarEach grammar symbol has a set of attributes.Each grammatical production A has a set of semantic rules in the form b:=f(c1,c2
13、,ck),where f is a function,and b,c1,c2,ckare attributes of the grammar symbols of the productionSynthesized attribute:If b is the attribute of A,c1,c2,ckisthe attribute of the right grammar symbol of the production orother attributes of AInherited attribute:If b is the attribute of a grammar symbol
14、Xon the right of the production,c1,c2,ckare the attribute ofthe grammar symbol on the right of the production or otherattributes of AThe attribute value is calculated by the attribute values of its siblings,itselfand parent.The attribute value is calculated from the attribute values of its children
15、and itself in the parse treeForm of Syntax-directed DefinitionsCommon sense about attributesTerminals only have synthesized attributes.Attributes for terminals have lexical values that supplied by the lexical analyzer.Non-terminals have both synthesized attribute and inherited attribute.Start symbol
16、s of grammar have no inherited attributes unless stated.The intersection of the synthesized attribute set and the inherited attribute set of the grammar symbol should be empty.Properties of Synthesized and Inherited AttributesCommon sense about attributesTerminals only have synthesized attributes.At
17、tributes for terminals have lexical values that supplied by the lexical analyzer.Non-terminals have both synthesized attribute and inherited attribute.Start symbols of grammar have no inherited attributes unless stated.The intersection of the synthesized attribute set and the inherited attribute set
18、 of the grammar symbol should be empty.The attribute value is computed by that of itssiblings and parentProperties of Synthesized and Inherited AttributesCommon sense about attributeA calculation rule must be provided for both inherited attributes that appear on the right of a production and synthes
19、ized attributes that appear on the left of a production.Only attributes of grammar symbols in the corresponding production can be used in attribute evaluation rules.Inherited attributes appearing on the left of a production and synthesized attributes appearing on the right of a production are not co
20、mputed by the attribute calculation rules of the given production,but are computed by the attribute rules of other production or provided by the parameters of the attribute evaluator.Properties of Synthesized and Inherited AttributesThe work described by semantic rules can include.Example:Consider n
21、onterminals A,B and C,where A has an inherited attribute a and a synthesized attribute b,B has a synthesized attribute c,and C has an inherited attribute d.Production ABC may have rules:Attribute evaluation,static semantics checking,symbol table operation,code generation,etc.C.d:=B.c+1A.b:=A.a+B.cTh
22、e attributes A.a and B.c are computed elsewhere.Semantic Rules In semantic rule b:=f(c1,c2,ck),the function f is usually an expression（T.val=F.val）.There are also some rules written as procedure calls or program segments(printing values,output of intermediate codes,etc.),called operations which have
23、 side effects(e.g.Print(E.val)can be regarded as virtual synthesized attributes of productions left non-terminals.Attribute grammar refers to the syntax-directed definition of semantic rule functions without side effects.Attribute grammarBasic grammarSemantic RulesSynthesized attributesProductionSem
24、antic rulesL E nprint(E.val)E E1+TE.val:=E1.val+T.valE TE.val:=T.valT T1*FT.val:=T1.val*F.valT FT.val:=F.valF(E)F.val:=E.valF digit F.val:=digit.lexvalAttrbute definitions：syntax-directed definitions using only synthesized attributesSyntax-directed DefinitionsAnnotated parse tree for 8+5*2 nThe pars
25、e tree marked with the attribute value of each node is called Syntax-directed Definitionsdigit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5The attribute computation of each node in the parse tree can be completed from bottom to top8+5*2 nSyntax-d
26、irected Definitionsdigit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5ProductionSemantic rulesL E nprint(E.val)E E1+TE.val:=E1.val+T.valE TE.val:=T.valT T1*FT.val:=T1.val*F.valT FT.val:=F.valF(E)F.val:=E.valF digit F.val:=digit.lexvalAnnotated Par
27、se Tree for 3*5+4ndigit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5Inherited attributes In the syntax tree,the inherited attributes of a node are determined by certain attributes of itsparent and/or its siblings It is very convenient to use inhe
28、rited attributes to represent context dependencies in programming language structuresInherited AttributesInherited attributesint id,id,idProductionSemantic rulesD TLL.in:=T.typeT intT.type:=integerT realT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lid addtype(id.entry,L.in)Inherited Attribute
29、sAnnotated Parse Tree for int id1,id2,id3DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,Annotated Parse Tree for int id1,id2,id3DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,ProductionSemantic rulesD TLL.in:=T.typeT intT.type:=integerT realT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lid addtype(id.entry,L.in)Compilers TechniquesSyntax-DirectedTranslation