6
$\begingroup$

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).

$\endgroup$
2
  • 13
    $\begingroup$ 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? $\endgroup$
    – Michael Homer
    Nov 3, 2023 at 7:12
  • 2
    $\begingroup$ 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. $\endgroup$
    – kaya3
    Nov 3, 2023 at 17:47

2 Answers 2

6
$\begingroup$

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" 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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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