stringtranslate.com

Gramática de Van Wijngaarden

En informática , una gramática de Van Wijngaarden (también vW-grammar o W-grammar [1] ) es un formalismo para definir lenguajes formales . El nombre deriva del formalismo inventado por Adriaan van Wijngaarden [2] con el propósito de definir el lenguaje de programación ALGOL 68. La especificación resultante [3] sigue siendo su aplicación más notable.

Las gramáticas de Van Wijngaarden abordan el problema de que las gramáticas libres de contexto no pueden expresar acuerdo o referencia, donde dos partes diferentes de la oración deben concordar entre sí de alguna manera. Por ejemplo, la oración "Los pájaros estaban comiendo" no es inglés estándar porque no concuerda en el número . Una gramática libre de contexto analizaría "Los pájaros estaban comiendo" y "Los pájaros estaban comiendo" y "El pájaro estaba comiendo" de la misma manera. Sin embargo, las gramáticas libres de contexto tienen el beneficio de la simplicidad, mientras que las gramáticas de van Wijngaarden se consideran altamente complejas. [4]

Dos niveles

Las gramáticas W son gramáticas de dos niveles : están definidas por un par de gramáticas que operan en diferentes niveles:

El conjunto de cadenas generadas por una gramática W se define mediante un proceso de dos etapas:

  1. dentro de cada hiperregla, para cada atributo que aparece en ella, elija un valor generado por la metagramática; el resultado es una regla gramatical normal libre de contexto; haga esto de todas las formas posibles;
  2. Utilice la gramática libre de contexto resultante (posiblemente infinita) para generar cadenas de la forma normal.

La sustitución consistente utilizada en el primer paso es la misma que la sustitución en la lógica de predicados , y en realidad admite la programación lógica ; corresponde a la unificación en Prolog , como lo señaló Alain Colmerauer [ ¿dónde? ] .

Las gramáticas W son Turing completas ; [5] por lo tanto, todos los problemas de decisión relacionados con los lenguajes que generan, como

son indecidibles​

Se desarrollaron variantes restringidas, conocidas como gramáticas de afijos , y se aplicaron en la construcción de compiladores y en la descripción de lenguajes naturales.

Los programas lógicos definidos , es decir, programas lógicos que no hacen uso de la negación, pueden considerarse una subclase de las gramáticas W. [6]

Motivación e historia

En la década de 1950, comenzaron los intentos de aplicar las computadoras al reconocimiento, interpretación y traducción de idiomas naturales, como el inglés y el ruso. Esto requiere una descripción legible por máquina de la estructura sintáctica de las oraciones, que pueda usarse para analizarlas, interpretarlas y generarlas. Las gramáticas independientes del contexto, un concepto de la lingüística estructural , se adoptaron para este propósito; sus reglas pueden expresar cómo se construyen oraciones de forma recursiva a partir de partes del discurso , como frases nominales y frases verbales , y, en última instancia, palabras, como sustantivos , verbos y pronombres .

Este trabajo influyó en el diseño y la implementación de lenguajes de programación , más notablemente, de ALGOL 60 , que introdujo una descripción de sintaxis en forma Backus-Naur .

Sin embargo, las reglas libres de contexto no pueden expresar acuerdo o referencia ( anáfora ), donde dos partes diferentes de la oración deben concordar entre sí de alguna manera.

Estos pueden expresarse fácilmente en gramáticas W. (Vea el ejemplo a continuación).

Los lenguajes de programación tienen nociones análogas de tipificación y alcance . Un compilador o intérprete del lenguaje debe reconocer qué usos de una variable pertenecen juntos (hacen referencia a la misma variable). Esto suele estar sujeto a restricciones como:

Las gramáticas W se basan en la idea de proporcionar a los símbolos no terminales de gramáticas libres de contexto atributos (o afijos ) que pasan información entre los nodos del árbol de análisis , utilizados para restringir la sintaxis y especificar la semántica.

