¿Son C#y Java Grammars LALR(x)?

parsing

Question

Me pregunto si las gramáticas C # y Java son LALR (x). Si es así, ¿cuál es el valor de x?

Editar:

Después de aceptar la respuesta verdadera, creo que es mejor cambiar la Q de esta manera:

¿Hay algún analizador LALR (x) que pueda analizar las versiones actuales de Java (versión 7) o C # (versión 4)? Si es así, ¿cuál es el valor de x?

Answer 1

No puede hacer esta pregunta sin antes designar una gramática específica para un idioma, como pueden ser algunas gramáticas, y otras no.

Quizás te refieres a la gramática de Java publicada en las últimas especificaciones de Java. ¿Te refieres a Java 7?

No estoy seguro de que pueda designar una gramática específica para C #, al menos no una de Microsoft, especialmente para C # 4.0; No creo que hayan publicado una gramática.

Puedo decirte que no creo que C # pueda ser LALR (x), porque tiene algunos elementos que parecen identificadores, pero que pueden ser palabras clave en ciertos contextos. Esto requiere que el lexer sepa qué está esperando el analizador para decidir si un identificador de tipo token es una palabra clave, o simplemente e identificador. Por lo tanto, tiene que haber retroalimentación del analizador para leer más, o el lexer tiene que producir ambos tokens y pasarlos al analizador para decidir qué quiere. Los analizadores LALR se definen en las transmisiones de tokens sin comentarios, y cada token de entrada tiene una sola interpretación.

Tampoco creo que Java sea de Java 1.5 y superior, cuando enum se introdujo como un tipo especial con su propia palabra clave. Esto se debe a que, para que los compiladores de Java 1.5 procesen programas existentes de Java 1.4 que utilizan enum como nombre de variable, enum debe tratarse como una palabra clave en algunos contextos y como un nombre de variable en otros. Entonces, un analizador de Java 1.5 tiene los mismos problemas que C #.

Como cuestión práctica, no hay langauges reales son LALR (1) [la primera edición de Java puede ser una excepción] y cualquiera que cree un analizador real (especialmente LALR) tiene que hacer algún tipo de truco para evitar esto. (GCC famoso analizó C ++ con un analizador LALR con un terrible truco de tabla de símbolos durante mucho tiempo, por lo que podría decir la diferencia entre un identificador como una variable y un identificador como una instancia typedef. Ahora tiene algún tipo de implementación manual analizador de descenso recursivo, pero creo que el hack horrible sigue siendo). Entonces no estoy seguro del valor de responder a tu pregunta.

Nuestros miembros de C # 4.0 y Java 7 de nuestra familia de frontales de lenguaje analizan los idiomas utilizando un analizador GLR, que se amplía con la capacidad de retroalimentación y la capacidad de procesar dos interpretaciones del mismo token. GLR hace que la cuestión de LALR (x) sea discutible, y la retroalimentación y las múltiples interpretaciones nos permiten manejar muchos lenguajes que estarían fuera de la capacidad de GLR puro, también.

EDITAR: Después de pensarlo un poco, podría haber una manera realmente desagradable de hacer que ambas gramáticas manejen su palabra clave en contexto. Usemos la enumeración de Java como ejemplo. Realmente tiene que haber una regla gramatical:

  type = ''enum'' ''{''  enum_members ''}'' ;

Pero también debemos permitir ''enum'' como identificador. Podemos hacer eso, reemplazando el identificador de token terminal por un no terminal:

  identifier = IDENTIFIER | ''enum'' ;

e insisten en que IDENTIFICADORES son los terminales producidos por el lexer. Ahora al menos el lexer no tiene que decidir cómo tratar enum ; el analizador lo hace. Pero su gramática designada tendría que tener esta forma para incluso tener la posibilidad de ser LALR (x).

Nuestros analizadores solían hacer esto para permitir que algunas palabras clave se usen a veces como identificadores. Cambiamos nuestro motor de análisis como se describió anteriormente, y ya no hacemos esto.

Answer 2

Al menos para Java (Versión 1.0) es: http://java.sun.com/docs/books/jls/first_edition/html/19.doc.html

Answer 3

La gramática de Java (versión 1.0) es conocida por ser LALR (1); este sitio proporciona una gramática y comienza con el aviso de que

La gramática ha sido revisada mecánicamente para asegurar que sea LALR (1).

No estoy seguro de si C # es LALR (1), pero hay un analizador de C # escrito en bison disponible aquí, lo que sugiere que probablemente sea LALR (1) (suponiendo que permita las declaraciones de precedencia).

Por lo que vale, normalmente LALR (1) es el único analizador LALR utilizado. Si necesita usar algo como LALR (2) para una gramática, por lo general es una mejor idea usar un analizador LALR (1) con desambiguación de precedencia explícita, o un analizador sintáctico más potente como un analizador GLR.

¡Espero que esto ayude!