<p>Some operators have multiple meanings.</p>
<p>For example:</p>
<ul>
<li><code>-</code> represents the prefix <code>negative</code>, or it can represent the infix <code>minus</code>.</li>
<li><code>!</code> represents the prefix <code>not</code>, and can also represent the postfix <code>factorial</code>.</li>
</ul>
<p>How should lexer determine which token should be output?</p>
<hr />
<p>I ran into this problem while implementing a parser for the wolfram language</p>
<p><code>x^a!y</code> should be interpreted <code>x^(a!)*y</code>.</p>
<p>But my lexer thinks <code>!</code> stands for <code>not</code>, causing the parser to incorrectly parse the expression as <code>(x^a)*(!y)</code>.</p>

<compilers><parsing><lexing><operator-overloading>
How to determine the meaning of a polymorphic operator?
CC BY-SA 4.0
2023-11-03T07:12:42.837Z
Is it necessary that this be determined in the lexer? It’s more traditional to tokenise to symbols and handle this sort of thing (trivially) in the parser, which understands the context. Is the *token* sequence important here?
Michael Homer
CC BY-SA 4.0
2023-11-03T17:47:21.143Z
Exactly the same issue occurs with many tokens in many languages; their meaning depends on context (e.g. is `x` a local variable, a global variable, a type name? Is `if` part of a conditional statement or a conditional expression like Python's `a if b else c`? Is `[` part of a list literal or an indexed access? The answer is that it is not the lexer's job to determine the *meaning* of a token, that is done by the parser or even later.
kaya3
<p>Typically, this is not something that the <em>lexer</em> is concerned with in systems with a traditional lexer-parser sequence. Instead, it produces a token representing the symbol that appeared in the source, and the <em>parser</em> understands how to distinguish them in context.</p>
<p>In your examples, call the tokens <code>MINUS</code> and <code>EXCLAMATION</code>. The parser always knows whether it's expecting a term at the current point or not, and can do the right thing with that information when it sees either token:</p>
<ul>
<li>If it sees <code>MINUS</code> in a position where it's expecting a term, this can only be the prefix operation, so enter the production for that.</li>
<li>If it sees <code>MINUS</code> <em>after</em> a term, it must be the infix operator, so enter that production.</li>
<li>If it sees <code>EXCLAMATION</code> after a term, it treats it as the unary postfix operator.</li>
<li>If it sees <code>EXCLAMATION</code> while expecting a term, it is the unary prefix operator.</li>
</ul>
<p>This works provided that there are only <em>two</em> of the three prefix, infix, postfix operators available for any given symbol, as here. If all three exist, the grammar is ambiguous at this level, and needs more processing at a higher level.</p>
<p>Note that the order of operations is transposed for the two symbols above. That order is semantic here, given the use of juxtaposition as an operator in the language you're describing: swapping the last two would treat <code>a!y</code> as <code>a(!y)</code> instead of <code>(a!)(y)</code>, because immediately after a term you are permitted another term. You need to specify these productions on a per-operator basis in this case. Parser generators usually apply rules in top-to-bottom or bottom-to-top order, while hand-written parsers can choose what to look for first.</p>
<p>If the <em>token sequence</em> really is the important element here, you could reconstruct a disambiguated sequence from the parser by emitting distinct <code>NOT</code>, <code>FACTORIAL</code>, <code>NEGATE</code>, <code>SUBTRACT</code> tokens into an accumulating list when taking each production, but generally that's not useful. A token sequence might be used by some static processing tools, and this would be how to produce a disambiguated one for that. Usually a parse tree is strictly better for these purposes in any tool you're building yourself.</p>
<hr />
<p>Scannerless parsers mesh the lexing and parsing phases together, and so also don't have this issue. A typical scenario there is that there are simply two grammatical constructs containing <code>-</code>, and the parser speculatively takes both paths when it sees <code>-</code> in the source knowing that one will always fail. Other scannerless approaches fall back essentially to the approach above, that when <code>-</code> or <code>!</code> appears, only one rule applies in context. These approaches to parsing sidestep the question of what happens in the tokenising and parsing phases and can avoid some of the complexities of needing information from the later phase to produce the right tokens (e.g. the &quot;<a href="https://langdev.stackexchange.com/a/1769/133">lexer hack</a>&quot; problem).</p>
<p>Given all three operator kinds plus juxtaposition, it's <em>possible</em> that the language being parsed here is context-sensitive. General parsing for context-sensitive grammars is much more complex and there are few parser generators that can do it, but limited context-sensitivity can be implemented manually in hand-written parsers. Speculating parsing of a covering grammar is also possible.</p>

CC BY-SA 4.0
2023-11-03T18:56:26.557Z
2023-11-03T18:56:26.557Z
Michael Homer
<p>Not at all. You are trying to derive information in a stage where the required facts have not yet been computed. The most common approaches would be either to solve the issue in the grammar by using different tokens, i.e. different operator symbols. This approach is kind of what you are trying to do. The other approach would be to keep a flat operator expression that is just a list of operator symbols and expressions and turn it into a tree somewhere in the middle of your semantic analysis phase. This tree construction algorithm would allow you to use type-based overload resolution reflecting what you would expect as human.</p>

CC BY-SA 4.0
2023-11-03T16:20:09.950Z
2023-11-03T16:20:09.950Z
feldentm
# How to determine the meaning of a polymorphic operator?
Posted by: username_0 on 2023-11-03
Some operators have multiple meanings.

For example:

* `-` represents the prefix `negative`, or it can represent the infix `minus`.
* `!` represents the prefix `not`, and can also represent the postfix `factorial`.

How should lexer determine which token should be output?

---

I ran into this problem while implementing a parser for the wolfram language

`x^a!y` should be interpreted `x^(a!)*y`.

But my lexer thinks `!` stands for `not`, causing the parser to incorrectly parse the expression as `(x^a)*(!y)`.
**Tags:** compilers parsing lexing operator-overloading
> **Comments:**
> **username_1**: Is it necessary that this be determined in the lexer? It’s more traditional to tokenise to symbols and handle this sort of thing (trivially) in the parser, which understands the context. Is the *token* sequence important here?  
> **username_2**: Exactly the same issue occurs with many tokens in many languages; their meaning depends on context (e.g. is `x` a local variable, a global variable, a type name? Is `if` part of a conditional statement or a conditional expression like Python's `a if b else c`? Is `[` part of a list literal or an indexed access? The answer is that it is not the lexer's job to determine the *meaning* of a token, that is done by the parser or even later.  
---
## 2 answers
### Answer by username_1 on 2023-11-03. Score: 6
Typically, this is not something that the *lexer* is concerned with in systems with a traditional lexer-parser sequence. Instead, it produces a token representing the symbol that appeared in the source, and the *parser* understands how to distinguish them in context.

In your examples, call the tokens `MINUS` and `EXCLAMATION`. The parser always knows whether it's expecting a term at the current point or not, and can do the right thing with that information when it sees either token:

* If it sees `MINUS` in a position where it's expecting a term, this can only be the prefix operation, so enter the production for that.
* If it sees `MINUS` *after* a term, it must be the infix operator, so enter that production.
* If it sees `EXCLAMATION` after a term, it treats it as the unary postfix operator.
* If it sees `EXCLAMATION` while expecting a term, it is the unary prefix operator.

This works provided that there are only *two* of the three prefix, infix, postfix operators available for any given symbol, as here. If all three exist, the grammar is ambiguous at this level, and needs more processing at a higher level.

Note that the order of operations is transposed for the two symbols above. That order is semantic here, given the use of juxtaposition as an operator in the language you're describing: swapping the last two would treat `a!y` as `a(!y)` instead of `(a!)(y)`, because immediately after a term you are permitted another term. You need to specify these productions on a per-operator basis in this case. Parser generators usually apply rules in top-to-bottom or bottom-to-top order, while hand-written parsers can choose what to look for first.

If the *token sequence* really is the important element here, you could reconstruct a disambiguated sequence from the parser by emitting distinct `NOT`, `FACTORIAL`, `NEGATE`, `SUBTRACT` tokens into an accumulating list when taking each production, but generally that's not useful. A token sequence might be used by some static processing tools, and this would be how to produce a disambiguated one for that. Usually a parse tree is strictly better for these purposes in any tool you're building yourself.

---

Scannerless parsers mesh the lexing and parsing phases together, and so also don't have this issue. A typical scenario there is that there are simply two grammatical constructs containing `-`, and the parser speculatively takes both paths when it sees `-` in the source knowing that one will always fail. Other scannerless approaches fall back essentially to the approach above, that when `-` or `!` appears, only one rule applies in context. These approaches to parsing sidestep the question of what happens in the tokenising and parsing phases and can avoid some of the complexities of needing information from the later phase to produce the right tokens (e.g. the "[lexer hack](https://langdev.stackexchange.com/a/1769/133)" problem).

Given all three operator kinds plus juxtaposition, it's *possible* that the language being parsed here is context-sensitive. General parsing for context-sensitive grammars is much more complex and there are few parser generators that can do it, but limited context-sensitivity can be implemented manually in hand-written parsers. Speculating parsing of a covering grammar is also possible.
---
### Answer by username_3 on 2023-11-03. Score: -1
Not at all. You are trying to derive information in a stage where the required facts have not yet been computed. The most common approaches would be either to solve the issue in the grammar by using different tokens, i.e. different operator symbols. This approach is kind of what you are trying to do. The other approach would be to keep a flat operator expression that is just a list of operator symbols and expressions and turn it into a tree somewhere in the middle of your semantic analysis phase. This tree construction algorithm would allow you to use type-based overload resolution reflecting what you would expect as human.
---
