TY - RPRT
T1 - Linear Bidirectional Parsing for a Subclass of Linear Languages
A1 - Andrei,Stefan
A1 - Kudlek,Manfred
Y1 - 2009/08/25
N2 - In this paper, we consider a useful subclass of linear grammars, called LLin(m,n), which are similar to the class of LL(k) grammars. Intuitively, 'looking ahead' to the next m terminal symbols and 'looking back' to the previous n terminal symbols suffices to determine uniquely the production which was applied. The membership problem for such grammars can be solved using a linear time complexity algorithm. The paper contains results related to unambiguity, a hierarchy of languages, a comparison to LL(k) grammars, recursivity, and closure properties. We also show that there exist non-deterministic languages which can be generated by this new class of grammars. Finally, we present a characterization theorem for such grammars and describe a bidirectional parser for LLin(m,n) grammars. The case LLin(1,1) is presented in detail.
KW - LLk-Parser
CY - Hamburg
PB -
AD -
L2 - http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/40
ER -