Attribute-Based Precedence Relations for Free-Form Grammars

We extend the well-known and efficient parsing algorithm of operator-precedence (OP) grammars to unrestricted context-free grammar rules by means of newly defined precedence relations between nodes of syntax trees. Such relations are defined over pairs of attributes of Knuth's synthesized type that can be computed by a bottom-up parser that operates locally and in any direction (or in parallel) on the input. An algorithm for computing, given a grammar, the attributes and their relations is presented and supported by a tool. The new family of PR grammars is characterized by the absence of conflicts between precedence relations. The corresponding family of PR languages strictly include the OP family. A new normal form of PR grammars permits to prove the closure of PR languages under union. Future developments towards Boolean closures and application to model checking are mentioned.