Practical Earley Parsing
| Autor: | R. Nigel Horspool, John Aycock |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Statement (computer science)
Parsing Finite-state machine General Computer Science Grammar Programming language Computer science media_common.quotation_subject Parsing expression grammar Top-down parsing computer.software_genre Earley parser TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Simple (abstract algebra) computer media_common |
| Zdroj: | The Computer Journal. 45:620-630 |
| ISSN: | 1460-2067 0010-4620 |
| DOI: | 10.1093/comjnl/45.6.620 |
| Popis: | Earley’s parsing algorithm isa general algorithm, ableto handleany context-free grammar. As with most parsing algorithms, however, the presence of grammar rules having empty right-hand sides complicates matters. By analyzing why Earley’s algorithm struggles with these grammar rules, we have devised a simple solution to the problem. Our empty-rule solution leads to a new type of finite automaton expressly suited for use in Earley parsers and to a new statement of Earley’s algorithm. We show that this new form of Earley parser is much more time efficient in practice than the original. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|