A4 Refereed article in a conference publication
Recursive Descent Parsing for Grammars with Contexts
Authors: Mikhail Barash
Editors: Peter van Emde Boas, Frans C A Groen, Giuseppe F Italiano, Jerzy Nawrocki, Harald Sack
Publication year: 2013
Book title : SOFSEM 2013: Theory and Practice of Computer Science. 39th Conference on Current Trends in Theory and Practice of Computer Science. Proceedings. Volume II
ISBN: 978-80-87136-15-7
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.
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.
UTU Research Portal