TY - RPRT
T1 - Bidirectional Parsing for Context Free Languages
A1 - Andrei,Stefan
A1 - Kudlek,Manfred
Y1 - 2009/08/25
N2 - In this paper, we describe some subclasses of context-free grammars for which a parallel approach useful for solving the membership problem will be defined. More precisely, we will combine the classical type of parser attached to a grammar $G$ with a â€śmirror" process for $G$. They analyse the input word from both sides using two processors. In the first section, we present the (general) left and right bidirectional parsers which use a nondeterministic device for any context free language. In the second section, a general SIMD model for describing bidirectional parsing is introduced. It contains two algorithms which use a backtracking method to describe the nondeterministic behaviour of the (general) left and right bidirectional model. The third section treats some deterministic subclasses of context free grammars, such as $RR(k)$, $RL(k)$ and $SIP$ grammars. The idea is to put in a reverse view" the classical deterministic subclasses of context free grammars. The fourth section points out the application of the (general) left and right bidirectional parser to the deterministic subclasses described in the previous section. Ten new classes of grammars obtained by combining the previous ones are defined, using descendant and ascendant strategies. The membership problem for all these type of grammars can be solved with a parallel algorithm in linear time.
KW - Kontextfreie Grammatik
CY - Hamburg
PB -
AD -
L2 - http://edoc.sub.uni-hamburg.de/informatik/volltexte/2009/42
ER -