parsing - example - antlr4 tutorial español

¿Cómo el lexer ANTLR desambigua sus reglas(o por qué mi analizador produce errores de "entrada no coincidente")?

Question

Nota: Esta es una pregunta con respuesta propia que tiene como objetivo proporcionar una referencia sobre uno de los errores más comunes cometidos por los usuarios de ANTLR.

Cuando pruebo esta gramática muy simple:

grammar KeyValues;

keyValueList: keyValue*;
keyValue: key=IDENTIFIER ''='' value=INTEGER '';'';

IDENTIFIER: [A-Za-z0-9]+;
INTEGER: [0-9]+;

WS: [ /t/r/n]+ -> skip;

Con la siguiente entrada:

foo = 42;

Termino con el siguiente error de tiempo de ejecución:

línea 1: 6 entrada ''42'' no coincidente esperando INTEGER
línea 1: 8 entrada no coincidente '';'' esperando ''=''

¿Por qué ANTLR no reconoce 42 como INTEGER en este caso?
Debe coincidir con el patrón [0-9]+ muy bien.

Si invierto el orden en que se definen INTEGER e IDENTIFIER , parece funcionar, pero ¿por qué importa el orden en primer lugar?

Answer 1

En ANTLR, el lexer está aislado del analizador, lo que significa que dividirá el texto en tokens escritos de acuerdo con las reglas de gramática del lexer, y el analizador no tiene influencia en este proceso (por ejemplo, no puede decir "dame un INTEGER ") ) Produce un flujo de tokens por sí mismo. Además, al analizador no le importa el texto del token, solo le importan los tipos de token 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á de acuerdo con estas reglas de precedencia :

• Primero, seleccione las reglas lexer que coinciden con la subcadena de entrada más larga
• Si la subcadena coincidente más larga 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

Es muy importante tener en cuenta estas reglas para utilizar 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 tokens implícitos.

Como 42 puede coincidir con INTEGER e 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 puede comunicarse con el lexer, solo puede recibir datos de él, por lo tanto no puede decir "intente hacer coincidir INTEGER continuación" .

Es aconsejable minimizar la superposición de 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]* (requiera que comience con una letra). Esto evita el problema por completo, pero evita que se definan nombres de identificadores que comienzan con un número, 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 totalmente 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 token cuando las reglas lexer se superponen:
  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, 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 tokens del lexer:

IDENTIFIER ''foo'' BAR IDENTIFIER IDENTIFIER EOF

• aaa es de tipo IDENTIFIER

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

• foo es del tipo ''foo''

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

• bar es de tipo BAR

  Este texto coincide con la regla BAR , que se define antes que 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 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 ( final del archivo ) es un tipo de token definido implícitamente que siempre ocurre 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 definida previamente, nunca se utilizará.

Las reglas definidas implícitamente como ''foo'' actúan como si estuvieran definidas antes que todas las otras 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 lugar en lugar de tenerlos dispersos en la gramática es una ventaja convincente de este enfoque.