2012-01-10 18 views
5

Parece que a veces el lector de Antlr hace una mala elección sobre la regla que se debe usar al tokenizar una secuencia de caracteres ... Estoy tratando de encontrar la manera de ayudar a Antlr a tomar la decisión más obvia a la humana. Quiero analizar el texto así:Antlr lexer tokens que coinciden con cadenas similares, ¿y si el codicioso lexer comete un error?

d/dt(x)=a 
a=d/dt 
d=3 
dt=4 

Esta es una sintaxis de un lenguaje desafortunado que los actuales usos y estoy tratando de escribir un analizador de. La "d/dt (x)" representa el lado izquierdo de una ecuación diferencial. Ignora la jerga si debes, solo debes saber que no está "d" dividida por "dt". Sin embargo, la segunda aparición de "d/dt" realmente es "d" dividida por "dt".

Aquí es mi gramática:.!

grammar diffeq_grammar; 

program : (statement? NEWLINE)*; 

statement 
    : diffeq 
    | assignment; 

diffeq : DDT ID ')' '=' ID; 

assignment 
    : ID '=' NUMBER 
    | ID '=' ID '/' ID 
    ; 

DDT : 'd/dt('; 
ID : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n'|'\r'|'\n'; 

Al utilizar esta gramática del analizador léxico agarra el primer "d/dt (" y lo convierte al DDT símbolo perfecto ahora más tarde, el analizador léxico ve la segunda "d" seguido de un "/" y dice "hmmm, puedo unir esto como un ID y un '/' o puedo ser codicioso y unir DDT". El lexer elige ser codicioso ... pero poco sabe, hay no "(" algunos caracteres más adelante en la secuencia de entrada. Cuando el lexer busca la falta "(" arroja una excepción MismatchedToken!

La única solución que he encontrado hasta ahora, es mover todas las reglas al analizador con un la gramática como:

grammar diffeq_grammar; 

program : (statement? NEWLINE)*; 

statement 
    : diffeq 
    | assignment; 

diffeq : ddt id ')' '=' id; 

assignment 
    : id '=' number 
    | id '=' id '/' id 
    ; 

ddt : 'd' '/' 'd' 't' '('; 
id : CHAR+; 
number : DIGIT+; 
CHAR : 'a'..'z'; 
DIGIT : '0'..'9'; 
NEWLINE : '\r\n'|'\r'|'\n'; 

Ésta es una buena solución si no tuviera ya miles de líneas de código de trabajo que dependen de la primera gramática de trabajo. Después de pasar 2 días investigando este problema, he llegado a la conclusión de que un lexer ... realmente debería ser capaz de distinguir los dos casos. En algún momento, Antlr lexer está decidiendo entre dos reglas: DDT e ID. Elige DDT porque el lexer es codicioso. Pero cuando falla la coincidencia de DDT, me gustaría que el lexer vuelva a usar ID.

Estoy de acuerdo con el uso de predicados u otros trucos, siempre y cuando la gramática permanezca básicamente igual (es decir, las reglas en el lexer, permanecer en el lexer. Y la mayoría de las reglas no se tocan).

Idealmente, puedo modificar la regla de lexer para DDT con cualquier código Antlr válido ... y listo.

Mi idioma de destino es Java.

Gracias!

ACTUALIZACIÓN

Gracias chicos por algunos grandes respuestas !! Acepté la respuesta que mejor se ajustaba a mi pregunta. La solución real que utilicé está en mi propia respuesta (no la respuesta aceptada), y hay más respuestas que podrían haber funcionado. Lectores, revisen todas las respuestas; algunos de ellos pueden adaptarse a su caso mejor que el mío.

Respuesta

5

estoy bien con el uso de predicados u otros trucos, siempre y cuando la gramática sigue siendo básicamente los mismos (es decir, las reglas en el léxico, la estancia en el léxico. Y la mayoría de las normas se deja intacto.).

En ese caso, la fuerza del analizador léxico para mirar hacia adelante en el char-corriente para asegurarse de que realmente hay "d/dt(" utilizando un gated syntactic predicate.

Una demostración:

grammar diffeq_grammar; 

@parser::members { 
    public static void main(String[] args) throws Exception { 
    String src = 
     "d/dt(x)=a\n" + 
     "a=d/dt\n" + 
     "d=3\n" + 
     "dt=4\n"; 
    diffeq_grammarLexer lexer = new diffeq_grammarLexer(new ANTLRStringStream(src)); 
    diffeq_grammarParser parser = new diffeq_grammarParser(new CommonTokenStream(lexer)); 
    parser.program(); 
    } 
} 

@lexer::members { 
    private boolean ahead(String text) { 
    for(int i = 0; i < text.length(); i++) { 
     if(input.LA(i + 1) != text.charAt(i)) { 
     return false; 
     } 
    } 
    return true; 
    } 
} 

program 
: (statement? NEWLINE)* EOF 
; 

