Context Free Grammars

• Context Free Grammars describe Context Free Languages.
• All production rules are of the form A -> b, where A is a non-terminal and b a (possibly empty) string of terminals and non-terminals.
• Require a push down automaton (PDA), which is essentially a FA and a stack.
• Many different kinds of CFGs.
  • Bottom up parsers.
    • Shift-reduce parsers.
    • Operator Precedence parsing.
    • yacc
  • Top down parsers.
    • Recursive Descent parsers.
  • Predictive Parsers (LL(k), LR(k), LALR(k)).

• Parse::RecDescent mostly recognizes CFGs; however, it has enough hooks and features to recognize a subset of CSGs.
• Parse::RecDescent generates top down parsers.
• Parse::RecDescent doesn't generate predictive parsers; its parsers backtrack.