Phrase-Structure Grammars

Phrase-structure grammars (PSG) are the most general kind of grammar — the type 0 grammars of the Chomsky hierarchy. Per the slides Chapter 8 (Def 1.1, p.347), a PSG is a 4-tuple $\langle N, \Sigma, P, S \rangle$ where:
- $N$ — a finite set of nonterminal symbols (placeholders that get rewritten).
- $\Sigma$ — a finite set of terminal symbols (the actual characters of the language). $N \cap \Sigma = \emptyset$.
- $P \subseteq N^+ \times (N \cup \Sigma)^*$ — a finite set of production rules of the form $h \rightarrow b$ (head → body).
- $S \in N$ — a distinguished start symbol.

The language $L(G)$ generated by $G$ is the set of all terminal strings derivable from $S$.

But to talk rigorously about any mathematical object we need more than a pile of sets — we need a way to bundle them together. The slides introduce record data structures (Def 1.2, p.347) for this: container types with named components, accessed via dot notation. C structs, OOP classes, and SML records are all examples. A PSG $\langle N, \Sigma, P, S \rangle$ is naturally a record with four named fields.

The slides go further with structure signatures (Def 1.5, p.349): a tabular overview listing each component, its type, and an accessor name. We will use signatures throughout Chapter 5 to keep track of what each structure contains.