Semantic Analysis - Cs.rpi.edu
Semantic AnalysisRead: Scott, Chapter 4.1-4.31
Lecture OutlinenSyntax vs. static semanticsStatic semantics vs. dynamic semanticsnAttribute GrammarsnnnnnAttributes and rulesSynthesized and inherited attributesS-attributed grammarsL-attributed grammarsProgramming Languages CSCI 4430, A. Milanova2
Static SemanticsnEarlier we considered syntax analysisnnWe now look at static semantic analysisnnInformally, syntax deals with the form ofprogramming language constructsSemantics deals with the meaning ofprogramming language constructsThe distinction between the two is fuzzynIn practice, anything that is not expressed interms of certain CFG (LALR(1), in particular) isconsidered semanticsProgramming Languages CSCI 4430, A. Milanova3
Static Semantics vs. Dynamic SemanticsnStatic semantic analysis (compile-time)nInformally, reasons about program propertiesstatically, before program executionnnE.g., determine static types of expressions, detectcertain errorsDynamic semantic analysis (run-time)nReasons about program properties dynamically,during program executionnE.g., could expression a[i] index out of arraybounds, etc.?Programming Languages CSCI 4430, A. Milanova4
The Role of Semantic AnalysisnnDetect errors in programs!Static semantic analysisnDetect as many errors as possible early, before executionnnDynamic semantic analysisnDetect errors by performing checks during executionnnnType inference and type checkingAgain, detect errors as early as possible. E.g., flagging an arrayout-of-bounds at assignment a[i] is usefulTradeoff: dynamic checks slow program executionLanguages differ greatly in the amount of staticsemantic analysis and dynamic semantic analysisthey performProgramming Languages CSCI 4430, A. Milanova5
Examples of Static Semantic ErrorsnType mismatch:nnnx y z w: type of left-hand-side does not“match” type of right-hand-sideA a; ; a.m(): m() cannot be invoked ona variable of type ADefinite assignment check in Java: a localvariable must be assigned before it is usedProgramming Languages CSCI 4430, A. Milanova6
Examples of Dynamic SemanticErrorsnNull pointer dereference:nnnArray-index-out-of-bounds:nnna[i], i goes beyond the bounds of aWhat happens in C ? What happens in Java?Casting an object to a type of which it is not aninstancenna.m() in Java, and a is null (i.e., uninitialized reference)What happens?C ? Java?And more Programming Languages CSCI 4430, A. Milanova7
Static Semantics vs. Dynamic SemanticsnnAgain, distinction between the two is fuzzyFor some programs, the compiler can predictrun-time behavior by using static analysisnnE.g., there is no need for a nullness check:x new X();x.m(); // x is non-nullIn general, the compiler cannot predict runtime behaviornStatic analysis is limited by the halting problemProgramming Languages CSCI 4430, A. Milanova8
Semantic Analyzercompilercharacter streamscanneroptimizertoken streamparserparse treessemantic analyzerand intermediatecode generatormodifiedintermediateformcode generatorassembly codeintermediateformSemantic analyzer performs static semantic analysis on parse trees and ASTs.Optimizer performs static semantic analysis on intermediate 3-address code.Programming Languages CSCI 4430, A. Milanova9
Lecture OutlinenSyntax vs. static semanticsStatic semantics vs. dynamic semanticsnAttribute GrammarsnnnnnAttributes and rulesSynthesized and inherited attributesS-attributed grammarsL-attributed grammarsProgramming Languages CSCI 4430, A. Milanova10
Attribute Grammars:Foundation for Static Semantic AnalysisnAttribute Grammars: generalization ofContext-Free GrammarsnnAssociate meaning with parse treesAttributesnnEach grammar symbol has one or more values calledattributes associated with it. Each parse tree node hasits own instances of those attributes; attribute valuecarries the “meaning” of the parse tree rooted at nodeSemantic rulesnEach grammar production has associated rule, whichmay refer to and compute the values of attributesProgramming Languages CSCI 4430, A. Milanova11
Example: Attribute Grammar to Compute Valueof Expression (denote grammar by AG1)S EE E T TT T*F FF numProductionS EE E1 TSemantic Ruleprint(E.val)E.val : E1.val T.valE TT T1*FE.val : T.valT.val : T1.val * F.valT FF numT.val : F.valF.val : num.valval: AttributesProgramming Languages CSCI 4430, A. Milanova12
Example: Decorated parse tree for input3*5 2*4S EE E1 TE TT T1*FT FF numSprint(E.val)E.val : E1.val T.valE.val : T.valT.val : T1.val*F.valT.val : F.valF.val : num.valE 23E 15 T 15T3F3num 3*T8T2 *F5F2F4num 4num 5 num 2Programming Languages CSCI 4430, A. Milanova13
Examplenval: Attributes associated to symbolsnnnIndices are used to distinguish between symbolswith same name within same productionnnIntuitively, A.val holds the value of the expression,represented by the subtree rooted at ASeparate attributes are associated with separate nodes inthe parse treeE.g., E E1 TE.val : E1.val T.valAttributes of terminals supplied by scannernIn example, attributes of and * are never usedProgramming Languages CSCI 4430, A. Milanova14
Building an Abstract Syntax Tree (AST)nAn AST is an abbreviated parse treennnOperators and keywords do not appear asleaves, but at the interior node that would havebeen their parentChains of single productions are collapsedCompilers typically work with ASTsProgramming Languages CSCI 4430, A. Milanova15
Building ASTs for ExpressionsAbstract syntax tree (AST) Parse tree for 3*5 2*4E m:2How do we construct syntax trees for expressions?Programming Languages CSCI 4430, A. Milanova16
Attribute Grammar to build AST forExpression (denote by AG2)nAn attribute grammar:Attribute “nodepointer”points to ASTProductionSemantic RuleE E1 TE.nptr : mknode( , E1.nptr, T.nptr)E TE.nptr : T.nptrT T1 *FT.nptr : mknode(*, T1.nptr, F.nptr)T FT.nptr : F.nptrF numF.nptr : mkleaf(num, num.val)mknode(op,left,right) creates an operator node withlabel op, and two fields containing pointers left, to leftoperand and right, to right operandmkleaf(num,num.val) creates a leaf node with label num,and a field containing the value of the number17
Constructing ASTs for ExpressionsInput:3 * 5 2 * 4 ,ETTFnum,3* *,T.nptr : F.nptrF.nptr : mkleaf(‘num’, num.val),*,T,FE.nptr : mknode(‘ ’, E1.nptr, T.nptr)E.nptr : T.nptrT.nptr : mknode(‘*’, T1.nptr, F.nptr)T FF numSEE E1 TE TT T1 *FTFnum,5 num,2*,Fnum,4
ExercisenWe know that the language L anbncn is notcontext free. It can be captured however withan attribute grammar. Give an underlyingCFG and a set of attribute rules thatassociate an attribute ok with the root S ofeach parse tree, such that S.ok is true if andonly if the string corresponding to the fringeof the tree is in L.Programming Languages CSCI 4430, A. Milanova19
ExerciseProgramming Languages CSCI 4430, A. Milanova20
ExercisenConsider the expression grammarE E T TT T*F FF num ( E )Give attribute rules to accumulate into the roota count of the maximum depth to whichparentheses are nested in the expression. E.g.,((1 2)*3 4)*5 6 has a count of 2.Programming Languages CSCI 4430, A. Milanova21
ExerciseProgramming Languages CSCI 4430, A. Milanova22
Another GrammarnE stands for exprT stands for termTT stands for term tailNow, the right-recursive LL(1) grammar:E T TTTT - T TTTT εT numnGoal: construct an attribute grammar thatcomputes the value of an expressionValues must be computed “normally”, i.e.,5-3-2 must be evaluated as (5-3)-2, not as5-(3-2)nProgramming Languages CSCI 4430, A. Milanova23
QuestionnWhat happens if we wrote a “bottom-upattribute flow” grammar?E T TTTT - T TT1TT εT numE.val T.val – TT.valTT.val T.val – TT1.valTT.val 0T.val num.valA hack:E T TTE.val T.val – TT.valTT - T TT1TT.val T.val TT1.valTT εTT.val 0T numT.val num.valUnfortunately, this won’t work if we add TT T TT1Programming Languages CSCI 4430, A. Milanova24
Attribute Grammar to Compute Value ofExpressions (denote by AG3)E T TTProductionE T TTTT -T TT T TT εT numSemantic Rules(1) TT.sub : T.val(2) E.val : TT.valTT - T TT1 (1) TT1.sub: TT.sub - T.val (2) TT.val : TT1.valTT T TT1 (1) TT1.sub: TT.sub T.val (2) TT.val : TT1.valTT ε(1) TT.val : TT.subT num(1) T.val : num.val(provided by scanner)Attributes flow from parent to node, and from “siblings” to node!Programming Languages CSCI 4430, A. Milanova25
Attribute FlowAttribute TT1.sub: computed based on parentTT and sibling T: TT.sub - T.val15 TT24T 3TT12115 TTE.g., 25 – 1 - 3 - 6TT holds subtotal 24 (for 25 – 1, computed so far)T holds value 3 (i.e., the value of next term)TT1 gets subtotal 21 (for 25 – 1 – 3)Passed down the tree of TT1 to next TT on chainEventually, we hit TT ε and value gets subtotal 15Value 15 is passed back up26
ExampleProgramming Languages CSCI 4430, A. Milanova27
Attribute FlownnnAttribute .val carries the total valueAttribute .sub is the subtotal carried from leftRules for nonterminals E, T do not performcomputationnnNo need for .sub attribute.val attribute is carried to the rightnnIn E T TT : val of T is passed to sibling TTIn TT -T TT1 : val of T is passed to sibling TT1Programming Languages CSCI 4430, A. Milanova28
Attribute FlownRules for nonterminal TT do performcomputationnTT needs to carry subtotal in .subnE.g., in TT - T TT1 the subtotal of TT1 is computedby subtracting the value of T from the subtotal of TTProgramming Languages CSCI 4430, A. Milanova29
Lecture OutlinenSyntax vs. static semanticsStatic semantics vs. dynamic semanticsnAttribute GrammarsnnnnnAttributes and rulesSynthesized and inherited attributesS-attributed grammarsL-attributed grammarsProgramming Languages CSCI 4430, A. Milanova30
Synthesized and Inherited AttributesnSynthesized attributesnnnnAttribute value computed from attributes ofdescendants in parse tree, and/or attributes of selfE.g., attributes val in AG1, val in AG3E.g., attributes nptr in AG2Inherited attributesnnAttribute value computed from attributes of parentin tree and/or attributes of siblings in treeE.g., attributes sub in AG3nIn order to compute value “normally” we needed topass sub down the tree (sub is inherited attribute).Programming Languages CSCI 4430, A. Milanova31
S-attributed GrammarsnAn attribute grammar for which all attributesare synthesized is said to be S-attributedn“Arguments” of rules are attributes of symbolsfrom the production right-hand-sidenn“Result” is placed in attribute of the symbol onthe left-hand-side of the productionnnI.e., attributes of children in parse treeI.e., computes attribute of parent in parse treeI.e., attribute values depend only on descendantsin tree. They do not depend on parents orsiblings in tree!32
QuestionsnCan you give examples of S-attributedgrammars?nnAnswer: AG1 and AG2How can we evaluate S-attributedgrammars?nnI.e., in what order do we visit nodes of the parsetree and compute attributes, bottom-up or topdown?Answer: bottom-upProgramming Languages CSCI 4430, A. Milanova33
L-attributed GrammarnAn attribute grammar is L-attributed if eachinherited attribute of Xj on the right-hand-sideof A X1 X2 Xj-1Xj Xn depends only onnn(1) the attributes of symbols to the left of Xj: X1,X2 , , Xj-1(2) the inherited attributes of AProgramming Languages CSCI 4430, A. Milanova34
QuestionsnCan you give examples of L-attributedgrammars?nnAnswer: AG3How can we evaluate L-attributed grammars?nnI.e., in what order do we visit the nodes of theparse tree?Answer: top-downProgramming Languages CSCI 4430, A. Milanova35
QuestionnAn attribute grammar is L-attributed if eachinherited attribute of Xj on the right-hand-sideof A X1 X2 Xj-1Xj Xn depends only onnnn(1) the attributes of symbols to the left of Xj: X1,X2 , , Xj-1(2) the inherited attributes of AWhy the restriction on siblings and kinds ofattributes of parent? Why not allowdependence on siblings to the right of Xj,e.g., Xj 1, etc.?Programming Languages CSCI 4430, A. Milanova36
Recursive Descent (sketch)S E E T TTTT - T TT T TT εT numnum S()case lookahead() ofnum: val E(); match( ); return valotherwise PARSE ERRORnum E()case lookahead() ofnum: sub T(); val TT(sub); return valotherwise PARSE ERRORnum TT(num sub)case lookahead() of- : match(‘-’); Tval T(); val TT(sub -Tval); return val : match(‘ ’); Tval T(); val TT(sub -Tval); return val :val sub; return valotherwise: PARSE ERROR37
Evaluating Attributes and Attribute FlownS-attributed grammarsnnnnA very special case of attribute grammarsMost important case in practiceCan be evaluated on-the-fly during a bottom-up(LR) parseL-attributed grammarsnA proper superset of S-attributed grammarsnnEach S-attributed grammar is also L-attributedbecause restriction applies only to inherited attributesCan be evaluated on-the-fly during a top-down(LL) parse38
The EndProgramming Languages CSCI 4430, A. Milanova39
5 The Role of Semantic Analysis nDetect errors in programs! nStatic semantic analysis n Detect as many errorsas possible early, before execution n Type inference and type checking nDynamic semantic analysis n Detect errors by performing checks during execution n Again, detect errors as early as possible. E.g., flagging an ar
Jian Shi (shij4@rpi.edu) MRC 161 Chaitanya Ullal (ullalc@rpi.edu) MRC 112 Edmund Palermo (palere@rpi.edu) MRC 206 Department Coordinator (for URP) Meeli Chew Leith (leithm@rpi.edu) MRC 103 Graduate Admissions: Ganpati Ramanath (ganapr@rpi.edu) MRC 111 Graduate Advising Minoru Tomozawa (tomozm@rpi.edu) MRC 109B
1. RPI Re-Flex TPO Bonding Adhesive (solvent-based). 2. RPI Re-Flex H2O Bonding Adhesive (low VOC). 3. Royal Edge 2-Part Pourable Sealant for use in sealant pans. 4. RPI Re-Flex Caulking for use in sealing termination bars and penetration clamping bands. 5. RPI Re-Flex TPO Cut Edge Sealant. 7. RPI Re-Flex Primer. 2.06 Traffic Protection
Setting up an RPI with FLDIGI This is a very rudimentary explanation of getting FLDIGI onto the raspberry PI once you have already configured the PI with Raspbian. I actually used a pre-built RPI image from SDRPLAY which has built in drivers for my SDR-PLAY but it was based on the standard Raspbian image most people use for RPI’s.
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
Equipment/Pit Chair Andrew Calcutt calcua@rpi.edu Cairn Editor Nathan Gibson gibson2@rpi.edu Member at Large Melanie Ouellette ouellm@rpi.edu CLUB ACTIVITIES: Canoeing – Have you ever wanted to float down a flowing riv
YET TO BE DECIDED ENGINEERING UNDERGRADUATE BOOKLET 09/06/16 . RENSSELAER POLYTECHNIC INSTITUTE . School of Engineering . . fotim@rpi.edu) JEC 7049 Kristen Bryk (brykk@rpi.edu . biomedical, chemical, food, nuclear, semiconductor processing, and environmental operations. By emphasizing basic principles, the program prepares its graduates for .
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
--Russell, S. J., & Norvig, P. (2016). Artificial intelligence: a modern approach. Malaysia; Pearson Education Limited. Intelligence is the computational part of the ability to achieve goals in the world. It is related to the similar task of using computers to understand human intelligence, but AI does not have to confine itself to methods that are biologically observable.--By Prof. John .
