¿Cómo el ANTLR lexer desambigua sus reglas (o por qué mi analizador produce errores de “entradas no coincidentes”)?

En ANTLR, el lexer está aislado del analizador sintáctico, lo que significa que dividirá el texto en tokens tipeados de acuerdo con las reglas gtwigticales lexer, y el analizador no tiene influencia en este proceso (no puede decir “dame un INTEGER ahora”, por ejemplo ) Produce un flujo de tokens por sí mismo. Además, el analizador no se preocupa por el texto del token, solo se preocupa por los tipos de tokens para que coincidan con sus reglas.

Esto puede convertirse fácilmente en un problema cuando varias reglas lexer pueden coincidir con el mismo texto de entrada. En ese caso, el tipo de token se elegirá según estas reglas de precedencia :

• Primero, seleccione las reglas lexer que coincidan con la subcadena de entrada más larga
• Si la subcadena más larga coincidente es igual a un token definido implícitamente (como '=' ), use la regla implícita como el tipo de token
• Si varias reglas lexer coinciden con la misma entrada, elija la primera , según el orden de definición

Estas reglas son muy importantes a tener en cuenta para usar ANTLR de manera efectiva.

En el ejemplo de la pregunta, el analizador espera ver la siguiente secuencia de tokens para que coincida con la keyValue analizador keyValue : IDENTIFIER '=' INTEGER ';' donde '=' y ';' son tipos de token implícitos.

Como 42 puede coincidir tanto con INTEGER como IDENTIFIER , y IDENTIFIER se define primero, el analizador recibirá la siguiente entrada: IDENTIFIER '=' IDENTIFIER ';' que no podrá coincidir con la regla keyValue . Recuerde, el analizador no se puede comunicar con el lexer, solo puede recibir datos de él, por lo tanto, no puede decir “intente hacer coincidir INTEGER siguiente” .

Es aconsejable minimizar las superposiciones de las reglas lexer para limitar el impacto de este efecto. En el ejemplo anterior, tenemos varias opciones:

• Redefina el IDENTIFIER como [A-Za-z] [A-Za-z0-9]* (solicite que comience con una letra). Esto evita por completo el problema, pero evita que los nombres de los identificadores que comiencen con un número se definan, por lo que cambia la intención de la gramática.
• Reordenar INTEGER e IDENTIFIER . Esto resuelve el problema para la mayoría de los casos, pero evita que se definan identificadores completamente numéricos, por lo tanto, también cambia la intención de la gramática de una manera sutil, no tan obvia.
• Haga que el analizador acepte ambos tipos de tokens cuando las reglas de lexer se solapen:
  Primero, intercambie INTEGER e IDENTIFIER para dar prioridad a INTEGER . Luego, defina una id: IDENTIFIER | INTEGER; regla de analizador id: IDENTIFIER | INTEGER; id: IDENTIFIER | INTEGER; luego use esa regla en lugar de IDENTIFIER en otras reglas del analizador, lo que cambiaría keyValue a key=id '=' value=INTEGER ';' .

Aquí hay un segundo ejemplo de comportamiento lexer para resumir:

La siguiente gramática combinada:

 grammar LexerPriorityRulesExample; // Parser rules randomParserRule: 'foo'; // Implicitly declared token type // Lexer rules BAR: 'bar'; IDENTIFIER: [A-Za-z]+; BAZ: 'baz'; WS: [ \t\r\n]+ -> skip; 

Dada la siguiente entrada:

 aaa foo bar baz barz 

Producirá la siguiente secuencia de token del lexer:

IDENTIFIER 'foo' IDENTIFIER IDENTIFIER IDENTIFIER IDENTIFIER BAR EOF

• aaa es de tipo IDENTIFIER

  Solo la regla del IDENTIFIER puede hacer coincidir este token, no hay ambigüedad.

• foo es del tipo 'foo'

  La regla del analizador randomParserRule introduce el tipo de token implícito 'foo' , que es prioritario con respecto a la regla del IDENTIFIER .

• bar es de tipo BAR

  Este texto coincide con la regla BAR , que se define antes de la regla IDENTIFIER , y por lo tanto tiene prioridad.

• baz es de tipo IDENTIFIER

  Este texto coincide con la regla BAZ , pero también coincide con la regla IDENTIFIER . Este último se elige como se define antes de BAR .

  Dada la gramática, BAZ nunca podrá coincidir, ya que la regla del IDENTIFIER ya cubre todo lo que BAZ puede igualar.

• barz es de tipo IDENTIFIER

  La regla BAR puede coincidir con los primeros 3 caracteres de esta cadena ( bar ), pero la regla IDENTIFIER coincidirá con 4 caracteres. Como IDENTIFIER coincide con una subcadena más larga, se elige sobre BAR .

• EOF ( fin de archivo ) es un tipo de token definido implícitamente que siempre se produce al final de la entrada.

Como regla general, las reglas específicas deben definirse antes que las reglas más genéricas. Si una regla solo puede coincidir con una entrada que ya está cubierta por una regla previamente definida, nunca se usará.

Las reglas implícitamente definidas, como 'foo' actúan como si estuvieran definidas antes que todas las demás reglas lexer. A medida que agregan complejidad, es aconsejable evitarlos por completo y declarar reglas lexer explícitas en su lugar. Solo tener una lista de tokens en un solo lugar en lugar de tenerlos dispersos en la gramática es una ventaja convincente de este enfoque.