A Polynomial-Time Parsing Algorithm forK-Depth Languages

摘要

K-depth grammars extend context-free grammars allowingk⩾1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated byk-depth grammars is a proper extension of the family of context-free languages, while retaining many context-free properties, such as closure properties, a version of Chomsky–Schützenberger theorem, the existence of an accepting device (the multi-pushdown automaton). Here a polynomial-time parsing algorithm fork-depth languages is defined, and its correctness is proved.