How to disambiguate CFG with unary/binary minus and binary prefix operator

Question

I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1).

I'm facing the current fragment of the language:

$$ \begin{align} S & → T \quad | \quad \texttt{prefix} \quad T \quad S \\ T & → F \quad | \quad T \texttt{-} F \quad | \quad \texttt{-} F \\ F & → \texttt{1} \end{align} $$

The tokens prefix and 1 and - are terminals.

Note that prefix 1 - 1 - 1 has at least two parses: prefix (1-1) (-1) and prefix 1 (-(1-1)).

I'm willing to make small changes to the language to resolve this ambiguity, but I would prefer only making grammar changes that resolve just this ambiguity. Are there local transformations I can make? Global ones?

I think inserting a new token, e.g. :, between T and S in the prefix production should disambiguate the grammar.

Is it possible to transform the grammar such that it (a) becomes LR(1); and (b) encodes the rule "always parse the shortest possible substring as the T part in a prefix production"?

(I think I cannot do the longest string—it seems hard to know that what follows will fail to parse as an S. It will become even harder once I add in the rest of the language.)

Answer 1

I'm going to limit myself, at least for now, to the question actually asked here: how to deal with the ambiguity between an operator which could be prefix or infix (such as unary negation) and a prefix operator which takes two consecutive arguments. There is a second interesting question, which has to do with prefix operators which bind less tightly than (some) infix operators.

These two language features are not really related, but they are similar in that the naïve grammars are ambiguous, and the ambiguities are difficult to resolve in a strict LR(k) grammar. They are also similar in the fact that many languages suffer from inadequate resolutions of these ambiguities, or resolve them in ways that are poorly understood by language users, in part because the resolutions are hard to document.

Ambiguity with prefix negation

Since prefix negation and infix difference operators generally use the same symbol (-), an ambiguity is created in any syntactic construct in which two expressions can appear consecutively without an intervening token. Many languages have such constructs. They include:

• Prefix operators which take more than one argument, as in your question.

• Implicit operators such as implied multiplication (2x instead of 2*x) and function application (as in Haskell, where f a calls f with argument a, similar to f(a) in many other languages). Other examples include Awk's implicit string concatenation syntax, where a b represents the concatenation of the two variables.

• Undelimited sequences, usually lists or tuples, where consecutive elements are simply specified one after another and the elements can be expressions. One early language with this feature is Logo, but there are many others.

• Undelimited statements. In languages in which statements can be written consecutively without a separating delimiter (Lua, for example), two expressions can be consecutive if an expression can be a statement, or more generally if there are statement syntaxes which start with an expression (such as assignment statements) and other syntaxes which end with an expression (such as return statements).

That's not an exhaustive catalogue, but it gives an idea of the range of the issue.

There are three broad strategies to resolve this ambiguity:

1. Require the first expression (or both expressions) to be either an atomic term or a parenthesised subexpression. If the ambiguity is the result of an implicit operator, this resolution will be natural if the implicit operator's binding precedence is at the top of the precedence list; that's the case with Haskell, for example, where function application takes precedence over any other operator. This strategy is also sometimes used for undelimited lists, allowing a list of three elements to be written [a b c] if the components are simple, but requiring [a (b + c) d] for more complicated components.

2. Prohibit the second expression from starting with an ambiguous prefix operator. Or, in other words, resolve the ambiguity in favour of the infix operator, when there is a choice. This is the preferred solution for implicit multiplication, and it follows the Principle of Least Astonishment, since resolving 2-x as 2*(-x) would astonish most users. This does not require the implicit operator to have maximum precedence; indeed, most grammars with implicit multiplication would parse 2x^4 (where ^ is the exponentiation operator) as 2*(x^4), again to avoid surprises. (Different parsers resolve 2a/3b in different ways, so there can still be surprises. Some people feel that implicit multiplication should bind more strongly than explicit multiplication and division; others that implicit and explicit multiplication should bind equally. But that's a different issue.)

3. Resolve the ambiguity between unary negation and binary difference during lexical analysis. For example, Logo requires that the unary negation operator either be preceded by an open parenthesis or some token which cannot be part of an expression, so that binary difference is not a possible interpretation, or that it be written with at least one space before and no spaces after. The second rule allows a -10 * b to be interpreted as the two expressions a and ((-10)*b), while a - 10 * b would necessarily be interpreted as a single expression. A similar, but more complicated, set of whitespace-aware rules was proposed for the Frontier language (never implemented, to my knowledge); it was criticised for being too subtle for code readers.

Solution one is appropriate for Haskell. Since it's simply an operator precedence rule, it's easy to describe. The expression fmap f (Just x) needs to be written that way because function application is left-associative; fmap f Just x would be (((fmap f) Just) x) so the requirement to parenthesise (Just x) is pretty clear, in the same way that you would have to write a - (b - c), if that's what you meant. (It's worth noting that Haskell also has an explicit application operator, $, with low binding precedence, which can sometimes be used to avoid parentheses.)