Esta idea era bien conocida en ese momento; por ejemplo, Donald Knuth visitó el comité de diseño de ALGOL 68 mientras desarrollaba su propia versión, las gramáticas de atributos . [7]

Si se amplía la descripción de la sintaxis con atributos, se pueden comprobar restricciones como las anteriores, descartando muchos programas no válidos en el momento de la compilación. Como escribió Van Wijngaarden en su prefacio: [2]

Mis principales objeciones eran, para mí, las restricciones innecesarias y la definición de la sintaxis y la semántica. En realidad, la sintaxis vista en MR 75 produce una gran cantidad de programas, mientras que yo preferiría tener el subconjunto de programas significativos lo más grande posible, lo que requiere una sintaxis más estricta. [...] pronto se hizo evidente que algunas herramientas mejores que la notación Backus podrían ser ventajosas [...]. Desarrollé un esquema [...] que permite que el diseño de un lenguaje lleve mucha más información en la sintaxis de la que se lleva normalmente.

Algo muy peculiar de las gramáticas W es su estricto tratamiento de los atributos como cadenas, definidas por una gramática independiente del contexto, en la que la concatenación es la única operación posible; las estructuras de datos y operaciones complejas se pueden definir mediante la coincidencia de patrones (véase el ejemplo siguiente).

Después de su introducción en el "Informe final" de ALGOL 68 de 1968 , las gramáticas W fueron consideradas en general demasiado poderosas y sin restricciones para ser prácticas. [ cita requerida ]

Esto fue en parte una consecuencia de la forma en que se habían aplicado; el "Informe Revisado" ALGOL 68 de 1973 contiene una gramática mucho más legible, sin modificar el formalismo de la gramática W en sí.

Mientras tanto, se hizo evidente que las gramáticas W, cuando se utilizan en su totalidad, son en realidad demasiado potentes para fines prácticos como servir como entrada para un generador de analizadores sintácticos . Describen con precisión todos los lenguajes recursivamente enumerables , [8] lo que hace que el análisis sintáctico sea imposible en general: es un problema indecidible decidir si una cadena dada puede ser generada por una gramática W dada.

Por lo tanto, su uso debe restringirse seriamente cuando se utilizan para análisis o traducción automáticos. Se desarrollaron variantes restringidas y modificadas de gramáticas W para abordar este problema, por ejemplo

Después de la década de 1970, el interés en este enfoque disminuyó; ocasionalmente, se publican nuevos estudios. [9]

Ejemplos

Concordancia en la gramática inglesa

En inglés, los sustantivos, pronombres y verbos tienen atributos como número gramatical , género y persona , que deben concordar entre el sujeto , el verbo principal y los pronombres que hacen referencia al sujeto:

Son oraciones válidas; no válidas, por ejemplo:

Aquí, el acuerdo sirve para enfatizar que ambos pronombres (por ejemplo, yo y yo mismo ) se refieren a la misma persona.

Una gramática libre de contexto para generar todas esas oraciones:

 < oración >  ::=  < sujeto >  < verbo >  < objeto >  < sujeto >  ::= yo | tú | él | ella | nosotros | ellos < verbo >  ::= lavar | lava < objeto >  ::= yo mismo | tú mismo | él mismo | ella misma | nosotros mismos | vosotros mismos | ellos mismos

A partir de <sentence>, podemos generar todas las combinaciones:

Me lavoMe lavoMe lavo[...]Se lavan ustedes mismosSe lavan ellos mismos

Una gramática W para generar solo las oraciones válidas:

<oración < NÚMERO >  < GÉNERO >  < PERSONA > > ::= <sujeto < NÚMERO >  < GÉNERO >  < PERSONA > > <verbo < NÚMERO >  < PERSONA > > <objeto < NÚMERO >  < GÉNERO >  < PERSONA > > <sujeto singular < GÉNERO > 1º> ::= Yo <sujeto < NÚMERO >  < GÉNERO > 2º> ::= Tú < sujeto singular masculino 3º >  ::= Él < sujeto singular femenino 3º >  ::= Ella <sujeto plural < GÉNERO > 1º> ::= Nosotros <sujeto singular < GÉNERO > 3º> ::= Ellos < verbo singular 1º >  ::= lavar < verbo singular 2º >  ::= lavar < verbo singular 3º >  ::= lava< verbo plural <PERSONA> > :: = lavar <objeto singular < GÉNERO > 1º> ::= yo mismo <objetivo singular < GÉNERO > 2º> ::= usted mismo < objeto singular masculino 3º >  ::= él mismo < objeto singular femenino 3º >  ::= ella misma <object plural < GENDER > 1st> ::= nosotros mismos <object plural < GENDER > 2nd> ::= vosotros mismos <object plural < GENDER > 3rd> ::= ellos mismos < NÚMERO >  ::= = singular | plural < GÉNERO >  ::= = masculino | femenino < PERSONA >  ::= = 1.º | 2.º | 3.º

Un lenguaje estándar no libre de contexto

Un lenguaje no libre de contexto muy conocido es

Una gramática de dos niveles para este idioma es la metagramática.

N::= 1 | N1
X ::= a | b

junto con el esquema gramatical

Inicio ::= ⟨a N ⟩ ⟨b N ⟩ ⟨a N ⟩
⟨X N1 ⟩  ::= ⟨X N ⟩ X
⟨X 1 ⟩  ::= X

Preguntas. Si se sustituye una nueva letra, por ejemplo C, por N1, ¿se conserva el lenguaje generado por la gramática? ¿O N1 debería leerse como una cadena de dos símbolos, es decir, N seguida de 1? Fin de las preguntas.


Requerimiento de uso válido de variables en ALGOL

El Informe revisado sobre el lenguaje algorítmico Algol 60 [10] define una sintaxis completamente libre de contexto para el lenguaje.

Las asignaciones se definen de la siguiente manera (sección 4.2.1):

 < parte izquierda >  ::=  < variable >  := | < identificador de procedimiento >  :=  < lista de la parte izquierda >  ::=  < parte izquierda > | < lista de la parte izquierda >  < parte izquierda >  < declaración de asignación >  ::=  < lista de la parte izquierda >  < expresión aritmética > | < lista de la parte izquierda >  < expresión booleana >

A <variable>puede ser (entre otras cosas) un <identifier>, que a su vez se define como:

<identificador> ::= <letra> | <identificador> <letra> | <identificador> <dígito>

Ejemplos (sección 4.2.2):

s:=p[0]:=n:=n+1+sn:=n+1A:=B/Cvq×SS[v,k+2]:=3-arctan(sTIMESzeta)V:=Q>Y^Z

Las expresiones y asignaciones deben tener comprobación de tipo : por ejemplo,

Las reglas anteriores distinguen entre <arithmetic expression>y <Boolean expression>, pero no pueden verificar que la misma variable siempre tenga el mismo tipo.

Este requisito (no independiente del contexto) se puede expresar en una gramática W anotando las reglas con atributos que registran, para cada variable utilizada o asignada, su nombre y tipo.

Luego, este registro se puede llevar a todos los lugares de la gramática donde es necesario hacer coincidir los tipos e implementar la verificación de tipos.

De manera similar, se puede utilizar para comprobar la inicialización de variables antes de su uso, etcétera.

Uno podría preguntarse cómo crear y manipular una estructura de datos de este tipo sin un soporte explícito en el formalismo para las estructuras de datos y las operaciones sobre ellas. Se puede hacer utilizando la metagramática para definir una representación de cadena para la estructura de datos y utilizando la coincidencia de patrones para definir las operaciones:

< parte izquierda con <TIPIFICADO> <NOMBRE> > :: = < variable con <TIPIFICADO> <NOMBRE> > : =  | < identificador de procedimiento con <TIPO> <NOMBRE> > : =  < parte izquierda lista <TYPEMAP1> > :: = < parte izquierda con <TYPED> <NAME> > < donde <TYPEMAP1> es <TYPED> <NAME> añadido a ordenado <EMPTY> >​​​​​ | <lista de la parte izquierda <TYPEMAP2> >< parte izquierda con <TIPO> <NOMBRE> >​ < donde <TYPEMAP1> es <TYPED> <NAME> añadido a <TYPEMAP2> ordenado​​​​​​   <sentencia de asignación < ASIGNADO A >  < UTILIZADO > > ::= <lista de la parte izquierda < ASIGNADO A > > <expresión aritmética < UTILIZADA > > | <lista de la parte izquierda < ASIGNADO A > > <expresión booleana < UTILIZADA > >  <donde < TIPO >  < NOMBRE > se agrega < TIPO >  < NOMBRE > al < VACÍO > ordenado ::= < donde <TYPEMAP1> es <TYPED1> <NAME1> añadido a <TYPEMAP2> ordenado > :: = < donde <TYPEMAP2> es <TYPED2> <NAME2> añadido a <TYPEMAP3> ordenado >​​​​​ ​​​​   <donde < NOMBRE1 > está lexicográficamente antes de < NOMBRE2 > > < donde <TYPEMAP1> es <TYPED1> <NAME1> añadido a <TYPEMAP2> ordenado > :: = < donde <TYPEMAP2> es <TYPED2> <NAME2> añadido a <TYPEMAP3> ordenado >​​​​​ ​​​​   <donde < NOMBRE2 > está lexicográficamente antes de < NOMBRE1 > > <donde < TYPEMAP3 > es < TYPED1 >  < NAME1 > añadido a < TYPEMAP4 > ordenado  <donde < VACÍO > está lexicográficamente antes de < NOMBRE1 > > ::= <donde < NOMBRE1 > es < LETRA O DÍGITO > seguido de < NOMBRE2 > >  <donde < NOMBRE1 > está lexicográficamente antes de < NOMBRE2 > > ::= <donde < NOMBRE1 > es < LETRA O DÍGITO > seguido de < NOMBRE3 > > <donde < NOMBRE2 > es < LETRA O DÍGITO > seguido de < NOMBRE4 > > <donde < NOMBRE3 > está lexicográficamente antes de < NOMBRE4 > >  <donde < NOMBRE1 > está lexicográficamente antes de < NOMBRE2 > > ::= <donde < NOMBRE1 > es < LETRA O DÍGITO 1 > seguido de < NOMBRE3 > > <donde < NOMBRE2 > es < LETRA O DÍGITO 2 > seguido de < NOMBRE4 > > <donde < LETRA O DÍGITO 1 > precede a + < LETRA O DÍGITO 2 >  <donde < LETRA O DÍGITO 1 > precede a + < LETRA O DÍGITO 2 >  ::= <donde < LETRA O DÍGITO 1 > precede a < LETRA O DÍGITO 2 >  <donde < LETRA O DÍGITO 1 > precede+ < LETRA O DÍGITO 2 >  ::= <donde < LETRA O DÍGITO 1 > precede+ < LETRA O DÍGITO 3 > <donde < LETRA O DÍGITO 3 > precede+ < LETRA O DÍGITO 2 >  < donde a precede a b >  :== < donde b precede a c >  :== [...]  < TYPED >  ::= = real | entero | Booleano  < NOMBRE >  ::= = < LETRA > | < NOMBRE >  < LETRA > | < NOMBRE >  < DÍGITO >  < LETRA O DÍGITO >  ::= = < LETRA > | < DÍGITO >  < LETRA O DÍGITO 1 >  ::=  < LETRA O DÍGITO >  < LETRA O DÍGITO 2 >  ::=  < LETRA O DÍGITO >  < LETRA O DÍGITO 3 >  ::=  < LETRA O DÍGITO >  < LETRA >  ::= = a | b | c | [...] < DÍGITO >  ::= = 0 | 1 | 2 | [...]  < NOMBRES1 >  ::= = < NOMBRES >  < NOMBRES2 >  ::= = < NOMBRES >  < ASIGNADO A >  ::= = < NOMBRES >  < UTILIZADO >  ::= = < NOMBRES >  < NOMBRES >  ::= = < NOMBRE > | < NOMBRE >  < NOMBRES >  < VACÍO >  ::= = < TYPEMAP >  ::= = ( < TYPED >  < NOMBRE > ) < TYPEMAP >  < TYPEMAP1 >  ::= = < TYPEMAP >  < TYPEMAP2 >  ::= = < TYPEMAP >  < TYPEMAP3 >  ::= = < TYPEMAP >

En comparación con la gramática original, se han añadido tres elementos nuevos:

Las nuevas hiperreglas son ε -reglas: sólo generan la cadena vacía.

Ejemplos de ALGOL 68

Los informes ALGOL 68 utilizan una notación ligeramente diferente sin <corchetes angulares>.

ALGOL 68 como en el Informe Final de 1968 §2.1

a) programa: símbolo abierto, preludio estándar, opción de preludio de biblioteca, programa particular, salir, opción de posludio de biblioteca, posludio estándar, símbolo de cierre. b) preludio estándar: secuencia de preludio de declaración. c) preludio de la biblioteca: secuencia de preludio de declaración. d) programa particular: Opción de secuencia de etiquetas, cláusula nula CERRADA fuerte. e) salir: continuar símbolo, letra e letra x letra i letra t, etiqueta símbolo. f) postludio de la biblioteca: interludio de declaración. g) postludio estándar: cláusula nula fuerte

ALGOL 68 como en el Informe Revisado de 1973 §2.2.1, §10.1.1

programa : fuerte nulidad nueva cláusula cerrada A) EXTERNO:: estándar; biblioteca; sistema; particular. B) STOP:: etiqueta letra s letra t letra o letra p. a) texto del programa: STYLE comienza el token, preludia el nuevo LAYER1, token paralelo, nuevo PAQUETE de tareas LAYER1, Token final de ESTILO. b) Preludios NEST1: preludio estándar NEST1 con DECS1, Preludio de la biblioteca NEST1 con DECSETY2, Preludio del sistema NEST1 con DECSETY3, donde (NEST1) es (nuevo VACÍO nuevo DECS1 DECSETY2 DECSETY3). c) Preludio EXTERNO NEST1 con DECSETY1: fuerte vacío serie NEST1 con DECSETY1, continúa con token; donde (DECSETY1) es (VACÍO), VACÍO. d) Tareas NEST1: lista de tareas del sistema NEST1 y también token, Lista de paquetes de tareas de usuario NEST1. e) Tarea del sistema NEST1: unidad NEST1 de vacío fuerte. f) Tarea de usuario NEST1: preludio particular de NEST2 con DECS, Programa particular NEST2 PACK, continúa con el token, Postludio particular de NEST2, donde (NEST2) es (NEST1 nuevo DECS STOP). g) Programa particular de NEST2: Definición de etiqueta incorporada a NEST2 y LABSETY3 de LABSETY3, fuerte vacío NEST2 nuevo LABSETY3 Cláusula adjunta. h) Definición de etiqueta unida NEST de LABSETY: donde (LABSETY) es (VACÍO), VACÍO; donde (LABSETY) es (LAB1 LABSETY1), Definición de etiqueta NEST de LAB1, NEST se unió a la definición de etiqueta de $ LABSETY1. i) Postludio particular de NEST2: Serie NEST2 de fuerte vacío con STOP.

Un ejemplo simple del poder de las gramáticas W es la cláusula

a) texto del programa: STYLE comienza el token, preludia el nuevo LAYER1, token paralelo, nuevo PAQUETE de tareas LAYER1, Token final de ESTILO.

Esto permite BEGIN... END y { } como delimitadores de bloque, mientras que descarta BEGIN... } y {... END.

Quizás deseemos comparar la gramática del informe con el analizador Yacc para un subconjunto de ALGOL 68 de Marc van Leeuwen. [11]

Implementaciones

Anthony Fisher escribió yo-yo , [12] un analizador sintáctico para una gran clase de gramáticas W, con gramáticas de ejemplo para expresiones , eva , sal y Pascal (el estándar ISO 7185 actual para Pascal utiliza la forma extendida Backus–Naur ).

Dick Grune creó un programa en C que generaría todas las producciones posibles de una gramática W. [13]

Aplicaciones fuera de ALGOL 68

Las aplicaciones de las gramáticas de afijos extendidos (GAE) mencionadas anteriormente pueden considerarse efectivamente como aplicaciones de las gramáticas W, ya que las GE son muy similares a las gramáticas W. [14]

También se han propuesto gramáticas W para la descripción de acciones humanas complejas en ergonomía . [ cita requerida ]

También se ha proporcionado una descripción de gramática W para Ada . [15]

Véase también

Referencias

  1. ^ Cleaveland, J. Craig; Uzgalis, Robert C. (1977). Gramáticas para lenguajes de programación . Elsevier. ISBN 978-0-444-00199-3.
  2. ^ ab van Wijngaarden, Adriaan (1972-04-04) [Edición prematura y preliminar 1965-10-22]. MR 76: Diseño ortogonal y descripción de un lenguaje formal (PDF) (Informe técnico). Ámsterdam: CWI . Archivado desde el original (PDF) el 2017-10-02.
  3. ^ van Wijngaarden, A.; et al. (eds.). "Informe revisado sobre el lenguaje algorítmico ALGOL 68". Archivado desde el original el 24 de enero de 2002.
  4. ^ Koster, CHA (1996). "La creación de Algol 68". En Bjørner, D; Broy, M.; Pottosin, IV (eds.). Perspectivas de la informática de sistemas. Apuntes de clase en informática. Vol. 1181. Berlín: Springer. págs. 55–67. doi :10.1007/3-540-62064-8_6. ISBN 978-3-540-62064-8.
  5. ^ Sintzoff, M. (1967). "Existencia de la sintaxis de van Wijngaarden para cada conjunto recursivamente enumerable". Annales de la Société Scientifique de Bruselas . 2 : 115-118.
  6. ^ Deransart, Pierre; Maluszynski, Jan (1993), "Extensiones gramaticales de programas lógicos", Una visión gramatical de la programación lógica , The MIT Press, págs. 109-140, doi :10.7551/mitpress/3345.003.0008, ISBN 9780262290845, consultado el 14 de junio de 2023
  7. ^ Knuth, Donald E (1990), "La génesis de las gramáticas de atributos" ( Plain TeX , gZiped ) , Actas de la Conferencia internacional sobre gramáticas de atributos y sus aplicaciones , Springer Verlag : 1–12.
  8. ^ Sintzoff, M. (1967). "Existencia de una sintaxis de van Wijngaarden para cada conjunto recursivamente enumerable". Annales de la Société scientifique de Bruselas . 81 : 115-118.
  9. ^ Augusto, LM (2023). "Gramáticas de dos niveles: algunas propiedades interesantes de las gramáticas de van Wijngaarden" (PDF) . Omega - Revista de Lenguas Formales . 1 : 3–34.
  10. ^ Backus, JW; et al. (1963). "Informe revisado sobre el lenguaje algorítmico ALGOL 60". The Computer Journal . 5 (4): 349–367. doi : 10.1093/comjnl/5.4.349 .
  11. ^ "Sintaxis", Algol 68, FR : Univ Poitiers
  12. ^ Fisher, Anthony (30 de julio de 2024), "yo-yo", Software, Reino Unido : York.
  13. ^ Grune, Dick, Un generador de oraciones de dos niveles, NL : VU.
  14. ^ Alblas, Henk; Melichar, Borivoj (1991). Gramáticas, aplicaciones y sistemas de atributos. Apuntes de conferencias sobre informática. vol. 545. Saltador. pag. 371.ISBN​ 978-3540545729.
  15. ^ Flowers, Roy, Una descripción de la gramática W para Ada (PDF) (Tesis de maestría), Instituto de Tecnología de la Fuerza Aérea, Universidad del Aire

Lectura adicional