<p>A paper at ICFP 2010 this year, <a href="http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.html" rel="nofollow">Total Parser Combinators</a>, describes a provably terminating parser combinator library and also establishes that in this library "parser combinators are as expressive as possible" given that the parser is guaranteed to terminate. Unfortunately I don't remember the explanation the author gave for what "as expressive as possible" means, but it certainly seems relevant to your question about "power."</p>

CC BY-SA 3.0
2013-06-13T09:49:23.723Z
I have a car that does not pollute, Actually it does not move either... So the question is : what kind of language is parsed by this library ?  Not meaning that this work is not interesting, of course.
babou
CC BY-SA 2.5
2010-10-23T05:04:42.087Z
2010-10-23T05:04:42.087Z
Rob Simmons
<p>If you want to go beyond context-free grammars for parsing programming languages, but still parse in polynomial time, you can resort to <a href="http://en.wikipedia.org/wiki/Parsing_expression_grammar" rel="nofollow" title="parsing expression grammars"><em>parsing expression grammars</em></a>, or <em>boolean grammars</em> - the latter are also available in LL and LR flavors (see <a href="http://users.utu.fi/aleokh/" rel="nofollow">here</a>). In formal language theory, also the powerful yet linear-time recognizable <em>Church-Rosser languages</em> are studied, but I am not aware of any implemented parser generators for these.</p>

<p>In natural language processing, tastes are different, for instance, dealing with ambiguity (also: inherent ambiguity) and free word order plays a very prominent role. Here the keywords <a href="http://en.wikipedia.org/wiki/Mildly_context-sensitive_language" rel="nofollow"><em>mildly context sensitive languages</em></a> and <em>restart automata</em> might help you to start reading.   </p>

CC BY-SA 3.0
2013-06-12T22:42:08.173Z
Considering the way the question was asked, and the complaint that CF is too constraining, your answer is clearly the best. So it goes ...
babou
CC BY-SA 4.0
2022-08-12T12:48:11.117Z
The link to Alexander Okhotin doesn't work now - the new website seems to be here: https://users.math-cs.spbu.ru/~okhotin/
Martin
CC BY-SA 2.5
2010-12-22T09:00:40.470Z
2010-12-22T09:00:40.470Z
Hermann Gruber
<p>A grammar is usually defined as a <a href="http://en.wikipedia.org/wiki/Context-free_grammar" rel="noreferrer">Context Free grammar</a> - a precise definition is given on the Wikipedia page, but it works the same as it does in PLY, which is based on <a href="http://en.wikipedia.org/wiki/GNU_bison" rel="noreferrer">Bison</a>, which is in turn based on <a href="http://en.wikipedia.org/wiki/Yacc" rel="noreferrer">yacc</a>.</p>

<p>It says <a href="http://www.dabeaz.com/ply/ply.html#ply_nn36" rel="noreferrer">here</a> that PLY uses a <a href="http://en.wikipedia.org/wiki/LALR" rel="noreferrer">LALR parser</a>. This is essentially an <a href="http://en.wikipedia.org/wiki/LR_parser" rel="noreferrer">LR parser</a> where the lookup tables are condensed, possibly introducing parsing conflicts, reducing some of the expressiveness of an LR grammar (ie, a context free grammar that an LR parser can parse). If you want to know about the limitations of this particular branch of parsers and those of other parsers, an overview of all kinds of parsing techniques (LL, LR and others) is given <a href="http://en.wikipedia.org/wiki/Parser#Examples_of_parsers" rel="noreferrer">here</a>.</p>

<p>To answer your question: there exist parsing algorithms capable of parsing any context-free language, even if the language is ambiguous (ie, there is more than one way to interpret the input):</p>

<p>The first such algorithm was the <a href="http://en.wikipedia.org/wiki/CYK_algorithm" rel="noreferrer">CYK algorithm</a>, which unfortunately has a running time of $O(n^3 |G|)$, where $n$ is the length of the input string and $|G|$ is the size of the grammar and is therefore impractical for parsing languages.</p>

