Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Contexts in Recursive Descent ...

Contexts in Recursive Descent Parsing

Mikhail Barash, Contexts in Recursive Descent Parsing. TUCS Technical Reports 1151, TUCS, 2015.

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, 2014). 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:

@TECHREPORT{tBarash_Mikhail15a,
  title = {Contexts in Recursive Descent Parsing},
  author = {Barash, Mikhail},
  number = {1151},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2015},
  keywords = {formal grammars, contexts, recursive descent, parsing},
}

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

Edit publication