Grammatica - 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 |
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
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.