When lexing, what would be the best way to tokenize operators? Would one just create a BinaryOperator token, or a separate token for every single binary operator? Examples: PlusOperator, MinusOperator, DivisionOperator …
I am tended towards having a universal one, but going from the documentations and project sources I’ve read the vast majority of lexers are using one token per operator. Is there a particular reason for this? Does it even matter? Does it give you any advantages?
I once wrote a program that used one universal operator type. It was a horrible idea, because the number of checks exploded. To check whether I had an addition operator, I would have to check that the current token is an operator token and contains the "+" string as value.
When using different tokens for different operators, you enjoy a number of benefits:
-
If you use a parser generator, then using a different token type for each operator makes handling operators much easier. Depending on the generator, it may actually be impossible to deal with operator precedence unless each operator has a different token type.
Specifically, a context-free parser is limited to only considering the type of each token. Otherwise, we quickly land in “recursively enumerable” territory.
-
You don’t have to store the lexed string of an operator, as all necessary information is already stored in the token type.
3
Most parser generators require different operators to be distinguished at the lexical analysis stage. If you’re writing the parser by hand, then either option is fine.
If you use a universal ‘operator’ token type, you will (probably) be able to write a general expression parser with your operators (including precedence information) defined in a data structure (rather than hard-wired into the parser code), which might be nicer if you have a lot of operators, and would be essential if you’re parsing a language which allows user defined operators.
Using a separate token type for each operator lets you maintain a clearer distinction between the (traditional) lexical and syntactic analysis stages, and may make it easier for other people (who are familiar with having separate lexers and parser) to understand your system.
Overall, I think this is just a stylistic choice in most cases.
1
Since the tokens signify something literally different, make them unique. If you need to understand the set of them as a single item, the place to do that is in the parser grammar:
operator := PlusOperator | MinusOperator | DivisionOperator
Remember that the lexer’s job is to split the input and not make any semantic decisions about its meaning. That’s the parser’s business, and I’d opt not to put any kind of meaning into the names of the tokens:
operator := PLUS | MINUS | DIVIDE
1
If you have some language support that can leverage, bigger tokens can help improvong efficiency.
From my personal experience from writing a lexer in Objective-C, I leveraged the feature that an Objective-C object can change its class. I defined all binary tokens as one token, but in AST I used one class for each binary operator, sharing one base class. When lexing the lexer emits an object of the base class, BinaryOperator, which later changes itself to object of operator-specific class using simpler table lookup.