En informática , una gramática de Van Wijngaarden (también vW-gramática o W-gramática [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 concordancia 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 coincide en el número . Una gramática libre de contexto analizaría "Los pájaros comían", "Los pájaros comían" y "El pájaro comía" de la misma manera. Sin embargo, las gramáticas libres de contexto tienen la ventaja de la simplicidad, mientras que las gramáticas de van Wijngaarden se consideran muy complejas. [4]
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:
La sustitución consistente utilizada en el primer paso es la misma que la sustitución en la lógica de predicados y, de hecho, admite la programación lógica ; corresponde a la unificación en Prolog , como señala 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 , que se aplicaron en la construcción de compiladores y en la descripción de lenguajes naturales.
Los programas de lógica definida , es decir, los programas lógicos que no utilizan la negación, pueden verse como una subclase de las gramáticas W. [6]
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 de las oraciones, que pueda usarse para analizarlas, interpretarlas y generarlas. Para ello se adoptaron gramáticas libres de contexto, un concepto de la lingüística estructural ; sus reglas pueden expresar cómo las oraciones se construyen recursivamente a partir de partes del discurso , como frases nominales y 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 , en particular, 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 se pueden expresar 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 van juntos (consulte la misma variable). Esto suele estar sujeto a restricciones tales como:
Las gramáticas W se basan en la idea de proporcionar a los símbolos no terminales de las gramáticas libres de contexto atributos (o afijos ) que pasan información entre los nodos del árbol de análisis , utilizado 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, Gramáticas de atributos . [7]
Al aumentar la descripción de la sintaxis con atributos, se pueden verificar 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 fueron ciertas 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 quedó claro que algunas herramientas mejores que la notación Backus podrían ser ventajosas [...]. Desarrollé un esquema [...] que permite el diseño de un lenguaje para contener mucha más información en la sintaxis de la que normalmente se lleva.
Bastante peculiar de las gramáticas W fue su tratamiento estricto de los atributos como cadenas, definidas por una gramática libre de contexto, en la que la concatenación es la única operación posible; Se pueden definir operaciones y estructuras de datos complejas mediante la coincidencia de patrones . (Vea el ejemplo a continuación).
Después de su introducción en el "Informe final" de ALGOL 68 de 1968 , las gramáticas W fueron ampliamente consideradas como demasiado poderosas y ilimitadas para ser prácticas. [ cita necesaria ]
Esto fue en parte 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, quedó claro que las gramáticas W, cuando se usan en toda su generalidad, son realmente demasiado poderosas para propósitos prácticos como servir como entrada para un generador de analizadores . Describen precisamente todos los lenguajes recursivamente enumerables , [8] lo que hace que el análisis sea imposible en general: es un problema indecidible decidir si una determinada cadena puede ser generada por una determinada W-gramática.
Por lo tanto, su uso debe verse seriamente restringido cuando se utiliza para análisis o traducción automática. Se desarrollaron variantes restringidas y modificadas de gramáticas W para abordar esto, por ejemplo
Después de la década de 1970, el interés en este enfoque decayó; ocasionalmente se publican nuevos estudios. [9]
En inglés, los sustantivos, pronombres y verbos tienen atributos como número gramatical , género y persona , los cuales deben concordar entre sujeto , verbo principal y pronombres referidos al sujeto:
son oraciones válidas; no válidos son, por ejemplo:
Aquí, la concordancia 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 estas oraciones:
<oración> ::= <sujeto> <verbo> <objeto><sujeto> ::= Yo | Tú | El | Ella | Nosotros | Ellos<verbo> ::= lavar | lava<objeto> ::= yo mismo | usted mismo | él mismo | ella misma | nosotros mismos | ustedes mismos | ellos mismos
A partir de la frase, podemos generar todas las combinaciones:
me lavome lavome lavo[...]se lavanse lavan
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º> ::= I<sujeto <NÚMERO> <GÉNERO> 2do> ::= 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 2do> ::= lavar<verbo singular 3º> ::= lava<verbo plural <PERSONA>> ::= lavar
<objeto singular <GÉNERO> 1º> ::= yo mismo<objeto singular <GÉNERO> 2do> ::= tú mismo<objeto singular masculino 3º> ::= él mismo<objeto singular femenino 3º> ::= ella misma<objeto plural <GÉNERO> 1º> ::= nosotros mismos<objeto plural <GÉNERO> 2do> ::= ustedes mismos<objeto plural <GÉNERO> 3º> ::= ellos mismos
<NÚMERO> ::== singular | plural<GÉNERO> ::== masculino | femenino<PERSONA> ::== 1er | 2do | 3er
Un lenguaje bien conocido no libre de contexto es
Una gramática de dos niveles para este idioma es la metagramática.
junto con el esquema gramatical
El Informe revisado sobre el lenguaje algorítmico Algol 60 [10] define una sintaxis completa libre de contexto para el lenguaje.
Las asignaciones se definen de la siguiente manera (sección 4.2.1):
<parte izquierda> ::= <variable> := | <identificador del procedimiento> :=<lista de partes izquierda> ::= <parte izquierda> | <lista de partes izquierda> <parte izquierda><declaración de tarea> ::= <lista de partes izquierda> <expresión aritmética> | <lista de partes izquierda> <expresión booleana>
Una <variable> puede ser (entre otras cosas) un <identificador>, 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+snorte:=n+1A:=B/Cvq×SS[v,k+2]:=3-arctan(sTIMESzeta)V:=Q>Y^Z
Se debe verificar el tipo de expresiones y asignaciones : por ejemplo,
Las reglas anteriores distinguen entre <expresión aritmética> y <expresión booleana>, pero no pueden verificar que la misma variable siempre tenga el mismo tipo.
Este requisito (no libre de contexto) se puede expresar en una gramática W anotando las reglas con atributos que registren, para cada variable utilizada o asignada, su nombre y tipo.
Este registro luego se puede llevar a todos los lugares de la gramática donde los tipos deben coincidir e implementar la verificación de tipos.
De manera similar, se puede utilizar para verificar la inicialización de variables antes de su uso, etc.
Uno podría preguntarse cómo crear y manipular dicha estructura de datos sin un apoyo explícito en el formalismo de las estructuras de datos y las operaciones sobre ellas. Se puede hacer usando la metagramática para definir una representación de cadena para la estructura de datos y usando la coincidencia de patrones para definir operaciones:
<parte izquierda con <TIPO> <NOMBRE>> ::= <variable con <TIPO> <NOMBRE>> := | <identificador de procedimiento con <TIPO> <NOMBRE>> :=<lista de partes izquierda <TYPEMAP1>> ::= <parte izquierda con <TIPO> <NOMBRE>> <donde <TYPEMAP1> es <TYPED> <NOMBRE> agregado al <VACÍO> ordenado | <lista de partes izquierda <TYPEMAP2>> <parte izquierda con <TIPO> <NOMBRE>> <donde <TYPEMAP1> es <TYPED> <NOMBRE> agregado al <TYPEMAP2> ordenado<declaración de asignación <ASIGNADO A> <USADO>> ::= <lista de partes izquierda <ASIGNADO A>> <expresión aritmética <USADO>> | <lista de partes izquierda <ASIGNADO A>> <Expresión booleana <USADO>><donde <TIPO> <NOMBRE> es <TIPO> <NOMBRE> agregado al <VACÍO> ordenado ::=<donde <TYPEMAP1> es <TYPED1> <NAME1> agregado al <TYPEMAP2> ordenado ::= <donde <TYPEMAP2> es <TYPED2> <NAME2> agregado al <TYPEMAP3> ordenado <donde <NOMBRE1> está lexicográficamente antes de <NOMBRE2>><donde <TYPEMAP1> es <TYPED1> <NAME1> agregado al <TYPEMAP2> ordenado ::= <donde <TYPEMAP2> es <TYPED2> <NAME2> agregado al <TYPEMAP3> ordenado <donde <NOMBRE2> está lexicográficamente antes de <NOMBRE1>> <donde <TYPEMAP3> es <TYPED1> <NAME1> agregado al <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 a+ <LETRA O DÍGITO 2> ::= <donde <LETRA O DÍGITO 1> precede a+ <LETRA O DÍGITO 3> <donde <LETRA O DÍGITO 3> precede a+ <LETRA O DÍGITO 2><donde a precede a b> :==<donde b precede a c> :==[...]<TIPO> ::== 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 | segundo | c | [...]<DÍGITO> ::== 0 | 1 | 2 | [...]<NOMBRES1> ::== <NOMBRES><NOMBRES2> ::== <NOMBRES><ASIGNADO A> ::== <NOMBRES><USADOS> ::== <NOMBRES><NOMBRES> ::== <NOMBRE> | <NOMBRE> <NOMBRES><VACÍO> ::==<MAPA DE TIPO> ::== (<MAPA DE TIPO> <NOMBRE>) <MAPA DE TIPO><MAPA DE TIPO1> ::== <MAPA DE TIPO><MAPA DE TIPO2> ::== <MAPA DE TIPO><MAPA DE TIPO3> ::== <MAPA DE TIPO>
En comparación con la gramática original, se han agregado tres elementos nuevos:
Las nuevas hiperreglas son reglas: solo generan la cadena vacía.
Los informes ALGOL 68 utilizan una notación ligeramente diferente sin <corchetes angulares>.
a) programa: símbolo abierto, preludio estándar, opción de preludio de biblioteca, programa particular, salida, 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 biblioteca: declaración de secuencia de preludio. 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, símbolo de etiqueta. f) postludio de biblioteca: interludio de declaración. g) postludio estándar: tren de cláusula de nulidad fuerte
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: token de inicio de ESTILO, nuevos preludios de CAPA1, token paralelo, nuevo PAQUETE de tareas LAYER1, Token de fin de ESTILO. b) Preludios de NEST1: preludio estándar de 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: Serie NEST1 de fuerte vacío con DECSETY1, continúa con el 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 con vacío fuerte. f) Tarea de usuario NEST1: preludio particular de NEST2 con DECS, PACK de programa particular NEST2, vaya en token, Postludio particular de NEST2, donde (NEST2) es (NEST1 nuevo DECS STOP). g) programa particular NEST2: NEST2 nueva definición de etiqueta unida a LABSETY3 de LABSETY3, fuerte vacío NEST2 nuevo LABSETY3 Cláusula CERRADA. h) Definición de etiqueta unida a 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: token de inicio de ESTILO, nuevos preludios de CAPA1, token paralelo, nuevo PAQUETE de tareas LAYER1, Token de fin de ESTILO.
Esto permite BEGIN... END y { } como delimitadores de bloque, mientras descarta BEGIN... } y {... END.
Es posible que desee comparar la gramática del informe con el analizador Yacc para un subconjunto de ALGOL 68 de Marc van Leeuwen. [11]
Anthony Fisher escribió yo-yo , [12] un analizador para una gran clase de gramáticas W, con gramáticas de ejemplo para expresiones , eva , sal y Pascal (el estándar ISO 7185 real para Pascal usa 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]
Las aplicaciones de las gramáticas de afijos extendidas (EAG) mencionadas anteriormente pueden considerarse efectivamente aplicaciones de gramáticas W, ya que las EAG están muy cerca de 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 necesaria ]
También se ha proporcionado una descripción W-Grammar para Ada . [15]
