# Formal definition of parser?

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).

• Unambiguous grammars give you a parse tree. The AST is a transformation of the parse tree. Keller et al., "Tree transformation techniques and experiences" seems to have some formalization of the latter process. May 5, 2011 at 11:14
• In Chapter 5 of Robert Harper's book cs.cmu.edu/~rwh/plbook/book.pdf you can find a relational definition of what you are looking for (excepts it's not a function). May 5, 2011 at 16:44

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

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.

• let us suppose that we restrict to such subclass of context free (deterministic grammars, right?), then $|\langle \mathcal{G},w\rangle |\leq 1$, is this right? May 11, 2011 at 8:14
• @NoWhereMan: if you consider unambiguous grammars, then the set of parse trees is either a singleton or empty for any $w$. The grammars accepted by deterministic parser generators are unambiguous (being for instance LL(1) or LALR(1)), modulo some ambiguity resolution mechanisms (typically precedence and associativity). May 11, 2011 at 9:31

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.

• This is a nice observation! May 6, 2011 at 9:15

In attribute-value logic, a parser is a function $f: \Sigma^* \rightarrow \Phi_\mathcal{L}$ that takes words to formulae over a (first-order) language. The formulae are usually interpreted as directed acyclic graphs but they could be restricted to trees (ASTs).