Characterizing unambiguous precedence systems in expressions without superfluous parentheses
Wafik Boulos Lotfallah · International Journal of Computer Mathematics · 2008
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.