Scribd Logo
Upload

Welcome to Scribd!

  • 72 views

    Context-Free Grammars Example Grammar: Arithmetic Expressions

    Uploaded by

    Abir Dutta
    1) Context-free grammars are defined as 4-tuples that specify a set of nonterminals, terminals, production rules, and a starting symbol. 2) Parse trees can be constructed from derivations to represent the structure of strings generated by a grammar. 3) Grammars can be ambiguous if strings have more than one possible parse tree, such as through left and right recursion of nonterminals. Techniques like eliminating recursion can resolve ambiguities.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Context-Free Grammars Example Grammar: Arithmetic Expressions

    Uploaded by

    Abir Dutta
    72 views4 pages
    1) Context-free grammars are defined as 4-tuples that specify a set of nonterminals, terminals, production rules, and a starting symbol. 2) Parse trees can be constructed from derivations to represent the structure of strings generated by a grammar. 3) Grammars can be ambiguous if strings have more than one possible parse tree, such as through left and right recursion of nonterminals. Techniques like eliminating recursion can resolve ambiguities.

    Original Description:

    grammar

    Original Title

    3grammars.4up

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1) Context-free grammars are defined as 4-tuples that specify a set of nonterminals, terminals, production rules, and a starting symbol. 2) Parse trees can be constructed from derivations to represent the structure of strings generated by a grammar. 3) Grammars can be ambiguous if strings have more than one possible parse tree, such as through left and right recursion of nonterminals. Techniques like eliminating recursion can resolve ambiguities.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    72 views4 pages

    Context-Free Grammars Example Grammar: Arithmetic Expressions

    Uploaded by

    Abir Dutta
    1) Context-free grammars are defined as 4-tuples that specify a set of nonterminals, terminals, production rules, and a starting symbol. 2) Parse trees can be constructed from derivations to represent the structure of strings generated by a grammar. 3) Grammars can be ambiguous if strings have more than one possible parse tree, such as through left and right recursion of nonterminals. Techniques like eliminating recursion can resolve ambiguities.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    CS 326 Lecture 3 Context Free Grammars

    CS 326 Lecture 3 Context Free Grammars

    Context-free Grammars
    Def: A Context-free Grammar (CFG) is a 4-tuple G=(N, !, P, S) where: 1. N is a finite, nonempty set of symbols (non-terminals) 2. ! is a finite set of symbols (terminals) 3. N * ! =+ 4. V, N$ ! (vocabulary) 5. S & N (Goal symbol or start symbol) 6. P is a finite subset of N - V* (Production rules). Sometimes written as G=(V, !, P,S), N = V \ !.

    Example Grammar: Arithmetic Expressions


    G = (N, !, P, E) where: N = { E, T, F} ! = { (, ), +, *, id} P = { E "T E"E+T T"F T " T*F F " id F " (E) } Note: P # NxV*, where V = N $ ! = { E,T,F,C,(,),+,*,id} Note: (A, % ) & P is usually written A"% or A :: = % or A : %

    University of Illinois at Urbana-Champaign

    Page 1

    University of Illinois at Urbana-Champaign

    Page 2

    CS 326 Lecture 3 Context Free Grammars

    CS 326 Lecture 3 Context Free Grammars

    Derivations of a Grammar
    Directly Derives or ': If % and ( are strings in V* (vocabulary), then % directly derives ( (written % ' () iff there is a production A") s.t. A is a symbol in % Substituting string ) for A in % produces the string ( Canonical Derivation Step: The above derivation step is called rightmost if A is the rightmost nonterminal in %. (Similarly, leftmost.) A rightmost derivation step is also called canonical.

    Derivations and Sentential Forms


    Derivation: A sequence of steps %0 ' %1 ' %2 ' ' %n where %0 = S is called a derivation. It is written S '* %n If every derivation step is rightmost, then this is a canonical derivation. Sentential Form Each %i in a derivation is called a sentential form of G. Sentences and the Language L(G) A sentential form %i consisting only of tokens (i.e., terminals) is called a sentence of G. The language generated by G is the set of all sentences of G. It is denoted L(G).
    University of Illinois at Urbana-Champaign
    Page 4

    University of Illinois at Urbana-Champaign

    Page 3

    CS 326 Lecture 3 Context Free Grammars

    CS 326 Lecture 3 Context Free Grammars

    Parse Trees of a Grammar


    A Parse Tree for a grammar G is any tree in which: The root is labeled with S Each leaf is labeled with a token a (a & !) or . (the empty string) Each interior node is labeled by a non-terminal. If an interior node is labeled A and has children labeled X1Xn , then A " X1Xn is a production of G If A " . is a production in G, then a node labeled A may have a single child labeled . The string formed by the leaf labels (left to right) is the yield of the parse tree.

    Parse Trees (continued)


    An intermediate parse tree is the same as a parse tree except the leaves can be non-terminals. Notes: Every % & L(G)is the yield of some parse tree. Why? Consider a derivation, S ' %1 ' %2 ' ' %n , where %n & L(G) For each %i, we can construct an intermediate parse tree. The last one will be the parse tree for the sentence %n . A parse tree ignores the order in which symbols are replaced to derive a string.

    University of Illinois at Urbana-Champaign

    Page 5

    University of Illinois at Urbana-Champaign

    Page 6

    CS 326 Lecture 3 Context Free Grammars

    CS 326 Lecture 3 Context Free Grammars

    Derivations and Parse Trees


    id * id

    Uniqueness of Derivations
    Derivations and Parse Trees Every parse tree has a unique derivation: Yes? No? Every parse tree has a unique rightmost derivation: Yes? No? Every parse tree has a unique leftmost derivation: Yes? No? Derivations and Strings of the Language Every u & L(G) has a unique derivation: Yes? No? Every u & L(G) has a unique rightmost derivation: Yes? No? Every u & L(G) has a unique leftmost derivation: Yes? No?

    E ' T ' T * F ' T * id


    E T T F

    '

    F * id
    E T T F F

    '

    id * id
    E T T F F

    * id

    id * id

    University of Illinois at Urbana-Champaign

    Page 7

    University of Illinois at Urbana-Champaign

    Page 8

    CS 326 Lecture 3 Context Free Grammars

    CS 326 Lecture 3 Context Free Grammars

    Ambiguity
    Def. A grammar, G, is said to be unambiguous if / u & L(G), 0 exactly one canonical derivation S '* u. Otherwise, G is said to be ambiguous. E.g., Grammar: E " E + E | E * E | ( E ) | id Two parse trees for u = id + id * id
    E E

    Order of Evaluation of Parse Tree


    Note: These are conventions, not theorems Code for a non-terminal is evaluated as a single block I.e., cannot partially execute it, then execute something else, then evaluate the rest A different parse tree would be needed to achieve that E.g. 1: Non-terminal T enforces precedence of * over + E.g. 2: E " E + T enforces left-associativity, E " T + E enforces right-associativity. Parse tree does not specify order of execution of code blocks Must be enforced by the code generated for parent block. Obey:
    * id

    E E id +

    E E E id

    E E + id

    id * id

    These are different syntactic interpretations of the input code


    University of Illinois at Urbana-Champaign
    Page 9

    Operator (e.g, +) cannot be evaluated before operands Associativity rules


    University of Illinois at Urbana-Champaign
    Page 10

    CS 326 Lecture 3 Context Free Grammars

    CS 326 Lecture 3 Context Free Grammars

    Detecting Ambiguity
    Caution: There is no mechanical algorithm to decide whether an arbitrary CFG is ambiguous. But one common kind of ambiguity can be detected: If a symbol, A & N is both left-recursive (I.e., A '+ A%, |%| 1 0) and rightrecursive (i.e., A '+ (2, |(| 1 0), then G is ambiguous, provided that G is reduced (i.e., has no redundant symbols).
    A A

    Removal of Ambiguity: Example 1


    1. Enforce higher precedence for * E"E+E|T T " T * T | id | (E) 2. Eliminate right-recursion for E " E + E and T " T * T. E"E+T|T T " T * id | T * (E) | id | ( E )

    (
    A

    %
    A

    University of Illinois at Urbana-Champaign

    Page 11

    University of Illinois at Urbana-Champaign

    Page 12

    CS 326 Lecture 3 Context Free Grammars

    Removal of Ambiguity: Example 2


    The Infamous Dangling-Else Grammar: Stmt " if expr then stmt | if expr then stmt else stmt | other Solution: Introduce new non-terminals to distinguish matched then/else Stmt " matched_stmt | unmatched_stmt matched_stmt " if expr then matched_stmt else matched_stmt | other unmatched_stmt " if expr then stmt | if expr then matched_stmt else unmatched_stmt
    University of Illinois at Urbana-Champaign
    Page 13

    You might also like