TY - JOUR

T1 - Improved normal form for grammars with one-sided contexts

AU - Okhotin, Alexander

PY - 2015/7/11

Y1 - 2015/7/11

N2 - Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin ("An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014) further extending the author's earlier work on propositional connectives in grammars (A. Okhotin, "Conjunctive grammars", J. Autom. Lang. Comb., 2001). These grammars allow two types of context specifications: for a substring v of a string uvx, a proper left context operator ◃ D states that u is of the form described by D, and an extended left context operator ⊴ E states that uv is described by E. This paper establishes a normal form for these grammars, in which extended left contexts are never used, whereas left contexts may be applied only to individual symbols, so that all rules are of the form A→B1C1&...&BmCm or A→a&◃D. This eliminates circular dependencies in the grammar and leads to a new, clearer version of the known cubic-time parsing algorithm. With some further improvements, the algorithm is accelerated from time O(n3) to time O(n3logn).

AB - Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin ("An extension of context-free grammars with one-sided context specifications", Inform. and Comput., 2014) further extending the author's earlier work on propositional connectives in grammars (A. Okhotin, "Conjunctive grammars", J. Autom. Lang. Comb., 2001). These grammars allow two types of context specifications: for a substring v of a string uvx, a proper left context operator ◃ D states that u is of the form described by D, and an extended left context operator ⊴ E states that uv is described by E. This paper establishes a normal form for these grammars, in which extended left contexts are never used, whereas left contexts may be applied only to individual symbols, so that all rules are of the form A→B1C1&...&BmCm or A→a&◃D. This eliminates circular dependencies in the grammar and leads to a new, clearer version of the known cubic-time parsing algorithm. With some further improvements, the algorithm is accelerated from time O(n3) to time O(n3logn).

KW - Conjunctive grammars

KW - Contexts

KW - Formal grammars

KW - Normal forms

KW - Parsing

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

U2 - 10.1016/j.tcs.2015.03.041

DO - 10.1016/j.tcs.2015.03.041

M3 - Article

AN - SCOPUS:84937018469

VL - 588

SP - 52

EP - 72

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -