37.1. Context-Free Grammars Part 1¶
37.1.1. Context-Free Languages¶
In previous chapters, we saw that some languages are regular languages, which means that we can define a DFA, NFA that recognizes that language, or we can represent it with a regular expression or regular grammar. Here are a few examples of regular languages:
keywords in a programming language
names of identifiers
integers
a finite list of miscillaneous symbols such as \(=\).
We also know that some languages are non-regular, and we learned how to use tools like the Pumping Lemma to prove a given language is non-regular. Examples of non-regular languages include:
\(\{a^ncb^n\ |\ n > 0\}\)
mathematical expressions like \(((a + b) - c)\)
block structures for programming languages (\(\{\}\) in Java/C++ and
begin…endin Pascal)Balanced parentheses
Now we will look at a class of languages that is larger than the class of regular languages, called context-free languages or CFG. Perhaps not surprisingly, a CFL is any language that can be represented by a context-free grammar or CFG.
37.1.2. String Derivation¶
37.1.2.1. Recursive Derivation Practice¶
Construct a derivation of aaabbb using the grammar from the example.
Each correct production application contributes one point toward completion.
37.1.2.2. Palindrome Derivation Practice¶
Construct the palindrome ababa by choosing productions that build matching
outer symbols, then replace the remaining nonterminal with the middle symbol.
37.1.3. Derivation Trees¶
37.1.4. Derivation Trees Example¶
37.1.4.1. Leftmost Derivation Practice¶
Derive aacbb, replacing the leftmost remaining nonterminal at each step.
Applying an empty production also counts as a step. Compare your completed
parse tree with your derivation table.
