Rules that decide which strings are valid
A context-free grammar is a set of rewriting rules. It describes which strings are valid, such as every correctly bracketed expression or every sentence of a programming language.
Unlike a regular expression, a grammar can describe nesting. That is why a compiler uses one to read your code.
By the end of this lesson
Note
I can use a grammar to decide whether a string is valid.
Key words
| Word | What it means | Example |
|---|---|---|
| Grammar | a set of rules that builds strings | |
| Terminal | a symbol that stays in the final string | ( |
| Non-terminal | a name that still has to be rewritten | S |
| Rule | one way to rewrite a non-terminal | S becomes (S)S |
| Derivation | the steps from the start symbol to a string | |
| Nesting | one thing inside another of the same kind | ((())) |
The cells students fill in are left blank in this preview.
A grammar rewrites names into symbols
A grammar starts from one special non-terminal, the start symbol, here written S. A rule says what a non-terminal may be replaced with.
Keep replacing non-terminals until only terminals are left. The string you end with is valid. Here the grammar for balanced round brackets has two rules: S becomes (S)S, or S becomes nothing.
Worked example: deriving (()) from S
| Step | String so far | Rule used |
|---|---|---|
| 1 | S | Start symbol |
| 2 | (S)S | S becomes (S)S |
| 3 | ((S)S)S | S becomes (S)S, on the first S inside |
| 4 | (()S)S | S becomes nothing |
| 5 | (())S | S becomes nothing |
| 6 | (()) | S becomes nothing: valid |
The cells students fill in are left blank in this preview.
To check a string, run the rules backwards
A derivation builds a string from S. To decide whether a string is valid, a parser works the other way. It finds a side-by-side pair of brackets that the rules could have made, and takes it out.
If the string shrinks to nothing, it was valid. If it gets stuck, it was not.
Shrinking a string to check brackets
# Run the rules backwards: a pair () next to each other can be taken out.
text = "(()())"
print(text)
while "()" in text:
text = text.replace("()", "", 1)
print(text)
if text == "":
print("balanced")
else:
print("not balanced")
# Change text to "(()" and run again.
A common mistake
Warning
Many people think a grammar is a program that checks a string. It is only a description of which strings are valid. A parser is a separate program that uses the grammar to find a derivation, or to fail. Write the rules first, then the parser.
A grammar can nest and a pattern cannot
The rule S becomes (S)S puts a new S in the middle of a pair. That S can use the same rule again, as deep as you like. This is nesting.
A finite automaton cannot follow it, because it would have to remember how many brackets are open. A parser keeps that count on a stack, a pile where you add and remove only at the top.
Which tool describes which strings
| Strings | Regular expression | Grammar |
|---|---|---|
| Any a then any b: aabbb | Yes: a*b* | Yes |
| Equal a then b: aabb | No | Yes: S becomes aSb or nothing |
| Balanced brackets: (()()) | No | Yes: S becomes (S)S or nothing |
The cells students fill in are left blank in this preview.
A pattern accepts a bracket it cannot match
printf '(())\n(()\n' | grep -E '^\(+\)+$'Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The lab calculator's expr rule
grep -A5 "^expr" ~/compiler/calc.yShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further
Write a grammar for the strings a, b and c joined by plus signs, such as a+b+c. One rule must use the start symbol on both sides of the plus.
Derive a+b+c step by step in a table like the one above, and say how many rules you used.