bugGrammatica - Bugs: bug #13246, Parser: The LookAheadSet class...


You are not allowed to post comments on this tracker with your current authentication level.

bug #13246: Parser: The LookAheadSet class should be implemented as a tree

Submitter:  Per Cederberg <cederberg>
Submitted:  Tue 31 May 2005 06:51:08 PM UTC
Severity:  2 - Normal Item Group:  Future Improvement
Status:  None Assigned to:  cederberg
Open/Closed:  Open

Tue 31 May 2005 06:51:08 PM UTC, original submission:  

The LookAheadSet data structure is currently implemented as a list of lists. This is pretty ineffective, as look-ahead token searches are run with O(n*m) performance, where n is the number of look-ahead sets and m the maximum length of the look-ahead sequences. The current representation is also wasteful of resources, as roughly similar sequences (differing only in the last token) are completely duplicated.

By using an efficient tree representation using hash tables (or similar) at each node, the look-ahead tree sets could use less data while also performing better. Ideally O(m) performance could be reached, where m is the maximum length of the look-ahead sequences.

This change is not trivial, however. Probably, the easiest way would be to first create an intermediary solution where the external API of LookAheadSet is kept intact. This means that the current Sequence class would be kept, although no longer used internally inside LookAheadSet for storing the actual tokens.

Per Cederberg <cederberg>
Group administrator


(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


CC list is empty


There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.


No changes have been made to this item

Back to the top

Powered by Savane 3.13-04b1.
Corresponding source code