¿Qué modelos de cálculo se pueden expresar a través de gramáticas?

18

Esta es una reformulación de ¿Son los programas de gramáticas? previamente preguntado por Vag y con muchas sugerencias de los comentaristas.

¿De qué manera puede verse una gramática que especifica un modelo de cálculo? Si, por ejemplo, tomamos una gramática simple sin contexto, como

G ::= '1' -> '0' '+' '1'
      '1' -> '1' '+' '0'
      '2' -> '2' '+' '0'
      '2' -> '1' '+' '1'
      '2' -> '0' '+' '2'
      '3' -> '3' '+' '0'
      '3' -> '2' '+' '1'
      '3' -> '1' '+' '2'
      '3' -> '1' '+' '2'

Suponiendo que el analizador no distingue entre símbolos terminales y no terminales como he demostrado aquí, entonces es posible realizar una aritmética simple para números hasta 3.

Por ejemplo, toma la cuerda

"2 + 0 + 1"

Ejecutar un analizador LR (1) en esta cadena debería darnos el siguiente árbol de sintaxis concreta donde el resultado del cálculo se almacena en la raíz del árbol:

           '3'
         /  |  \
        /   |   \
      '2'  '+'  '1'
     / | \
    /  |  \
  '2' '+' '0'

Por lo tanto, si consideramos que una gramática es un programa y un generador de analizadores para ser un compilador , ¿podríamos ver el lenguaje de especificación gramatical como un lenguaje de programación ?

Además, ¿podríamos construir programas completos de Turing especificando gramáticas similares a cómo podría construir programas completos de Turing con autómatas celulares o el cálculo lambda ?

En otras palabras, se sabe que, en el sentido de reconocer un idioma, los lenguajes regulares corresponden a autómatas de estado finito , los lenguajes libres de contexto corresponden a autómatas de empuje y los lenguajes sensibles al contexto corresponden a autómatas lineales . Sin embargo, si consideramos las gramáticas como dispositivos computacionales (es decir, programas en el sentido del ejemplo anterior), ¿cómo clasificamos la fuerza computacional de cada clase de gramáticas en la jerarquía de Chomsky?

Además, ¿qué hay de las subclases menos conocidas de gramáticas como

Gramáticas deterministas sin contexto (también LR (k) / LL (k) / SLR / LALR, etc.)
Gramáticas de palabras anidadas
Gramáticas adyacentes a los árboles
Gramáticas indexadas

EDITAR: Por cierto, este es un punto crítico en mi propia pregunta, pero no mencioné que no di ningún símbolo de inicio para la gramática de ejemplo y agité a mano la necesidad de distinguir entre terminales y no terminales. Técnica o tradicionalmente creo que la gramática probablemente debería escribirse en una forma más complicada como esta (donde S es el símbolo de inicio y $ representa el terminal de fin de flujo):

G ::= S -> R0 '$'
      S -> R1 '$'
      S -> R2 '$'
      R0 -> '0'
      R0 -> R0 '+' '0'
      R1 -> '1'
      R1 -> R0 '+' '1'
      R1 -> '1' '+' R0
      R1 -> R0 '+' '1' '+' R0
      R2 -> '2'
      R2 -> R0 '+' '2'
      R2 -> '2' '+' R0
      R2 -> R0 '+' '2' '+' R0
      R2 -> R1 '+' '1'
      R2 -> R1 '+' '1' '+' R0

... no es que realmente cambie nada, pero pensé que debería mencionarlo.

EDITAR: Algo más que me vino a la mente cuando leí la respuesta de Gasche es que cada rama en el árbol en mi ejemplo representa un sub-cálculo. Si observa cada regla de producción como una función donde el LHS representa el resultado y el RHS representa sus argumentos, entonces la estructura de la gramática determina cómo se componen las funciones.

En otras palabras, el contexto del analizador junto con su mecanismo de búsqueda anticipada ayuda a determinar no solo qué funciones aplicar ('un poco' como el polimorfismo paramétrico) sino cómo deben componerse juntas para formar nuevas funciones.

Al menos, supongo que podrías verlo de esta manera para CFG inequívocos, para otras gramáticas, la gimnasia mental es demasiado para mí en este momento.

fl.formal-languages pl.programming-languages grammars universal-computation Rehno Lindeque
fuente

3

Se olvidó de mencionar el Autómata Visiblemente Pushdown (palabras anidadas), ¡un aparato tan encantador y prometedor! Es importante porque parece haber una mejora mínima sobre las expresiones regulares para poder analizar programas escritos en lenguajes de programación populares. ( cis.upenn.edu/~alur/nw.html )

