{"article":{"slug":"some-problems-of-recursive-descent-parsers","title":"Some problems of recursive descent parsers","subtitle":null,"summary":"Eli Bendersky revisits the recursive descent parser from his earlier article, examining problems such as handling left-associative binary operators and proposing practical solutions to make the parser correct.","content_type":"tutorial","language":"en","canonical_url":"https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers","author":{"name":"Eli Bendersky","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Eli Bendersky's website","url":"https://eli.thegreenplace.net/","listing_slug":null,"listing":null},"topics":[{"name":"compilers","slug":"compilers","url":"https://listedarticles.com/topics/compilers"},{"name":"algorithms","slug":"algorithms","url":"https://listedarticles.com/topics/algorithms"},{"name":"programming","slug":"programming","url":"https://listedarticles.com/topics/programming"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":1234,"reading_minutes":5,"published_at":"2009-03-14T11:24:00.000Z","added_at":"2026-11-15T19:54:36.429Z","updated_at":"2026-11-15T19:54:36.429Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/some-problems-of-recursive-descent-parsers","markdown_url":"https://listedarticles.com/articles/some-problems-of-recursive-descent-parsers.md","example":false,"citation":"Eli Bendersky, Eli Bendersky's website. \"Some problems of recursive descent parsers.\" 14 Mar 2009. https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers"},"body_markdown":"# Some problems of recursive descent parsers\n\n### Reminder - recursive descent (RD) parsers\n\n[Here's an article](https://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/) I wrote on the subject a few months ago. It provides a good introduction on how RD parsers are constructed and what grammars they can parse.\n\nHere I want to focus on a couple of problems with the RD parser developed in that article, and propose solutions.\n\n### Problem #1: operator associativity\n\nIf you recall from the [previous article](https://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/), the expr rule of the parser looks like this (BNF notation):\n\n```\n<expr>    : <term> + <expr>\n          | <term> - <expr>\n          | <term>\n```\n\nIt's built this way (expr on the right-hand side of the expression, term on the left-hand side), to avoid *left-recursion* in the grammar, which can crash a RD parser by sending it wheeling in an infinite loop.\n\nBut as I hinted in the footnotes (and some readers caught on in the comments), this injects an associativity problem into the grammar. Let's see why.\n\nWikipedia is much better than me at explaining what [operator associativity](http://en.wikipedia.org/wiki/Operator_associativity) is, so I'll assume you've read and understood it.\n\nIn short, however, left associativity of the minus operator means that 5 - 1 - 2 = (5 - 1) - 2 and not 5 - (1 - 2) (which returns a different result).\n\nBut if you run 5 - 1 - 2 in the parser with the above BNF for expr, you'll get 6 instead of 2. So what went wrong?\n\nThe problem is in the grammar definition (BNF) itself. The way the expr rule is defined makes it inherently right-associative instead of left-associative. The hierarchy of the rules implicitly defines their associativity, because it defines what will be grouped together. To understand it better, perhaps the code implementing the expr rule will help:\n\n```\ndef _expr(self):\n    lval = self._term()\n\n    if self.cur_token.type == '+':\n        self._match('+')\n        op = lambda a, b: a + b\n    elif self.cur_token.type == '-':\n        self._match('-')\n        op = lambda a, b: a - b\n    else:\n        print 'returning lval = %s' % lval\n        return lval\n\n    rval = self._expr()\n    print 'lval = %s, rval = %s, res = %s' % (\n        lval, rval, op(lval, rval))\n    return op(lval, rval)\n```\n\nNote that the first term is parsed, and then the rule recursively calls itself for the next one. So the expression is being built from right to left, and this causes its right-associativity.\n\nAs you can see, I've added a couple of printouts to better show what's going on. When run on the expression 5 - 1 - 2, this prints:\n\n```\nreturning lval = 2\nlval = 1, rval = 2, res = -1\nlval = 5, rval = -1, res = 6\n```\n\nWe clearly see the problem here. The actual returns are done from right to left because of the recursion.\n\nNote that this grammar evaluates addition, multiplication, subtraction and division in a right-associative way. This causes problems for both subtraction and division, but not for addition and multiplication, because these operations compute the same whether right-to-left or left-to-right [[1]](#id3).\n\n### A solution for the associativity problem\n\nI suppose the problem can be solved by rewriting the BNF rules in some sophisticated way that makes them both left-associative and not left-recursive [[2]](#id4), but I'll pick another way.\n\nBNF is somewhat limiting, since it doesn't really allow much options when defining rules. All the rules must have a very strict structure, and if you want to customize something you must resort to defining sub-rules and referencing them recursively.\n\nEnter [EBNF](http://en.wikipedia.org/wiki/Ebnf). It was developed to fix some of the deficiencies of plain BNF. One of those is the addition of repetition of sub-rules. For instance, we can write the expr rule in EBNF as follows:\n\n```\n<expr>    : <term> {+ <term>}\n          | <term> {- <term>}\n```\n\nNote the braces { ... }. In EBNF, these mean \"repeated 0 or more times\". This is still a LL(1) grammar, but now it's expressed a bit more comfortably. Such a representation is very suitable for coding, because the repetition can be expressed naturally with a loop.\n\nHere's a re-implementation of the expr rule using this idiom:\n\n```\ndef _expr(self):\n    lval = self._term()\n\n    while ( self.cur_token.type == '+' or\n            self.cur_token.type == '-'):\n        if self.cur_token.type == '+':\n            self._match('+')\n            lval += self._term()\n        elif self.cur_token.type == '-':\n            self._match('-')\n            lval -= self._term()\n\n    return lval\n```\n\nNote the while loop \"eating up\" all successive terms in the expression and accumulating the result in the expected left-to-right manner. Now the computation 5 - 1 - 2 will correctly produce 2.\n\n### The code\n\nThis is a good place to refer to the code. In [here](https://github.com/eliben/code-for-blog/tree/main/2009/py_rd_parser_example) you will find the source of both the old (BNF-based) parser and the new (EBNF-based) one, along with the lexer module that implements the tokenizer. Each of the parsers is self contained and can be used separately. Note that they were developed and tested with Python 2.5\n\n### Right-associative operators\n\nSome operators are inherently right-associative. Exponentiation, for example. 2^3^2 = 2^(3^2) = 512, and not (2^3)^2 (which equals 64).\n\nWe can leave these operators defined as before, using a recursive rule that naturally results in right-associativity. Here's the code of the power rule that was added to the EBNF-based parser to support exponentiation:\n\n```\n# <power>   : <factor> ** <power>\n#           | <factor>\n#\ndef _power(self):\n    lval = self._factor()\n\n    if self.cur_token.type == '**':\n        self._match('**')\n        lval **= self._power()\n\n    return lval\n```\n\n### Intermission\n\nWe now have a correct recursive descent parser that uses EBNF-based rules to parse expressions with the desired associativity for each operator. This parser can be readily employed to parse simple languages - it is production-use ready. The next \"problem\" I present only has to do with the parser's efficiency, so it is probably of no concern unless performance is crucial.\n\n### Problem #2: efficiency\n\nThere's an inherent performance problem with recursive-descent parsers when dealing with expressions. This problem stems from the need to define operator precedence, and in RD parsers the only way to define this precedence is by using recursive sub-rules. For example (from the EBNF-based code):\n\n```\n<expr>    : <term> {+ <term>}\n          | <term> {- <term>}\n<term>    : <power> {* <power>}\n          | <power> {/ <power>}\n```\n\nThe nesting of these rules defines the relative precedence of addition and multiplication. It tells the parser: between plus signs, dive into the expression and collect all sub-terms connected by multiply signs. In other words, it tells it to group the expression: 5 + 2 \\* 2 as 5 + (2 \\* 2) and not as (5 + 2) \\* 2.\n\nTo see the problem this nesting causes, I've inserted simple printouts into each of the expr, term, power and factor rules to show which functions get called while parsing. Let's see what happens when the trivial expression 42 is parsed:\n\n```\nexpr called with NUMBER(42) at 0\nterm called with NUMBER(42) at 0\npower called with NUMBER(42) at 0\nfactor called with NUMBER(42) at 0\n```\n\n**Yikes!!!** 4 function calls just to parse the single-token input 42! Unfortunately, while this problem may look simple on the surface, it is not. There's simply no other way to express precedence in RD parsers - you have to use nested rules, and this nesting turns out to be inefficient for parsing expressions.\n\nThe solution to this problem is to use a hybrid parser instead of a pure RD one. Some algorithms were developed to efficiently parse [infix expressions](http://en.wikipedia.org/wiki/Infix_notation). [This article](http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm) provides a good survey. One such algorithm can be combined with RD to provide a general-purpose parser for both expressions and higher programming language constructs.\n\nIn a future article I will discuss an implementation of such a parser.\n\n![](https://eli.thegreenplace.net/images/hline.jpg)\n\n|  |  |\n| --- | --- |\n| [[1]](#id1) | To be more precise, addition and multiplication are [associative binary operators](http://en.wikipedia.org/wiki/Associativity) in the mathematical sense. |\n\n|  |  |\n| --- | --- |\n| [[2]](#id2) | But I'm too lazy to look for such a way at the moment. Let me know if you find it. |\n","body_html":"<h1 id=\"some-problems-of-recursive-descent-parsers\">Some problems of recursive descent parsers</h1>\n<h3 id=\"reminder-recursive-descent-rd-parsers\">Reminder - recursive descent (RD) parsers</h3>\n<p><a href=\"https://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/\" rel=\"nofollow ugc noopener\">Here&#39;s an article</a> I wrote on the subject a few months ago. It provides a good introduction on how RD parsers are constructed and what grammars they can parse.</p>\n<p>Here I want to focus on a couple of problems with the RD parser developed in that article, and propose solutions.</p>\n<h3 id=\"problem-1-operator-associativity\">Problem #1: operator associativity</h3>\n<p>If you recall from the <a href=\"https://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/\" rel=\"nofollow ugc noopener\">previous article</a>, the expr rule of the parser looks like this (BNF notation):</p>\n<pre><code>&lt;expr&gt;    : &lt;term&gt; + &lt;expr&gt;\n          | &lt;term&gt; - &lt;expr&gt;\n          | &lt;term&gt;</code></pre>\n<p>It&#39;s built this way (expr on the right-hand side of the expression, term on the left-hand side), to avoid <em>left-recursion</em> in the grammar, which can crash a RD parser by sending it wheeling in an infinite loop.</p>\n<p>But as I hinted in the footnotes (and some readers caught on in the comments), this injects an associativity problem into the grammar. Let&#39;s see why.</p>\n<p>Wikipedia is much better than me at explaining what <a href=\"http://en.wikipedia.org/wiki/Operator_associativity\" rel=\"nofollow ugc noopener\">operator associativity</a> is, so I&#39;ll assume you&#39;ve read and understood it.</p>\n<p>In short, however, left associativity of the minus operator means that 5 - 1 - 2 = (5 - 1) - 2 and not 5 - (1 - 2) (which returns a different result).</p>\n<p>But if you run 5 - 1 - 2 in the parser with the above BNF for expr, you&#39;ll get 6 instead of 2. So what went wrong?</p>\n<p>The problem is in the grammar definition (BNF) itself. The way the expr rule is defined makes it inherently right-associative instead of left-associative. The hierarchy of the rules implicitly defines their associativity, because it defines what will be grouped together. To understand it better, perhaps the code implementing the expr rule will help:</p>\n<pre><code>def _expr(self):\n    lval = self._term()\n\n    if self.cur_token.type == &#39;+&#39;:\n        self._match(&#39;+&#39;)\n        op = lambda a, b: a + b\n    elif self.cur_token.type == &#39;-&#39;:\n        self._match(&#39;-&#39;)\n        op = lambda a, b: a - b\n    else:\n        print &#39;returning lval = %s&#39; % lval\n        return lval\n\n    rval = self._expr()\n    print &#39;lval = %s, rval = %s, res = %s&#39; % (\n        lval, rval, op(lval, rval))\n    return op(lval, rval)</code></pre>\n<p>Note that the first term is parsed, and then the rule recursively calls itself for the next one. So the expression is being built from right to left, and this causes its right-associativity.</p>\n<p>As you can see, I&#39;ve added a couple of printouts to better show what&#39;s going on. When run on the expression 5 - 1 - 2, this prints:</p>\n<pre><code>returning lval = 2\nlval = 1, rval = 2, res = -1\nlval = 5, rval = -1, res = 6</code></pre>\n<p>We clearly see the problem here. The actual returns are done from right to left because of the recursion.</p>\n<p>Note that this grammar evaluates addition, multiplication, subtraction and division in a right-associative way. This causes problems for both subtraction and division, but not for addition and multiplication, because these operations compute the same whether right-to-left or left-to-right <a href=\"#id3\">[1]</a>.</p>\n<h3 id=\"a-solution-for-the-associativity-problem\">A solution for the associativity problem</h3>\n<p>I suppose the problem can be solved by rewriting the BNF rules in some sophisticated way that makes them both left-associative and not left-recursive <a href=\"#id4\">[2]</a>, but I&#39;ll pick another way.</p>\n<p>BNF is somewhat limiting, since it doesn&#39;t really allow much options when defining rules. All the rules must have a very strict structure, and if you want to customize something you must resort to defining sub-rules and referencing them recursively.</p>\n<p>Enter <a href=\"http://en.wikipedia.org/wiki/Ebnf\" rel=\"nofollow ugc noopener\">EBNF</a>. It was developed to fix some of the deficiencies of plain BNF. One of those is the addition of repetition of sub-rules. For instance, we can write the expr rule in EBNF as follows:</p>\n<pre><code>&lt;expr&gt;    : &lt;term&gt; {+ &lt;term&gt;}\n          | &lt;term&gt; {- &lt;term&gt;}</code></pre>\n<p>Note the braces { ... }. In EBNF, these mean &quot;repeated 0 or more times&quot;. This is still a LL(1) grammar, but now it&#39;s expressed a bit more comfortably. Such a representation is very suitable for coding, because the repetition can be expressed naturally with a loop.</p>\n<p>Here&#39;s a re-implementation of the expr rule using this idiom:</p>\n<pre><code>def _expr(self):\n    lval = self._term()\n\n    while ( self.cur_token.type == &#39;+&#39; or\n            self.cur_token.type == &#39;-&#39;):\n        if self.cur_token.type == &#39;+&#39;:\n            self._match(&#39;+&#39;)\n            lval += self._term()\n        elif self.cur_token.type == &#39;-&#39;:\n            self._match(&#39;-&#39;)\n            lval -= self._term()\n\n    return lval</code></pre>\n<p>Note the while loop &quot;eating up&quot; all successive terms in the expression and accumulating the result in the expected left-to-right manner. Now the computation 5 - 1 - 2 will correctly produce 2.</p>\n<h3 id=\"the-code\">The code</h3>\n<p>This is a good place to refer to the code. In <a href=\"https://github.com/eliben/code-for-blog/tree/main/2009/py_rd_parser_example\" rel=\"nofollow ugc noopener\">here</a> you will find the source of both the old (BNF-based) parser and the new (EBNF-based) one, along with the lexer module that implements the tokenizer. Each of the parsers is self contained and can be used separately. Note that they were developed and tested with Python 2.5</p>\n<h3 id=\"right-associative-operators\">Right-associative operators</h3>\n<p>Some operators are inherently right-associative. Exponentiation, for example. 2^3^2 = 2^(3^2) = 512, and not (2^3)^2 (which equals 64).</p>\n<p>We can leave these operators defined as before, using a recursive rule that naturally results in right-associativity. Here&#39;s the code of the power rule that was added to the EBNF-based parser to support exponentiation:</p>\n<pre><code># &lt;power&gt;   : &lt;factor&gt; ** &lt;power&gt;\n#           | &lt;factor&gt;\n#\ndef _power(self):\n    lval = self._factor()\n\n    if self.cur_token.type == &#39;**&#39;:\n        self._match(&#39;**&#39;)\n        lval **= self._power()\n\n    return lval</code></pre>\n<h3 id=\"intermission\">Intermission</h3>\n<p>We now have a correct recursive descent parser that uses EBNF-based rules to parse expressions with the desired associativity for each operator. This parser can be readily employed to parse simple languages - it is production-use ready. The next &quot;problem&quot; I present only has to do with the parser&#39;s efficiency, so it is probably of no concern unless performance is crucial.</p>\n<h3 id=\"problem-2-efficiency\">Problem #2: efficiency</h3>\n<p>There&#39;s an inherent performance problem with recursive-descent parsers when dealing with expressions. This problem stems from the need to define operator precedence, and in RD parsers the only way to define this precedence is by using recursive sub-rules. For example (from the EBNF-based code):</p>\n<pre><code>&lt;expr&gt;    : &lt;term&gt; {+ &lt;term&gt;}\n          | &lt;term&gt; {- &lt;term&gt;}\n&lt;term&gt;    : &lt;power&gt; {* &lt;power&gt;}\n          | &lt;power&gt; {/ &lt;power&gt;}</code></pre>\n<p>The nesting of these rules defines the relative precedence of addition and multiplication. It tells the parser: between plus signs, dive into the expression and collect all sub-terms connected by multiply signs. In other words, it tells it to group the expression: 5 + 2 * 2 as 5 + (2 * 2) and not as (5 + 2) * 2.</p>\n<p>To see the problem this nesting causes, I&#39;ve inserted simple printouts into each of the expr, term, power and factor rules to show which functions get called while parsing. Let&#39;s see what happens when the trivial expression 42 is parsed:</p>\n<pre><code>expr called with NUMBER(42) at 0\nterm called with NUMBER(42) at 0\npower called with NUMBER(42) at 0\nfactor called with NUMBER(42) at 0</code></pre>\n<p><strong>Yikes!!!</strong> 4 function calls just to parse the single-token input 42! Unfortunately, while this problem may look simple on the surface, it is not. There&#39;s simply no other way to express precedence in RD parsers - you have to use nested rules, and this nesting turns out to be inefficient for parsing expressions.</p>\n<p>The solution to this problem is to use a hybrid parser instead of a pure RD one. Some algorithms were developed to efficiently parse <a href=\"http://en.wikipedia.org/wiki/Infix_notation\" rel=\"nofollow ugc noopener\">infix expressions</a>. <a href=\"http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm\" rel=\"nofollow ugc noopener\">This article</a> provides a good survey. One such algorithm can be combined with RD to provide a general-purpose parser for both expressions and higher programming language constructs.</p>\n<p>In a future article I will discuss an implementation of such a parser.</p>\n<figure><img src=\"https://eli.thegreenplace.net/images/hline.jpg\" alt=\"\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><a href=\"#id1\">[1]</a></td><td>To be more precise, addition and multiplication are <a href=\"http://en.wikipedia.org/wiki/Associativity\" rel=\"nofollow ugc noopener\">associative binary operators</a> in the mathematical sense.</td></tr></tbody></table></div>\n<div class=\"table-wrap\"><table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><a href=\"#id2\">[2]</a></td><td>But I&#39;m too lazy to look for such a way at the moment. Let me know if you find it.</td></tr></tbody></table></div>","headings":[{"level":1,"text":"Some problems of recursive descent parsers","id":"some-problems-of-recursive-descent-parsers"},{"level":3,"text":"Reminder - recursive descent (RD) parsers","id":"reminder-recursive-descent-rd-parsers"},{"level":3,"text":"Problem #1: operator associativity","id":"problem-1-operator-associativity"},{"level":3,"text":"A solution for the associativity problem","id":"a-solution-for-the-associativity-problem"},{"level":3,"text":"The code","id":"the-code"},{"level":3,"text":"Right-associative operators","id":"right-associative-operators"},{"level":3,"text":"Intermission","id":"intermission"},{"level":3,"text":"Problem #2: efficiency","id":"problem-2-efficiency"}]}}