1
$\begingroup$

The documentation says that expr& has lower precedence than expr1 /. expr2. Thus, parsing should start from operators with the lowest precedence, like FormBox, and then reach deep into the parse tree, all the way down to operators with high precedence, like raw symbols and numbers.

By this logic, a&/.b should be parsed like this:

  1. Attempt to parse FormBox, then CompoundExpression, down to the lambda expr&.
  2. a& is parsed as Function[a].
  3. We're done, but there's /.b left to parse. Yet there are no rules for (expr1 &) /. expr2 since expr& has lower precedence than expr1 /. expr2.
  4. Thus, a&/.b should be a syntax error.

I imagine an EBNF grammar for this "lambda+ReplaceAll with symbols" mini-language like this:

start: function
function: replace_all
 | function "&"
replace_all: symbol
 | replace_all "/." symbol
symbol: /[a-zA-Z][0-9a-zA-Z]*/

Apparently, this is incorrect since the Wolfram Language can parse this:

Hold[a & /. b] // TreeForm

Parse tree

Turns out, a&/.b parses as (a&) /. b. Doesn't this mean that expr& has higher precedence than expr1 /. expr2?

c/.d& parses as I'd expect:

  1. Try to parse expr1&.
  2. Here expr1 is c/.d.
  3. Try to parse expr1 as something with a higher precedence, like AddTo, SubtractFrom or ReplaceAll.
  4. expr2 /. expr3 matches, so we get expr2 == c and expr3 == d.

Thus, the tree is:

Needs["CodeParser`"]
CodeParse["(a&/.b);(c/.d&)"] //. {
   ContainerNode[_, {a_}, _] -> a,
   LeafNode[_, a_, _] -> a, 
   CallNode[head_, {args__}, _] -> head[args]
   } // TreeForm

enter image description here

The left subtree is for a&/.b (which doesn't make sense) and the right subtree is for c/.d& (which seems fine).

  • Why does a & /. b parse at all if a & has lower precedence than x /. y?
  • What could a proper (E)BNF grammar for the mini-language of lambdas and ReplaceAlls look like?
Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ I don't understand what alternative order of operations is possible, so that precedence is needed to decide between the alternatives. $\endgroup$ Commented Mar 5, 2023 at 0:51
  • $\begingroup$ @MichaelE2, the alternative "order of operations" is a syntax error: since a& has lower precedence, I parse it first, and that's it, there's no grammar to match /.b. Is this understanding incorrect? Also, since a&/.b is parsed as (a&)/.b, doesn't this imply that a& has higher precedence than x/.y? For this to work, I'd need to parse the binary /. operator first, followed by the unary & operator, right? $\endgroup$ Commented Mar 5, 2023 at 12:59
  • $\begingroup$ @MichaelE2, alternative way of asking the same question: if a&/.b is parsed as (a &) /. b, which operator has higher precedence: & or /.? It seems to me that & has higher precedence, but the documentation says otherwise. Where's my mistake? $\endgroup$ Commented Mar 5, 2023 at 13:03
  • $\begingroup$ It makes no sense at all to take a syntactically valid parse and declare it a syntax error. I doubt any existing parser would do that. Voting to close. $\endgroup$ Commented Mar 5, 2023 at 16:23
  • 1
    $\begingroup$ Perhaps the confusion arises due to the fact that & is a postfix operator, and /. is an infix operator. Imagine a similar example with Derivative and Map. Looking at the Operator Precedence Table, /@ has a higher precedence than ', yet f'/@{1, 2, 3} is parsed as expected to {Derivative[1][f][1], Derivative[1][f][2], Derivative[1][f][3]}. Similarly, + (infix) has higher precedence than ¬ (prefix), yet p+¬q is parsed ("as expected") to Plus[p,Not[q]]. $\endgroup$ Commented Mar 5, 2023 at 17:46

1 Answer 1

Reset to default
2
$\begingroup$

This is how I remember LR parsing and the role of precedence.

Grammar for the discussion at hand. I'll assume symbols are already tokenized by the lexer or whatever. Rule 2 is irrelevant in the examples below; it is included in case parentheses come up.

1. E   :  Symbol[...] 
2.     : '(' E ')'
3.     : E '/.' E
4.     : E '&'

The columns are (1) the current input token, (2) the stack, and (3) the action that occurs based the input and stack. The number of the reduction corresponds to the production rule in the grammar with the same number. I assume that /. has be specified in some way to have precedence over &. Precedence is a cheap way to resolve conflicts (easier and less costly than writing a grammar without conflicts, IIRC).

Input a /. b & Stack Action
a {} Shift
/. {a} Reduce 1: E(1) -> a
/. {E(1)} Shift
b {E(1), /.} Shift
& {E(1), /., b} Reduce 1: E(2) -> b
& {E(1), /., E(2)} Shift/Reduce conflict (4/3).
Precedence /. > &:
Reduce 3: E(3) -> a /. b
& {E(3)} Shift
< null > {E(3), &} Reduce 4: E(4) -> a /. b &
< null > {E(4)} < done >

"Precedence" as an add-on to the grammar is not needed here.

Input a & /. b Stack Action
a {} Shift
& {a} Reduce 1: E(1) -> a
& {E(1)} Shift
/. {E(1), &} Reduce 4: E(2) -> a &
/. {E(2)} Shift
b {E(2), /.} Shift
< null > {E(2), /., b} Reduce 1: E(3) -> b
< null > {E(2), /., E(3)} Reduce 3: E(4) -> a & /. b
< null > {E(4)} < done >

Precedence may have another meaning in a different context. Perhaps the problem can be examined in terms of unary v. binary, postfix v. infix (as suggested in the comments). I'm not sure how, except to say that production rule 3 in the grammar cannot be applied unless it has a valid E expression to the left (and to the right). It seems a stretch to say this is an infix issue, given that & is not a valid E -- to me, the problem centers on that. But if you want to say & is a problem because /. is infix, then I guess "infix" is an explanation. Whatever the point of view, rule 3 cannot (may not) be applied to & /. b.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.