Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Recursive Descent Parsing for ...

Recursive Descent Parsing for Grammars with Contexts

Mikhail Barash, Recursive Descent Parsing for Grammars with Contexts. In: Peter van Emde Boas, Frans C.A. Groen, Giuseppe F. Italiano, Jerzy Nawrocki, Harald Sack (Eds.), SOFSEM 2013: Theory and Practice of Computer Science, II, 10–21, Institute of Computer Science AS CR, 2013.

Abstract:

This paper undertakes to reconsider recursive descent parsing technique by using a general mathematical definition of contexts within grammar rules. This definition takes form of grammars with contexts (Barash, Okhotin, 2012). The model extends context-free grammars with quantifiers for referring to the context in which a substring being defined occurs. It has been shown that general parsing of such grammars is cubic-time, while their unambiguous subclass allows square-time parsing. The paper generalizes the recursive descent parsing to grammars with contexts. Right contexts, which can be explicitly specified, are used to choose the alternatives suitable during the parsing. The applicability of the proposed algorithm is restricted to a subset of grammars with contexts satisfying the properties of separability (Wood, 1971) and monotone decreasing prefixes. The latter allows proving the correctness of backtracking in this algorithm, which is defined similarly to Birman and Ullman (1973) and Ford (2004). A memoized version of the algorithm is guaranteed to have linear time complexity.

BibTeX entry:

@INPROCEEDINGS{inpBarash_Mikhail13a,
  title = {Recursive Descent Parsing for Grammars with Contexts},
  booktitle = {SOFSEM 2013: Theory and Practice of Computer Science},
  author = {Barash, Mikhail},
  volume = {II},
  editor = {Emde Boas, Peter van and Groen, Frans C.A. and Italiano, Giuseppe F. and Nawrocki, Jerzy and Sack, Harald},
  publisher = {Institute of Computer Science AS CR},
  pages = {10–21},
  year = {2013},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication