0
$\begingroup$

In Unix shell programming, there's the ideom:

program1 && program2 && program3

where successful completion of program1 and then program2 will lead to the execution of program3.

In Perl, there's 2 set of condition operators - punctuation styles &&, ||, etc., which binds more closely; and keyword style and, or, etc., which binds more loosely (precedence below assignment operators).

Yesterday, I write this in C:

yesno && pointer += offset;

trying to achieve this: if yesno is true, pointer is advanced by an offset, otherwise, no action is taken. Of couse this failed because condition operators binds more closely than assignments and the expression became:

(yesno && pointer) += offset;

which is invalid since the left-side of the assignment is no longer an lvalue.

Question:

Of course, if there's a programming language with grammar that makes it legal, it would create whole lot of problem designing a compiler for it and write correct and efficient codes in it.

But for curiosity, I'd like to know is it possible to define a grammar such that make it possible to do:

  • advance pointer by an offset with:
yesno && pointer += offset;

and

  • assign boolean predicate to a variable:
cond = input_ready && output_ready;
$\endgroup$
5
  • 2
    $\begingroup$ Sure. There's no rule that says that the left and right precedences have to be similar. $\endgroup$
    – rici
    Commented Nov 19, 2021 at 4:36
  • $\begingroup$ @rici, I know. I've read the drafts of the C standards and know how precedences (and left/right-associativity) are defined in terms of nested non-terminal symbols. I'll come up with a solution in context-free grammar in spare time if nobody else does. $\endgroup$
    – DannyNiu
    Commented Nov 19, 2021 at 5:50
  • 1
    $\begingroup$ Your question was just "is it possible". It is possible. If you want someone to do the work for you, you'll have to ask them to do that. :-) But my free time is perhaps more limited than yours. $\endgroup$
    – rici
    Commented Nov 19, 2021 at 5:58
  • $\begingroup$ @rici True. But if someone just literally answer "it's possible" without demonstrating or proving it, it wouldn't be an interesting and up-vote-able answer. $\endgroup$
    – DannyNiu
    Commented Nov 19, 2021 at 6:01
  • $\begingroup$ Which is why it's a comment :-) $\endgroup$
    – rici
    Commented Nov 19, 2021 at 7:36

2 Answers 2

0
$\begingroup$

What you seem to be asking for is for assignment and && to have different relevant precedence depending on which occurs on the left or the right -- = has higher precedence when it is to the left of the && and lower when it is to the right.

This turns out to be remarkably hard to do with a traditional "pure" CFG, but fairly straight-forward to do with yacc's precedence declarations. The key to that is to realize that "precedence" in yacc really isn't about operations, it is about rules and tokens -- whenever a shift/reduce conflict occurs, it compares the precedence of the token to be shifted with that of the rule to be reduced and it does whichever is higher.

To have different precedence for on-the-left vs on-th-right, you just need difference precedences for the rule and the token, which you can do with a %prec directive. For your example, something like:

%nonassoc ASSIGN_LOW
%left ANDAND
%right '='

%%

expr: expr '=' expr %prec ASSIGN_LOW
    | expr ANDAND expr
    | primary
    ;

This gives a higher precedence to an = token than an && (or the rule with && which gets that precedence by default), so when an = appears to the right, it has higher precedence. But the full expr '=' expr rule has lower precedence, so the = on the left will be lower precedence.

This has a side effect that = will always be right recursive, even if you used %left or %nonassoc for it, as the = rule has lower precedence than the = token. I used %right here for clarity. If you did something where a rule had higher precedence that its token, that would always be effectively left-recursive.


To address the comment in the other answer, this still has issues with something like

A && B = C && D = E

which will be parsed as

A && (B = (C && (D = E)))

which might not be what you want. There's not a good way of dealing with that as it would require looking at more context to determine the precedence.

$\endgroup$
-1
$\begingroup$

No. At least not unambiguously with context-free grammar.

Take the following grammar fragment as an example:

## preliminary
def assign-op # assignment operator
: ...
; 

def unary-expr # uniary expression
: ...
;

## main grammar

def arith-expr # arithmetic expression
: ...
;

def logic-expr # logical expression
: arith-expr
| logic-expr ( "&&" | "||" ) arith-expr
;

def assign-expr # assignment expression
: logic-expr
| unary-expr assign-op assign-expr
;

In assign-expr, the lvalue is already defined as an unary expression. The problem with compiler issuing error is that, yesno && pointer += offset is parsed as:

yesno && pointer      +=        offset
vvvvvvvvvvvvvvvv      ||        ||||||
(  logic-expr  )      vv        vvvvvv
(expecting:unary-expr assign-op assign-expr)

where the assignment expression is expecting an unary expression but a logical expression was present.

Also, consider:

cond1 && ptr1 = buf && ptr1 += offset;

where the expected behavior is

set ptr1 to buf + offset if cond1 is true and buf is not NULL.

If the proposed asymmetric precedence is realized, this expression would become essentially nonsense.

These can all be worked around with either a more complex grammar, or a non-conventional parser, but as explained in the question, this would make writing correct and efficient programs very difficult

$\endgroup$
1
  • $\begingroup$ Hi. I don't understand why cond1 && ptr1 = buf && ptr1 += offset would be nonsense? I think it should be parsed as cond1 && (ptr1 = (buf && (ptr1 += offset))). Basically = and && have the same priority but are right-associative. $\endgroup$
    – Stef
    Commented Feb 9 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.