Solution three is certainly possible, but whitespace-aware syntax is a common source of confusion for casual users. (And, as noted above, is easy to miss when you're reading code.)

So my preference would be solution two: when both interpretations of the unary/binary operator are possible, always prefer the binary interpretation. That's often simply the expected interpretation, although it can lead to surprises when the consecutive expressions are separated by a newline; even then, the rule is easy to explain.

It's also easy to implement. The basic idea is to define two different expression non-terminals. One is unrestricted; it is used for the first expression in a consecutive sequence. The other one does not accept any expression whose first token is an ambiguous unary operator. (If the language has unambiguous unary operators, they don't need to be restricted.)

If you were using a parser generator which accepted the formalism in the ECMAScript standard, this would be trivial. Unfortunately, few (if any) parser generators allow templated non-terminals, so the implementation requires annoying code duplication in the grammar. In yacc/bison syntax, assuming that operator precedence is established with prior precedence declarations:

expr: expr '+' expr
    | expr '-' expr
    | expr '*' expr
    /* other binary operators omitted */
    | '-' expr %prec UNOP
    | '+' expr %prec UNOP
    | CONSTANT
    | IDENTIFIER
    | '(' expr ')'
expr_follow
    : expr_follow '+' expr
    | expr_follow '-' expr
    | expr_follow '*' expr
    /* ... other binary operators */
    /* ambiguous unary operators omitted */
    | CONSTANT
    | IDENTIFIER
    | '(' expr ')'

Note that the expr_follow restriction cascades only through the first operand of the productions; the operands following an operator or ( do not need to be restricted since they will not affect the first token in the expression.

If you were using cascading-precedence style rather than precedence operators, you'd need to create two non-terminals at each precedence level, something like this:

expr: additive
additive
    : additive '+' multiplicative
    | additive '-' multiplicative
    | multiplicative
multiplicative
    : multiplicative '*' negative
    | multiplicative '/' negative
    | multiplicative '%' negative
    | negative
negative
    : '-' negative
    | exponential
exponential
    : unary '^' negative
    | unary
unary
    : '&' unary   /* '&' represents an unambiguous unary operator */
    | atom
atom: CONSTANT
    | IDENTIFIER
    | '(' expr ')'

expr_follow
    : additive_follow
additive_follow
    : additive_follow '+' multiplicative
    | additive_follow '-' multiplicative
    | multiplicative_follow
multiplicative_follow
    : multiplicative_follow '*' exponential
    | multiplicative_follow '/' exponential
    | multiplicative_follow '%' exponential
    | exponential

In the first stanza, I would usually simplify negative to:

negative
    : '-' negative
    | unary '^' negative
    | unary

I wrote it the way I did to better illustrate the difference between the two cascades. The second cascade does not have negative because the unary negative cannot appear at the start of expr_follow (so there is no negative_follow). exponential, unary and atom do not need to be duplicated because none of them can start with unary negative.

Read this if you're considering designing a language with consecutive expressions

On the whole, a syntax which allows two consecutive expressions is a snakepit of perpetual syntactic problems. Each ambiguity needs to be identified and then resolved in the parser. Since there is no universal principle which determines a unique resolution, the language designer needs to think through the possible disambiguations and choose the one they feel is best suited to the problem domain.

Each such resolution is, in general, easy to implement once it has been precisely spelled out, but the rules can be very difficult to describe or justify to users. That can lead to mysterious bugs, in which a syntactic construct was resolved in an unexpected way, or mysterious syntax errors, in which a syntactic construct which seems reasonable to the coder was banned for ease of implementation. One frequent consequence in languages which develop to the point of having style guides and linters, is a stylistic ban on precisely these syntactic constructs; either alternative syntaxes or redundant parentheses are required, and these can even give rise to the language implementation itself issuing warnings.

Answer 2

I came up with a simple and acceptable solution: the first argument to the binary prefix operator can be any expression with a precedence binding tighter than unary negation. That's almost no expressions, but it does include integer literals which is the most common case.

This reminds me of a bit of haskell syntax. Note that <Expression> <Expression> is valid Haskell syntax, e.g. for function application which associates left; the associativity and precedence should be enough to work around the ambiguity of $E → E \ E$.

There's also pattern matching in function declarations, e.g.

fmap f (Just x) = Just (f x)
fmap f Nothing = Nothing

Here you have to parenthesize the multi-token pattern (Just x), but not the single-token pattern Nothing. I suspect this is for similar reasons.

To answer rici's questions in the comments: I am trying to implement this and would prefer an LALR(1) grammar.

My current grammar, including my solution, does the usual

<Term> ::= <Factor>
         | <Term> + <Factor>

shenanigans to encode precedence and associativity. I have some productions which benefit from the rules being split up into small chunks this way, once again having to do with ambiguities around prefix vs. infix operators.

I guess I could look in the Happy manual and experiment with precedence rules to express my solution that way, but I'd rather start by building something that works on the basis of my understanding of context-free grammars. Also, I'm learning plenty in the process, which is one of my goals. But I'll definitely put experimenting with precedence rules on the TODO list, just to see if it does anything to the underlying PDA.