<p>The second algorithm is the <a href="http://en.wikipedia.org/wiki/Earley_parser" rel="noreferrer">Earley algorithm</a>. This algorithm is also capable of parsing any context free grammar. Although the algorithm needs $O(n^3)$ time to parse an ambiguous language, it only needs $O(n^2)$ time to parse an unambiguous language. In addition, it apparently works in linear time for most LR grammars and works particularly well on left-recursive grammars.</p>

<p><a href="http://webhome.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf" rel="noreferrer">Here</a> you can find a paper discussing a practical implementation of (an adaptation of) the Earley algorithm. They conclude: "Given the generality of Earley parsing compared to LALR(1) parsing ((which is roughly what PLY does)), and considering that even PEP’s ((their implementation of Earley's algorithm)) worst time would not be noticeable by a user, this is an excellent result".</p>

<p>The last type of parser is the <a href="http://en.wikipedia.org/wiki/GLR_parser" rel="noreferrer">GLR parser</a>. This is a generalised version of LR parsing, capable of parsing any context-free language.</p>

<p>A mature implementation of GLR is <a href="http://en.wikipedia.org/wiki/ASF%2BSDF_Meta_Environment" rel="noreferrer">ASF+SDF</a>. Bison can also generate a GLR parser, though its implementations is slightly different from the 'standard' GLR algorithm. The <a href="http://scottmcpeak.com/elkhound/sources/elkhound/algorithm.html" rel="noreferrer">Elkhound Algorithm</a> is a GLR/LALR hybrid algorithm. It uses LALR when possible and GLR when needed, in order to be both fast and capable of parsing any grammar.</p>

<p>Beyond context free grammars there are <a href="http://en.wikipedia.org/wiki/Context-sensitive_grammar" rel="noreferrer">context sensitive grammars</a>, but these are in general hard to parse and don't add that much expressiveness: you can do more with them, but for most applications the extra uses are not relevant, unless you're parsing a natural language.</p>

<p>As the final step there are <a href="http://en.wikipedia.org/wiki/Unrestricted_grammar" rel="noreferrer">unrestricted grammars</a>. At this point the grammar is Turing-complete, so there is no bound one can give on how long it will take to parse a particular language, which is undesirable for most parsing applications. The extra power is almost never needed. If you do want to use all that power, there is the <a href="http://languagemachine.sourceforge.net/" rel="noreferrer">language machine</a> available.</p>

<p>Lastly, implementing your own parser-generator is not a trivial affair, in particular to get it to be fast. I've personally just finished making my own version of flex (the lexer generator), and while this seemed like an exercise in relatively simple algorithmic problems, it became quite complex to get right, in particular when I tried to support Unicode. Consider using an already existing implementation instead of writing your own.</p>

