Packrat parsers and memoization

Kay Schluehr <kay@fiber-space.de>
Sun, 7 Jun 2009 06:41:28 -0700 (PDT)

          From comp.compilers
Related articles
Packrat parsers and memoization kay@fiber-space.de (Kay Schluehr) (2009-06-07)
RE: Packrat parsers and memoization quinn_jackson2004@yahoo.ca (Quinn Tyler Jackson) (2009-06-08)
Re: Packrat parsers and memoization armelasselin@hotmail.com (Armel) (2009-06-08)
Re: Packrat parsers and memoization kay@fiber-space.de (Kay Schluehr) (2009-06-09)
| List of all articles for this month |
From: Kay Schluehr <kay@fiber-space.de>
Newsgroups: comp.compilers
Date: Sun, 7 Jun 2009 06:41:28 -0700 (PDT)
Organization: Compilers Central
Keywords: parse, question
Posted-Date: 08 Jun 2009 04:56:22 EDT

Hello compiler list,


I have a question concerning packrat parsing and memoization. Suppose
one has following grammar


G -> A1 b / A2 c
A1 -> a
A2 -> a


and an input string 'a c'. Since the rule on the left of the ordered
choice fails to parse the string the second one is tried. Now the
major claim is that packrat parsing avoids exponential complexity in
backtracking by means of memoization of intermediate results. However
I fail to see how this helps here because 'A1 c' would simply be an
unknown rule and create the wrong parse tree.


Thanks


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.