<p><a href="https://langdev.stackexchange.com/q/4068/330">My previous question</a> was about how the tokenizers for programming languages which support both the ternary conditional operator <code>?:</code> and labels (with the syntax <code>labelName:</code>) know, when they see <code>:</code>, whether it belongs to <code>?:</code> or whether it's a part of a label. The general consensus in the comments and answers seems to be that the tokenizer is not supposed to know that, that it's the parser's job to determine that. However, that's not trivial to implement in the parser I made, because I'm parsing <code>?:</code> by &quot;scanning backwards&quot;, so the parser will see the <code>:</code> before it sees <code>?</code> which would warn it that the next <code>:</code> is not a label.</p>
<p>On Discord, I received some comments that the &quot;scanning backwards&quot; way of parsing right-associative operators is actually considered to be an anti-pattern in the world of programming languages. So, is that true? If so, what alternatives are recommended?</p>
<p><a href="https://github.com/FlatAssembler/PicoBlaze_Simulator_in_JS/blob/09698e1ade30cb193b3191295fda9f64e57903eb/parser.js#L289C1-L345C6" rel="noreferrer">Here is how I'm parsing <code>?:</code> in my PicoBlaze assembler</a>:</p>
<pre class="lang-js prettyprint-override"><code>  // Ternary conditional operator...
  let lastColon = tokenized.length - 2;
  if (lastColon &gt; 0)
    while (lastColon) {
      if (tokenized[lastColon].text == ':' &amp;&amp;
          tokenized[lastColon].text != '\n') {
        let questionMarkCorrespondingToTheLastColon = lastColon, counter = 1;
        console.log(
            &quot;DEBUG: Parsing the ternary conditional operator. The colon is at the index: &quot; +
            lastColon);
        while (counter) {
          questionMarkCorrespondingToTheLastColon--;
          if (!questionMarkCorrespondingToTheLastColon ||
              questionMarkCorrespondingToTheLastColon &lt; 0) {
            alert(
                &quot;Line #&quot; + tokenized[lastColon].lineNumber +
                &quot;: There is a colon without a matching question mark before it!&quot;);
            return root_of_abstract_syntax_tree;
          }
          if (tokenized[questionMarkCorrespondingToTheLastColon].text == '?')
            counter--;
          else if (tokenized[questionMarkCorrespondingToTheLastColon].text ==
                   ':')
            counter++;
        }
        console.log(&quot;DEBUG: The corresponding question mark is at the index: &quot; +
                    questionMarkCorrespondingToTheLastColon);
        let nodesThatRecursionDealsWith = [];
        for (let i = questionMarkCorrespondingToTheLastColon + 1; i &lt; lastColon;
             i++)
          nodesThatRecursionDealsWith.push(tokenized[i]);
        tokenized[questionMarkCorrespondingToTheLastColon].text = &quot;?:&quot;;
        tokenized[questionMarkCorrespondingToTheLastColon].children.push(
            tokenized[questionMarkCorrespondingToTheLastColon - 1]);
        const whatTheRecursionReturned = parse(nodesThatRecursionDealsWith);
        if (whatTheRecursionReturned.children.length &gt; 1) {
          alert(&quot;Line #&quot; + whatTheRecursionReturned.children[1].lineNumber +
                &quot;: Unexpected token `&quot; +
                whatTheRecursionReturned.children[1].text + &quot;`!&quot;);
          return root_of_abstract_syntax_tree;
        }
        tokenized[questionMarkCorrespondingToTheLastColon].children.push(
            whatTheRecursionReturned.children[0]);
        tokenized[questionMarkCorrespondingToTheLastColon].children.push(
            tokenized[lastColon + 1]);
        console.log(
            &quot;DEBUG: The ternary conditional operator converted to LISP is: &quot; +
            tokenized[questionMarkCorrespondingToTheLastColon]
                .getLispExpression());
        tokenized.splice(questionMarkCorrespondingToTheLastColon + 1,
                         lastColon - questionMarkCorrespondingToTheLastColon +
                             1);
        tokenized.splice(questionMarkCorrespondingToTheLastColon - 1, 1);
        lastColon = questionMarkCorrespondingToTheLastColon;
      }
      lastColon--;
    }
