Question? Leave a message!




Context free grammars

Context free grammars
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Website URL
Comment
Syntax Analysis www.ThesisScientist.comOutline  Role of parser  Context free grammars  Top down parsing  Bottom up parsing  Parser generators www.ThesisScientist.comThe role of parser token Source Parse tree Intermediate Lexical Rest of Parser program representation Analyzer Front End getNext Token Symbol table www.ThesisScientist.comUses of grammars E - E + T T T - T F F F - (E) id E - TE’ E’ - +TE’ Ɛ T - FT’ T’ - FT’ Ɛ F - (E) id www.ThesisScientist.comError handling  Common programming errors  Lexical errors  Syntactic errors  Semantic errors  Lexical errors  Error handler goals  Report the presence of errors clearly and accurately  Recover from each error quickly enough to detect subsequent errors  Add minimal overhead to the processing of correct progrms www.ThesisScientist.comError-recover strategies  Panic mode recovery  Discard input symbol one at a time until one of designated set of synchronization tokens is found  Phrase level recovery  Replacing a prefix of remaining input by some string that allows the parser to continue  Error productions  Augment the grammar with productions that generate the erroneous constructs  Global correction  Choosing minimal sequence of changes to obtain a globally least-cost correction www.ThesisScientist.comContext free grammars  Terminals  Nonterminals expression - expression + term  Start symbol expression - expression – term expression - term  productions term - term factor term - term / factor term - factor factor - (expression) factor - id www.ThesisScientist.comDerivations  Productions are treated as rewriting rules to generate a string  Rightmost and leftmost derivations  E - E + E E E -E (E) id  Derivations for –(id+id)  E = -E = -(E) = -(E+E) = -(id+E)=-(id+id) www.ThesisScientist.comParse trees  -(id+id)  E = -E = -(E) = -(E+E) = -(id+E)=-(id+id) www.ThesisScientist.comAmbiguity  For some strings there exist more than one parse tree  Or more than one leftmost derivation  Or more than one rightmost derivation  Example: id+idid www.ThesisScientist.comElimination of ambiguity www.ThesisScientist.comElimination of ambiguity (cont.)  Idea:  A statement appearing between a then and an else must be matched www.ThesisScientist.comElimination of left recursion  A grammar is left recursive if it has a non-terminal A + such that there is a derivation A= Aα  Top down parsing methods cant handle left- recursive grammars  A simple rule for direct left recursion elimination:  For a rule like:  A - Aαβ  We may replace it with  A -β A’  A’ -α A’ ɛ www.ThesisScientist.comLeft recursion elimination (cont.)  There are cases like following  S - Aa b  A - Ac Sd ɛ  Left recursion elimination algorithm:  Arrange the nonterminals in some order A1,A2,…,An.  For (each i from 1 to n)  For (each j from 1 to i-1)  Replace each production of the form Ai- Aj γ by the production Ai - δ1 γ δ2 γ … δk γ where Aj- δ1 δ2 … δk are all current Aj productions   Eliminate left recursion among the Ai-productions  www.ThesisScientist.comLeft factoring  Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive or top-down parsing.  Consider following grammar:  Stmt - if expr then stmt else stmt  if expr then stmt  On seeing input if it is not clear for the parser which production to use  We can easily perform left factoring:  If we have A-αβ1 αβ2 then we replace it with  A - αA’  A’ - β1 β2 www.ThesisScientist.comLeft factoring (cont.)  Algorithm  For each non-terminal A, find the longest prefix α common to two or more of its alternatives. If α ɛ, then replace all of A-productions A-αβ1 αβ2 … αβn γ by  A - αA’ γ  A’ - β1 β2 … βn  Example:  S - I E t S i E t S e S a  E - b www.ThesisScientist.comwww.ThesisScientist.comIntroduction  A Top-down parser tries to create a parse tree from the root towards the leafs scanning input from left to right  It can be also viewed as finding a leftmost derivation for an input string  Example: id+idid E E E E E E E - TE’ lm lm lm lm lm E’ - +TE’ Ɛ T E’ T E’ T E’ T E’ T E’ T - FT’ F T’ F T’ F T’ F T’ + T E’ T’ - FT’ Ɛ F - (E) id id id id ƐƐ www.ThesisScientist.comRecursive descent parsing  Consists of a set of procedures, one for each nonterminal  Execution begins with the procedure for start symbol  A typical procedure for a non-terminal void A() choose an A-production, A-X1X2..Xk for (i=1 to k) if (Xi is a nonterminal call procedure Xi(); else if (Xi equals the current input symbol a) advance the input to the next symbol; else / an error has occurred / www.ThesisScientist.comRecursive descent parsing (cont)  General recursive descent may require backtracking  The previous code needs to be modified to allow backtracking  In general form it cant choose an A-production easily.  So we need to try all alternatives  If one failed the input pointer needs to be reset and another alternative should be tried  Recursive descent parsers cant be used for left- recursive grammars www.ThesisScientist.com