Vag

1

Gracias, eso es muy interesante, ¡no lo he buscado! Hay un par de otros que también omití como deterministas, sin contexto, adyacentes a árboles, indexados, etc., solo pensé que podría ser un poco demasiado para una pregunta ... Pero tal vez los

agregaré

1

@imz Me refiero a las gramáticas, ya que se definen formalmente en la jerarquía chomsky (es decir, como conjuntos de producciones). Como estoy afirmando exactamente lo que estás diciendo: que las gramáticas son programas, solo significa la clase de programas representables por gramáticas (que es la pregunta).

Rehno Lindeque

1

@imz Para ser honesto, realmente no estoy familiarizado con las gramáticas indexadas, solo las agregué como una reflexión posterior.

Rehno Lindeque

1

Estoy empezando a pensar que podría haber sido una buena idea publicar esta pregunta en el foro de LtU en lugar de mirar las interesantes discusiones: P. Por cierto @imz, quizás sería mejor leer la pregunta como "qué clases de gramáticas corresponden con qué clases de programas en el sentido 'funcional' descrito por Jukka en la respuesta de Marc Hamman". Quizás debería dejar esto más claro ...

Rehno Lindeque

10

Existe una correspondencia biunívoca entre las gramáticas Chomsky Type-0 y las máquinas de Turing.

Esto se explora en el lenguaje de programación Thue que le permite escribir programas completos de Turing especificados por una cadena inicial y un conjunto de reglas de reescritura de cadenas (una gramática semi-Thue , que es equivalente a una gramática de tipo 0).

ACTUALIZAR:

Además de los lenguajes esotéricos "Turing tar-pit" como Thue, se pueden usar varios lenguajes de propósito general que permiten al programador extender su propia sintaxis para realizar el cómputo completo de Turing durante la etapa de compilación de análisis.

Los idiomas de la familia Lisp , en particular Common Lisp , son probablemente los ejemplos más obvios, pero también, en términos generales, los idiomas con comprobación de tipo estático que no siempre tienen que detenerse, como C ++ con plantillas , Scala y Qi .

Antonio Valerio Miceli-Barone
fuente

Pero la pregunta es sobre cosas que funcionan al revés: uno debe llegar al resultado no reescribiendo una secuencia inicial de símbolos de acuerdo con las reglas, sino que el "resultado" del cálculo definido por una gramática en esta pregunta es una inicial símbolo que puede producir la secuencia de "entrada" de acuerdo con las reglas de la gramática.

imz - Ivan Zakharyaschev

2

Pero, si entiendo correctamente, las dos cosas son esencialmente equivalentes: si y solo si, a partir de un símbolo inicial fijo, la gramática puede generar la secuencia de entrada, entonces la máquina Turing correspondiente acepta en esa secuencia. Si desea considerar los cálculos que devuelven un resultado que no sea aceptar / rechazar, pero aún en un conjunto finito, debe agregar una selección no determinista del símbolo inicial (en realidad, eso es solo una regla adicional). Para permitir resultados en un conjunto infinito, puede definir una gramática que genere la cadena iff .

c o n c a t (q u o t e (i n), o u t)

$concat(quote(in), out)$

T M (i n) = o u t

$TM(in) = out$

Antonio Valerio Miceli-Barone

Estoy de acuerdo en que la correspondencia entre gramáticas Tipo0 y TM es una respuesta válida a la pregunta (especialmente, si se limita a calcular funciones sí / no). La sugerencia adicional de modelar una TM arbitraria con una gramática introduciendo alguna convención sobre cómo representar los pares de entrada-salida me parece que no coincide con el interés previsto de la pregunta original: (para continuar)

imz - Ivan Zakharyaschev

Lo entiendo como una pregunta para explotar exactamente los marcos de gramática existentes y los analizadores correspondientes para realizar cálculos, es decir, la forma permitida de la traducción entre una función f y una gramática solo puede ser: una entrada que se analizó como S significa f ( I) = S.

imz - Ivan Zakharyaschev

1

Superficialmente, el lenguaje de programación Thue no parece caer en este tipo de uso de un marco gramatical: aunque tiene reglas de reescritura como una gramática, el cálculo de un resultado de una entrada va en la dirección de las reglas, no al revés dirección, como Rehno quiere. (Pero tal vez solo se trate de cambiar la dirección de las flechas en las producciones: traducir una gramática de "cálculo como analizador sintáctico" en el sentido de esta Q a Thue solo podría ser cambiar las direcciones de las reglas, luego el programa Thue llegará a los símbolos iniciales como los resultados, ¿verdad? ..)

