On the linear computational complexity of the parser for quasi-context sensitive languages

摘要

An efficient, O(n), parsing algorithm for languages generated by dynamically programmed grammars, so-called DPLL(k) grammars, is presented. The class of grammars is stronger descriptively than context-free grammars and it can be used for analysis of complex trend functions describing the behaviour of an industrial equipment.