Formal definition of parser?

Question

I'm looking for an accepted, formal definition of a parser as function $f$ returning an AST, but I cannot find any reference in literature; all I can find is the definition of a recognizer as a function $f:\Sigma^*\to \{0,1\}$ with obviously $f(w)=1$ when $w\in L(G)$ and $0$ otherwise ($G$ being a grammar and $L(G)$ the generated language).

Answer 1

A reasonable formal definition of (context-free) parsing is thus: given $\langle \mathcal{G},w\rangle$ a context-free grammar over some alphabet $\Sigma$ and an input word in $\Sigma^\ast$, return the set of parse trees of $w$ in $\mathcal{G}$ (note that the grammar might be ambiguous, which means that this is indeed a set, which might even be infinite if the grammar is cyclic). Recognition then consists in finding out whether this set is empty or not.

A very elegant way of solving the parsing problem is known as parsing as intersection: context-free languages are effectively closed under intersection with regular languages, i.e. given $\langle \mathcal{G},\mathcal{A}\rangle$ where $\mathcal{G}$ is context-free and $\mathcal{A}$ is a finite-state automaton (a NFA), we can construct $\mathcal{G}'$ a context-free grammar such that $L(\mathcal{G}')=L(\mathcal{G})\cap L(\mathcal{A})$ and furthermore the set of derivation trees of $\mathcal{G}'$ is (a relabelling of) the set of parse trees of all the words in $L(\mathcal{A})$. Of course a single word $w$ can be recognized by a NFA. This construction is almost as old as context-free grammars; see

• Bar-Hillel, Perles, and Shamir, On formal properties of simple phrase-structure grammars, Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikations-forschung 14:143--172, 1961,
• Lang, Recognition can be harder than parsing, Computational Intelligence 10(4):486--494, 1994, doi: 10.1111/j.1467-8640.1994.tb00011.x.

Formally, let $\mathcal{G}=\langle N,\Sigma,P,S\rangle$ with nonterminal alphabet $N$, terminal alphabet $\Sigma$, finite set of productions $P\subseteq N\times (N\cup\Sigma)^\ast$, and start symbol $S\in N$. For the automaton, let $\mathcal{A}=\langle Q,\Sigma,\delta,I,F\rangle$ with state set $Q$, input alphabet $\Sigma$, transition relation $\delta\subseteq Q\times\Sigma\times Q$, initial states $I\subseteq Q$, and final states $F\subseteq Q$. Construct $\mathcal{G}'=\langle N',\Sigma,P',S'\rangle$ where $$\begin{align*} N'&=(Q\times (N\cup\Sigma)\times Q)\uplus \{S'\}\\ P'&=\{S'\to (q,S,q')\mid q\in I, q'\in F\}\\ &\:\cup\;\{(q_0,A,q_m)\to (q_0,X_1,q_1)(q_1,X_2,q_2)\cdots(q_{m-1},X_m,q_m)\\&\qquad\qquad\qquad\qquad\qquad\qquad\mid A\to X_1X_2\cdots X_m\in P\wedge q_0,\ldots,q_m\in Q\}\\ &\:\cup\;\{(q,a,q')\to a\mid (q,a,q')\in\delta\}\;. \end{align*}$$ The intuition behind this construction is that a nonterminal $(q,X,q')$ in $Q\times(N\cup\Sigma)\times Q$ derives the intersection of the language of the symbol $X$ with the language of $\mathcal{A}$ restricted to paths from $q$ to $q'$.

The beauty of it is that the construction of $\mathcal{G}'$ is asymptotically efficient: it has size $$O(|\mathcal{G}|\cdot |Q|^{m+1})$$ with $m$ the maximal length of a production right-hand side. Since without loss of generality we can "binarize" $\mathcal{G}$ so that $P\subseteq N\times(N\cup\Sigma)^{\leq 2}$ at the expense of a linear blowup in the grammar size (this is not the Chomsky normal form, which would forbid $\varepsilon$ and unit productions, and would induce a quadratic blow-up), we obtain an $$O(|\mathcal{G}|\cdot |Q|^3)$$ parsing complexity. As context-free grammar emptiness can be solved in linear time, the recognition problem is also in $O(|\mathcal{G}|\cdot |Q|^3)$, which matches the complexity of the CKY and Earley algorithms since an automaton for $w$ has $|w|+1$ states.

Answer 2

There is more in recognition that appears at the first sight. It is naturally generalized into recognizing all the substrings of a given string so that the output is a matrix A where matrix element A[i,j) corresponding to semiopen interval/segment [i,j) contains all the symbols derived for the substring cut by this interval. For example, given a grammar

S → S + M
   | M
M → M * T
   | T
T → number

and an input

6 + 7 * 8

we have

A[2,5) = {M,S}

i.e. the symbols M and S were derived for the substring 7 * 8 at the interval [2,5). It is essentially a table used by CYK parser. “Principles and Implementation of Deductive Parsing” by Shieber, Schabes, Pereira describes how Earley parsing fits into this framework as well.

Given a parsing matrix, one can recover a parse tree (and contrary to what wikipedia CYK page says, one doesn't have to store backpointers), but the takeout message here is that parsing matrix is more fundamental than the parse tree; in particular, it is well defined even for ambiguous derivation.