Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 6 down vote accepted

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.

share|improve this answer
    
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. –  delnan May 2 at 14:01
    
@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 May 2 at 14:07
    
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. –  delnan May 2 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.

share|improve this answer
1  
+1 for mentioning user defined operators as a use-case for conflating operators to one token. –  ChuckCottrill May 2 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
share|improve this answer
    
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. –  Spencer Rathbun May 2 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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