Re: Packrat parsers and memoization

"Armel" <armelasselin@hotmail.com>
Mon, 8 Jun 2009 17:18:30 +0200

          From comp.compilers

Related articles
Packrat parsers and memoization kay@fiber-space.de (Kay Schluehr) (2009-06-07)
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: "Armel" <armelasselin@hotmail.com>
Newsgroups: comp.compilers
Date: Mon, 8 Jun 2009 17:18:30 +0200
Organization: les newsgroups par Orange
References: 09-06-029
Keywords: parse
Posted-Date: 09 Jun 2009 05:32:12 EDT

>[...]
> G -> A1 b / A2 c
> A1 -> a
> A2 -> a
>[...]
> I fail to see how this helps here because 'A1 c' would simply be an
> unknown rule and create the wrong parse tree.


Packrat/memoization parser would probably help with rules such as:


G -> A b | A c
A -> a


by recognizing that the first "A" of second rule immediately on "ac",
because it was already found in first alternate.


also rules such as:


G -> A b | A c
A -> a | a A


could then be greatly enhanced on "aaaaaaaaaaaaaac", for the same reason: A
of "G->A c" will be skipped, testing immediately the "c".


I do not think that memoization will do any good to your original case
because the parser would have to "deduce" that a A1 and a A2 are indeed the
same. Grammar preparation could do this computation and actually macth one
for the other, then disambiguate on G rules acceptation but I think its
beyond simple packrat/memoization.


Regards
Armel



Post a followup to this message

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