This paper generalizes the notion of a strong LL(k) context-free grammar for the case of conjunctive grammars and develops a top-down parsing algorithm for the resulting language family. A top-down parser of a conjunctive language attempts to construct a derivation of the input string, at each step using a finite lookahead to determine which grammar rule to apply. Fragments of formulae that form the derivation are stored in a tree-structured pushdown. Two ways to implement top-down parsers are suggested: a table-driven parser with a tree-structured pushdown and a recursive descent parser. Both techniques naturally extend their context-free counterparts.

Original languageEnglish
Pages (from-to)21-40
Number of pages20
JournalGrammars
Volume5
Issue number1
StatePublished - 3 Apr 2002
Externally publishedYes

    Research areas

  • Conjunctive grammar, Parsing, Recursive descent, Top-down, Tree-structured pushdown

    Scopus subject areas

  • Management of Technology and Innovation

ID: 41145332