¿Es posible tener una gramática en la que una "palabra clave" también se pueda tratar como "no palabra clave"?

Question

Tengo la siguiente gramática en ANTLRWorks 1.4. Estoy jugando con ideas para la implementación de un analizador sintáctico en un creador de juegos de texto y aventuras, donde el usuario especificará los diversos comandos permitidos para su juego.

grammar test; 

parse  : cmd EOF; 


cmd   : putSyn1 gameObject inSyn1 gameObject; 

putSyn1  : Put | Place | Drop ; 

inSyn1  : In | Into | Within; 


gameObject : det obj; 

det   : The | A | An | ; 

obj   : Word obj | Word; 


Space  :  (' ' | '\t' | '\r' | '\n'){$channel=HIDDEN;}; 
Put   : 'put'; 
Place  : 'place'; 
Drop  : 'drop'; 
In   : 'in'; 
Into  : 'into'; 
Within  : 'within'; 
The   : 'the'; 
A   : 'a'; 
An   : 'an'; 

Word  : ('a'..'z' | 'A'..'Z')+; 

me estoy haciendo una idea de las diversas sutilezas involucradas (como lo hice here).

Esta vez, usando antlr, me pregunto si puedo analizar la entrada tales como:

put wood in fire place 

Es decir, "madera" y "chimenea" son los GameObjects anteriores. Sin embargo, "lugar" es también un sinónimo de "poner". Por lo que este sería igualmente válida:

place wood in fire place 

antlr me da una NoViableAltException al intentar analizar el último "lugar" token. Quiero reconocer "fire place" como gameObject.

¿Es posible este tipo de cosas en ANTLR? ¿Es posible en gramática?

En el lado, estoy trabajando en una implementación manual que utiliza una estructura de datos personalizada extraña con bits de NFA, Dictionary's y whatnot. Pero aún necesito más tiempo y debo sacrificar algunas células cerebrales para diseñar los algoritmos de inserción de búsqueda & requeridos.

Pero si esto es posible en ANTLR, podría usar el archivo C# generado, ¿eh?

Answer 1

Sure. PL/1 es famoso por no tener palabras reservadas, por ejemplo, puede utilizar las palabras clave (por ejemplo, SI) como un nombre de variable en cualquier lugar que no es necesario como una palabra clave:

IF IF = 1 THEN ELSE=3; ELSE END=4; 

La construcción de un analizador que esto es mas dificil No puede hacer esto "simplemente" en el lexer, porque no conoce el contexto en el que el identificador podría ser una palabra clave, o no.

Hay varias formas de salir. Cuando se encuentra un identificador como entidad:

1) Haga que el lexer pregunte al analizador, "¿quiere una palabra clave ahora?". En ese caso, produce una palabra clave. Hacer que el analizador coopere aquí podría ser difícil. También puede ser que el analizador no lo sepa, porque tiene que ver más información para decidir. Considere instrucción de formato famosa de Fortran:

 FORMAT (A1, I2, ...) X 

No se puede saber cuando vea la palabra "formato" si se trata de una palabra clave o un identificador; tiene que escanear arbitrariamente lejos para inspeccionar X. Si X no es más que un final de instrucción, la palabra FORMATO es el nombre de un identificador de matriz; si X es el fin de la declaración, es una declaración y palabra clave FORMAT.

2) emiten tanto una palabra clave (si el identificador coincide con uno) y el identificador, y hacen que el analizador tratar ambos. La mayoría de los analizadores no manejar esta bien, pero GLR parsers pueden manejar esto con aplomo si se diseñan razonable. Esto maneja el problema de FORMAT trivialmente al presionar en la capacidad de anticipación del analizador. (Antlr no es GLR. Nuestra DMS Software Reengineering Toolkit tiene exactamente un analizador tales GLR, y usar este truco mucho).

3) Colocar todas las cosas-como identificador en una tabla hash. Use un analizador de descenso recursivo (ANTLR es uno); cuando ese analizador quiere una palabra clave, simplemente se inspecciona el identificador llegó a comprobar que es la palabra clave que necesita. Si no quiere una palabra clave, simplemente usa el identificador como identificador. No sé cómo implementar este truco con ANTLR ya que no lo uso. Esto no manejará bien el caso "no puedo decidir sin mirar hacia adelante".

Answer 2

Me gustaría manejar algo como esto con el lexer en lugar del analizador: haga que el lexer haga un "máximo munch", por lo que reconoce "fire place" como un solo token, y solo reconoce "place" como un token separado si no está precedido inmediatamente por "fuego".

Con eso, el analizador no tiene que notar que la misma secuencia de caracteres en la entrada pasa a formar la totalidad o parte de dos tokens completamente separados.