[antlr-interest] Re: how does memoization work?

Terence Parr parrt at cs.usfca.edu
Sun Dec 4 10:49:18 PST 2005


On Dec 4, 2005, at 10:41 AM, Geir Ove Skjaervik wrote:

> Hello,
>
> Excuse me for asking, but what excatly is "The memoization  
> mechanism" ?
> I am not comfortable with these terms.

It simply records the result of matching any rule at every input  
position at which the parser is guessing.  Later if you ask again  
(which happens a lot in backtracking), you simply jump ahead in the  
input stream according to what happened last time and don't descend  
into the rule.  It's a trivial bit of code at the start/end of each  
rule.

It guarantees linear parsing performance at the cost of memory.

Ter


More information about the antlr-interest mailing list