context-free grammars

(60 minutes to learn)

Summary

Context-free grammars are a formalism for defining the syntax of formal languages. Strings are generated by applying a sequence of productions, each of which replaces a nonterminal symbol with a sequence of terminals and nonterminals. They are widely used in the implementation of programming languages and in modeling the syntax of natural languages.

Context

-this concept has no prerequisites-

Goals

  • Know the basic terminology: context-free grammars, substitution rules (or productions), variables, terminals, start variable, derivation, parse tree.
  • Define how a context-free grammar specifies a language
  • Be able to design context-free grammars to represent simple languages
  • Define what it means for a CFG to be ambiguous, and give an example of an ambiguous grammar

Core resources (read/watch one of the following)

-Free-

Coursera: Automata
An introductory course on automata and the theory of computation.
Author: Jeffrey D. Ullman

-Paid-

See also

-No Additional Notes-