Characterizing unambiguous precedence systems in expressions without superfluous parentheses

Abstract

When infix notation is used, parentheses are sometimes omitted according to specified rules, where it is assumed that the operators are stratified in precedence levels, and operators on each level are either left or right associative. Instead of making such an assumption, we carefully analyse the notion of superfluous parentheses by first giving a definition of a general precedence system, which declares the superfluous parenthesis pairs for any given expression. We provide a characterization of unambiguity in this general setting, and study the complexity of parsing expressions without superfluous parentheses. Also, we study the two notions of maximal unambiguous and complete precedence systems, and give a characterization for each one of these notions. Finally, we show that complete precedence systems can be equivalently described by a chain of left associative and right associative classes of operators, with some extra restrictions on the relative positions and the associativity of unary operators.

Keywords:

• formal languages
• superfluous parentheses
• precedence order
• infix notation
• unambiguous grammars

2000 AMS Subject Classification :

• 03D05
• 68Q42
• 68Q45

CCS Category :

• F.4.2
• F.4.3
• G.2.2

Acknowledgements

The author would like to thank three anonymous referees for their meticulous reading and helpful comments on the paper.

Notes

Note that in our metalanguage, we sometimes use the brackets [,] instead of the parentheses (,), when the latter may appear in the object language.

Note that the unary negation ‘⊖’ is different form the binary subtraction operator ‘−’.

Note that the root at Level 0 is always labelled by the starting symbol S. The reader may be used to a slightly different convention, where the root gets labelled by the main operator. However, this convention is useful only when we abstract the expression from its linear syntactical form.

The reader may prefer to say that + precedes ×, but this, of course, depends on the way we view an expression, whether it is a tree growing downward or upward, and whether we evaluate that tree by first evaluating its leaves, and then proceed to the root (or vice versa).

I always explain to my students the wisdom behind the right associativity in an expression like , namely, we do not really mean e ^2x . This, of course, does not rule out that some CS scholars prefer all the operators to be left associative.

This is an even better reason for the right associativity of ↑.

In predicate logic, logicians have adopted the convention that constant symbols are merely function symbols with zero arity, and propositional symbols are predicate symbols with zero arity.