Abstract
In this study, table sizes and parsing efficiency of Tomita's algorithm with LR(0), SLR(1), LALR(1) and LR(1) parsing tables are compared on the basis of empirical data. From this comparison, it can be concluded that LALR(1) tables are the best choice regarding parsing time. These tables are about the same size as SLR(1) and noticeably smaller than LR(1) tables. If the size of the tables or the ease of construction is a determining factor, it can be advisable to use LR(0) tables.
As is known from the theory of 'standard' LR parsing, the useofLR(1) tables is expected to result in the best parsing efficiency compared to the other three types. However, this is not the case in Generalized LR parsing. LR(1) turns out to be significantly slower than the other types presented. We give an elegant explanation for this unexpected phenomenon.
As is known from the theory of 'standard' LR parsing, the useofLR(1) tables is expected to result in the best parsing efficiency compared to the other three types. However, this is not the case in Generalized LR parsing. LR(1) turns out to be significantly slower than the other types presented. We give an elegant explanation for this unexpected phenomenon.
| Original language | English |
|---|---|
| Title of host publication | Tomita's Algorithm - Extensions and Applications |
| Subtitle of host publication | Proceedings of the first Twente Workshop on Language Technology |
| Editors | Rob Heemels, Anton Nijholt, Klaas Sikkel |
| Place of Publication | Enschede |
| Publisher | University of Twente |
| Pages | 87-94 |
| Number of pages | 8 |
| Publication status | Published - 1991 |
| Event | 1st Twente Workshop on Language Technology, TWLT 1: Tomita's Algorithm: Extensions and Applications - Enschede, Netherlands Duration: 22 Mar 1991 → 22 Mar 1991 Conference number: 1 |
Publication series
| Name | Memoranda informatica |
|---|---|
| Publisher | University of Twente |
| Number | 91-68 |
| ISSN (Print) | 0924-3755 |
Workshop
| Workshop | 1st Twente Workshop on Language Technology, TWLT 1 |
|---|---|
| Abbreviated title | TWLT |
| Country/Territory | Netherlands |
| City | Enschede |
| Period | 22/03/91 → 22/03/91 |