statement 
: diffeq  {System.out.println("diffeq  : " + $text);} 
| assignment {System.out.println("assignment : " + $text);} 
; 

diffeq 
: DDT ID ')' '=' ID 
; 

assignment 
: ID '=' NUMBER 
| ID '=' ID '/' ID 
; 

DDT  : {ahead("d/dt(")}?=> 'd/dt('; 
ID  : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n' | '\r' | '\n'; 

Si ahora ejecuta la demo:

java -cp antlr-3.3.jar org.antlr.Tool diffeq_grammar.g 
javac -cp antlr-3.3.jar *.java 
java -cp .:antlr-3.3.jar diffeq_grammarParser

(cuando se utiliza Windows, reemplace el : con ; en el último comando)

se verá la siguiente salida:

diffeq  : d/dt(x)=a 
assignment : a=d/dt 
assignment : d=3 
assignment : dt=4
+0

@dasblinkenlight, ya lo recomendó, por lo que el OP es consciente de ello: no es necesario que me convenza. Ya que el OP preguntó específicamente si la gramática podría seguir siendo mismo, publiqué esto. –

+0

Tiene razón, me perdí la parte sobre "miles de líneas de código de trabajo" en la primera lectura. – dasblinkenlight

+0

@dasblinkenlight, ¡aunque no quise que eliminaras tu respuesta! Aunque el OP quería cambiar su gramática lo menos posible, usted plantea un punto válido que merece una respuesta. –

3

Aunque esto no es lo que estás tratando de hacer teniendo en cuenta la gran cantidad de código de trabajo que tienes en el proyecto, aún deberías considerar separar tu analizador y el analizador más a fondo. Lo mejor es dejar que el analizador y el lexer hagan lo que mejor saben hacer, en lugar de "fusionarlos". La indicación más obvia de que algo anda mal es la falta de simetría entre tus tokens ( y ): uno es parte de un token compuesto, mientras que el otro es un token autónomo.

Si refactorización es en absoluto una opción, puede cambiar el analizador y el léxico de esta manera:

grammar diffeq_grammar; 

program : (statement? NEWLINE)* EOF; // <-- You forgot EOF 

statement 
    : diffeq 
    | assignment; 

diffeq : D OVER DT OPEN id CLOSE EQ id; // <-- here, id is a parser rule 

assignment 
    : id EQ NUMBER 
    | id EQ id OVER id 
    ; 

id : ID | D | DT; // <-- Nice trick, isn't it? 

D  : 'D'; 
DT  : 'DT'; 
OVER : '/'; 
EQ  : '='; 
OPEN : '('; 
CLOSE : ')'; 
ID  : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n'|'\r'|'\n'; 

Es posible que necesite para permitir que dar marcha atrás y memoization para que esto funcione (pero intenta compilarlo sin dar marcha atrás primero) .

+0

¿Por qué es una mala práctica que el paréntesis abierto sea parte de un token más grande y el paréntesis cerrado sea su propio token? Por cierto, me gusta el truco de identificación. – Jason

+0

Me gusta esta solución, está limpia. Esto podría caer directamente en mi código si la regla "id" pudiera devolver un nodo AST con el tipo "ID" (observe la mayúscula) y el valor del texto igual al texto coincidente. Tal vez eso sea posible con: id: ID | D | DT -> ID [$ texto]; – Jason

+1

@Jason En general, las gramáticas para idiomas con signos de puntuación simétricos emparejados (por ejemplo, '()', '{}', '[]', '« »' etc.) esperan reflejar esa simetría en su estructura. Lumping '(' con 'd/dt (' rompe esta simetría, enviando al lector en busca del paréntesis de cierre "desequilibrado." Dado que los archivos de gramática comunican su intención a los lectores y mantenedores de su código tanto como comunican su intención a la herramienta ANTLR, creo que es importante seguir la estructura de su lenguaje en la gramática lo más cerca posible. – dasblinkenlight

1

Aquí está la solución que finalmente utilicé. Sé que infringe uno de mis requisitos: mantener las reglas más lexer en las reglas del analizador y del analizador en el analizador, pero como resulta que mover DDT a ddt no requiere cambios en mi código. Además, dasblinkenlight hace algunos buenos comentarios sobre los paréntesis no coincidentes en sus respuestas y comentarios.

grammar ddt_problem; 

program : (statement? NEWLINE)*; 

statement 
    : diffeq 
    | assignment; 

diffeq : ddt ID ')' '=' ID; 

assignment 
    : ID '=' NUMBER 
    | ID '=' ID '/' ID 
    ; 

ddt : (d=ID) { $d.getText().equals("d") }? '/' (dt=ID) { $dt.getText().equals("dt") }? '('; 
ID : 'a'..'z'+; 
NUMBER : '0'..'9'+; 
NEWLINE : '\r\n'|'\r'|'\n'; 
Cuestiones relacionadas