</code></pre>
<p>I'm doing a similar thing <a href="https://github.com/FlatAssembler/AECforWebAssembly/blob/24df8d70d286c27d8e90cda71aff159b0d138b49/parser.cpp#L292C1-L362C6" rel="noreferrer">in the compiler for my programming language written in C++</a>. And I'm also parsing the right-associative assignment operator <code>:=</code> by scanning backwards.</p>
<p>In the first compiler I made for my programming language, I was parsing the <code>?:</code> operator <a href="https://github.com/FlatAssembler/ArithmeticExpressionCompiler/blob/7a8d7427635e5c26b64812a2ea51220f473ba8fb/compiler.html#L1683C1-L1716C12" rel="noreferrer">like this</a>:</p>
<pre class="lang-js prettyprint-override"><code>        for (var i = 0; i &lt; arth.length; i++)
          if (arth[i].text == &quot;?&quot;) {
            if (arth.length - 1 == i || !i) {
              alerted = 1;
              alert(
                &quot;Parser error: The ternary operator '?:' has less than three operands!&quot;
              );
              return arth[0];
            }
            arth[i].operands.push(arth[i - 1]);
            arth[i].text = &quot;?:&quot;;
            var j = 1;
            var c = 1;
            do {
              if (i + j &gt;= arth.length) {
                alerted = 1;
                alert(
                  &quot;Parser error: There is a '?' without its corresponding ':'.&quot;
                );
                return arth[0];
              }
              if (arth[i + j].text == &quot;?&quot;) c++;
              if (arth[i + j].text == &quot;:&quot;) c--;
              j++;
            } while (c);
            var drugiOperand = new Array();
            for (var k = i + 1; k &lt; i + j - 1; k++) drugiOperand.push(arth[k]);
            arth[i].operands.push(parseArth(drugiOperand));
            var treciOperand = new Array();
            for (var k = i + j; k &lt; arth.length; k++)
              treciOperand.push(arth[k]);
            arth[i].operands.push(parseArth(treciOperand));
            arth = [arth[i]]; //Znam da ovo nije bas pametno, ali raditi ce dokle god je uvijetni operator upravo operator najnizeg prioriteta u cijelom jeziku.
          }
</code></pre>
<p>But, like the comments say, I don't think that's a good idea because that will work only if there is no operator with lower precedence than <code>?:</code>.</p>

<parsing>
Why is the "scan backwards" method of parsing right-associative operators considered to be anti-pattern? What alternatives are recommended?
CC BY-SA 4.0
2024-09-21T16:49:07.373Z
I don't exactly understand how your "scan backwards" algorithm works, but my first thought is that it's an overly complicated ad-hoc way to solve what is essentially a non-problem (a standard [operator precedence parser](https://en.wikipedia.org/wiki/Operator-precedence_parser) can handle both left- and right-associative operators), and potentially could lead to quadratic runtime in the worst case if you have to scan backwards over the same tokens over and over (though I would have to think more about it to be sure).
kaya3
CC BY-SA 4.0
2024-09-23T17:30:11.930Z
These people don't know what a "pattern" is. A pattern in programming is something that people do all the time. An anti-pattern is a pattern that doesn't work well for some reasons. You don't write one parser after the other, so it's not a pattern.
gnasher729
<blockquote>
<p>What alternatives are recommended?</p>
</blockquote>
<p>I'll share what I'm doing — for context, I'm using a bottom-up expression parser.  My parser is a bottoms-up shift-reduce parser, simplified (no tables) by being dedicated to infix expression parsing.</p>
<p>I treat <code>?</code> and <code>:</code> separately, each as their own individual binary operator.  Let's make <code>a ? b : c</code> an example input.</p>
<p>In some sense, my parser <em>is looking backwards</em>, but not at tokens, instead rather at operators in the intermediate state of parse/recognition.  My intermediate state is an operator stack and an operand stack — the operator stack has true language operators, not tokens, so <code>binarySubtraction</code> vs. <code>unaryNegation</code> rather than the undifferentiated <code>-</code> token; the operand stack is a stack of ASTs waiting to be combined into larger ASTs.  (And rather than having parse tables as usually seen with shift-reduce approach, I have two states represented by separate code sections in the expression parser: one for unary state and one for binary state.)</p>
<p>When I find a <code>?</code> (in the binary state) I push a special binary operator for this onto the operator stack.  I call this operator <code>TernaryTest</code> — this will not appear in the AST as it will be removed by finishing the <code>:</code> part of the operator.  At this point, the operand stack has <code>a</code> and the operator stack has <code>TernaryTest</code>, and the parser is ready to parse the next expression operand (<code>b</code>) similar to any other binary operator.</p>
<p>Then when finding a <code>:</code> operator (also found in the binary state), the parser crawls up the operator stack to find the associated <code>TernaryTest</code> (i.e. the matching <code>?</code>), much like finding the matching <code>(</code> for a <code>)</code>, with the obvious error conditions (no match found).</p>
<p><em>As an aside, a <code>?</code> or <code>:</code> found in unary state would be something else, like <code>?a</code> alone or <code>:b</code> as in <code>a + :b</code> (makes no sense to C but could be used in some other language).  Unary state vs. binary state is how the parser knows whether an incoming <code>*</code> token, for example, is unary indirection operator or binary multiplication operator.</em></p>
<p>At this point, my parser removes the matched <code>TernaryTest</code> operator from the operator stack (while fully reducing the expression in between the <code>?</code> and the <code>:</code> — reduction means popping operators and operands off the stacks to make larger ASTs that go back onto the operand stack) and pushes the <code>TernaryChoice</code> operator onto the operator stack (no popping operands or building AST as the <code>?:</code> itself is yet to be fully recognized).  Then here, the state is that there are the two operands on the operand stack (<code>a</code>, and <code>b</code>) and one operator on the stack (<code>TernaryChoice</code>), and the parser is expecting another expression in the same manner as it expects an operand expression following any other binary operator (i.e. by going to the unary state).</p>
<p>After the remaining expression that belongs on the right side of <code>:</code> is parsed, there will be three operands on the operand stack, and <code>TernaryChoice</code> as the top operator on the operator stack.  The <code>TernaryChoice</code> operator consumes three operands from the operand stack to build the associated AST node.</p>
<p>If during finishing the expression, there's still a <code>TernaryTest</code> operator on the stack, then there was no matching <code>:</code> for the <code>?</code>, so, a syntax error.</p>
<p>Otherwise, the normal mechanisms handle the precedence matching.</p>
<p><em>I should also note that in my approach, the expression between <code>?</code> and <code>:</code> is automatically parsed as if it had been parenthesized (as this is both sensible and correct interpretation for C).  For example,  for <code>a?b=x:c</code> as if it were <code>a?(b=x):c</code>).  So this parses as it should even though in C, it is stated that <code>=</code> is lower precedence than <code>?:</code>.  (The alternative of interpretation as <code>(a?b) = (x:c)</code>, would be two separate syntax errors, and that's not what C language/compilers do.)</em></p>
<p>A similar approach would work for other parsing techniques, I would think — parse as two independent binary operators, and matching each <code>?</code> operator with one <code>:</code> operator as building AST.  (In parsing, we can pretend/simulate that a <code>(</code> follows <code>?</code> and similarly would pretend/simulate that a <code>)</code> precedes <code>:</code>, if that simplifies precedence handling, possibly at the expense of complicating error messaging — in my parser, such happens naturally as handling of <code>:</code> reduces all expressions between the <code>:</code> to the matching <code>?</code> without regard to other operators to the left and to the right, if they were paramount on their own.)</p>

CC BY-SA 4.0
2024-09-21T17:19:50.680Z
2024-09-26T20:24:42.517Z
2024-09-26T20:24:42.517Z
Erik Eidt
CC BY-SA 4.0
2024-09-22T14:32:48.780Z
Reading your description makes me think of the [Shunting Yard](https://en.wikipedia.org/wiki/Shunting_yard_algorithm) parsing algorithm, but I'm not quite sure it's an exact match.
Matthieu M.
CC BY-SA 4.0
2024-09-22T15:13:50.137Z
@MatthieuM., yes. The Shunting Yard algorithm has a number of defects, in some sense it is simply incomplete.  My approach is like two Shunting Yards glued together (one for unary operand state and one for binary operator state) and that makes for an industrial strength expression parser.  For more information see [the Double-E Infix Expression parsing method](https://erikeidt.github.io/The-Double-E-Method.html).
Erik Eidt
# Why is the "scan backwards" method of parsing right-associative operators considered to be anti-pattern? What alternatives are recommended?
Posted by: username_0 on 2024-09-21
My previous question was about how the tokenizers for programming languages which support both the ternary conditional operator ?: and labels (with the syntax labelName:) know, when they see :, whether it belongs to ?: or whether it's a part of a label. The general consensus in the comments and answers seems to be that the tokenizer is not supposed to know that, that it's the parser's job to determine that. However, that's not trivial to implement in the parser I made, because I'm parsing ?: by "scanning backwards", so the parser will see the : before it sees ? which would warn it that the next : is not a label.
On Discord, I received some comments that the "scanning backwards" way of parsing right-associative operators is actually considered to be an anti-pattern in the world of programming languages. So, is that true? If so, what alternatives are recommended?
Here is how I'm parsing ?: in my PicoBlaze assembler:
  // Ternary conditional operator...
  let lastColon = tokenized.length - 2;
  if (lastColon > 0)
    while (lastColon) {
      if (tokenized[lastColon].text == ':' &&
          tokenized[lastColon].text != '\n') {
        let questionMarkCorrespondingToTheLastColon = lastColon, counter = 1;
        console.log(
            "DEBUG: Parsing the ternary conditional operator. The colon is at the index: " +
            lastColon);
        while (counter) {
          questionMarkCorrespondingToTheLastColon--;
          if (!questionMarkCorrespondingToTheLastColon ||
              questionMarkCorrespondingToTheLastColon < 0) {
            alert(
                "Line #" + tokenized[lastColon].lineNumber +
                ": There is a colon without a matching question mark before it!");
            return root_of_abstract_syntax_tree;
          }
          if (tokenized[questionMarkCorrespondingToTheLastColon].text == '?')
            counter--;
          else if (tokenized[questionMarkCorrespondingToTheLastColon].text ==
                   ':')
            counter++;
        }
        console.log("DEBUG: The corresponding question mark is at the index: " +
                    questionMarkCorrespondingToTheLastColon);
        let nodesThatRecursionDealsWith = [];
        for (let i = questionMarkCorrespondingToTheLastColon + 1; i < lastColon;
             i++)
          nodesThatRecursionDealsWith.push(tokenized[i]);
        tokenized[questionMarkCorrespondingToTheLastColon].text = "?:";
        tokenized[questionMarkCorrespondingToTheLastColon].children.push(
            tokenized[questionMarkCorrespondingToTheLastColon - 1]);
        const whatTheRecursionReturned = parse(nodesThatRecursionDealsWith);
        if (whatTheRecursionReturned.children.length > 1) {
          alert("Line #" + whatTheRecursionReturned.children[1].lineNumber +
                ": Unexpected token `" +
                whatTheRecursionReturned.children[1].text + "`!");
          return root_of_abstract_syntax_tree;
        }
        tokenized[questionMarkCorrespondingToTheLastColon].children.push(
            whatTheRecursionReturned.children[0]);
        tokenized[questionMarkCorrespondingToTheLastColon].children.push(
            tokenized[lastColon + 1]);
        console.log(
            "DEBUG: The ternary conditional operator converted to LISP is: " +
            tokenized[questionMarkCorrespondingToTheLastColon]
                .getLispExpression());
        tokenized.splice(questionMarkCorrespondingToTheLastColon + 1,
                         lastColon - questionMarkCorrespondingToTheLastColon +
                             1);
        tokenized.splice(questionMarkCorrespondingToTheLastColon - 1, 1);
        lastColon = questionMarkCorrespondingToTheLastColon;
      }
      lastColon--;
    }

I'm doing a similar thing in the compiler for my programming language written in C++. And I'm also parsing the right-associative assignment operator := by scanning backwards.
In the first compiler I made for my programming language, I was parsing the ?: operator like this:
        for (var i = 0; i < arth.length; i++)
          if (arth[i].text == "?") {
            if (arth.length - 1 == i || !i) {
              alerted = 1;
              alert(
                "Parser error: The ternary operator '?:' has less than three operands!"
              );
              return arth[0];
            }
            arth[i].operands.push(arth[i - 1]);
            arth[i].text = "?:";
            var j = 1;
            var c = 1;
            do {
              if (i + j >= arth.length) {
                alerted = 1;
                alert(
                  "Parser error: There is a '?' without its corresponding ':'."
                );
                return arth[0];
              }
              if (arth[i + j].text == "?") c++;
              if (arth[i + j].text == ":") c--;
              j++;
            } while (c);
            var drugiOperand = new Array();
            for (var k = i + 1; k < i + j - 1; k++) drugiOperand.push(arth[k]);
            arth[i].operands.push(parseArth(drugiOperand));
            var treciOperand = new Array();
            for (var k = i + j; k < arth.length; k++)
              treciOperand.push(arth[k]);
            arth[i].operands.push(parseArth(treciOperand));
            arth = [arth[i]]; //Znam da ovo nije bas pametno, ali raditi ce dokle god je uvijetni operator upravo operator najnizeg prioriteta u cijelom jeziku.
          }

But, like the comments say, I don't think that's a good idea because that will work only if there is no operator with lower precedence than ?:.
**Tags:** parsing
> **Comments:**
> **username_1**: I don't exactly understand how your "scan backwards" algorithm works, but my first thought is that it's an overly complicated ad-hoc way to solve what is essentially a non-problem (a standard [operator precedence parser](https://en.wikipedia.org/wiki/Operator-precedence_parser) can handle both left- and right-associative operators), and potentially could lead to quadratic runtime in the worst case if you have to scan backwards over the same tokens over and over (though I would have to think more about it to be sure).  
> **username_2**: These people don't know what a "pattern" is. A pattern in programming is something that people do all the time. An anti-pattern is a pattern that doesn't work well for some reasons. You don't write one parser after the other, so it's not a pattern.  
---
## 1 answers
### Answer by username_3 on 2024-09-21. Score: 13 | Accepted answer
> What alternatives are recommended?

I'll share what I'm doing — for context, I'm using a bottom-up expression parser.  My parser is a bottoms-up shift-reduce parser, simplified (no tables) by being dedicated to infix expression parsing.

I treat `?` and `:` separately, each as their own individual binary operator.  Let's make `a ? b : c` an example input.

In some sense, my parser *is looking backwards*, but not at tokens, instead rather at operators in the intermediate state of parse/recognition.  My intermediate state is an operator stack and an operand stack — the operator stack has true language operators, not tokens, so `binarySubtraction` vs. `unaryNegation` rather than the undifferentiated `-` token; the operand stack is a stack of ASTs waiting to be combined into larger ASTs.  (And rather than having parse tables as usually seen with shift-reduce approach, I have two states represented by separate code sections in the expression parser: one for unary state and one for binary state.)

When I find a `?` (in the binary state) I push a special binary operator for this onto the operator stack.  I call this operator `TernaryTest` — this will not appear in the AST as it will be removed by finishing the `:` part of the operator.  At this point, the operand stack has `a` and the operator stack has `TernaryTest`, and the parser is ready to parse the next expression operand (`b`) similar to any other binary operator.

Then when finding a `:` operator (also found in the binary state), the parser crawls up the operator stack to find the associated `TernaryTest` (i.e. the matching `?`), much like finding the matching `(` for a `)`, with the obvious error conditions (no match found).

*As an aside, a `?` or `:` found in unary state would be something else, like `?a` alone or `:b` as in `a + :b` (makes no sense to C but could be used in some other language).  Unary state vs. binary state is how the parser knows whether an incoming `*` token, for example, is unary indirection operator or binary multiplication operator.*

At this point, my parser removes the matched `TernaryTest` operator from the operator stack (while fully reducing the expression in between the `?` and the `:` — reduction means popping operators and operands off the stacks to make larger ASTs that go back onto the operand stack) and pushes the `TernaryChoice` operator onto the operator stack (no popping operands or building AST as the `?:` itself is yet to be fully recognized).  Then here, the state is that there are the two operands on the operand stack (`a`, and `b`) and one operator on the stack (`TernaryChoice`), and the parser is expecting another expression in the same manner as it expects an operand expression following any other binary operator (i.e. by going to the unary state).

After the remaining expression that belongs on the right side of `:` is parsed, there will be three operands on the operand stack, and `TernaryChoice` as the top operator on the operator stack.  The `TernaryChoice` operator consumes three operands from the operand stack to build the associated AST node.

If during finishing the expression, there's still a `TernaryTest` operator on the stack, then there was no matching `:` for the `?`, so, a syntax error.

Otherwise, the normal mechanisms handle the precedence matching.

*I should also note that in my approach, the expression between `?` and `:` is automatically parsed as if it had been parenthesized (as this is both sensible and correct interpretation for C).  For example, for `a?b=x:c` as if it were `a?(b=x):c`).  So this parses as it should even though in C, it is stated that `=` is lower precedence than `?:`.  (The alternative of interpretation as `(a?b) = (x:c)`, would be two separate syntax errors, and that's not what C language/compilers do.)*

A similar approach would work for other parsing techniques, I would think — parse as two independent binary operators, and matching each `?` operator with one `:` operator as building AST.  (In parsing, we can pretend/simulate that a `(` follows `?` and similarly would pretend/simulate that a `)` precedes `:`, if that simplifies precedence handling, possibly at the expense of complicating error messaging — in my parser, such happens naturally as handling of `:` reduces all expressions between the `:` to the matching `?` without regard to other operators to the left and to the right, if they were paramount on their own.)
> **Comments:**
> **username_4** (2024-09-22): Reading your description makes me think of the [Shunting Yard](https://en.wikipedia.org/wiki/Shunting_yard_algorithm) parsing algorithm, but I'm not quite sure it's an exact match.  
> **username_3** (2024-09-22): @MatthieuM., yes. The Shunting Yard algorithm has a number of defects, in some sense it is simply incomplete.  My approach is like two Shunting Yards glued together (one for unary operand state and one for binary operator state) and that makes for an industrial strength expression parser.  For more information see [the Double-E Infix Expression parsing method](https://erikeidt.github.io/The-Double-E-Method.html).  
---
