title: How Lexer lookahead works with greedy and non-greedy matching in ANTLR3 and ANTLR4?
body: <p>If someone would clear my mind from the confusion behind look-ahead relation to tokenizing involving greery/non-greedy matching i'd be more than glad. Be ware this is a slightly long post because it's following my thought process behind.</p>
  
  <p>I'm trying to write antlr3 grammar that allows me to match input such as:</p>
  
  <p>"identifierkeyword"</p>
  
  <p>I came up with a grammar like so in Antlr 3.4:</p>
  
  <pre><code>KEYWORD: 'keyword' ;
  
  IDENTIFIER
  : 
    (options {greedy=false;}: (LOWCHAR|HIGHCHAR))+ 
  ;
  
  /** lowercase letters */
  fragment LOWCHAR
  :   'a'..'z';
  /** uppercase letters */
  fragment HIGHCHAR
  :   'A'..'Z';
  
  parse: IDENTIFIER KEYWORD EOF;
  </code></pre>
  
  <p>however it complains about it can never match IDENTIFIER this way, which i don't really understand. (The following alternatives can never be matched: 1)</p>
  
  <p>Basically I was trying to specify for the lexer that try to match (LOWCHAR|HIGHCHAR) non-greedy way so it stops at KEYWORD lookahead. What i've read so far about ANTLR lexers that there supposed to be some kind of precedence of the lexer rules. If i specify KEYWORD lexer rule first in the lexer grammar, any lexer rules that come after shouldn't be able to match the consumed characters.</p>
  
  <p>After some searching I understand that problem here is that it can't tokenize the input the right way because for example for input: "identifierkeyword" the "identifier" part comes first so it decides to start matching the IDENTIFIER rule when there is no KEYWORD tokens matched yet.</p>
  
  <p>Then I tried to write the same grammar in ANTLR 4, to test if the new run-ahead capabilities can match what i want, it looks like this:</p>
  
  <pre><code>KEYWORD: 'keyword' ;
  
  /** lowercase letters */
  fragment LOWCHAR
  :   'a'..'z';
  /** uppercase letters */
  fragment HIGHCHAR
  :   'A'..'Z';
  
  IDENTIFIER
  : 
    (LOWCHAR|HIGHCHAR)+?
  ;
  
  parse: IDENTIFIER KEYWORD EOF;
  </code></pre>
  
  <p>for the input: "identifierkeyword" it produces this error:
  line 1:1 mismatched input 'd' expecting 'keyword'</p>
  
  <p>it matches character 'i' (the very first character) as an IDENTIFIER token, and then the parser expects a KEYWORD token which he doesn't get this way.</p>
  
  <p>Isn't the non-greedy matching for the lexer supposed to match till any other possibility is available in the look ahead? Shouldn't it look ahead for the possibility that an IDENTIFIER can contain a KEYWORD and match it that way?</p>
  
  <p>I'm really confused about this, I have watched the video where Terence Parr introduces the new capabilities of ANTLR4 where he talks about run-ahead threads that watch for all "right" solutions till the end while actually matching a rule. I thought it would work for Lexer rules too, where a possible right solution for tokenizing input "identifierkeyword" is matching IDENTIFIER: "identifier" and matching KEYWORD: "keyword"</p>
  
  <p>I think I have lots of wrongs in my head about non-greedy/greedy matching. Could somebody please explain me how it works?</p>
  
  <p>After all this I've found a similar question here: <a href="https://stackoverflow.com/questions/11902168/antlr-trying-to-match-token-within-longer-token">ANTLR trying to match token within longer token</a> and made a grammar corresponding to that:</p>
  
  <pre><code>parse
  :   
    identifier 'keyword'
  ;
  
  identifier
  :   
    (HIGHCHAR | LOWCHAR)+
  ;
  
  /** lowercase letters */
  LOWCHAR
  :   'a'..'z';
  /** uppercase letters */
  HIGHCHAR
  :   'A'..'Z';
  </code></pre>
  
  <p>This does what I want now, however I can't see why I can't change the identifier rule to a Lexer rule and LOWCHAR and HIGHCHAR to fragments. 
  A Lexer doesn't know that letters in "keyword" can be matched as an identifier? or vice versa? Or maybe it is that rules are only defined to have a lookahead inside themselves, not all possible matching syntaxes?</p>