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.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Chapter 2, "Context-free languages," up through 2.1, "Context-free grammars," pages 99-109
Additional dependencies:
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Chapter 5, "Context-free grammars and languages," pages 171-215
See also
-No Additional Notes-