¿La gramática de expresión lambda de C#es LALR(1)?

parsing (4)

La pregunta que deseo hacer se presenta sucintamente en el título. Permítanme dar un ejemplo de la gramática en cuestión:

identifier_list : identifier | identifier_list identifier; lambda_arguments : ''('' identifier_list '')'' | identifier; lambda : lambda_arguments ''=>'' expression

Luego agregamos la gramática de la expresión C normal, en particular,

primary_expression : ''('' expression '')'' | identifier | lambda;

La verdadera pregunta es, ¿es esta gramática LALR (1) procesable, es decir, capaz de ser analizada por generadores de analizadores automáticos? ¿O requiere un analizador GLR o laminado a mano? Tenga en cuenta que deseo conocer específicamente esta subsección, no las palabras clave sensibles al contexto ni ninguna otra sección.

Lo que estoy pensando ahora es que si el analizador ve ''('' identifier '')'' , esto tiene dos análisis válidos, por lo que si el analizador ve el identifier , mira hacia adelante a '')'' , no podrá decidir qué árbol de análisis para bajar. Sin embargo, esto podría ser un conflicto de cambio / reducción que podría eliminar asignando una precedencia arbitraria (probablemente favouriing ''('' identifier '')'' ).

Editar: En realidad, estaba considerando ~~robar~~ usando esta subsección de la gramática para una función similar en un nuevo idioma. Ya tengo funciones anónimas similares a JavaScript en forma gramatical, pero mis comentarios sobre ~~chirridos de conejillos de Indias se~~ quejan de que son demasiado detallados para muchos usos, y señaló las expresiones C # lambda como una solución más ideal. Estaba preocupado por la posible ambigüedad que resulta de esta solución. Entonces, realmente, solo estaba interesado en esa subsección. Las otras cosas, como genéricos y moldes, no son problemas para mí.

Las ediciones anteriores de mi gramática son mecánicamente analizables y no quisiera perder esta propiedad, y mi experiencia previa con un generador mecánico me dice que es mejor verificar aquí en lugar de probarlo. Para mi analizador sintáctico enrollado a mano, podría, por supuesto, simplemente un ''('' identifier especial ''('' identifier para mirar un poco más allá de lo normal.

En primer lugar, la teoría del analizador fue siempre uno de mis puntos débiles. Trabajo principalmente en analizadores semánticos.

En segundo lugar, todos los analizadores de C # en los que he trabajado han sido analizadores de descenso recursivos generados a mano. Uno de mis antiguos colegas, que tiene una sólida formación en teoría de analizadores, construyó su propio generador de analizadores sintácticos y lo alimentó con la gramática C # con éxito, pero no sé qué clase de intrincados hacks implicaron.

Entonces, lo que estoy diciendo aquí es tomar esta respuesta con la cantidad apropiada de escepticismo.

Como observa, las lambdas son un poco molestas porque hay que tener cuidado con la expresión entre paréntesis: puede ser una expresión entre paréntesis, un operador de conversión o una lista de parámetros lambda, y la lista de parámetros lambda podría tener diferentes formas. Pero considerando todo, agregar lambdas a C # 3.0 fue relativamente fácil, gramaticalmente; piratear el analizador no fue muy difícil, fue el análisis semántico que fue un oso para lambdas.

Los verdaderos problemas de la gramática C # en lo que respecta a la anticipación son los genéricos y los yesos .

Los genéricos se agregaron en C # 2, después de que el lenguaje ya tenía los operadores >> , > y < , todos los cuales pueden causar problemas extraños cuando se arrojan genéricos a la mezcla.

El problema clásico es, por supuesto, A ( B < C, D > ( E ) ) ¿La invocación del método A toma dos argumentos: B < C y D > (E) o uno, B<C,D>( E ) ?

La regla para desambiguar es:

Si una secuencia de tokens se puede analizar como un nombre simple, acceso de miembro o acceso de miembro de puntero que termina con una lista de argumento de tipo, se examina el token que sigue inmediatamente al token de cierre. Si es uno de ( ) ] : ; , . ? == != ( ) ] : ; , . ? == != ( ) ] : ; , . ? == != entonces la lista de argumento de tipo se conserva como parte del nombre simple, acceso de miembro o acceso de miembro de puntero y se descarta cualquier otro posible análisis de la secuencia de tokens. De lo contrario, la lista de argumento de tipos no se considera parte del nombre simple, acceso de miembro o acceso de miembro de puntero, incluso si no hay otro posible análisis de la secuencia de tokens.

El segundo problema con la gramática vuelve a C # 1.0, y ese es el operador de reparto. El problema es que (x)-y podría significar "cast -y para escribir x " o podría significar restar y de x . La regla aquí es:

