TY - JOUR

T1 - Top-down parsing of conjunctive languages

AU - Okhotin, Alexander

PY - 2002/4/3

Y1 - 2002/4/3

N2 - 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.

AB - 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.

KW - Conjunctive grammar

KW - Parsing

KW - Recursive descent

KW - Top-down

KW - Tree-structured pushdown

UR - http://www.scopus.com/inward/record.url?scp=0036125548&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0036125548

VL - 5

SP - 21

EP - 40

JO - Grammars

JF - Grammars

SN - 1386-1793

IS - 1

ER -