<p>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 <code>A</code> where matrix element <code>A[i,j)</code> corresponding to semiopen interval/segment <code>[i,j)</code> contains all the symbols derived for the substring cut by this interval. For example, given a grammar</p>

<pre><code>S → S + M
   | M
M → M * T
   | T
T → number
</code></pre>

<p>and an input</p>

<pre><code>6 + 7 * 8
</code></pre>

<p>we have</p>

<pre><code>A[2,5) = {M,S}
</code></pre>

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

<p>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.  </p>

CC BY-SA 3.0
2011-05-06T09:15:23.023Z
This is a nice observation!
Neel Krishnaswami
CC BY-SA 3.0
2011-05-05T18:01:00.657Z
2011-05-05T20:40:02.583Z
2011-05-05T20:40:02.583Z
Tegiri Nenashi
<p>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).</p>

CC BY-SA 3.0
2013-09-22T01:06:57.717Z
2013-09-22T01:06:57.717Z
Atamiri
<p>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 <em>set of parse trees</em> 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.</p>

<p>A very elegant way of solving the parsing problem is known as <em>parsing as intersection</em>: 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}&#39;$ a context-free grammar such that $L(\mathcal{G}&#39;)=L(\mathcal{G})\cap L(\mathcal{A})$ and furthermore the set of derivation trees of $\mathcal{G}&#39;$ 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</p>

<ul>
<li>Bar-Hillel, Perles, and Shamir, On formal properties of simple phrase-structure grammars, <em>Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikations-forschung</em> 14:143--172, 1961,</li>
<li>Lang, <a href="http://pauillac.inria.fr/~lang/papers/harder/harder.pdf">Recognition can be harder than parsing</a>, <em>Computational Intelligence</em> 10(4):486--494, 1994, <a href="http://dx.doi.org/10.1111/j.1467-8640.1994.tb00011.x">doi: 10.1111/j.1467-8640.1994.tb00011.x</a>.</li>
</ul>

<p>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}&#39;=\langle N&#39;,\Sigma,P&#39;,S&#39;\rangle$ where
$$\begin{align*}
  N&#39;&amp;=(Q\times (N\cup\Sigma)\times Q)\uplus \{S&#39;\}\\
  P&#39;&amp;=\{S&#39;\to (q,S,q&#39;)\mid q\in I, q&#39;\in F\}\\
    &amp;\:\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)\\&amp;\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\}\\
    &amp;\:\cup\;\{(q,a,q&#39;)\to a\mid (q,a,q&#39;)\in\delta\}\;.
\end{align*}$$
The intuition behind this construction is that a nonterminal $(q,X,q&#39;)$ 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&#39;$.</p>

<p>The beauty of it is that the construction of $\mathcal{G}&#39;$ 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 <em>not</em> 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.</p>

CC BY-SA 3.0
2011-05-11T08:14:34.403Z
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?
NoWhereMan
CC BY-SA 3.0
2011-05-11T09:31:33.053Z
@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).
Sylvain
CC BY-SA 3.0
2011-05-09T08:53:07.983Z
2011-05-10T08:33:46.153Z
2011-05-10T08:33:46.153Z
Sylvain
<p>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).</p>

CC BY-SA 3.0
2011-05-05T11:14:20.493Z
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.
Radu GRIGore
CC BY-SA 3.0
2011-05-05T16:44:45.153Z
In Chapter 5 of Robert Harper's book http://www.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).
Dave Clarke
<fl.formal-languages><automata-theory><parsing>
Formal definition of parser?
NoWhereMan
# Formal definition of parser?

(Asked by: username_0 on 2011-05-05)

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

**Tags:** fl.formal-languages, automata-theory, parsing

> **Comments:**
> **username_1**: 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.  
> **username_2**: In Chapter 5 of Robert Harper's book http://www.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).  

---

## 3 answers

### Answer by username_6 on 2011-05-09. Score: 8 | Accepted answer

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](http://pauillac.inria.fr/~lang/papers/harder/harder.pdf), *Computational Intelligence* 10(4):486--494, 1994, [doi: 10.1111/j.1467-8640.1994.tb00011.x](http://dx.doi.org/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.

> **Comments:**
> **username_0**: 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?  
> **username_6**: @username_0: 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).  

---

### Answer by username_3 on 2011-05-05. Score: 10

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.

> **Comments:**
> **username_4**: This is a nice observation!  

---

### Answer by username_5 on 2013-09-22. Score: 0

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


---