Una secuencia de uno o más tokens entre paréntesis se considera el inicio de una expresión de conversión solo si al menos uno de los siguientes es verdadero:
La secuencia de tokens es la gramática correcta para un tipo, pero no para una expresión.
La secuencia de tokens es la gramática correcta para un tipo, y el token que sigue inmediatamente al paréntesis de cierre es el token "~", el token "!", El token "(", un identificador, un literal o cualquier palabra clave excepto as y is .

Las reglas que eliminan la ambigüedad de ambos casos implican teorías potencialmente grandes en teoría, pero en la práctica rara vez tiene que realizar una copia de seguridad del analizador sintáctico muy lejos.

No creo que la pregunta de la gramática lambda-expression sea interesante por sí misma, a menos que uno sepa que el resto del lenguaje es LALR (1).

Si quieres saber la respuesta, alimenta tu subgrama a un generador de analizador LALR (1). Si se queja de conflictos shift-reduce o reduce-reduce, no es LALR (1). Si una gramática es LALR (1) se decide si se pueden construir tablas de transición para ella, por definición.

En su mayoría, uno quiere un analizador sintáctico para todo el lenguaje.

Hay dos preguntas interesantes aquí.

1) ¿Es C # 4.5 como un lenguaje LALR (1) en absoluto? (por ejemplo, ¿hay alguna gramática que sea LALR (1)? Tenga en cuenta que una gramática particular que no sea LALR (1) no significa que no hay otra.

2) ¿Alguna de las gramáticas de C # está publicada por Microsoft (en sus múltiples formas) LALR (1)?

Creo que Eric nos dijo que 1) no es cierto. Eso sugiere 2) que no es verdad, también.

C ++ requiere una búsqueda infinita para resolver sus plantillas, causada en gran parte por las posibilidades locales de ">" interpretarse como "argumentos finales de la plantilla" o "mayor que". Como C # copió esto, espero que también tenga requisitos infinitos de anticipación para la resolución de la plantilla. Eso definitivamente no es LALR (1). [Hay un lío adicional en cuanto a si ">>" puede tratarse como un operador de desplazamiento, y ">>" no puede, que no se puede corregir en la gramática porque no puede ver el espacio en blanco.]

Mi compañía usa GLR para sus herramientas de procesamiento de lenguaje, y tenemos una gramática C # 4.5 que funciona muy bien. GLR significa que no tenemos que pensar en cómo convertir una gramática libre de contexto en una forma compatible con LALR (1) (por ejemplo, doblar, girar, factor izquierda / derecha, mezclar), o codificar ad hoc, etc. y así podemos enfocarnos en los problemas de procesar el código, no analizar.

Significa que los moldes y otras construcciones producen árboles ambiguos en el tiempo de análisis, pero estos se resuelven fácilmente si tiene información de tipo.

Sí, esta situación es un conflicto directo de reducción / reducción.

%token identifier ARROW %% program : expression | program expression ; identifier_list : identifier | identifier_list identifier; lambda_arguments : ''('' identifier_list '')'' | identifier; lambda : lambda_arguments ARROW expression; primary_expression : ''('' expression '')'' | identifier | lambda; expression : primary_expression $ yacc -v test.6.y conflicts: 1 reduce/reduce

Esto es exactamente por no saber qué reducción hacer cuando aparece el siguiente símbolo ) : ¿estamos reduciendo una lista lambda_arguments o una primary_expression ?

El generador del analizador lo resolvió de forma incorrecta, al favorecer la lista lambda. Pero eso significa que nunca se puede producir una expresión entre paréntesis.

Hay varias formas de salir de este lío. Este es probablemente el enfoque más fácil, una gramática modificada que no contiene conflictos:

%token identifier ARROW %% program : expression | program expression ; identifier_list : identifier | identifier_list identifier ; lambda_arguments : ''('' identifier identifier_list '')'' | identifier ; primary_expression : ''('' expression '')'' | ''('' expression '')'' ARROW expression | lambda_arguments ARROW expression | identifier ; expression : primary_expression

primary_expression sintaxis lambda en primary_expression , y lambda_arguments ahora es un único identificador sin parentesco, o una lista de al menos dos identificadores.

Además, hay dos casos sintácticos ahora para lambdas:

| ''('' expression '')'' ARROW expression | lambda_arguments ARROW expression

Entonces dos reglas de acción semántica deben ser escritas. Parte de la lógica será común, por lo que puede ser desarrollada en una función auxiliar que construye el nodo de árbol de sintaxis para una lambda.

