From Stateful Parsing to Transactional Parsing

By: on August 12, 2005

Thinking further on the problem of stateful parsing (from yesterday’s article), the way we’ve done it in the past (essentially by using Scheme’s parameter mechanism) is a special case of a transactional system, with rollback on error and commit after each toplevel expression parsed.

This suggests that if Scheme had an implementation of a Software Transactional Memory, then it would be a good fit for a stateful packrat parser. The symbol-table (or whatever state needs to be speculatively propagated along a line of parsing) would simply be placed under transactional control. Each time an attempt is made to match against a particular nonterminal a nested transaction would be entered. If the nonterminal matched the input successfully, the nested transaction would be committed; otherwise it would be rolled back, and any alternative options would be tried in their own nested transactions.


Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>