Phrase-Structure Grammars

A phrase-structure grammar (PSG) is a finite recipe that can describe an
infinite language. It is the workhorse of syntax in formal language theory.

Definition 7.2.1 (notes p. 134): A PSG is a 4-tuple

A production rule $h \to b$ says "rewrite $h$ as $b$". We may write
$h \to b_1 \mid b_2 \mid \dots \mid b_n$ as a shorthand for $n$ rules with the
same head.

Derivation (Definition 7.2.2): $s$ derives $t$ in one step, written
$s \Rightarrow_G t$, if there is a production rule $h \to b$ and strings $u, v$
such that $s = uhv$ and $t = ubv$. We write $\Rightarrow^*_G$ for the
reflexive-transitive closure (zero or more steps).

Sentential form (Definition 7.2.3): any $s$ reachable from $S$ via $\Rightarrow^*_G$.
A sentence is a sentential form with no nonterminals — i.e., a string in
$\Sigma^*$.

Language generated (Definition 7.2.4): $L(G)$ is the set of all sentences of $G$.

Two grammars are equivalent (Definition 7.2.5) iff they generate the same
language.

A PSG with rule set $P$ is often split into two parts:

• Lexical rules (Def 2.10): produce individual words / tokens / lexemes from characters. Example: Det → the | a | an.
• Structural / syntactic rules (Def 2.11): combine words into phrases. Example: NP → Det N | Pron.

A lexicon (or vocabulary, Def 2.11) is the set of terminal strings produced by the lexical rules — i.e. the 'words' of the language. The syntactic categories (Def 2.12) are the nonterminals of the structural rules (e.g. NP, VP, S).

This split mirrors how real NLP systems work: a lexer/tokeniser first chops the input into tokens, then a parser builds the phrase structure.

Definition 2.7. Parsing is syntax analysis — given a string $s$ and a grammar $G$, decide whether $s \in L(G)$ and produce a parse tree if so.

Parsing is the inverse of derivation: derivation goes from $S$ outward to a string; parsing goes from a string back to $S$ (and the tree of how).