Paper Info
Title
Gap Parsing with LL(1) Grammars
Abstract
We study the time complexity of the parsing problem for input strings that contain gaps. For context-free languages the time requirement is cubic. For re- stricted classes of languages given by LL(1), bidirectional LL(1), and a specific kind of XML grammars, the time requirement is bounded linearly or quadrati- cally depending on the number of separate gaps.
Year
Venue
Keywords
2005
Grammars
context free language,time complexity
Field
DocType
Volume
Rule-based machine translation,Quadratic growth,XML,Computer science,Theoretical computer science,Parsing,Time complexity,Bounded function
Journal
8
Citations 
PageRank 
References 
2
0.36
12
Authors
2
Name
Order
Citations
PageRank
Eberhard Bertsch16326.54
Mark-jan Nederhof238753.30