A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Recursive Descent Parsing for Grammars with Contexts
Tekijät: Mikhail Barash
Toimittaja: Peter van Emde Boas, Frans C A Groen, Giuseppe F Italiano, Jerzy Nawrocki, Harald Sack
Julkaisuvuosi: 2013
Kokoomateoksen nimi: 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
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali