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

Submitted by:  Per Cederberg <cederberg>
Submitted on:  Tue 31 May 2005 06:51:08 PM UTC  
 
Severity: 2 - NormalItem Group: Future Improvement
Status: NoneAssigned to: Per Cederberg <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>
Project AdministratorIn charge of this item.

 

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

Do you think this task is very important?
If so, you can click here to add your encouragement to it.
This task has 0 encouragements so far.

Only logged-in users can vote.

 

Please enter the title of George Orwell's famous dystopian book (it's a date):

 

 

No Changes Have Been Made to This Item

Back to the top


Powered by Savane 3.1-cleanup1