10
$\begingroup$

I've found that many grammars have a production called PrimaryExpression or something along those lines. ECMAScript has PrimaryExpression, Python has primary, C# has primary_expression, Java has Primary, and many more I've seen over the years.

It cannot be a coincidence that all these specifications have it. What is considered a "primary expression"?

Maybe Haskell has one too, but I can't decipher which one it is. If there's a primary expression, what's it called in their specification? If there's no primary expression, what's different about Haskell's syntax (or the way grammar is defined) that makes it stand out?

$\endgroup$
2
  • 1
    $\begingroup$ I would argue that it is indeed a coincidence - "primary" is just a good name for the "top" of whatever expression hierarchy you have. $\endgroup$
    – blueberry
    Nov 29, 2023 at 22:43
  • $\begingroup$ In Haskell it seems to be "aexp". $\endgroup$
    – kaya3
    Nov 29, 2023 at 23:21

3 Answers 3

13
$\begingroup$

I don't think there is a universal definition, but I'll attempt one anyway: the primary expressions in a language are those which have the highest level of precedence, and for which there is no need to specify the relative precedence of different primary expressions because the syntax would never be ambiguous.

So, expressions like 1 (a literal) or x (a simple name) are primary, but also f(x) is primary in languages like Java because there are no other primaries you could replace f or x with that would need additional parentheses to be unambiguous. Likewise, x.y.z() is primary because there is no syntactic ambiguity: it must mean (x.y).z(), because x.(y.z()) is not valid.

Compare this with binary operator expressions, like x + y * z where either (x + y) * z or x + (y * z) could be valid, or unary operator expressions like *x++ where either (*x)++ or *(x++) could be valid. In these cases, precedence rules are required to disambiguate.


It's also worth thinking about this from the perspective of parsers. In a hand-written parser, the parseExpression() function could look something like this:

function parseExpression(minPrecedence) {
    let expr = parseUnaryExpression(minPrecedence);
    while(hasNextBinaryOperator(minPrecedence)) {
        let op = pollBinaryOperator();
        let rhs = parseExpression(precedenceOf(op));
        expr = new BinaryExpr(expr, op, rhs);
    }
    return expr;
}

This is an oversimplification, but let's keep it simple. You need a parseUnaryExpression() function because you want to call it unconditionally; if you called parseExpression() recursively there, it would never terminate. So then the parseUnaryExpression() function could look like this:

function parseUnaryExpression(minPrecedence) {
    if(hasNextUnaryOperator(minPrecedence)) {
        let op = pollUnaryOperator();
        let rhs = parseUnaryExpression(precedenceOf(op));
        return new UnaryExpr(op, rhs);
    } else {
        return parsePrimaryExpression();
    }
}

Again, this is an oversimplification (e.g. it ignores the possibility of postfix unary operators), but it gets the point across: the binary operators are already handled in the first function, and now this function handles all the unary operators, and then for the same reason ─ recursion needing a base case ─ you need a separate parsePrimaryExpression() function.

However, note that parsePrimaryExpression() doesn't need a minPrecedence argument. This is because for all the remaining types of expression, we know when to stop parsing based on knowing what the last token in that expression should be. There might be a loop condition (e.g. to parse a.b.c.d, keep going as long as there is another dot) but there is no need to consider precedence, because all operators with precedences below the maximum have already been handled elsewhere.

$\endgroup$
5
  • 1
    $\begingroup$ And of course there are languages (not even terribly obscure ones) where f(x) or x.y.z() wouldn't be primary in that sense. So it all comes down to the language you're parsing. $\endgroup$
    – hobbs
    Nov 30, 2023 at 20:32
  • $\begingroup$ ... such as C, among others. $\endgroup$ Nov 30, 2023 at 21:55
  • $\begingroup$ But precedence of operations does seem to be the conventional way to look at it. The primary expressions are those that can be operands of the highest-precedence operators. $\endgroup$ Nov 30, 2023 at 21:59
  • $\begingroup$ @JohnBollinger Yes, although I wouldn't phrase it like that because conventionally things like (...) and x.y are included alongside "operators" in precedence tables, e.g. Python and Javascript. So many people would consider these to be the highest-precedence constructs, even though they are not technically operators $\endgroup$
    – kaya3
    Nov 30, 2023 at 22:39
  • $\begingroup$ In my language they are both implemented as the highest-precedence postfix operators, not as primaries, so you can still have that “technically” not be technical $\endgroup$
    – Seggan
    Dec 1, 2023 at 1:25
2
$\begingroup$

It's merely a convention, which goes back to at least Schorre's definition of Meta-2 in 1964. I don't know to what extent there were equivalent (published) syntax specifications before that, particularly in the form of text-based rules or equations.

See https://dl.acm.org/doi/10.1145/800257.808896 where in the specification for either the VALGOL-I or VALGOL-II demonstration language a primary is defined as the product of terms and so on.

This has obviously been quite a lot of tidying up and codification in the intervening 60 years.

Updated: here is a direct link to a reprint https://forum.lazarus.freepascal.org/index.php?action=dlattach;topic=56614.0;attach=45608

$\endgroup$
1
$\begingroup$

All of the instances you link are atomic (or at least cohesive) value head expressions, without including any operator expressions: x and 3.5 and (x + 3.5) are primary expressions, but x + 3.5 is not, while still being an expression. This structure can make unambiguous parsing easier. The name itself is not significant, but Primary is a common term for it.

Other parts of the grammar can say they accept any "expression" (for example, the right-hand side of an assignment or an argument list), but the parts that deal with constructing expressions themselves want to talk about the indivisible units of expressions in places.

$\endgroup$
2
  • $\begingroup$ This isn't quite accurate: in Java x.y.z is a primary expression, but I wouldn't call it atomic. $\endgroup$
    – kaya3
    Nov 29, 2023 at 23:07
  • $\begingroup$ Yeah, I’m not sure quite what the right phrasing is. It’s treated as a unit by the rest of the grammar and most are genuinely atomic, but a few are still slightly divisible. Some of the others don’t include that sort of thing in with the rest. $\endgroup$
    – Michael Homer
    Nov 29, 2023 at 23:11

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .