Gramma... littera... Letras
Alicia Sisca · Dialnet (Universidad de la Rioja) · 1997
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 restricted classes of languages given by LL(1), bidirectional LL(1), and a specific kind of XML grammars, the time requirement is bounded linearly or quadratically depending on the number of separate gaps.