Lecture 9 (Context-Free Grammars), 2/20/06

Concepts, definitions (in italics):

• Context Free Grammar, Formal Definition (definition 2.2)
  • Variables (aka non-terminal symbols)
  • Symbols (aka terminal symbols)
  • Substitution Rules (aka rules)
  • Start variable (aka start symbol)
• The length of a derivation: number of substitutions it contains.
• A grammar G generates a string w if there is a derivation for w in G.
• L(G), the language generated by a grammar G: set of all strings generated by G
• A language L₀ is context-free iff there is some context-free grammar G such that L₀ = L(G)
• Two grammars are equivalent iff they generate the same language.
• Parse Trees: root, internal nodes, leaves
• A grammar G generates a string w if there is a parse tree for w in G rooted at S (G's start symbol).
• Parsing: given string w and grammar G, constructing parse tree for w in G
• Applications of parsing in compilers/interpreters.

Reading:

• Chapter 2.1 through middle of p. 105

Skills:

• Know new definitions, understand new concepts
• Given a CFG G and a string w, find a derivation for w in G.
• Given a CFG G, describe L(G).
• Given a description of a language, find a context-free grammar for it.
• What are the root, the internal nodes, and the leaves in a parse tree?
• What is the string generated by a given parse tree?
• Given a derivation, construct the corresponding tree.
• Given a CFG G and a string w, find a parse tree for w in G.

Notes:

• In the book, variables are also called "non-terminal symbols", and symbols are called "terminal symbols".
• Last time we showed that {0ⁿ 1ⁿ : n >= 0}is not a regular language; today we saw that it is a context-free language.
• Backus-Naur form is a special notation for specifying context-free grammars that is often used to describe the syntax of programming languages. Here is the Wikipedia page about it.
• Here is C syntax in Backus-Naur form
• Here is SQL syntax in Backus-Naur form