On the complexity of regular-grammars with integer attributes

摘要

Regular grammars with attributes overcome some limitations of classical regular grammars, sensibly enhancing their expressiveness. However, the addition of attributes increases the complexity of this formalism leading to intractability in the general case. In this paper, we consider regular grammars with attributes ranging over integers, providing an in-depth complexity analysis. We identify relevant fragments of tractable attribute grammars, where complexity and expressiveness are well balanced. In particular, we study the complexity of the classical problem of deciding whether a string belongs to the language generated by any attribute grammar from a given class C (call it PARSE[C]). We consider deterministic and ambiguous regular grammars, attributes specified by arithmetic expressions over {||,+,−,÷,%,⁎}, and a possible restriction on the attributes composition (that we call strict composition). Deterministic regular grammars with attributes computed by arithmetic expressions over {||,+,−,÷,%} are P-complete. If the way to compose expressions is strict, they can be parsed in L, and they remain tractable even if multiplication is allowed. Problem PARSE[C] becomes NP-complete for general regular grammars over {||,+,−,÷,%,⁎} with strict composition and for grammars over {||,+,−,÷,%} with unrestricted attribute composition. Finally, we show that even in the most general case the problem is in polynomial space.