imz - Ivan Zakharyaschev

6

Mi respuesta no pretende ser formal, precisa y absolutamente dentro del tema. Creo que la respuesta de Marc Hamman es sólida, pero su pregunta me hizo pensar en un tema relacionado.

Las gramáticas pueden considerarse casos especiales de sistemas deductivos: la entrada es un juicio, y el árbol de análisis es una derivación del juicio, o prueba de que el juicio es válido de acuerdo con las reglas (gramaticales).

En ese sentido, su pregunta podría estar relacionada con el enfoque de alguna parte de la comunidad de programación lógica / búsqueda de pruebas (estoy pensando en Dale Miller, por ejemplo), que es que la búsqueda de pruebas tiene contenido computacional, a diferencia del más clásico punto de vista de la teoría de tipo / prueba donde el cálculo es normalización de prueba .

Observación: releyendo mi respuesta, creo que la idea de que "la construcción del árbol de análisis es una búsqueda de prueba" es un poco descabellada aquí. La búsqueda de pruebas fluye más bien en la otra dirección: se parte de un juicio determinado y bastante complejo y, mediante el uso repetido de reglas de inferencia que trabajan en la estructura de la prueba, se espera obtener axiomas más simples que no es necesario probar más. Por lo tanto, sería más natural ver, en términos gramaticales, juicios complejos como no terminales, átomos como terminales, y la búsqueda de pruebas como un problema de generación de palabras, o prueba de no vacío.

gasche
fuente

Comentarios muy interesantes sin embargo. Mi cerebro está demasiado cansado para dar una buena respuesta en este momento, sin embargo, en mi ejemplo, las ramas del árbol esencialmente representan sub-cálculos que se componen juntos de acuerdo con las reglas de análisis ...

Rehno Lindeque

6

Además, ¿podríamos construir programas completos de Turing especificando gramáticas ...?

No estoy seguro si entendí correctamente su pregunta, pero si está buscando un lenguaje de programación basado en un tipo de sistema de reescritura de cadenas, probablemente estaría interesado en Refal , que se basa en el formalismo del algoritmo de Markov (un Turing- formalismo completo, que también es un sistema de reescritura de cadenas tipo gramática).

Artem Pelenitsyn
fuente

1

Entendí la pregunta de la siguiente manera: Rehno está interesado en el proceso de análisis de arranque (definido por una gramática) para ser visto como un cálculo del resultado. El cálculo debe generar el resultado de las partes que van en la dirección opuesta a las reglas de producción de la gramática. Las reglas de reescritura de Refal (IIUC, de manera similar al lenguaje de programación Thue mencionado anteriormente) irían en la otra dirección (desde la entrada hasta el resultado).

imz - Ivan Zakharyaschev

Sin embargo, ahora que lo pienso, las gramáticas sensibles al contexto tienen más de un símbolo en el LHS de las reglas de producción. Así que creo que no hay una diferencia práctica real. Un analizador de un lenguaje sensible al contexto sería un sistema de reescritura de cadenas sin importar cómo lo veas, ¿verdad?

Rehno Lindeque

@imz gracias por la aclaración sobre la pregunta de Rehno. @Rehno “Un analizador de un lenguaje sensible al contexto sería un sistema de reescritura de cadenas, sin importar cómo lo veas, ¿verdad?”, Probablemente tenga sentido, sí.

Artem Pelenitsyn

Pero, ¿se tratan las reglas de reescritura de Refal de manera no determinista? (O dicho de otra manera: ¿hará Refal retroceder en la búsqueda de una ruta de reescritura funcional?) Si queremos modelar este enfoque de "análisis como cálculo" con reglas de reescritura en la dirección inversa, necesitamos reglas no deterministas; considerar una gramática como S -> A a; S -> B b; A -> 0; B -> 0. Si programamos esto invirtiendo las reglas, tendremos que elegir diferentes reglas para procesar 0en tiempo de ejecución para evaluar "0a" o "0b" S.

imz - Ivan Zakharyaschev

6

(Solo algunas consideraciones triviales. Podría ser un comentario, pero demasiado largo).

De hecho, lo que describe se ve en efecto como la visión muy natural de lo que es un idioma (en la comprensión humana del "lenguaje", su propósito) y cómo una gramática define un idioma.

Un lenguaje comprende (infinitamente) formas sintácticas correctas que se interpretan para dar los valores semánticos .

