[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