Syntax Analysis - Computer Action Team
Syntax Analysis - Part 1Syntax AnalysisOutlineContext-Free Grammars (CFGs)ParsingTop-DownRecursive DescentTable-DrivenBottom-UpLR Parsing AlgorithmHow to Build LR TablesParser GeneratorsGrammar Issues for Programming Languages Harry H. Porter, 20051Syntax Analysis - Part 1Top-Down Parsing !LL Grammars - A subclass of all CFGs !Recursive-Descent Parsers - Programmed “by hand” !Non-Recursive Predictive Parsers - Table Driven !Simple, Easy to Build, Better Error HandlingBottom-Up Parsing !LR Grammars - A larger subclass of CFGs !Complex Parsing Algorithms - Table Driven !Table Construction Techniques !Parser Generators use this technique !Faster Parsing, Larger Set of Grammars !Complex !Error Reporting is Tricky Harry H. Porter, 20052
Syntax Analysis - Part 1Output of Parser?Succeed is string is recognized. and fail if syntax errorsSyntax Errors?Good, descriptive, helpful message!Recover and continue parsing!*Build a “Parse Tree” (also called “derivation tree”)Build Abstract Syntax Tree (AST)In memory (with objects, pointers)Output to a filex y1Execute Semantic ActionsBuild ASTType CheckingGenerate CodeDon’t build a tree at all! Harry H. Porter, 20053Syntax Analysis - Part 1Errors in ProgramsLexicalif x 1 thenn y 5:“Typos”Syntacticif ((x 1) & (y 5))) .{ . { . }Semanticif (x 5) then .Type ErrorsUndefined IDs, etc.Logical Errorsif (i 9) then .Should be not BugsCompiler cannot detect Logical Errors Harry H. Porter, 20054
Syntax Analysis - Part 1CompilerAlways haltsAny checks guaranteed to terminate“Decidable”Other Program Checking TechniquesDebuggingTestingCorrectness Proofs“Partially Decidable”Okay? ! The test terminates.Not Okay? ! The test may not terminate!You may need to run some programs to see if they are okay. Harry H. Porter, 20055Syntax Analysis - Part 1RequirementsDetect All Errors (Except Logical!)Messages should be helpful.Difficult to produce clear messages!Example:Syntax ErrorExample:Line 23: Unmatched Parenif ((x 1) then Compiler Should RecoverKeep going to find more errorsExample:x : (a 5)) * (b 7));This error missedWe’re in the middle of a statementSkip tokens until we see a “;”Error detected hereResume ParsingMisses a second error. Oh, well.Checks most of the source Harry H. Porter, 20056
Syntax Analysis - Part 1Difficult to generate clear and accurate error messages.Examplefunction foo () {.if (.) {.} else {.} eof Missing } hereNot detected until hereExamplevar myVarr: Integer;.x : myVar;Misspelled ID here.Detected here as“Undeclared ID” Harry H. Porter, 20057Syntax Analysis - Part 1For Mature LanguagesCatalog common errorsStatistical studiesTailor compiler to handle common errors wellStatement terminators versus separatorsTerminators: C, Java, PCAT{A;B;C;}Separators: Pascal, Smalltalk, HaskellPascal Examplesbeginvar t: Integer;t : x;x : y;Tend to insert a ; herey : tendif (.) thenx : 1elsey : 2;z : 3;Tend to insert a ; herefunction foo (x: Integer; y: Integer). Harry H. Porter, 2005Tend to put a comma here8
Syntax Analysis - Part 1Error-Correcting Compilers !Issue an error message !Fix the problem !Produce an executableExampleError on line 23: “myVarr” undefined.“myVar” was used.Is this a good idea?Compiler guesses the programmer’s intentA shifting notion of what constitutes a correct / legal / valid programMay encourage programmers to get sloppyDeclarations provide redundancy! Increased reliability Harry H. Porter, 20059Syntax Analysis - Part 1Error AvalancheOne error generates a cascade of messagesExamplex : 5 while ( a b ) do Expecting ; Expecting ; Expecting ;The real messages may be buried under the avalanche.Missing #include or import will also cause an avalanche.Approaches:Only print 1 message per token [ or per line of source ]Only print a particular message onceError: Variable “myVarr” is undeclaredAll future notices for this ID have been suppressedAbort the compiler after 50 errors. Harry H. Porter, 200510
Syntax Analysis - Part 1Error Recovery Approaches: Panic ModeDiscard tokens until we see a “synchronizing” token.ExampleSkip to next occurrence of} end ;Resume by parsing the next statement !Simple to implement !Commonly used !The key.Good set of synchronizing tokensKnowing what to do then !May skip over large sections of source Harry H. Porter, 200511Syntax Analysis - Part 1Error Recovery Approaches: Phrase-Level RecoveryCompiler corrects the programby deleting or inserting tokens.so it can proceed to parse from where it was.Examplewhile (x 4)y : a b; .Insert do to “fix” the statement. !The key.Don’t get into an infinite loop.constantly inserting tokens.and never scanning the actual source Harry H. Porter, 200512
Syntax Analysis - Part 1Error Recovery Approaches: Error ProductionsAugment the CFG with “Error Productions”Now the CFG accepts anything!If “error productions” are used.Their actions:{ print (“Error.”) }Used with. LR (Bottom-up) parsing !Parser GeneratorsError Recovery Approaches: Global CorrectionTheoretical ApproachFind the minimum change to the source to yield a valid program(Insert tokens, delete tokens, swap adjacent tokens)Impractical algorithms - too time consuming Harry H. Porter, 200513Syntax Analysis - Part 1CFG: Context Free GrammarsExample Rule:Stmt " if Expr then Stmt else StmtTerminalsKeywordselse “else”Token ClassesID INTEGER REALPunctuation;“;”;Non-terminalsAny symbol appearing on the lefthand side of any ruleStart SymbolUsually the non-terminal on the lefthand side of the first ruleRules (or “Productions”)BNF: Backus-Naur Form / Backus-Normal FormStmt :: if Expr then Stmt else Stmt Harry H. Porter, 200514
Syntax Analysis - Part 1Rule AlternativesEEEE"E E"(E)"-E" IDE "E E"(E)"-E" IDAll Notations are EquivalentE "E E (E) -E IDE "E E (E) -E ID Harry H. Porter, 200515Syntax Analysis - Part 1Notational ConventionsTerminalsa b c .NonterminalsA B C .SExprGrammar Symbols (Terminals or Nonterminals)X Y Z U V W .Strings of Symbols# % .Strings of Terminalsx y z u v w .A sequence of zeroOr more terminalsAnd nonterminalsIncluding &ExamplesA"#BA rule whose righthand side ends with a nonterminalA"x#A rule whose righthand side begins with a string of terminals (call it “x”) Harry H. Porter, 200516
Syntax Analysis - Part 1Derivations1.2.3.4.5.E "E E"E*E"(E)"-E" IDA “Derivation” of “(id*id)”E ! (E) ! (E*E) ! (id*E) ! (id*id)“Sentential Forms”A sequence of terminals and nonterminals in a derivation(id*E) Harry H. Porter, 200517Syntax Analysis - Part 1Derives in one step !If A " is a rule, then we can write#A% ! # %Any sentential form containing a nonterminal (call it A). such that A matches the nonterminal in some rule.Derives in zero-or-more steps !*E !*If #(id*id)!* and ! %, then # !* %Derives in one-or-more steps ! Harry H. Porter, 200518
Syntax Analysis - Part 1GivenGSA grammarThe Start SymbolDefineL(G) The language generatedL(G) { w S ! w}“Equivalence” of CFG’sIf two CFG’s generate the same language, we say they are “equivalent.”G1 ' G2 whenever L(G1) L(G2)In making a derivation.Choose which nonterminal to expandChoose which rule to apply Harry H. Porter, 200519Syntax Analysis - Part 1Leftmost DerivationsIn a derivation. always expand the leftmost nonterminal.E!E E!(E) E!(E*E) E!(id*E) E!(id*id) E!(id*id) id1.2.3.4.5.E "E E"E*E"(E)"-E" IDLet !LM denote a step in a leftmost derivation (!LM* means zero-or-more steps )At each step in a leftmost derivation, we havewA% !LM w %where A " is a rule(Recall that w is a string of terminals.)Each sentential form in a leftmost derivation is called a “left-sentential form.”If S!LM* # Harry H. Porter, 2005then we say # is a “left-sentential form.”20
Syntax Analysis - Part 1Rightmost DerivationsIn a derivation. always expand the rightmost nonterminal.E1.!E E2.!E id3.!(E) id4.!(E*E) id5.!(E*id) id!(id*id) idE "E E"E*E"(E)"-E" IDLet !RM denote a step in a rightmost derivation (!RM* means zero-or-more steps )At each step in a rightmost derivation, we have#Aw !RM # wwhere A " is a rule(Recall that w is a string of terminals.)Each sentential form in a rightmost derivation is called a “right-sentential form.”If S!RM* #then we say # is a “right-sentential form.” Harry H. Porter, 200521Syntax Analysis - Part 1Bottom-Up ParsingBottom-up parsers discover rightmost derivations!Parser moves from input string back to S.FollowS !RM* win reverse.At each step in a rightmost derivation, we have#Aw !RM # wwhere A " is a ruleString of terminals (i.e., the rest of the input,which we have not yet seen) Harry H. Porter, 200522
Syntax Analysis - Part 1Parse TreesTwo choices at each step in a derivation. !Which non-terminal to expand !Which rule to use in replacing itThe parse tree remembers only thisLeftmost Derivation:!!!!!!EE E(E) E(E*E) E(id*E) E(id*id) E(id*id) id1. E " E E2."E*E3."(E)4."-E5." IDEE E(E)idE*Eidid Harry H. Porter, 200523Syntax Analysis - Part 1Parse TreesTwo choices at each step in a derivation. !Which non-terminal to expand !Which rule to use in replacing itThe parse tree remembers only thisRightmost Derivation:!!!!!!E1. E " E E2."E*E3."(E)4."-E5." IDE E(E)idE*Eid Harry H. Porter, 2005EE EE id(E) id(E*E) id(E*id) id(id*id) idid24
Syntax Analysis - Part 1Parse TreesTwo choices at each step in a derivation. !Which non-terminal to expand !Which rule to use in replacing itThe parse tree remembers only thisLeftmost Derivation:!!!!!!Rightmost Derivation:EE E(E) E(E*E) E(id*E) E(id*id) E(id*id) id1. E " E E2."E*E3."(E)4."-E5." ID!!!!!!EE E(E)idE*idEE EE id(E) id(E*E) id(E*id) id(id*id) idEid Harry H. Porter, 200525Syntax Analysis - Part 1Given a leftmost derivation, we can build a parse tree.Given a rightmost derivation, we can build a parse tree.Lefttmost Derivation ofRightmost Derivation of(id*id) id(id*id) idSame Parse TreeEvery parse tree corresponds to. A single, unique leftmost derivation A single, unique rightmost derivationAmbiguity:However, one input string may have several parse trees!!!Therefore: !Several leftmost derivations !Several rightmost derivations Harry H. Porter, 200526
Syntax Analysis - Part 1Ambuiguous GrammarsELeftmost Derivation #1!!!!!EE Eid Eid E*Eid id*Eid id*idE EidE*Input: id id*idEididLeftmost Derivation #2!!!!!1. E " E E2."E*E3."(E)4."-E5." IDEE*EE E*Eid E*Eid id*Eid id*idEEidE*E Eidid Harry H. Porter, 200527Syntax Analysis - Part 1Ambiguous GrammarMore than one Parse Tree for some sentence.The grammar for a programming language may be ambiguousNeed to modify it for parsing.Also: Grammar may be left recursive.Need to modify it for parsing. Harry H. Porter, 200528
Syntax Analysis - Part 1Translating a Regular Expression into a CFGFirst build the NFA.For every state in the NFA.Make a nonterminal in the grammarFor every edge labeled c from A to B.Add the ruleA " cBFor every edge labeled & from A to B.Add the ruleA" BFor every final state B.Add the ruleB" & Harry H. Porter, 200529Syntax Analysis - Part 1Recursive Transition NetworksRegular Expressions ( NFA ( DFAContext-Free Grammar ( Recursive Transition NetworksExactly as expressive a CFGs. But clearer for Stmt.Stmtelseend.;Terminal Symbols: Harry H. Porter, 2005Nonterminal Symbols:30
Syntax Analysis - Part 1The Dangling “Else” ProblemThis grammar is ambiguous!Stmt " if Expr then Stmt" if Expr then Stmt else Stmt" .Other Stmt Forms.Example String: if E1 then if E2 then S1 else S2Interpretation #1: if E1 then (if E2 then S1) else S2SifE1thenifSE2elsethenS2S1Interpretation #2: if E1 then (if E2 then S1 else S2)SifE1ifE2thenthenSS1elseS2 Harry H. Porter, 200531Syntax Analysis - Part 1The Dangling “Else” ProblemGoal: “Match else-clause to the closest if without an else-clause already.”Solution:StmtWithElse"""""if Expr then Stmtif Expr then WithElse else Stmt.Other Stmt Forms.if Expr then WithElse else WithElse.Other Stmt Forms.Any Stmt occurring between then and else must have an else.i.e., the Stmt must not end with “then Stmt”.Interpretation #2: if E1 then (if E2 then S1 else S2)StmtififE1E2thenStmtthen WithElse else WithElseS1 Harry H. Porter, 2005S232
Syntax Analysis - Part 1The Dangling “Else” ProblemGoal: “Match else-clause to the closest if without an else-clause already.”Solution:StmtWithElse"""""if Expr then Stmtif Expr then WithElse else Stmt.Other Stmt Forms.if Expr then WithElse else WithElse.Other Stmt Forms.Any Stmt occurring between then and else must have an else.i.e., the Stmt must not end with “then Stmt”.Interpretation #1: if E1 then (if E2 then S1) else S2StmtifE1thenWithElseelseStmt Harry H. Porter, 200533Syntax Analysis - Part 1The Dangling “Else” ProblemGoal: “Match else-clause to the closest if without an else-clause already.”Solution:StmtWithElse"""""if Expr then Stmtif Expr then WithElse else Stmt.Other Stmt Forms.if Expr then WithElse else WithElse.Other Stmt Forms.Any Stmt occurring between then and else must have an else.i.e., the Stmt must not end with “then Stmt”.Interpretation #1: if E1 then (if E2 then S1) else S2StmtififE2 Harry H. Porter, 2005E1thenWithElseelseStmtthen WithElse else WithElse34
Syntax Analysis - Part 1The Dangling “Else” ProblemGoal: “Match else-clause to the closest if without an else-clause already.”Solution:StmtWithElse"""""if Expr then Stmtif Expr then WithElse else Stmt.Other Stmt Forms.if Expr then WithElse else WithElse.Other Stmt Forms.Any Stmt occurring between then and else must have an else.i.e., the Stmt must not end with “then Stmt”.Interpretation #1: if E1 then (if E2 then S1) else S2StmtififE2E1thenWithElseelseStmtthen WithElse else WithElseOops, No Match! Harry H. Porter, 200535Syntax Analysis - Part 1Top-Down ParsingFind a left-most derivationFind (build) a parse treeStart building from the root and work down.As we search for a derivation.Must make choices: !Which rule to use !Where to use itMay run into problems!Option 1:“Backtracking”Made a bad decisionBack up and try another choiceOption 2:Always make the right choice.Never have to backtrack: “Predictive Parser”Possible for some grammars (LL Grammars)May be able to fix some grammars (but not others) !Eliminate Left Recursion !Left-Factor the Rules Harry H. Porter, 200536
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbd Harry H. Porter, 200537Syntax Analysis - Part 1BacktrackingInput: aabbdeSA Harry H. Porter, 2005a1.2.3.4.5.6.7.S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbd38
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaaS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdB Harry H. Porter, 200539Syntax Analysis - Part 1BacktrackingInput: aabbdeSAaa Harry H. Porter, 2005a1.2.3.4.5.6.7.S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdB40
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaaS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdB Harry H. Porter, 200541Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaaBbb Harry H. Porter, 2005S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdb42
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaaBbbS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdb Harry H. Porter, 200543Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaaBbb Harry H. Porter, 2005S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdb44
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaaBbbS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdbFailure Occurs Here!!! Harry H. Porter, 200545Syntax Analysis - Part 1BacktrackingInput: aabbdeSAaaa1.2.3.4.5.6.7.S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdBWe need an ability toback up in the input!!! Harry H. Porter, 200546
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbd Harry H. Porter, 200547Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaa Harry H. Porter, 2005abS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbda48
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaabS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbda Harry H. Porter, 200549Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaa Harry H. Porter, 2005abS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbda50
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaabS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbda Harry H. Porter, 200551Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaaabS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdaFailure Occurs Here!!! Harry H. Porter, 200552
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SAaS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbd Harry H. Porter, 200553Syntax Analysis - Part 1BacktrackingInput: aabbdeS Harry H. Porter, 20051.2.3.4.5.6.7.S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbd54
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SCeS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbd Harry H. Porter, 200555Syntax Analysis - Part 1BacktrackingInput: aabbdeSCaa Harry H. Porter, 2005e1.2.3.4.5.6.7.S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdD56
Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SCaeaDbbS " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdd Harry H. Porter, 200557Syntax Analysis - Part 1BacktrackingInput: aabbde1.2.3.4.5.6.7.SCaeaDbb Harry H. Porter, 2005S " Aa" CeA " aaB" aabaB " bbbC " aaDD " bbdd58
Syntax Analysis - Part 1Predictive ParsingWill never backtrack!Requirement:For every rule:A " #1 #2 #3 . #NWe must be able to choose the correct alternativeby looking only at the next symbolMay peek ahead to the next symbol (token).ExampleA" aB" cD"EAssuming a,c ) FIRST (E)ExampleStmt " if Expr ." for LValue ." while Expr ." return Expr ." ID . Harry H. Porter, 200559Syntax Analysis - Part 1Predictive ParsingLL(1) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next 1 input symbol Harry H. Porter, 200560
Syntax Analysis - Part 1Predictive ParsingLL(1) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next 1 input symbolLL(k) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next k input symbols Harry H. Porter, 200561Syntax Analysis - Part 1Predictive ParsingLL(1) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next 1 input symbolLL(k) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next k input symbolsTechniques to modify the grammar: !Left Factoring !Removal of Left Recursion Harry H. Porter, 200562
Syntax Analysis - Part 1Predictive ParsingLL(1) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next 1 input symbolLL(k) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next k input symbolsTechniques to modify the grammar: !Left Factoring !Removal of Left RecursionBut these may not be enough! Harry H. Porter, 200563Syntax Analysis - Part 1Predictive ParsingLL(1) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next 1 input symbolLL(k) GrammarsCan do predictive parsingCan select the right ruleLooking at only the next k input symbolsTechniques to modify the grammar: !Left Factoring !Removal of Left RecursionBut these may not be enough!LL(k) LanguageCan be described with an LL(k) grammar. Harry H. Porter, 200564
Syntax Analysis - Part 1Left-FactoringProblem:Stmt" if Expr then Stmt else Stmt" if Expr then Stmt" OtherStmtWith predictive parsing, we need to know which rule to use!(While looking at just the next token) Harry H. Porter, 200565Syntax Analysis - Part 1Left-FactoringProblem:Stmt" if Expr then Stmt else Stmt" if Expr then Stmt" OtherStmtWith predictive parsing, we need to know which rule to use!(While looking at just the next token)Solution:Stmt" if Expr then Stmt ElsePart" OtherStmtElsePart " else Stmt & Harry H. Porter, 200566
Syntax Analysis - Part 1Left-FactoringProblem:Stmt" if Expr then Stmt else Stmt" if Expr then Stmt" OtherStmtWith predictive parsing, we need to know which rule to use!(While looking at just the next token)Solution:Stmt" if Expr then Stmt ElsePart" OtherStmtElsePart " else Stmt &General Approach:Before: A" # 1 # 2 # 3 . *1 *2 *3 .After:AC" #C *1 *2 *3 ." 1 2 3 . Harry H. Porter, 200567Syntax Analysis - Part 1Left-FactoringProblem:StmtA" if Expr then Stmt else Stmt#& 1# 2" if Expr then Stmt" OtherStmt*1With predictive parsing,we need to know which rule to use!(While looking at just the next token)Solution:Stmt" if Expr then Stmt ElsePart" OtherStmtElsePart " else Stmt &General Approach:Before: A" # 1 # 2 # 3 . *1 *2 *3 .After: Harry H. Porter, 2005AC" #C *1 *2 *3 ." 1 2 3 .68
Syntax Analysis - Part 1Left-FactoringProblem:StmtA" if Expr then Stmt else Stmt#& 1# 2" if Expr then Stmt" OtherStmt*1With predictive parsing,we need to know which rule to use!(While looking at just the next token)Solution:Stmt" if Expr then Stmt ElsePart#AC" OtherStmt*1ElsePart " else Stmt &C 2General Approach: 1Before: A" # 1 # 2 # 3 . *1 *2 *3 .After:AC" #C *1 *2 *3 ." 1 2 3 . Harry H. Porter, 200569Syntax Analysis - Part 1Left RecursionWheneverA ! A#Simplest Case: Immediate Left RecursionGiven:A " A# Transform into:A " A'A' " #A' &where A' is a new nonterminalMore General (but still immediate):A " A#1 A#2 A#3 . 1 2 3 .Transform into:A " 1A' 2A' 3A' .A' " #1A' #2A' #3A' . & Harry H. Porter, 200570
Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes. Harry H. Porter, 200571Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Harry H. Porter, 200572
Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! Sdf Harry H. Porter, 200573Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! SdfApproach:Look at the rules for S only (ignoring other rules). No left recursion. Harry H. Porter, 200574
Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! SdfApproach:Look at the rules for S only (ignoring other rules). No left recursion.Look at the rules for A. Harry H. Porter, 200575Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! SdfApproach:Look at the rules for S only (ignoring other rules). No left recursion.Look at the rules for A.Do any of A’s rules start with S? Yes.A " Sd Harry H. Porter, 200576
Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! SdfApproach:Look at the rules for S only (ignoring other rules). No left recursion.Look at the rules for A.Do any of A’s rules start with S? Yes.A " SdGet rid of the S. Substitute in the righthand sides of S.A " Afd bd Harry H. Porter, 200577Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! SdfApproach:Look at the rules for S only (ignoring other rules). No left recursion.Look at the rules for A.Do any of A’s rules start with S? Yes.A " SdGet rid of the S. Substitute in the righthand sides of S.A " Afd bdThe modified grammar:S " Af bA " Ac Afd bd e Harry H. Porter, 200578
Syntax Analysis - Part 1Left Recursion in More Than One StepExample:S " Af bA " Ac Sd eIs A left recursive? Yes.Is S left recursive? Yes, but not immediate left recursion.S ! Af ! SdfApproach:Look at the rules for S only (ignoring other rules). No left recursion.Look at the rules for A.Do any of A’s rules start with S? Yes.A " SdGet rid of the S. Substitute in the righthand sides of S.A " Afd bdThe modified grammar:S " Af bA " Ac Afd bd eNow eliminate immediate left recursion involving A.S " Af bA " bdA' eA'A' " cA' fdA' & Harry H. Porter, 200579Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd e Harry H. Porter, 200580
Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kAssume there are still more nonterminals;Look at the next one. Harry H. Porter, 200581Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' & Harry H. Porter, 200582
Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " Ag Sh kLook at the B rules next;Does any righthand sidestart with “S”? Harry H. Porter, 200583Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " Ag Afh bh kSubstitute, using the rules for “S”Af. b. Harry H. Porter, 200584
Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " Ag Afh bh kDoes any righthand sidestart with “A”? Harry H. Porter, 200585Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " Ag Afh bh kDo this one first. Harry H. Porter, 200586
Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " bdA'g BeA'g Afh bh kSubstitute, using the rules for “A”bdA'. BeA'. Harry H. Porter, 200587Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " bdA'g BeA'g Afh bh kDo this one next. Harry H. Porter, 200588
Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " bdA'g BeA'g bdA'fh BeA'fh bh kSubstitute, using the rules for “A”bdA'. BeA'. Harry H. Porter, 200589Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " bdA'g BeA'g bdA'fh BeA'fh bh k Harry H. Porter, 2005Finally, eliminate any immediateLeft recursion involving “B”90
Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd BeB " Ag Sh kSo Far:S " Af bA " bdA' BeA'A' " cA' fdA' &B " bdA'gB' bdA'fhB' bhB' kB'B' " eA'gB' eA'fhB' &Finally, eliminate any immediateLeft recursion involving “B” Harry H. Porter, 200591Syntax Analysis - Part 1Left Recursion in More Than One StepThe Original Grammar:S " Af bA " Ac Sd Be CIf there is another nonterminal,B " Ag Sh kthen do it next.C " BkmA AS jSo Far:S " Af bA " bdA' BeA' CA'A' " cA' fdA' &B " bdA'gB' bdA'fhB' bhB' kB' CA'gB' CA'fhB'B' " eA'gB' eA'fhB' & Harry H. Porter, 200592
Syntax Analysis - Part 1Algorithm to Eliminate Left RecursionAssume the nonterminals are ordered A1, A2, A3,.(In the example: S, A, B)for each nonterminal Ai (for i 1 to N) dofor each nonterminal Aj (for j 1 to i-1) doLet Aj " 1 2 3 . N be all the rules for Ajif there is a rule of the formA i " Aj #then replace it byAi " 1# 2# 3# . N#endIfendForA1Eliminate immediate left recursionA2among the Ai rulesA3Inner LoopendFor.Aj.A7AiOuter Loop Harry H. Porter, 200593Syntax Analysis - Part 1Table-Driven Predictive Parsing AlgorithmAssume that the grammar is LL(1)i.e., Backtracking will never be neededAlways know which righthand side to choose (with one look-ahead) !No Left Recursion ! Grammar is Left-Factored.ExampleE "E' "T "T' "F "Step 1:Step 2:Term .T E' T E' &F T'* F T' &( E ) id Term Term . TermFactor .* Factor * Factor * . * FactorFrom grammar, construct table.Use table to parse strings. Harry H. Porter, 200594
Syntax Analysis - Part 1E "E' "T "T' "F "Table-Driven Predictive Parsing Algorithm(aXYZ Stack ofgrammar symbols* 4 )Input String 3 AlgorithmT E' T E' &F T'* F T' &( E ) idOutputPre-Computed Table: Harry H. Porter, 200595Syntax Analysis - Part 1E "E' "T "T' "F "Table-Driven Predictive Parsing Algorithm(aXYZ Stack ofgrammar symbols* 4 )Input StringidE"TE'T Harry H. Porter, 2005OutputInput Symbols, plus *( E'"&E'"&T'"&T'"&T"FT'T'"&F"id)E"TE'T"FT'T'F E'" TE'E'Nonterminals3AlgorithmPre-Computed Table:E T E' T E' &F T'* F T' &( E ) idT'"*FT'F"(E)96
Syntax Analysis - Part 1E "E' "T "T' "F "Table-Driven Predictive Parsing Algorithm(aXYZ Stack ofgrammar symbols* 4 )Input StringidE"TE'T OutputInput Symbols, plus *(T"FT'FF"id)
The parse tree remembers only this Leftmost Derivation: E! E E! (E) E! (E*E) E! (id*E) E! (id*id) E ! (id*id) id Rightmost Derivation: E! E E! E id! (E) id! (E*E) id! (E*id) id ! (id*id) id E E E E E E id id id * 1.E" E E ( ) 2. " E * E 3. "(E ) 4. "-E 5. " ID 26 Syntax Analysis - Part 1 Harry H. Porter, 2005 Given a leftmost derivation .
team xl team 2. t050710-f xl team 3. t050907-f xl team xl team 4. t050912-f xl team xl team 5. t050825-f xl team xl team 6. t050903-f xl team. 2 7. t050914-f xl team xl team 8. t061018-f xl team 9. t061105-f xl team name xl team 10. t060717-f xl team xl team 11. t070921-f xl team xl team xl team 12. t061116-f xl team. 3 13. 020904-f name/# xl .
What is syntax? When we concentrate on the structure & ordering of components within a sentence studying the syntax of a language Syntax (originally Greek) „putting together‟/ „arrangement‟ Syntax is the study of the rules governing th
1. Launch an instance of SPSS 19 a. At the top-left, click File Open Syntax i. Find you your syntax file, and click [Open] 1. Diabetes_Student.sps is for you to type and/or paste syntax into as you follow along a. Open this one for good practice 2. Diabetes_Workbook.sps is the master file containing all of the correct syntax ii.
SPSS Syntax For Academics . What is Syntax? Instructions to SPSS Just a text file GUI is creating and runing syntax . Why use Syntax Faster - Faster to type than to click - Faster to run Easier - Easy to do the same thing with different variables
It is advisable to keep a copy of the original syntax file supplied by Statistics Canada as a reference when making modifications to the syntax file in order to load the data into Equinox. Action Normally, the DLI program stores SPSS syntax files in the documentation (DOC) directory for the survey.
Round 3 Game 1 Game 2 Game 3 Game 4 Team 1 Team 7 Team 8 Team 2 Team 6 Team 5 Team 4 Team 3 Continuing the method, which team plays Team 7 in Round 4? Team . 14 Infection Model This is a simple example of how people in a community might become infected with a disease. O
File-AID/MVS Batch Reference. Notation Rules . This manual uses the following notation rules when describing File-AID/Batch control card syntax: † Parameter syntax is shown in syntax boxes. Des criptions of the parameter elements are below the syntax box. † All keywords are printed in uppercase letters.
Syntax Definition: The way an author chooses to join words into phrases, clauses, and sentences. Syntax is similar to diction, but you can differentiate them by thinking of syntax as the groups of words, which diction refers to the individual words. Expect to be asked about how the author manipulates syntax to accomplish his/her purpose
