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?

4 Answers 4


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.

  • Since the lexmes are usually described by regular languages, you could (in theory) forgo the lexer and tokens and do the "lexical analysis" in the same CFG. You're right that arbirary decisions based on the input string lead down a rabbit hole of language power, but for things like a universal operator token with the operator as string, it's enough to consider "operator" tokens containing different strings to be different non terminals. Whether the parser generator supports this is, of course, a different matter.
    – user7043
    Commented May 2, 2014 at 14:01
  • 1
    @delnan yes. But there is a difference between Expr = Expr (Op where value is "+") Expr; Op = "+" | "-" and Expr = Expr Plus Expr; Plus = "+"; Minus = "-". Only the latter grammar is formally a context free grammar, although both describe a context free language.
    – amon
    Commented May 2, 2014 at 14:07
  • 1
    A CFG concerns itself with terminals and nonterminals (btw I just noticed I mixed up the two in my previous post; a token is a terminal). How you recognize those terminals from a string and in what format they are presented is solely the concern of the lexer/parser; as far as the CFG is concerned your alphabet can be {"+", "-"} or it can be {Op where value is "+", Op where value is "-"}, that's just names. The token representation that inspired those names only affects how the parser decides which terminal symbol the upcoming token represents.
    – user7043
    Commented May 2, 2014 at 14:19

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
    +1 for mentioning user defined operators as a use-case for conflating operators to one token. Commented May 2, 2014 at 14:26

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
  • And on a related note, if they are really the same token, I.E. MATH, then the lexer can return that token for various different regex matches. Commented May 2, 2014 at 19:30

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.