Name
Abstract | ||
|---|---|---|
We compare the asymptotic time complexity of left-to-right and bidirectional parsing techniques for bilexical context-free grammars, a grammar formalism that is an abstraction of language models used in several state-of-the-art real-world parsers. We provide evidence that left-to-right parsing cannot be realised within acceptable time-bounds if the so called correct-prefix property is to be ensured. Our evidence is based on complexity results for the representation of regular languages. |
Year | Venue | Keywords |
|---|---|---|
2000 | ANLP | bilexical context-free grammar,language model,complexity result,acceptable time-bounds,asymptotic time complexity,state-of-the-art real-world parsers,left-to-right parsing,correct-prefix property,bidirectional parsing technique,regular language,grammar formalism,time complexity,context free grammar |
Field | DocType | Citations |
Top-down parsing language,Top-down parsing,Programming language,Context-free grammar,L-attributed grammar,S-attributed grammar,Computer science,Parsing expression grammar,Natural language processing,Artificial intelligence,Parser combinator,Parsing | Conference | 1 |
PageRank | References | Authors |
0.36 | 17 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark-jan Nederhof | 1 | 387 | 53.30 |
| Giorgio Satta | 2 | 902 | 90.85 |