La acción para la primera variante sintáctica tiene que inspeccionar el símbolo de la mano derecha de $2 y comprobar que se trata de una expresión primaria simple que consiste en un token identificador. Si ese es el caso, la acción rompe la expresión, saca el identificador y crea una lista lambda a partir de ese identificador, y usa esa lista para generar el nodo sintáctico lambda que termina como la salida de la regla (el valor $$ , en términos de Yacc). Si $2 es cualquier otro tipo de expresión, se emite un diagnóstico: es mala sintaxis lambda, como ( 2 + 2 ) => foo . Por supuesto, esto fue aceptado por el analizador, que es cómo se invocó la regla. Pero ahora está siendo semánticamente rechazado (donde semánticamente se refiere a una versión baja en calorías de la palabra "semántica").

La acción para la segunda variante es simple: tomar la lista lambda, la expresión corporal y hacer un nodo lambda, como antes.

En pocas palabras, la sintaxis lambda está tan estrechamente integrada en la sintaxis de expresión, que no se puede cultivar fácilmente en reglas completamente separadas que se introducen a través de una única producción que requiere que lambda se reduzca a primary_expression . Eso es una ilusión, porque las reglas para un analizador de desplazamiento-reducción no son llamadas de función.

Una gramática de expresión aumentada con lambdas de estilo C # no es LALR (1), pero es probable que sea LALR (2). En consecuencia, es posible (aunque no necesariamente trivial) producir una gramática LALR (1) equivalente: ver edición a continuación.

Obtendrá un conflicto de reducción / reducción en la entrada:

( id )

porque id puede reducirse a identifier_list o a expression (indirectamente, en el segundo caso), y el analizador no puede decir cuál es correcto en función de un token de búsqueda anticipada ( ) ).

Podría decir en base a dos tokens de anticipación, ya que la reducción de identifier_list solo es posible si el segundo token siguiente es => , y siempre que => no sea un operador en su idioma, la reducción de expression no es posible si el segundo token siguiente es => . Entonces creo que es probablemente LALR (2), aunque no puedo decir eso con certeza.

El caso donde hay más de un identificador no es problemático, ya que en

( id1 id2 )

id1 id2 no se puede reducir a una expresión (en la mayoría de los lenguajes de expresión, el suyo puede, por supuesto, diferir). El caso en el que un único identificador no apareado es seguido inmediatamente por => tampoco es problemático, siempre que `=> ''no sea un operador válido.

Editar

Me olvidé de mencionar en mi respuesta original que no existe el lenguaje LALR (2). El lenguaje reconocido por una gramática LALR (2) también es reconocido por alguna gramática LALR (1). De hecho, hay una prueba constructiva de esta afirmación, que permite la creación mecánica de dicha gramática LALR (1), junto con un procedimiento para recuperar el árbol de análisis sintáctico original.

En este caso, es aún más simple generar una gramática LALR (1), ya que, como se mencionó anteriormente, solo hay una producción que requiere un análisis adicional. La solución es retrasar la reducción en un token. En otras palabras, en la gramática original incluye algo como:

primary: ''('' expression '')'' lambda_parameters: ''('' id_list '')''

donde id_list y expression derivan la ID terminal. Además de la ID , las derivaciones de estos dos no terminales son disjuntas, por lo que podríamos resolver el problema de la siguiente manera:

primary: ''('' expression_not_id '')'' | ''('' ID '')'' lambda_parameters: ''('' id_list_not_id '')'' | ''('' ID '')'' "

Solo resta dividir las producciones para expression y id_list para separar el caso de ID , que no es muy difícil. A continuación se muestra un ejemplo simplificado, que podría ampliarse fácilmente; está restringido a la aplicación de adición, multiplicación y función (que incluí para demostrar que las dos listas separadas por comas no son un problema):

Nota: La gramática en el OP produce lambdas con múltiples parámetros como una secuencia de identificadores no separados por comas: (ab) => a + b . Creo que la intención real era usar comas: (a, b) => a + b , y eso es lo que hice en la gramática anterior. La diferencia es importante si su idioma tiene un operador de coma, como lo hace la familia C, porque en ese caso una expresión podría ser ''('' expression_list '')'' , que entra en conflicto con una lista de parámetros lambda. Una implementación ingenua daría como resultado un conflicto de reducción / reducción en la primera expression en la expression_list que no puede resolverse con una búsqueda anticipada finita, ya que la expression_list puede ser arbitrariamente larga.

Sin embargo, también hay una solución para este caso: consiste en separar id_list de expression_list , algo como lo siguiente:

id_list: ID | id_list '','' ID ; expression_list_not_id_list: expression_not_id | id_list '','' expression_not_id | expression_list_not_id_list '','' expression ; expression_list: expression_list_not_id_list | id_list ;

Sin embargo, no hice una gramática completa, ya que no tengo idea de lo que requiere el idioma de destino.