Si la interpretación es computable, entonces las formas sintácticas de un lenguaje pueden verse como programas que computan los valores semánticos.

Si suponemos que un idioma se implementa como un dispositivo finito, podemos llamar a esta representación finita de un idioma una "gramática". Según esta comprensión, una gramática se preocupa por la sintaxis, pero también por la semántica, es decir, cómo calcular el valor semántico de una expresión completa a partir de los valores de sus partes (las partes atómicas y sus valores se almacenan en un "léxico") .

Algunas teorías del lenguaje natural tienen esa forma (la forma que es consistente con las consideraciones anteriores; ya se mencionó en la respuesta de @ gasche aquí): un sistema deductivo que busca una derivación de la entrada (junto con el cálculo de la semántica valor, o la construcción del término de prueba; cf. correspondencia de Curry-Horward). Entonces, si observamos sistemas como ese y los consideramos gramáticas, entonces su pregunta es trivial : estos sistemas están diseñados exactamente para realizar cálculos de la manera que usted describe.

Pero lo que tradicionalmente se llama "lenguajes formales" y "gramáticas formales" carece del lado semántico de esta visión sobre los lenguajes y las gramáticas. Entonces, su pregunta se vuelve interesante: ¿en qué medida se puede "simular" el lado semántico (cálculo) en la sintaxis? ¿Cuáles son los poderes computacionales de cada una de las clases conocidas de gramáticas formales (si el cálculo debe entenderse como el análisis de abajo hacia arriba: una gramática calcula una función en el sentido de su pregunta si se trata $f$ $G$ de una entrada válida si se analiza como el símbolo según )? $I$ $f(I)=S$ $I$ $S$ $G$

(De hecho, los compiladores reales para lenguajes de programación se parecen más a un sistema con sintaxis y semántica: transforman la forma sintáctica de un programa en un ejecutable, que es el significado semántico del programa, y no simplemente un símbolo de inicio de la gramática)

imz - Ivan Zakharyaschev
fuente

4

Solo para agregar:

Un programa de lógica pura tiene lectura declarativa y lectura procesal. Este informe analiza la idea de que estos pueden complementarse con una lectura gramatical, donde las cláusulas se consideran reglas de reescritura de una gramática. El objetivo es mostrar que este punto de vista facilita la transferencia de experiencia de la programación lógica a otras investigaciones sobre lenguajes de programación y viceversa. Se discuten algunos ejemplos de tales transferencias. Por otro lado, la vista gramatical presentada justifica algunas extensiones ad hoc a la programación lógica pura y facilita el desarrollo de fundamentos teóricos para tales extensiones.

Una vista gramatical de la programación lógica por Pierre Deransart y Jan Maluszynski.

Vag
fuente

Aparentemente, Prolog surgió de las gramáticas de atributos, por lo que esta vista es lo que inició la programación lógica.

reinierpost

1

¿Qué pasa con algo como los números de Peano:

S    -> int
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int

reconocerá cualquier cadena (número) de esta forma:

0   // zero
#0  // one
##0 // two

y debería devolver una estructura anidada, siendo la profundidad el número.

Pero comienza a complicarse cuando uno quiere implementar simplemente decir además:

S    -> int
int  -> sum
int  -> zero
int  -> succ
zero -> "0"
succ -> "#" int
sum  -> int "+" int

Tiene mucho sentido ya que solo reconocerá entradas bien formadas como esta:

#####0 + ####0

Pero esta gramática introduce una división en el árbol de análisis cada vez que hay una suma, por lo que, en lugar de tener un bonito árbol de una sola ramificación, que se mapea directamente a un número, tenemos la estructura de la expresión, todavía a unos pocos cálculos de lo efectivo valor. Entonces, no se realiza ningún cálculo, solo reconocimiento. El problema puede no ser la gramática sino el analizador. En cambio, uno puede usar otra cosa, idk ... Otro punto que viene a la mente es la adecuación del formalismo gramatical para expresar la computación. Cuando miras el axioma de Peano (en notación similar a Haskell):

1) Nat = Zero
2) Nat = Succ Nat
3) Sum ( Succ X ) ( Y ) = Succ ( X + Y )
4) Sum Zero X = X

La tercera regla establece explícitamente una transformación. ¿Alguien podría imaginar tener el mismo significado en una regla gramatical libre de contexto? Y si es así, ¿cómo?

dader
fuente

¿Qué modelos de cálculo se pueden expresar a través de gramáticas?

Respuestas: