We extend the well-known and eficient 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.
Within formal language theory, the classical topic of grammars and syntactic methods has recently
seen advances motivated by new applications and by mathematical interest. We mention parsing
algorithms that exploit parallel hardware architectures [
Other eforts have attempted to increase the expressive power of OP grammars while keeping the
operator-form of their rules (e.g., [
We define a novel concept of precedence relation (PR) that applies also to grammars not constrained by the operator-form. The new PRs difer from the known ones in their domain, which is neither the terminal alphabet of OP, nor the total grammar alphabet of the Wirth-Weber simple-precedence grammars, which by the way lack the closure and local parsability properties of OP. The domain of the new attribute precedence relations (APR) is a finite set of attributes, so called because they can be computed bottom-up by a local parser as the semantic attributes of Knuth’s attributed grammars [19]. Four binary relations, called topological, between tree nodes that are adjacent on an antichain, are introduced: sibling is self-explanatory, take/yield are similar to the OP relations of the same name, while facing is a new one that holds between two nodes placed at greater distance from their least common ancestor. In a tree decorated with the node attributes, the four topological relations induce corresponding relations on the attribute domain. The PR grammars are those that do not have conflicts in attribute relations. The PR language family strictly includes the OP family, of which it preserves some essential properties: we prove local parsability, closure under reversal and union. Other algebraic properties of OP languages (closure under concatenation and complement) are likely to hold but remain to be proved. To experiment with PR grammars, the algorithm that computes the attributes and their PRs has been implemented in a tool. We have found that many syntactic constructs found in typical deterministic languages satisfy the PR property, also when the grammar rules violate the operator form. The parsing algorithm for PR difers from the classic one for OP in that the arguments of precedence relations are not given in the input string, but are computed as synthesized attributes by the parser. The size of PR matrix, though larger than the one of the OP matrix, remains practical and should not jeopardize parsing speed.
After Sect. 2 on preliminaries, the main Sect. 3 contains the topological PRs, the definition of attributes and their PRs. Then the algorithm that computes and checks PRs for a grammar is presented. It involves a new normal form for attributed grammars. The proof of closure under union ends Sect. 3. Sect. 4 proves that each OP grammar is also PR, and that some PR grammars and languages are not OP. References to related work have been placed in all sections where pertinent.
The alphabet is denoted by Σ and the empty string by . We say two letters , are adjacent in a string , if is a substring of .
We assume familiarity with the basic theories of CF languages. A grammar is denoted by = (Σ, , , ) where the terminal and non-terminal alphabets are respectively Σ and and the total alphabet is = Σ ∪ . The set contains rules of the form → , ∈ +, ∈ . The set of axioms is ⊆ . We need some cases: copy rule ∈ ; terminal rule ∈ Σ+; operator form rule if does not contain two adjacent nonterminals. The reserved terminal # is used to delimit a string. We respectively denote by () ⊆ Σ+ and () the language and the set of syntax trees defined by .
Tree languages. We also use concepts and notation from the basic theory of regular tree languages (e.g., in [20]). A tree domain is a finite set of the form {, 1, 2, . . . , 11, 12, . . .}.1 In a tree , each node is identified by a unique element of the tree domain , for brevity here called a node-identifier nid . The root nid is , the root children have nid’s 1, 2, . . . , , where is the rank of the root, etc. Each node has a symbolic label on the tree alphabet Σ ∪ Γ, where the tree leaves have labels in Σ, and the alphabet Γ is used for labeling the internal nodes. An unlabeled tree has Σ = Γ = {∙} , a skeletal tree has Γ = {∙} . The frontier of a tree is the sequence of its leaves, that respects the order in which they appear in a preorder visit of , and is denoted by () ∈ Σ+.
We often assume for simplicity that the trees are chain-free, i.e., a node has either rank > 1 or rank 1 when its child label is in Σ.
We use the following relations on a tree domain: parent denoted ˙, sibling denoted ˙, and ancestor/descendant.
Given a tree, an antichain is a maximal lexically ordered sequence of nodes (nids) that are pairwise unrelated by the ancestor-descendant relation. Notice that if ′ and ′′ are adjacent in an antichain, they are either (i) adjacent siblings or (ii) descendants of adjacent siblings, such that ′ is a rightmost descendant and ′′ is a leftmost descendant; in case (ii) ′ and ′′ are cousins not necessarily of the same generation. E.g. some antichains of tree in Fig. 1 are: (); 11, 12, 13, 2, 3; 1, 2, 3; ; on the other hand 12, 13, 2, 3 is not an antichain since it is not maximal. The set of antichains of a tree is
partially ordered by the reduction operation that substitutes the parent nid for the sequence of all its children nid’s.
sentential form.
The traditional order of presentation of operator precedence as a relation between the terminal symbols of a grammar is not possible here because in a free form grammar some rules may not contain terminals. However, the concept of precedence can be reformulated for certain objects more hidden than terminals, to be called attributes. Such attributes need to be bottom-up and locally computable by a parser that starts from the attributes of the input terminals, so that the precedence relations between attributes make parsing deterministic. A natural question is whether nonterminal symbols can be used as attributes in the previous sense, since other well-known precedence-oriented grammar models (chiefly WirthWeber [21] and followers [22]) define precedence on terminals and nonterminals. The answer is negative since Wirth-Weber parsers necessarily operate from left to right and do not have the local parsing property; the corresponding language family loses the closure properties of OP languages, e.g., is not closed under union [23].
First, we introduce four topological precedence relations (facing, sibling, taking, yielding) on the nodes of (unlabeled) skeletal trees in analogy with the classical genealogical relations between nodes (parent, sibling, cousin, etc.). Then we define the attributes as bottom-up computable values on the nodes of skeletal trees whose frontier is labeled on Σ. For any tree in () and for any two tree nodes their topological precedence relation naturally maps on their attributes. A grammar has the PR property if between the same pair of attributes at most one of the four relations holds. The finite set of attributes found in the trees of grammar and their APRs are computed by an algorithm.2 The algorithm constructs a grammar in a new normal form, called attributed. An informal presentation of the parsing algorithm and its local parsability property comes after. The closure under union for the PR languages having non-conflictual APRs concludes the section.
Topological relations on unlabeled trees For a tree , with parent relation ˙, we define four sets of binary relations for any pair of nodes ′, ′′ that are adjacent in an antichain.
Definition 1 (Precedence relations on tree domain). Four topological precedence relation types (PR), named yield precedence, take precedence, facing and sibling are defined on the tree domain . Let nodes ′ and ′′ be adjacent in an antichain of tree and let be their nearest common ancestor. Notice that the adjacency (′, ′′) implies that ′ is met before ′′ during a left-to-right, depth-first visit of the tree nodes.
yield take facing sibling (′, ′′) ∈ Yield, better written in infix notation as ′ ˙ ′′, if ˙ ′ (i.e., ′ is child of ) and ′′ is a leftmost descendant but not a child of . (′, ′′) ∈ Take, or ′ ˙ ′′, if ′ is a rightmost descendant but not a child of and ˙ ′′. (′, ′′) ∈ Face, or ′ ˙ ′′ if ′ and ′′ are resp. a rightmost and a leftmost descendant – but not children of .
(′, ′′) ∈ Sibl, or ′ ˙ ′′ if ′ and ′′ are children of .
The set of PR types is denoted by ˙ = {˙ , ˙, ˙, ˙} and ˙ ∈ ˙ stands for a generic PR type. The graph with nodes and with the arcs, labeled on ˙, that represent the parent relation ˙ (already in ) and the precedence relations ˙, is called a parse graph; it is a supergraph of the tree graph , denoted super(). 2The algorithm is incorporated in the interactive tool (avaible at https://pradella.faculty.polimi.it/prgrweb.html) which aids testing of the PR property, otherwise painful by hand.
Clearly, on a given tree the relations in ˙ are mutually exclusive, i.e., disjoint, and for any pair of (antichain) adjacent nodes ′ and ′′ exactly one ˙ ′ exists. Notice also that in the traditional representation of syntax trees the sibling arcs are understood and not displayed.
11
12 s˙ 1 s˙
y˙ [#y˙a, af˙b] 1 [af˙b, bt˙b] 2 3, b [bt˙b, bt˙#] (#y˙a, as˙b) 11, a
12, b 13, a [af˙b, bt˙b] 21 (as˙b, bs˙a) (bs˙a, af˙b) 22, b
(bt˙b, bt˙b) 211, b (af˙b, bt˙b)
Example 1 (Topological PRs). Fig. 1, top, shows a tree (solid arcs representing ˙) and its supergraph (dashed arcs for ˙, ˙ and dotted ones for ˙). The maximal paths over ˙ arcs (excluding ˙) are the antichains. In antichain 1 21 22 3 the arcs between the adjacent pairs (1, 21), (21, 22), and (22, 3) have the respective type ˙, ˙, and ˙. 3.1. Node attributes and their precedence relations In a labeled tree domain, the topological PRs naturally induce four corresponding relations on node labels. Our main contribution is the definition of a novel domain of node labels, called attributes such that their precedence relations will permit to extend the desirable properties of OP grammars to a broader family of CF grammars and languages.
To define node attributes on a tree we introduce a function that can be computed bottom-up by a local parser.3 Intuitively, a local (bottom-up deterministic) parser has the property that its decision to enter a shift or a reduce move only depends on the current input letter and on a finite neighborhood thereof. This enables the parser to use precedence relations between attributes to locate the next handle 3Ours are synthesized semantic attributes in Knuth’s [19] sense, since a node attribute is computed on a tree as a function of the values of children attributes. inside the current antichain of the tree under construction. Upon handle reduction, the parser computes the attribute of the parent node, and a new antichain replaces the current one. Such a process can be done in any order, not necessarily left-to-right.
We stress that not any locally computable function would qualify for the intended use, because some essential requirements must me met. The attribute should 1. permit to parse any OP grammar, 2. enable local parsability for non-operator-form grammars of common syntax constructs, 3. preserve all or most of the closure properties of OP languages; 4. moreover, the cost of computing attributes should not penalize parsing speed.
The following definition combines simplicity with empirical adequacy; it is the simplest one among several others we examined and discarded.
for the left- and right-borders (defined below) of the node. The flag component is in {leaf, internal}, specifying whether the rank of is null or not. For readability, we will write (, ) for ⟨, , leaf⟩, and [, ] for ⟨, , internal⟩. We exclude from the next definition any tree containing a linear chain, in agreement with the practice of OP grammar parsing.
Definition 2 (Attributes of tree nodes). Let be a chain-free tree with frontier () over Σ. For a leaf node , let () and () be the (adjacent) leaf node resp. preceding and following in the string (). If is the first or last symbol of (), resp. let () = # and () = #. Denote by () ˙1 and by ˙2 (), with ˙1, ˙2 ∈ ˙, the topological PR (see Def. 1) between the nodes (), and between , (), respectively. Conventionally, for ∈ Σ, assume # ˙ and ˙ #.
The recursive definition of the attribute of a node follows.
() = ⎧ (() ˙1 , ˙2 ()), if is a leaf ⎪⎪⎨ [, ′] , if has rank ℓ > 0, where ⎪ (1) = ⟨, , ⟩, ⎩⎪ (ℓ) = ⟨′, ′, ′⟩ (1) A tree where each node carries its attribute is called attributed. The set of attributes of a tree and a tree language are denoted resp. by () and ( ), or () if = ().
The set ( ) conflicts if it contains two attributes , ′ such that = ⟨ ˙1 , ˙2 , ⟩, ′ = ⟨ ˙′1 , ˙′2 , ′⟩, and ˙1 ̸= ˙′1, or ˙2 ̸= ˙′2.
Given a tree with frontier over Σ, we compute the attributes starting with the leaf attributes, then proceeding in any topological order with respect to the child-parent relation. Fig. 1, bottom, shows the attributes for a skeletal tree with frontier .
Since the left and right borders of a node are the same as respectively the left border of the first child and the right border of the last child, if node has rank 1 and its child 1 is internal, their attributes are identical, () = (1), so that the two values are redundant and some spurious conflicts arise when their PRs are computed. To exclude them, Def. 2 is restricted to chain-free trees.
We formalize the precedence relations between the attributes of adjacent nodes in a tree. Definition 3 (Precedence relations on node attributes). Let be a tree and consider the parse graph super(). Let ′ and ′′ be nodes in and let the topological relation ′ ˙ ′′ hold. Then the attribute pair ( (′), (′′)) has the attribute precedence relation (APR) ˙, i.e., (′) ˙ (′′). We call APR() the set of PR among attribute pairs of the nodes of a tree . Moreover, given a set of trees, we define APR( ) = ⋃︀∈ APR().
The set APR( ) conflicts if it contains two relations ˙ ′ and ˙ ′ ′ with ˙ ̸= ˙′. A set of attributed trees has the precedence relation property (PRP) if no conflict occurs in APR( ). A grammar has the PRP if the set () has the PRP; we say that is a PR grammar.
Remarks. The two entities involved in a conflict may occur in the same or in distinct trees of language . Two types of conflicts are defined: conflict (1) holds between leaf attributes involving the same triple of terminals, while conflict (2) concerns two APRs between the same attribute pair , ′. Notice that conflicts of type (2) may involve leaf and internal attributes.
Example 2 (Precedence relations on attributes). The following APRs for the attribute set () of Fig. 1, bottom, are easily found by inspecting the super-graph in Fig. 1, top. We omit the relations involving the delimiter, e.g., # ˙ [#˙, ˙ ].
1 11 12 13 2 = 21 211 22 3 ˙ ˙ ˙, ˙ ˙, ˙ ˙ ˙ Set PR has two conflicts of type (2) (evidenced in magenta) between the attribute of node 1 vs the attribute of nodes 2, 21 and between the attribute of node 13 vs 2, 21.
Example 3 (PR on grammars.). The grammar 1 : { → | } has the PRP. Its attributes and their precedence relations APRs (explained later) follow.
y˙
α0 (ay˙a, ay˙a)
α1 (ay˙a, ay˙c)
α2 (#y˙a, ay˙a)
α3 (#y˙a, ay˙c)
α4 [ay˙a, at˙a] α6 (at˙a, as˙b)
α12 (#y˙c, ct˙#)
We anticipate that (1) is not an OP language.
Computation of the attributes and PRs for a grammar We outline the algorithm implemented in our interactive tool that computes the attributes of a grammar and their PRs. Preliminarily, we observe that it would be unpractical to compute attributes and PRs on a tree by tree basis, since the number of syntax trees in a language is often not finite and it is not immediate to set a bound on the number of trees needed. Let = (Σ, , , ) and denote by () the set of attributes of any node in any tree in ().
We first compute for each nonterminal ∈ the borders of the terminal strings derived from . () = {(, ) | → ∈ } ∪ {(, ) | →+ where ∈ Σ* }.
s˙
s˙ s˙ s˙ s˙ α8 (as˙b, bs˙a)
α9 (bs˙a, at˙a) s˙
α10 (bs˙a, at˙#) α14 [#y˙c, ct˙#] ˙ ˙ ˙ ˙ y˙ ˙ t s˙ y˙
α5 [ay˙c, ct˙a] s˙
α11 (ay˙c, ct˙a)
The algorithm computes a grammar ̃︀ = ( Σ̃︀ , ̃︀ , ̃︀, ̃︀), called attributed normal form ANF, essentially equivalent to , whose terminal and nonterminal symbols are resp. in Σ × () and in × (). In the former case, the attributes pertain to leaves, in the latter case they pertain to internal nodes. The algorithm computes () along with the rules of ̃︀, starting from the axioms. From the ANF rules, the APRs are then computed.
(1) For each axiom ∈ , for each pair (, ) ∈ border( )
̃︀ := ̃︀ ∪ {⟨, ⟩} where = ⟨#˙, ˙#, internal⟩ (2) For each nonterminal ⟨0, 0⟩ ∈ ̃︀ , for each rule 0 → 1 . . . ℓ ∈ Consider the tree, where = ⟨ ⏞˙⏟, ⏞˙′ ⏟, flag ⟩ .
α0 α1 α2 . . .
αℓ Compute all ℓ-tuples 1, 2, . . . , ℓ of attribute values such that the following conditions hold.
1. 1 = 0, ℓ = 0; 2. ∀1 ≤ ≤ ℓ, (, ) ∈ border(); 3. ∀1 ≤ < ℓ, +1 = ;
lfag = leaf ∧ flag +1 = leaf : ˙′ = ˙ lfag = leaf ∧ flag +1 = internal : ˙′ = ˙ lfag = internal ∧ flag +1 = leaf : ˙′ = ˙ lfag = internal ∧ flag +1 = internal : ˙′ = ˙ For each such ℓ-tuple add the corresponding nonterminal and rule to the ANF grammar: ̃︀ ̃︀ := ̃︀ ∪ {⟨1, 1⟩, . . . , ⟨ℓ, ℓ⟩} := ̃︀ ∪ {⟨0, 0⟩ → ⟨1, 1⟩ . . . ⟨ℓ, ℓ⟩} .
(3) If nothing new is produced by step (2) terminate, else return to step (2).
Notes. 0 is the value that would be computed from 1, 2, . . . , ℓ by Def. 2, Eq. (1). For all , ˙+1 = ˙′.
The relations APR() are computed as follows.
between the attributes of a rightmost descendant ′ of and of a leftmost descendant ′ of .
condition relation condition relation ′ = leaf, ′ = leaf ˙ ′ = leaf, ˙
→+ ′, ′ = ˙ →+ ′, →+ ′ ˙ The next property of ANF grammars immediately descends from the construction above. →+ ′ Proposition 1. Let () be a set of chain-free syntax trees. There is a one-to-one correspondence between the ANF trees (̃︀) and the trees () such that for each pair of corresponding trees ̃︀and , for each pair ̃︀, of corresponding nodes in ̃︀and , the labels are resp. ⟨, ()⟩ and where ∈ .
Remark. Proposition 1 can be made to hold also when a tree in () contains a chain: it sufices to collapse its (internal) nodes into a single node and to adjust accordingly the correspondence between nonterminal names.
Example 4 (ANF grammar). For the equivalent variant 2 : { → | , → } of grammar 1 : { → | } in Ex. 3, we show the ANF as output by the tool: 0 : [#˙, ˙#] → 1 : [#˙, ˙#] → 2 : [#˙, ˙#] → 3 : [#˙, ˙ ] → 4 : [˙ , ˙] → 5 : [˙ , ˙] → 6 : [#˙, ˙ ] → 7 : [˙ , ˙] → 8 : [˙ , ˙ ] → 9 : [˙ , ˙ ] → [#˙, ˙ ] [˙ , ˙] (˙, ˙) (˙, ˙) (˙, ˙#) [#˙, ˙ ] [˙ , ˙] (˙, ˙) (˙, ˙) (˙, ˙#) (#˙, ˙#) (#˙, ˙ ) [˙ , ˙ ] [˙ , ˙] (˙, ˙) (˙, ˙) (˙, ˙) [˙ , ˙ ] [˙ , ˙] (˙, ˙) (˙, ˙) (˙, ˙) (#˙, ˙ ) (˙ , ˙) (˙ , ˙ ) (˙ , ˙ ) The attributed tree of is below:
S[#y˙a, at˙#] A[#y˙a, af˙c]
S[af˙c, ct˙a] a(ct˙a, as˙b) b(as˙b, bs˙a) a(bs˙a, at˙#) a(#y˙a, af˙c)
c(af˙c, ct˙a)
Precedence-parsing algorithm The parsing algorithm for PR grammars is analogous to the one for
OP grammars described in [
Such a parser accepts also some strings not in () if their APRs comply with PR(). Far from
being a defect, this property is fundamental for the algebraic theory of OP languages [
The parsing algorithm difers from the classic OP one in two related aspects: (i) the grammar rules may exhibit adjacent nonterminals, and (ii) precedence relations involve attributes instead of terminals. We informally proceed to describe it.
The initial parser tape (which in left-to-right mode is a pushdown stack) is the input = #1 . . . #. For the current input letter , the attribute () is found in the APR table by look-up of the triple − 1+1, and it is pushed on the stack. If relation () ˙ (+1) is ˙ or ˙ attribute (+1) is pushed on the stack together with ˙ (shift move). If ˙ = ˙ or ˙ = ˙ the parser executes a reduction; else ˙ is undefined and the parser enters an error mode. In a reduction move, the stack is scanned backwards while relations ˙ occur, until a relation ˙ is found. The (finite) tape section in between ˙ and ˙ or ˙ is the handle. The handle is replaced by a single element, namely the attribute value (computed as in Eq. (1)) of the handle parent. Then the relations between the two attributes, one preceding the other following the parent attribute, determine the next parser move. The parser accepts if it completely scans the input and reduces to a single node, i.e. the root of the attributed skeletal tree.
Remark on local parsability. The earliest formal definition of local parsability (LP) we know is in [25]
and concerns a restricted family of regular languages called code-words. For context-free languages, LP
is a characteristic property of the OP family; it is preserved by some families that include OP and still
use operator form rules, see in particular [
Our PR parser has the local parsing property. The local parsability property is important for eficiently
implementing data-parallelism in parsers. The techniques for OP parser parallelization in [
Language recognized by parser vs language defined by grammar Since the set of strings
recognized by the PR parser only depends on the PRs of , we denoted it by (PR()). Clearly
() ⊆ (PR()). Interestingly, (PR()) is included in the language defined by a PR grammar,
called free, (the free PR grammars are the counterpart of the free OP grammars [
The free grammar associated to ̃︀ is ̂︀ = (Σ, ̂︀ , ̂︀, ̂︀) where ̂︀ = () and ̂︀ = { ∈ () | ⟨, ⟩ ∈ ̃︀}.
is defined as ℎ(⟨, ⟩) = , ∈ , i.e., the nonterminals that have identical attributes are coalesced, and ℎ(⟨, ⟩) = , ∈ Σ, i.e., it erases the (leaf) attributes of type 1 thus making the terminal alphabet identical to Σ. The rule set is ̂︀ = ℎ(̃︀).
Example 5 (Free grammar vs ANF grammar). The grammar = { → , → , → } has the ANF below.
ANF grammar ̃︀ free grammar ̂︀ [#˙, ˙#] → (#˙, ˙) [˙, ˙#] [#˙, ˙#] → [˙, ˙#] [˙, ˙#] → (˙, ˙) [˙, ˙#] [˙, ˙#] → [˙, ˙#] [˙, ˙#] → (˙, ˙#) [˙, ˙#] → Notice that () = 3 and (̂︀) = +.
The next statement is immediate.
Proposition 2. The language inclusion relations hold: () ⊆ (PR()) ⊆ (̂︀).
In fact, the APR() used by the parser at each reduction step are included into, but not necessarily saturate the APRs of the free grammar. Therefore the parser may reject some strings in (̂︀). Union It is natural to consider as compatible two PR grammars such that their APRs do not clash, in the sense that their union does not contain a conflict. For compatible grammars closure under union is immediate.
Theorem 1 (Closure under union). Let ′ and ′′ be PR grammars such that the set PR(′) ∪ PR(′′) is conflict-free. The language (′) ∪ (′′) has the PR property.
Proof. Assume for simplicity and without loss of generality that the grammars are free from copy rules. Let ′ ∩ ′′ = ∅, and define as (Σ, ′ ∪ ′′ , ′ ∪ ′′, ′ ∪ ′′) so that () = (′) ∪ (′′). Since PR() = PR(′) ∪ PR(′′) is conflict-free, grammar is PR.
We observe that grammar may be ambiguous in a mild way that does not prevent deterministic parsing. More precisely a string ∈ () may have two structurally identical syntax trees that only difer in the nonterminal labels. In that case the parser will compute only one syntax tree with two labels per internal node.
Our objective was to define a novel type of precedence relation and a corresponding family of languages that include the OPL yet do not require the operator form of grammars. We show that every OP grammar has the PRP.
We recall that on operator-precedence grammars three precedence relations, for brevity OPR, are defined over (Σ ∪ #)2: ⋖ , ⋗ and =. , resp. named yield, take, equal in precedence. Notice that such relations are defined between two terminals that are adjacent, or also separated by a nonterminal, in a sentential form (antichain). Although conceptually similar, our APR definitions difer in three ways: they are defined on attributes, they include the facing relation, and are only defined between two nodes that are adjacent in antichains. This requires a more analytical comparison of the efect of the no-conflict condition for OPR and APR, in the next lemma.
Lemma 1 (Operator-precedence grammars vs PR grammars). Let be an operator precedence grammar. Then G meets the PR property.
Proof. Assuming the relations OPR() ⊆ (Σ ∪ #)2 to be conflict-free, we prove that the relations APR() are conflict-free. First, the obvious constraints imposed on APRs by the operator form are: neither facing relations nor relations between two internal tree nodes are possible. The remaining cases are: (1) relations ˙, ˙, ˙ between two (adjacent) leaves, and (2) relations between a leaf and an internal node or conversely. For cases (1) and (2) we prove that a conflict in APR() implies a conflict in OPR().
Let the conflicting pairs be ′, ′′ and ′, ′′ with (′) = (′), (′′) = (′′). 1. Leaf-Leaf. From definitions, a terminal-terminal PR implies in OPR the corresponding relation through the correspondence: ˙ ↦→ ⋖, ˙ ↦→ ⋗, ˙ ↦→ =. . We prove just the case for the conflict ′ ˙ ′′, ′ ˙ ′′ schematized below, the others being similar.
•
•
From ′ ˙ ′′, the attributes of the first pair have the form (′) = (. . . , ˙ ) and (′′) = ( ˙ , . . .). From ′ ˙ ′′, the attributes of the second pair have the form (′) = (. . . , ˙ ) and (′′) = ( ˙ , . . .), whence the OPG conflict ⋖ , =. . 2. Leaf-Internal (Internal-Leaf is similar and omitted). By symmetry it sufices to prove the case for the two pairs ′ ˙ ′′ and ′ ˙ ′′, resp. schematized in tree , and in the trees 1 and 2. t t1 t2 • d
• n′′ . . .
n′′′, f e From ′ ˙ ′′ the attributes in tree have the forms: (′) = (. . . , ˙ ) and (′′) = [ ˙ , ˙ ]. The corresponding OPRs are ⋖ , ⋗ . In addition, relation ⋖ holds since the nonterminal label of ′′ is “transparent”, by convention in OP. From ′ ˙ ′′, the attributes forms in trees 1 and 2 are (′) = (. . . , ˙ ) and (′′) = [ ˙ , ˙ ]. The possible subcases for ′′′, schematized in tree 1 and 2, difer in the respective APRs: (′′) ˙ (′′′) and (′′) ˙ (′′′). They imply respectively the OPRs =. and ⋗ , conflicting in both cases with the previous OPR ⋖ of tree .
Theorem 2. The family of OP grammars is strictly included in the family of operator form grammars that have the PR property.
Proof. The weak inclusion follows from Lemma 1. The strict inclusion is witnessed by the PR grammar → | , → | , → | , → that has the OP conflict ⋖ , ⋗ . Lemma 2. The PR language = {() | ≥ 0} of Ex. 3 is not defined by any OP grammar. Proof. From the pumping lemma for CF languages, any long enough sentence in can be written as , ≥ 1, where , , are finite strings, = , and is a cyclic permutation of . Therefore any (operator-form grammar) for must produce a derivation of the form →+ where the cases for are: , , . This can be done in finitely many ways, each one can be proved to lead to OP conflicts. We just consider some cases, omitting the others, which are similar.
1. = and rule → . Conflicts: ⋖ , ⋗ , =. . 2. = and rule → . Conflicts: ⋖ , =. . Similarly for case = . 3. = and rules → , → , i.e., →2 . Conflicts: =. , ⋗ . Theorem 3. The family of OP languages is strictly included in the family of PR languages.
At last, we discuss a drawback of OP rules that we have been able to cure using PR grammars. Consider a set of operators that are syntactically equivalent, e.g., in arithmetic expressions, the multiply and divide. In OP rules we cannot factor out both operators into a nonterminal div_mult → * | /, without creating a non-operator rule such as → div_mult . We have experimentally found that such a transformation of typical OP grammars preserves the PRP. Notice that factoring transforms an OP grammar into the well-known generalized Chomsky normal form (GCNF), where only two types of rules are present: → with ∈ Σ, and → with ∈ +. In the GCNF, the only PR between terminals is ˙ . The question whether for any OP the corresponding GCNF has the PRP is open.
The idea of (sinthesized) attributes as the support of precedence relations is original and quite general, and its realization in Def. 2 is a satisfactory instantiation we arrived at after experimenting with other more complex definitions on a set of typical but small grammar examples. We intend to extend the experimentation to representative collections of grammars for artificial languages, to confirm the attribute definition or to improve it.
Several natural and interesting theoretical questions are ahead. The Boolean closure of the family of PR-compatible languages, if proved, would open the way to developing logical definitions of PR languages, in view of application to model checking of formal specifications.
Concerning syntactic properties, it would be interesting to extend PR definitions when regular expressions are permitted in grammar rules (as done for OP in [26]). Another range of open questions is which grammar transformations (e.g., into Greibach normal form) preserve the PR property. Acknowledgment. We thank Dino Mandrioli for continuous encouragement and helpful discussions, and the anonymous reviewers for their suggestions.
The author(s) have not employed any Generative AI tools. 3390/a17080345. [19] D. E. Knuth, Semantics of context-free languages, Math. Syst. Theory 2 (1968) 127–145. doi:10.
1007/BF01692511. [20] H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi, Tree automata techniques and applications, https://hal.inria.fr/hal-03367725, 2008. URL: http: //tata.gforge.inria.fr. [21] N. Wirth, H. Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Commun.
ACM 9 (1966) 13–25. URL: https://doi.org/10.1145/365153.365162. doi:10.1145/365153.365162. [22] D. Grune, Parsing Techniques: A Practical Guide, 2nd ed., Springer Publishing Company, Incorporated, 2010. [23] M. J. Fischer, Some properties of precedence languages, in: STOC ’69: Proc. first annual ACM
Symp. on Theory of Computing, ACM, New York, NY, USA, 1969, pp. 181–190. [24] A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman, Compilers: principles, techniques, and tools, second ed., Pearson/Addison Wesley, 2007. [25] R. McNaughton, S. Papert, Counter-free Automata, MIT Press, Cambridge, USA, 1971. [26] M. Chiari, D. Mandrioli, M. Pradella, Cyclic operator precedence grammars for improved parallel parsing, in: DLT’24, volume 14791 of LNCS, Springer, 2024, pp. 98–113. doi:10.1007/ 978-3-031-66159-4_8.