Mutually left-recursive lexer rules on ANTL4?

Question

I'm trying to write Swift language highlight. Also I would like to highlight in addition to tokens of some language constructs. Having problems with the following rule:

Type
   : '[' Type ']'   
   | '[' Type ':' Type ']' 
   | (Attributes? Function_type_argument_clause 'throws'? '->' Type | Attributes? Function_type_argument_clause 'rethrows' '->' Type)
   | (Type_name Generic_argument_clause? | Type_name Generic_argument_clause? '.' Type)
   | Tuple_type
   | Type '?' 
   | Type '!' 
   | (Type_name Generic_argument_clause? | Type_name Generic_argument_clause? '.' Type) '&' Protocol_composition_continuation 
   | (Type '.' 'Type' | Type '.' 'Protocol')
   | 'Any' 
   | 'Self' 
   | '(' Type ')'
   ;

Error: The following sets of rules are mutually left-recursive [Type]

Tried to leave in the rule, only the following cases:

Type
   : Type '?' 
   | 'Any' 
   | 'Self' 
   ; 

But the problem remained: The following sets of rules are mutually left-recursive [Type]

Answer 1

You defined Type as a lexer rule. Lexer rules cannot be left recursive. Type should be a parser rule.

See: Practical difference between parser rules and lexer rules in ANTLR?

Note that there are existing Swift grammars:

• https://github.com/antlr/grammars-v4/blob/master/swift2/Swift2.g4
• https://github.com/antlr/grammars-v4/blob/master/swift3/Swift3.g4

Note that these grammars are user-comitted, test them properly!

EDIT

I'm still unable to understand it from the point of view of lexical analysis

Oh, you're only tokenising? Well, then you can't use Type as you're doing it now. You will have to rewrite it so that there is no left recursion any more.

For example, let's say the simplified Type rule looks like this:

Type
   : '[' Type ']'   
   | '[' Type ':' Type ']' 
   | Type '?' 
   | Type '!' 
   | 'Any' 
   | 'Self' 
   | '(' Type ')'
   ;

then you should rewrite it like this:

Type
   : TypeStart TypeTrailing?
   ;

fragment TypeStart
   : '[' Type ']' 
   | '[' Type ':' Type ']'
   | 'Any'
   | 'Self'
   | '(' Type ')'
   ;

fragment TypeTrailing: [?!];