Generalized overlap resolvable grammars and their parsers

摘要

The class of GOR grammars admits ε-rules and includes a grammar for every deterministic language. Its simple decision procedure yields pairs of problematic phrases, if the grammar is not GOR, or tables used to drive a deterministic pushdown parser very rapidly. The parsing algorithm, based on one of Domolki, takes advantage of the architecture of binary computers by computing state transitions quickly with logical operations. These computations can be used by a pre-processor to compute an actual state transition table, if desired. This extension yields a still faster parser which can be abandoned temporarily by reverting to the state computing algorithm at any time, if the original grammar and relations need to be modified.