Noncanonical Extensions of Bottom-Up Parsing Techniques
| Autor: | Thomas G. Szymanski, John H. Williams |
|---|---|
| Rok vydání: | 1976 |
| Předmět: |
Theoretical computer science
Parsing General Computer Science Computer science Memoization General Mathematics Parsing expression grammar Top-down parsing computer.software_genre TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Parser combinator Top-down parsing language S-attributed grammar computer Bottom-up parsing |
| Zdroj: | SIAM Journal on Computing. 5:231-250 |
| ISSN: | 1095-7111 0097-5397 |
| DOI: | 10.1137/0205019 |
| Popis: | A bottom-up parsing technique which can make non-leftmost possible reductions in sentential forms is said to be non-canonical. Nearly every existing parsing technique can be extended to a non-canonical method which operates on larger classes of grammars and languages than the original technique. Moreover, the resulting parsers run in time linearly proportional to the length of their input strings. Several such extensions are defined and analyzed from the points of view of both power and decidability. The results are presented in terms of a general bottom-up parsing model which yields a common decision procedure for testing membership in many of the existing and extended classes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|