{"id":660,"date":"2008-07-25T09:41:20","date_gmt":"2008-07-25T16:41:20","guid":{"rendered":"http:\/\/balafon.net\/?p=660"},"modified":"2009-08-28T16:54:14","modified_gmt":"2009-08-28T23:54:14","slug":"parsing-expression-grammars-and-left-recursion","status":"publish","type":"post","link":"https:\/\/balafon.net\/?p=660","title":{"rendered":"Parsing Expression Grammars and Left Recursion"},"content":{"rendered":"<p>Parsing Expression Grammars are a form of context-free grammars with ordered choice.  This reduces ambiguity in the grammar and makes writing simple recursive-descent parsers (and parser generators) quite easy.  With memoization, you can parse in linear time.  The resulting parser is called a <a href=\"http:\/\/pdos.csail.mit.edu\/~baford\/packrat\/\">Packrat Parser<\/a>.<\/p>\n<p>The only problem is handling left-recursion.  If you have grammar rules like this:<\/p>\n<p><code>Expression = Expression \"+\" Term<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| Term<br \/>\n<\/code><\/p>\n<p>your recursive-descent parser will recurse until it runs out of stack.<\/p>\n<p>I just noticed a paper on detecting and handling left-recursion: <a href=\"http:\/\/www.vpri.org\/pdf\/packrat_TR-2007-002.pdf\">Packrat Parsers can Handle Left Recursion<\/a>.  It&#8217;s a nifty technique, but it somewhat reduces the simplicity of the resulting program.<\/p>\n<p>For a finger exercise a while ago I wrote a pretty basic packrat parser generator and used it to implement a C preprocessor.  Source is <a href=\"https:\/\/narwhal.svn.sourceforge.net\/svnroot\/narwhal\/branches\/old_c_work\">here<\/a>.  When my supply of circular tuits increases I&#8217;ll have to look at implementing the stuff from the paper.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Parsing Expression Grammars are a form of context-free grammars with ordered choice. This reduces ambiguity in the grammar and makes writing simple recursive-descent parsers (and parser generators) quite easy. With memoization, you can parse in linear time. The resulting parser is called a Packrat Parser. The only problem is handling left-recursion. If you have grammar &hellip; <a href=\"https:\/\/balafon.net\/?p=660\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Parsing Expression Grammars and Left Recursion&#8221;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[187,107,108],"class_list":["post-660","post","type-post","status-publish","format-standard","hentry","category-journal","tag-computing","tag-parsing","tag-parsing-expression-grammar"],"_links":{"self":[{"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts\/660","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=660"}],"version-history":[{"count":5,"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts\/660\/revisions"}],"predecessor-version":[{"id":958,"href":"https:\/\/balafon.net\/index.php?rest_route=\/wp\/v2\/posts\/660\/revisions\/958"}],"wp:attachment":[{"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=660"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=660"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/balafon.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=660"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}