CC BY-SA 3.0
2013-11-25T09:42:21.043Z
@AlextenBrink do you know that GLL is usually faster, and for what grammars? It is usually faster on worst case grammars, but for PL grammars we have yet to find out. Do you have already more information on this?
Jurgen Vinju
CC BY-SA 3.0
2013-06-12T21:30:54.027Z
What makes you believe that GLR parsing is more effective in time or space than simpler versions of tabular parsing not using the LR construction (there are many) ?  This is not an idle question. (I am not talking of complexity class, which is more or less the same for all).
babou
CC BY-SA 3.0
2013-06-13T08:17:11.707Z
@babou: I assume you are talking about algorithms like CYK and Earley. CYK is always cubic, so it is not very useful on near-deterministic grammars that occur in practice. If you take Earley and optimize it, you get GLL, a relatively new generalized parsing algorithm, that is usually even faster than GLR. The original Earley algorithm is not that fast (talking about constant factors) because it often needs to do a linear search for things that GLL already has a pointer to.
Alex ten Brink
CC BY-SA 3.0
2013-06-13T09:13:39.727Z
@Alex  No, I am not talking about CYK, obviously, nor Earley. I am
talking more abstractedly about the effect of predictiveness on the
efficiency of this family of parsing algorithms. That would actually
make a nice question by itself. Also parsing is supposed to produce
parse trees (or forests). Would you think that the result is not impacted by the chosen algorithm ? These are not idle
questions when you extend parsing techniques beyond the standard CF.
babou
CC BY-SA 3.0
2014-11-14T17:23:56.083Z
@jurgenv This [paper by Billot and
Lang](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) may shed
some light on this. They built a system that implements in a uniform
way various general CF parsers, for systematic comparison rather than
for production purpose. The analysis of their effectiveness on various
grammars give hints regarding the some reasons for the compared
efficiencies of different parsing strategies.
babou
CC BY-SA 2.5
2010-10-23T00:44:05.347Z
Excellent answer!! Any thoughts on how PEGs fit in?
Paul Biggar
CC BY-SA 2.5
2010-10-23T01:15:40.043Z
PEGs are 'different' than CFGs: there are CFGs that are not PEGs and vice versa. I refer you to here: http://stackoverflow.com/questions/1857022/limitations-of-peg-grammar-parser-generators.
Alex ten Brink
CC BY-SA 2.5
2010-10-23T01:18:24.000Z
This might also be of interest: http://blogs.ethz.ch/copton/2009/07/08/parsing-expression-grammars/.
Alex ten Brink
CC BY-SA 2.5
2010-10-23T08:48:10.860Z
Actually, most common parser generators (yacc, Antlr, bison) allow non-CF concepts by predicates or arbitrary code that checks wether one rule can be applied resp. deciding precedence. This can be used to implement static semantics mainly since basic syntax remains in essence context free.
Raphael
CC BY-SA 2.5
2010-10-23T20:28:54.263Z
What about recursive languages? is there any real power for languages in them compared to context-sensitive? thanks :)
Lasse Espeholt
CC BY-SA 2.5
2010-10-24T00:19:05.917Z
Recursive languages are precisely the languages decidable by always-halting Turing Machines. Any context sensitive language is therefore also recursive, but since context sensitive languages are decidable in exponential time, there are recursive languages that are not context sensitive. Unrestricted grammars are even more powerful: the halting problem can be described by an unrestricted grammar, but is not a recursive language.
Alex ten Brink
CC BY-SA 2.5
2010-10-24T07:43:33.270Z
Yup, I know the range of languages, but I was wondering what recursive languages brings to the table. An example recursive language which is not context-sensitive :)?
Lasse Espeholt
CC BY-SA 2.5
2010-10-25T00:54:29.693Z
Since deciding membership for a context-sensitive grammar is in PSPACE, any language in EXPSPACE or larger classes is expressable by a recursive grammar but not by a context-sensitive grammar. An example is the language of all true propositions in Presburger arithmetic (http://en.wikipedia.org/wiki/Presburger_arithmetic). Since we suspect that PSPACE $\neq$ EXPTIME, any language in EXPTIME or above would be sufficient. The extra power is almost never needed though - it would take too long to parse anyway.
Alex ten Brink
CC BY-SA 3.0
2010-10-23T00:29:59.683Z
2016-05-23T21:35:17.307Z
2016-05-23T21:35:17.307Z
Alex ten Brink
<p>As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of grammar, and I'm not interested in hacking up my language because of an impedance mismatch with the tool. Therefore, I'm not averse to writing my own.</p>

<p><strong>So what's the most powerful type of parser?</strong> Citations to papers (as well as more introductory articles) would be welcome.</p>

<p><em>(I know that 'powerful' is not precisely defined, but let's be a little loose with it and see where the answers go)</em></p>

CC BY-SA 3.0
2013-06-12T22:28:30.527Z
@Warren There has been much research on this ... the last 20 years are only missing from the answers. Much is in computational linguistics, though it would qualify for TCS. The linguists on stackexchange do a different kind of stuff, I believe.
babou
CC BY-SA 2.5
2010-10-23T01:07:48.460Z
Downvoted: not research level.
Warren Schudy
CC BY-SA 2.5
2010-10-23T01:30:41.603Z
@Warren: I checked the FAQ before asking - that doesn't seem to be a requirement.
Paul Biggar
CC BY-SA 2.5
2010-10-23T01:45:36.250Z
there are actually two FAQs, one for the general site and one for CStheory. The CStheory one indicates that questions that can be answered by e.g. reading Wikipedia are off-topic; see "What kind of questions are too basic?" in http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science .
Warren Schudy
CC BY-SA 2.5
2010-10-23T01:55:16.437Z
@Warren: That's the FAQ I read. I had read wikipedia, but I felt this needed actual insight.
Paul Biggar
CC BY-SA 2.5
2010-10-23T08:44:53.287Z
To you mean parsers in production or theoretical ones, i.e. ones that cover grammar types other than CFG?
Raphael
<fl.formal-languages><pl.programming-languages><grammars>
What is the most powerful kind of parser?
Paul Biggar
# What is the most powerful kind of parser?

(Asked by: username_0 on 2010-10-22)

As a side-project, I'm writing a language using Python. I started by using a flex/bison clone called Ply, but am coming up against the edges in the power of what I can express with that style of grammar, and I'm not interested in hacking up my language because of an impedance mismatch with the tool. Therefore, I'm not averse to writing my own.

**So what's the most powerful type of parser?** Citations to papers (as well as more introductory articles) would be welcome.

*(I know that 'powerful' is not precisely defined, but let's be a little loose with it and see where the answers go)*

**Tags:** fl.formal-languages, pl.programming-languages, grammars
> **Comments:**
> **username_2**: Downvoted: not research level.  
> **username_0**: @Warren: I checked the FAQ before asking - that doesn't seem to be a requirement.  
> **username_2**: there are actually two FAQs, one for the general site and one for CStheory. The CStheory one indicates that questions that can be answered by e.g. reading Wikipedia are off-topic; see "What kind of questions are too basic?" in http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science .  
> **username_0**: @Warren: That's the FAQ I read. I had read wikipedia, but I felt this needed actual insight.  
> **username_3**: To you mean parsers in production or theoretical ones, i.e. ones that cover grammar types other than CFG?  
> **username_1**: @Warren There has been much research on this ... the last 20 years are only missing from the answers. Much is in computational linguistics, though it would qualify for TCS. The linguists on stackexchange do a different kind of stuff, I believe.  

---

## 3 answers

### Answer by username_7 on 2010-10-23. Score: 35 | Accepted answer

A grammar is usually defined as a [Context Free grammar](http://en.wikipedia.org/wiki/Context-free_grammar) - a precise definition is given on the Wikipedia page, but it works the same as it does in PLY, which is based on [Bison](http://en.wikipedia.org/wiki/GNU_bison), which is in turn based on [yacc](http://en.wikipedia.org/wiki/Yacc).

It says [here](http://www.dabeaz.com/ply/ply.html#ply_nn36) that PLY uses a [LALR parser](http://en.wikipedia.org/wiki/LALR). This is essentially an [LR parser](http://en.wikipedia.org/wiki/LR_parser) where the lookup tables are condensed, possibly introducing parsing conflicts, reducing some of the expressiveness of an LR grammar (ie, a context free grammar that an LR parser can parse). If you want to know about the limitations of this particular branch of parsers and those of other parsers, an overview of all kinds of parsing techniques (LL, LR and others) is given [here](http://en.wikipedia.org/wiki/Parser#Examples_of_parsers).

To answer your question: there exist parsing algorithms capable of parsing any context-free language, even if the language is ambiguous (ie, there is more than one way to interpret the input):

The first such algorithm was the [CYK algorithm](http://en.wikipedia.org/wiki/CYK_algorithm), which unfortunately has a running time of $O(n^3 |G|)$, where $n$ is the length of the input string and $|G|$ is the size of the grammar and is therefore impractical for parsing languages.

The second algorithm is the [Earley algorithm](http://en.wikipedia.org/wiki/Earley_parser). This algorithm is also capable of parsing any context free grammar. Although the algorithm needs $O(n^3)$ time to parse an ambiguous language, it only needs $O(n^2)$ time to parse an unambiguous language. In addition, it apparently works in linear time for most LR grammars and works particularly well on left-recursive grammars.

[Here](http://webhome.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf) you can find a paper discussing a practical implementation of (an adaptation of) the Earley algorithm. They conclude: "Given the generality of Earley parsing compared to LALR(1) parsing ((which is roughly what PLY does)), and considering that even PEP’s ((their implementation of Earley's algorithm)) worst time would not be noticeable by a user, this is an excellent result".

The last type of parser is the [GLR parser](http://en.wikipedia.org/wiki/GLR_parser). This is a generalised version of LR parsing, capable of parsing any context-free language.

A mature implementation of GLR is [ASF+SDF](http://en.wikipedia.org/wiki/ASF%2BSDF_Meta_Environment). Bison can also generate a GLR parser, though its implementations is slightly different from the 'standard' GLR algorithm. The [Elkhound Algorithm](http://scottmcpeak.com/elkhound/sources/elkhound/algorithm.html) is a GLR/LALR hybrid algorithm. It uses LALR when possible and GLR when needed, in order to be both fast and capable of parsing any grammar.

Beyond context free grammars there are [context sensitive grammars](http://en.wikipedia.org/wiki/Context-sensitive_grammar), but these are in general hard to parse and don't add that much expressiveness: you can do more with them, but for most applications the extra uses are not relevant, unless you're parsing a natural language.

As the final step there are [unrestricted grammars](http://en.wikipedia.org/wiki/Unrestricted_grammar). At this point the grammar is Turing-complete, so there is no bound one can give on how long it will take to parse a particular language, which is undesirable for most parsing applications. The extra power is almost never needed. If you do want to use all that power, there is the [language machine](http://languagemachine.sourceforge.net/) available.

Lastly, implementing your own parser-generator is not a trivial affair, in particular to get it to be fast. I've personally just finished making my own version of flex (the lexer generator), and while this seemed like an exercise in relatively simple algorithmic problems, it became quite complex to get right, in particular when I tried to support Unicode. Consider using an already existing implementation instead of writing your own.

> **Comments:**
> **username_0**: Excellent answer!! Any thoughts on how PEGs fit in?  
> **username_7**: PEGs are 'different' than CFGs: there are CFGs that are not PEGs and vice versa. I refer you to here: http://stackoverflow.com/questions/1857022/limitations-of-peg-grammar-parser-generators.  
> **username_7**: This might also be of interest: http://blogs.ethz.ch/copton/2009/07/08/parsing-expression-grammars/.  
> **username_3**: Actually, most common parser generators (yacc, Antlr, bison) allow non-CF concepts by predicates or arbitrary code that checks wether one rule can be applied resp. deciding precedence. This can be used to implement static semantics mainly since basic syntax remains in essence context free.  
> **username_9**: What about recursive languages? is there any real power for languages in them compared to context-sensitive? thanks :)  
> **username_7**: Recursive languages are precisely the languages decidable by always-halting Turing Machines. Any context sensitive language is therefore also recursive, but since context sensitive languages are decidable in exponential time, there are recursive languages that are not context sensitive. Unrestricted grammars are even more powerful: the halting problem can be described by an unrestricted grammar, but is not a recursive language.  
> **username_9**: Yup, I know the range of languages, but I was wondering what recursive languages brings to the table. An example recursive language which is not context-sensitive :)?  
> **username_7**: Since deciding membership for a context-sensitive grammar is in PSPACE, any language in EXPSPACE or larger classes is expressable by a recursive grammar but not by a context-sensitive grammar. An example is the language of all true propositions in Presburger arithmetic (http://en.wikipedia.org/wiki/Presburger_arithmetic). Since we suspect that PSPACE $\neq$ EXPTIME, any language in EXPTIME or above would be sufficient. The extra power is almost never needed though - it would take too long to parse anyway.  
> **username_1**: What makes you believe that GLR parsing is more effective in time or space than simpler versions of tabular parsing not using the LR construction (there are many) ?  This is not an idle question. (I am not talking of complexity class, which is more or less the same for all).  
> **username_7**: @babou: I assume you are talking about algorithms like CYK and Earley. CYK is always cubic, so it is not very useful on near-deterministic grammars that occur in practice. If you take Earley and optimize it, you get GLL, a relatively new generalized parsing algorithm, that is usually even faster than GLR. The original Earley algorithm is not that fast (talking about constant factors) because it often needs to do a linear search for things that GLL already has a pointer to.  
> **username_1**: @Alex  No, I am not talking about CYK, obviously, nor Earley. I am talking more abstractedly about the effect of predictiveness on the efficiency of this family of parsing algorithms. That would actually make a nice question by itself. Also parsing is supposed to produce parse trees (or forests). Would you think that the result is not impacted by the chosen algorithm ? These are not idle questions when you extend parsing techniques beyond the standard CF.  
> **username_8**: @AlextenBrink do you know that GLL is usually faster, and for what grammars? It is usually faster on worst case grammars, but for PL grammars we have yet to find out. Do you have already more information on this?  
> **username_1**: @jurgenv This [paper by Billot and Lang](http://www.aclweb.org/anthology-new/P/P89/P89-1018.pdf) may shed some light on this. They built a system that implements in a uniform way various general CF parsers, for systematic comparison rather than for production purpose. The analysis of their effectiveness on various grammars give hints regarding the some reasons for the compared efficiencies of different parsing strategies.  

---

### Answer by username_4 on 2010-10-23. Score: 15

A paper at ICFP 2010 this year, [Total Parser Combinators](http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.html), describes a provably terminating parser combinator library and also establishes that in this library "parser combinators are as expressive as possible" given that the parser is guaranteed to terminate. Unfortunately I don't remember the explanation the author gave for what "as expressive as possible" means, but it certainly seems relevant to your question about "power."

> **Comments:**
> **username_1**: I have a car that does not pollute, Actually it does not move either... So the question is : what kind of language is parsed by this library ?  Not meaning that this work is not interesting, of course.  

---

### Answer by username_5 on 2010-12-22. Score: 2

If you want to go beyond context-free grammars for parsing programming languages, but still parse in polynomial time, you can resort to [*parsing expression grammars*](http://en.wikipedia.org/wiki/Parsing_expression_grammar "parsing expression grammars"), or *boolean grammars* - the latter are also available in LL and LR flavors (see [here](http://users.utu.fi/aleokh/)). In formal language theory, also the powerful yet linear-time recognizable *Church-Rosser languages* are studied, but I am not aware of any implemented parser generators for these.

In natural language processing, tastes are different, for instance, dealing with ambiguity (also: inherent ambiguity) and free word order plays a very prominent role. Here the keywords [*mildly context sensitive languages*](http://en.wikipedia.org/wiki/Mildly_context-sensitive_language) and *restart automata* might help you to start reading.

> **Comments:**
> **username_1**: Considering the way the question was asked, and the complaint that CF is too constraining, your answer is clearly the best. So it goes ...  
> **username_6**: The link to Alexander Okhotin doesn't work now - the new website seems to be here: https://users.math-cs.spbu.ru/~okhotin/  

---

