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
add comment

2 Answers

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
    
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
add comment

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
add comment

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.