Context free languages

[jimin-kiim]

• CFG(Context Free Grammar)
• Leftmost and Rightmost Derivations
• Parsing and Ambiguity

[jimin-kiim]

Regular Grammar

• in the case of right linear grammar, the variable can be at most and placed rightmost position

Context Free Grammar(CFG)

• the number of variables can be arbitrary and there's no constraints about the position of the variable.
• all regular grammar is context-free grammar
• a language L is context-free iff there's a context-free grammar G with L = L(G)

[jimin-kiim]

Derivations

• leftmost derivation
• rightmost derivation
• derivation tree

[jimin-kiim]

Parsing

G : CFG w : string

• check if w ∈ L(G) is yes or no (Membership problem)
• and if yes, find a sequence of productions by which w is derived
• Compiler : input string - parser(grammar) - derivation
• Exhaustive Search Parsing(brute force parsing)
  • problem
  • tedious
  • may never terminate
  • solution
  • eliminate λ-production
  • eliminate unit production
  • CFG without λ-production and unit production then Exhaustive Search Parsing can be made into an algorithm that for any string w, either produces a parsing of w or says "no parsing possible"
  • theoretically, parsing is possible for CFGs
  • for general context free grammars, there exists a parsing algorithm that parses a string w in time |w|^3

Ambiguity

• a CFG is ambiguous if some string w ∈ L(G) has two or more derivation trees

• a CFG is ambiguous if some string w ∈ L(G) has two or more leftmost[rightmost] derivations

• to get rid of the ambiguity, precedence to the statements should be given

[jimin-kiim]

Simplifications of Context Free Grammars

• for parsing, eliminating lambda production and unit production is better
• nullable variable : a variable can make a empty string
• lambda production : a production that makes a empty string
• unit production : a production where in both sides there's a single variable
• useless production
  • a derivation that never terminates
  • a derivation which is not reachable from the start symbol
  • variable A is useful if and only if there's at least one string w such that A appears in the derivation of making w starting from the start symbol
    1. removing lambda productions
    2. removing unit productions
    3. removing useless productions
  • find and keep only the variables that produce strings ( remove all the productions related to the rest variables )
  • find and keep only the variables reachable from S

[jimin-kiim]

Normal Forms for Context Free Grammars

Chomsky Normal Form (CNF)

• one variable in the left side
• two variables in the right side
• one symbol in the right side
• Conversion to CNF
  1. introduce new variables for symbols
  2. introduce new intermediate variables for variables
     • from any context free grammar not in CNF can be an equivalent grammar in CNF
     • for any context free grammar (which doesn't produce lambda ) there's an equivalent grammar in CNF

       Greinbach Normal Form (GNF)

     • one variable in the left side
     • one symbol and several variables in the right side
     • Conversion to Greinbach Normal Form
  3. introduce new variables for the symbols not in the leftmost in the right side
• for any context free grammar ( which doesn't produce lambda ) there's an equivalent grammar in Greinbach Normal Form

[jimin-kiim]

Membership Algorithm for CFG

• the CYK(J. Cocke, D. Younger, T. Kasami) algorithm
  • constructing a triangular table
  • table size : n * (n+1) / 2 = O(n^2) sets, n= |w|
  • each set takes O(n) time to compute