Hispanopedia WikiEn informática , una gramática de Van Wijngaarden (también conocida como gramática vW o gramática W [ 1 ] ) es un formalismo para definir lenguajes formales . Su 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 destacada.
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 "The birds was eating" no es inglés estándar porque no concuerda en número . Una gramática libre de contexto analizaría "The birds was eating", "The birds were eating" y "The bird was eating" 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 ]
Dos niveles
Las gramáticas W son gramáticas de dos niveles : se definen mediante un par de gramáticas que operan en diferentes niveles:
- La hipergramática es una gramática de atributos , es decir, un conjunto de reglas gramaticales libres de contexto en las que los no terminales pueden tener atributos; y
- La metagramática es una gramática libre de contexto que define los posibles valores para estos atributos.
El conjunto de cadenas generadas por una gramática W se define mediante un proceso de dos etapas:
- 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 maneras posibles;
- Utilice la gramática libre de contexto resultante (posiblemente infinita) para generar cadenas de la forma habitual.
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ñaló Alain Colmerauer .
Las gramáticas W son Turing completas ; [ 5 ] por lo tanto, todos los problemas de decisión relacionados con los lenguajes que generan, como
- si una gramática W genera una cadena dada
- si una gramática W no genera ninguna cadena
son indecidibles .
Se desarrollaron variantes abreviadas, 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, los programas lógicos que no utilizan 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 computadoras al reconocimiento, la interpretación y la traducción de lenguas 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. Para este propósito, se adoptaron las gramáticas libres de contexto, un concepto de la lingüística estructural ; sus reglas pueden expresar cómo se construyen recursivamente las oraciones a partir de partes de la oración , como sintagmas nominales y verbales , y, en última instancia, palabras, como sustantivos , verbos y pronombres .
Este trabajo influyó en el diseño e implementación de lenguajes de programación , sobre todo 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 coincidir entre sí de alguna manera.
Estas se pueden expresar fácilmente en gramáticas W. (Véase el ejemplo a continuación).
Los lenguajes de programación tienen las nociones análogas de tipado y ámbito . Un compilador o intérprete del lenguaje debe reconocer qué usos de una variable pertenecen juntos (se refieren a la misma variable). Esto suele estar sujeto a restricciones tales como:
- Una variable debe inicializarse antes de utilizar su valor.
- En los lenguajes fuertemente tipados, a cada variable se le asigna un tipo, y todos los usos de la variable deben respetar dicho tipo.
- A menudo, su tipo debe declararse explícitamente antes de su uso.
Las gramáticas W se basan en la idea de dotar a los símbolos no terminales de las gramáticas libres de contexto con atributos (o afijos ) que transmiten información entre los nodos del árbol de análisis sintáctico , utilizados para restringir la sintaxis y especificar la semántica.
Esta idea era bien conocida en aquel entonces; 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 ]
Al aumentar la descripción de la sintaxis con atributos, se pueden verificar restricciones como las anteriores, descartando muchos programas inválidos en tiempo de compilación. Como escribió Van Wijngaarden en su prefacio: [ 2 ]
Mis principales objeciones eran, sin duda, las restricciones innecesarias y la definición de la sintaxis y la semántica. De hecho, 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 de Backus podrían ser ventajosas [...]. Desarrollé un esquema [...] que permite diseñar un lenguaje para que contenga mucha más información en la sintaxis de la que normalmente se contiene.
Una característica peculiar de las gramáticas W era su estricto tratamiento de los atributos como cadenas de caracteres, definidas por una gramática libre de 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 a continuación).
Tras su introducción en el "Informe Final" de ALGOL 68 de 1968 , las gramáticas W fueron consideradas por muchos como demasiado potentes y sin restricciones para ser prácticas.
Esto fue en parte consecuencia de la forma en que se habían aplicado; el "Informe revisado" de 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 demasiado poderosas para propósitos prácticos como servir de 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 el análisis sintáctico o la traducción automáticos. Se desarrollaron variantes restringidas y modificadas de las gramáticas W para abordar este problema, por ejemplo:
- Gramáticas de afijos extendidas (EAG, por sus siglas en inglés), aplicadas para describir las gramáticas de lenguas naturales como el inglés y el español);
- Sistemas Q , también aplicados al procesamiento del lenguaje natural;
- la serie de lenguajes CDL , aplicados como lenguajes de construcción de compiladores para lenguajes de programación .
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 sujeto , verbo principal y pronombres que se refieren al sujeto:
- Me lavo.
- Ella se lava.
- Nos lavamos.
son oraciones válidas; las oraciones inválidas son, por ejemplo:
- *Nos lavamos.
- *Ella se lavó.
- *Nos lavamos.
En este caso, 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 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 lavo Me lavo Me lavo [...] Ellos se lavan Ellos se 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.º> ::= 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 plural < GÉNERO > 3.º> ::= Ellos < verbo singular 1.º > ::= lavar < verbo singular 2.º > ::= lavar < verbo singular 3.º > ::= lavar <verbo plural < PERSONA > > ::= lavar <objeto singular < GÉNERO > 1.º> ::= yo mismo <objeto singular < GÉNERO > 2.º> ::= 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 > ::= = 1.º | 2.º | 3.º Un lenguaje estándar no libre de contexto
Un lenguaje no libre de contexto bien 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
Requerir el uso válido de variables en ALGOL
El Informe Revisado sobre el Lenguaje Algorítmico Algol 60 [ 10 ] define una sintaxis libre de contexto completa para el lenguaje.
Las asignaciones se definen de la siguiente manera (sección 4.2.1):
< parte izquierda > :: = <variable> : = | < identificador de procedimiento > := < lista de partes izquierdas > ::= < parte izquierda > | < lista de partes izquierdas > < parte izquierda >< instrucción de asignación > ::= < lista de partes izquierdas > < expresión aritmética > | < lista de partes izquierdas > < 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+s n:=n+1 A:=B/Cvq×S S[v,k+2]:=3-arctan(sTIMESzeta) V:=Q>Y^Z
Las expresiones y las asignaciones deben ser verificadas en cuanto a su tipo : por ejemplo,
- en
n:=n+1, n debe ser un número (entero o real); - En este caso
A:=B/C-v-q×S, todas las variables deben ser números; - En
V:=Q>Y^Z, todas las variables deben ser de tipo booleano.
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 (que no depende del contexto) puede expresarse en una gramática W anotando las reglas con atributos que registren, para cada variable utilizada o asignada, su nombre y tipo.
Este registro se puede luego llevar a todos los lugares de la gramática donde sea necesario hacer coincidir los tipos e implementar la verificación de tipos.
De forma similar, puede utilizarse para comprobar la inicialización de variables antes de su uso, etcétera.
Cabe preguntarse cómo crear y manipular una estructura de datos de este tipo sin un soporte explícito en el formalismo para estructuras de datos y operaciones sobre ellas. Esto se puede lograr utilizando la metagramática para definir una representación en cadena para la estructura de datos y utilizando la coincidencia de patrones para definir las operaciones.
<parte izquierda con < TYPED > < NAME > > ::= <variable con < TYPED > < NAME > > := | <identificador de procedimiento con < TIPO > < NOMBRE > > := <lista de la parte izquierda < TYPEMAP1 > > ::= <parte izquierda con < TYPED > < NAME > > <donde < TYPEMAP1 > se agrega < TYPED > < NAME > a < EMPTY > ordenado > | <lista de la parte izquierda < TYPEMAP2 > > <parte izquierda con < ESCRITO > < NOMBRE > > <donde < TYPEMAP1 > se agrega < TYPED > < NAME > al < TYPEMAP2 > ordenado > <sentencia de asignación < ASIGNADO A > < USADO > > ::= <lista de partes izquierdas < ASIGNADO A > > <expresión aritmética < USADO > > | <lista de la parte izquierda < ASIGNADO A > > <expresión booleana < UTILIZADO > > <donde < TYPED > < NAME > se agrega a < TYPED > < NAME > ordenado < EMPTY > > ::= <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 que < 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 que < 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 que < 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 > :== [...] < 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 > < USADO > ::= = < NOMBRES > < NOMBRES > ::= = < NOMBRE > | < NOMBRE > < NOMBRES >< VACÍO > ::= = < MAPA DE TIPO > ::= = ( < ESCRITO > < 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 añadido tres elementos nuevos:
- atributos a los no terminales en lo que ahora son las hiperreglas;
- metarreglas para especificar los valores permitidos para los atributos;
- Nuevas hiperreglas para especificar operaciones sobre los valores de los atributos.
Las nuevas hiperreglas son reglas ε : solo generan la cadena vacía.
ALGOL 68 ejemplos
Los informes de 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 en 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 en particular: Opción de secuencia de etiquetas, cláusula de vacío CERRADA fuerte. e) salida: continuar símbolo, letra e letra x letra i letra t, símbolo de etiqueta. f) Postludio de la biblioteca: interludio de la declaración. g) Postludio estándar: cadena de cláusulas de nulidad fuerte
ALGOL 68 como en el Informe Revisado de 1973 §2.2.1, §10.1.1
programa: cláusula cerrada nueva de vacío fuerte A) EXTERNO :: estándar ; biblioteca ; sistema ; particular. B) ALTO :: etiqueta letra s letra t letra o letra p. a) texto del programa: STYLE begin token, new LAYER1 preludes, token paralelo, nuevo PAQUETE de tareas de CAPA1, Token de fin de ESTILO. b) Preludios NEST1: Preludio estándar NEST1 con DECS1, Preludio de la biblioteca NEST1 con DECSETY2, Sistema NEST1 preludio con DECSETY3, donde (NEST1) es (nuevo VACÍO nuevo DECS1 DECSETY2 DECSETY3). c) Preludio externo NEST1 con DECSETY1: fuerte vacío NEST1 serie con DECSETY1, ir en token; donde (DECSETY1) es (VACÍO), VACÍO. d) Tareas de NEST1: Lista de tareas del sistema NEST1 y también token, Lista de paquetes de tareas del usuario NEST1. e) Tarea del sistema NEST1: anular fuertemente la unidad NEST1. f) Tarea de usuario NEST1: Preludio particular de NEST2 con DECS, NEST2 programa particular PACK, ir en token, NEST2 postludio particular, donde (NEST2) es (NEST1 nuevo DECS STOP). g) Programa particular de NEST2: Definición de etiqueta NEST2 nueva LABSETY3 unida de LABSETY3, fuerte vacío NEST2 nuevo LABSETY3 Cláusula adjunta. h) Definición de etiqueta unida de 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 con fuerte vacío y STOP.Un ejemplo sencillo del poder de las gramáticas W es la cláusula
a) texto del programa: STYLE begin token, new LAYER1 preludes, token paralelo, nuevo PAQUETE de tareas de CAPA1, Token de fin de ESTILO.
Esto permite BEGIN ... END y { } como delimitadores de bloque, mientras que descarta BEGIN ... } y { ... END .
Se podría 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 de 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 afijas extendidas (EAG) mencionadas anteriormente pueden considerarse efectivamente como aplicaciones de las gramáticas W, ya que las EAG 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 .
También se ha proporcionado una descripción de la gramática W para Ada . [ 15 ]
Véase también
Referencias
- ↑ Cleaveland, J. Craig; Uzgalis, Robert C. (1977). Gramáticas para lenguajes de programación . Elsevier. ISBN 978-0-444-00199-3.
- 1 2 van Wijngaarden, Adriaan (1972-04-04) [Edición preliminar y prematura 1965-10-22]. MR 76: Diseño ortogonal y descripción de un lenguaje formal (PDF) (Informe técnico). Ámsterdam: CWI . Archivado del original (PDF) el 2 de octubre de 2017.
- ↑ van Wijngaarden, A.; et al. (eds.). "Informe revisado sobre el lenguaje algorítmico ALGOL 68" . Archivado del original el 24 de enero de 2002.
- ↑ 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 . Lecture Notes in Computer Science. Vol. 1181. Berlín: Springer. pp. 55–67 . doi : 10.1007/3-540-62064-8_6 . ISBN 978-3-540-62064-8.
- ^ 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 .
- ↑ Deransart, Pierre; Maluszynski, Jan (1993), "Extensiones gramaticales de programas lógicos" , Una visión gramatical de la programación lógica , The MIT Press, pp. 109–140 , doi : 10.7551/mitpress/3345.003.0008 , ISBN 9780262290845, consultado el 14 de junio de 2023
{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace ) - ↑ 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.
- ^ 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 .
- ↑ Augusto, LM (2023). "Gramáticas de dos niveles: algunas propiedades interesantes de las gramáticas de van Wijngaarden" (PDF) . Omega - Journal of Formal Languages . 1 : 3–34 .
- ↑ 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 .
- ↑ "Sintaxis", Algol 68 , FR : Univ Poitiers
- ↑ Fisher, Anthony (30 de julio de 2024), "yo-yo", Software , Reino Unido : York.
- ↑ Grune, Dick, Generador de oraciones de dos niveles , NL : VU.
- ^ 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.
- ↑ Flowers, Roy, Descripción de una gramática W para Ada (PDF) (Tesis de maestría), Instituto de Tecnología de la Fuerza Aérea, Universidad del Aire
Lecturas adicionales
- Augusto, LM (2023). "Las gramáticas de van Wijngaarden: una introducción a la sintaxis con restricciones decidibles" (PDF) . Journal of Knowledge Structures and Systems . 4 : 1–39 .
- Augusto, LM (2024). "Un poco de revuelo por el significado: la semántica intrínseca de las gramáticas de van Wijngaarden" (PDF) . Journal of Knowledge Structures and Systems . 5 : 1–42 .
- Pemberton, Steven (2016) [1982]. "Definición semántica ejecutable de lenguajes de programación utilizando gramáticas de dos niveles (gramáticas de Van Wijngaarden)" . Ámsterdam: Centrum Wiskunde & Informatica..
- Petersson, Kent (1990). "Sintaxis y semántica de los lenguajes de programación" (PDF) . Borrador de apuntes de clase . Archivado del original (PDF) el 5 de junio de 2001.
- Lenguajes formales
- Análisis sintáctico
- Construcción de compiladores
- Inventos holandeses