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.

I'm writing a lexer in JavaScript. It's pretty typical - rules are specified with regular expressions and produce a token.

I am unsure of the best way to handle when multiple rules are matched. The existing lexers I've looked at handle this by picking the rule with the longest match.

It also seems like a viable strategy, however, to simply use the first rule that matches. This is my current strategy.

Here is an example:

Input:

:=

Rules:

: -> COLON
= -> EQUALS
:= -> ASSIGN

The longest-match rule would return ASSIGN, where the first-match rule would return COLON and then EQUALS.

Obviously this is not desirable, so under my implementation I would just reorder the rules to put the ASSIGN rule first as follows:

:= -> ASSIGN
: -> COLON
= -> EQUALS

Is this a viable approach to just use the first matching rule? What are the advantages and disadvantages of each approach?

share|improve this question
2  
Related from SO - How Flex Handles Ambiguous Patterns. Short version - longest match wins, in case of tie, first match wins. –  MichaelT Jun 2 '13 at 4:35
    
Thanks, I have updated my lexer to use the same approach. –  jhewlett Jun 3 '13 at 0:50

3 Answers 3

up vote 5 down vote accepted

No, that is not a viable strategy -- at least not if you want to have identifiers as well as keywords in your language.

Let's say you have two rules: one for identifiers that consist of one or more arbitrary letters and one for some keyword that consists of letters. Let's take the keyword var for example. Now let's consider the input string var variant. If the identifier rule comes first in your lexer definition, this will be tokenized as two identifiers. Clearly that's not what we want, so let's put the keyword rule first. But now it's tokenized as two var keywords, followed by the identifier iant. That's also not what we want.

So there is no way to order the rules, such that we can get what we want here. However the maximal munch rule would give us exactly what we want in cases like this. Therefore it is preferable.

share|improve this answer
1  
Shouldn't identifier rules (and keyword rules as well) include that an identifier (or keyword) must be separated by a non-character from the containing text? So the keyword rule would not find the "var" in variant, as you wrote, even when it comes first. –  Doc Brown Jun 2 '13 at 13:23
    
@DocBrown That's not how it's usually done, no. The usual rule for identifiers is [a-zA-Z_][a-zA-Z_0-9]* and the usual rule for a keyword like var would simply be var. In fact, as far as I know, most lexer generators don't even offer a way of saying "This token should be separated by this kind of character from the surrounding text". –  sepp2k Jun 2 '13 at 13:31
    
But why not? Would this not help to prevent ambiguities like the ones in your example? –  Doc Brown Jun 2 '13 at 13:40
1  
@DocBrown First of all adding support for lookahead assertions to lexer generators (which I think is what you're suggesting - unless I misunderstood), would mean a lot of additional development effort just to offer an alternative to a rule that already works perfectly fine. But even more importantly, it seems to me that manually specifying where a token should end would just be more complicated and error prone. For example I would imagine that a common error would be that people forget to specify that a token may appear at the end of the file. –  sepp2k Jun 2 '13 at 13:52
    
@sepp2k: Great example, thanks. –  jhewlett Jun 2 '13 at 17:07

I wouldn't view it as "first" match, but having the lexer have defined priorities is not uncommon. The advantage of parsing colon first is on a miss, it eliminates two paths. If you miss assignment, you still need to check colon.

share|improve this answer

When I write a lexer I use a grammar, not regular expressions. The grammar has no ambiguities by design. The effect is exactly equivalent to your proposal of using regular expressions, ordering them by length descending, and accepting the first match. My way is more efficient (faster and less space) but a little harder to write.

The object raised regarding identifiers and reserved words does not apply. The tokens var and variant are parsed in exactly the same way. The lexer is tightly coupled to a symbol table, and the difference is that reserved words (and indeed every kind of token) are pre-loaded into the symbol table. The symbol table says what kind of token it is.

So your strategy (first match) is perfectly viable if you are prepared to look up tokens in a symbol table to find out what they are rather than building that knowledge into the lexer.

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.