bugGrammatica - Bugs: bug #3674, Parser: Look-ahead calculation can...


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

bug #3674: Parser: Look-ahead calculation can be slow for long sequences

Submitter:  Per Cederberg <cederberg>
Submitted:  Sun 18 May 2003 02:36:32 PM UTC
Severity:  2 - Normal Item Group:  Software
Status:  Fixed Assigned to:  cederberg
Open/Closed:  Closed

Mon 26 May 2003 07:35:02 AM UTC, comment #2: 

Included in version 1.1 released today.

Per Cederberg <cederberg>
Group administrator
Sun 18 May 2003 02:41:02 PM UTC, comment #1: 

The look-ahead algorithm has been replaced. The old algorithm
used a standard breadth-first search, whereas the new
algorithm is using a more directed approach. Only look-aheads
sequences causing conflicts are expanded further, making the
efficiency much higher. The new algoritm easily supports
calculation of look-aheads of 8 tokens or more.

Per Cederberg <cederberg>
Group administrator
Sun 18 May 2003 02:36:32 PM UTC, original submission:  

When calculating a look-ahead longer than 4 tokens, the
cost (in time) of the calculation is prohibitive. I.e. it
takes far too long to perform the calculation, and above 5
tokens the time can be counted in minutes.

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.


Follow 2 latest changes.

Date Changed by Updated Field Previous Value => Replaced by
2003-05-26 cederberg Open/ClosedOpen None
2003-05-18 cederberg StatusNone None

Back to the top

Powered by Savane 3.13-4b48.
Corresponding source code