Context-free grammars, LL(1), recursive descent — and why a parse is a proof.
Feed a machine more opening parentheses than it has states and two depths land in the same state. So no finite state machine checks that every ( has its ). The pumping lemma in one sentence.
The C* grammar has rules that mention each other, factor to expression to term to factor, and cannot be substituted into one rule. It is context-free, not regular.
What decides it is a finite state machine plus a stack: one FSM per rule, and the stack remembers where to return.
The grammar of grammars, in its own notation. A factor contains an expression in brackets, so braces nest, and nesting needs counting: EBNF is context-free, not regular.
So the parser for grammar.md is the kind of parser you write this week: one procedure per rule, and the call stack for the brackets. Nothing breaks: a text about texts is just another text.
Hold this example. It is self-reference on notation, and harmless. Week 8 makes the same move on meaning, a compiler compiling itself, and there the theorems start.
C* is LL(1): read the symbols from left to right, always expand the leftmost non-terminal, and decide which alternative of a rule applies by looking at one symbol. The grammar was designed so that this works — the same principle as the scanner's lookahead, one level up.
LR(1) languages need to be parsed from the right-hand sides backwards and are harder; most production compilers use generated parsers for them. LL(1) can be parsed by hand, with joy, and industry engineers do it routinely: simplify the syntax until it is LL(1), then write the parser.
One procedure per rule, named compile_X for non-terminal X. A non-terminal on the right-hand side is a call. A terminal is a check against symbol and a get_symbol(). { } is a while, [ ] is an if, | is an if-else chain. The grammar is the program.
A literal is used in exactly one place in the grammar, inside factor. So compile_factor looks at one symbol: if it is a value or a string, it calls compile_literal, which consumes it and returns its type — the first grammar attribute of the class.
Left of the bar: compile time, the compiler's memory. Right: runtime, the target's. Compile time is also runtime — for the compiler's own machine code — and keeping the two apart is the single most common difficulty in this class. Read that twice.
x + 7 * y groups as x + (7 * y) because * lives one rule deeper than +: lower precedence, higher in the grammar. That is syntactic, and EBNF can say it.
x - 7 + y groups as (x - 7) + y because the while loop in compile_expression emits code as it goes, left to right. That is associativity, and EBNF cannot say it.
Even + is made left-associative, although addition associates in arithmetic. It does not on a machine with overflow.
A compiler that stops at the first error is a compiler you run a hundred times. So every compile_X begins by synchronising: skip symbols until one arrives that can start an X, report what was skipped, and go on. The generated code may then be nonsense, and that is fine; nobody runs it.
Designing good error handling is more art than science, and selfie's is minimal: a message with the line number and the unexpected symbol. It is also, as week 8 will note, the compiler deciding something — about the text.
A derivation — start symbol, rule, rule, rule, down to the terminals — is a finite object that anyone can check step by step. That is what a proof is. A successful parse constructs one, and the parse tree is the proof written down.
And the parser always terminates: every call consumes symbols or returns, and there are finitely many. Membership in a context-free language is decidable. Everything the parser says is about the text, and everything about the text can be decided.
Whether x was declared. Whether the types match. Whether the program halts. The first two are next week, and they are still about the text. The third never is.
Regular: one rule, no memory. Context-free: many rules, a stack. Above that, grammars a machine can only semi-decide, and above that, the halting problem. Chomsky's ladder is the axis of this class, on the countable side.
Symbols and types: the symbol table, what a type is, and why type checking is proof checking while almost everything else about meaning is not. Assignment: bitwise shift operators, compilation.
Wagner · Siegfried — Barenboim, Kupfer, Berlin 1994. Act I is a riddle contest, three questions each way with a head as the stake, and a sword forged from its own fragments. The leitmotifs are the nonterminals: you recognise Nothung before Siegfried does.
Foundations of Computer Science — Aho and Ullman, free online: grammars and parsing in chapter 11, with BNF where EBNF came from. And, more technical, On the Translation of Languages from Left to Right — Knuth, 1965: LR parsing, the paper that made parser generators possible; recursive descent is what selfie does instead.