Alfabeto: un conjunto finito no vacío A.
Letra: un elemento de un alfabeto.
Palabra: una sucesión de letras.
Longitud de una palabra: |x| = número de letras.
Palabra vacía: palabra de longitud 0.
Universo del discurso o lenguaje universal: conjunto de todas las palabras sobre un alfabeto. Conjunto infinito, numerable, W(A).
Concatenación de palabras. Propiedades (cerrada sobre W(A), asociativa, elemento neutro, monoide libre no abeliano, |xy|=|x|+|y|.
Cabeza y cola de una palabra.
Potencia de una palabra: |x*i|=i.|x|.
Reflexión de palabras: |x*-1|=|x|.
Lenguaje: L c W(A).
Unión de lenguajes: cerrada, asociativa, elemento neutro, conmutativa, idempotente.
Concatenación de lenguajes: cerrada, asociativa, elemento neutro.
Binoide libre.
Potencia de un lenguaje. Clausura positiva. Iteración o cierre.
Reflexión, intersección, complementación.
G = (At, An, S, P)
Producción: (x,y) representado x::=y.
Derivación directa mediante x::=y : v=>w <=> existen z,u v=zxu, w=zyu.
Derivación: v =>+ w.
Relación de Thue: v =>* w.
Notación de Backus.
Forma sentencial de G: S =>* x.
Sentencia (instrucción) de G: S =>* x y x está en At*.
Lenguaje asociado a G: { x | S =>* x }.
Frase de una forma sentencial: S =>* xUy, U =>+ u.
Frase simple de una forma sentencial: S =>* xUy, U => u.
Asidero: frase simple más a la izquierda.
Recursividad de una gramática: uUv =>+ xUy.
Recursividad de una regla: uUv ::= xUy.
Recursividad a izquierdas y a derechas.
Clasificación de Chomsky y de los lenguajes. Máquinas. Equivalencias.
Arbol de derivación. Subárbol.
Ambigüedad de sentencias, gramáticas, lenguajes
Todos representables mediante gramáticas independientes del contexto, excepto dos:
Juan vio a Luis dejar que María ayudara a Pedro a hacer que Felipe trabajara.
Juan Luis María Pedro Felipe vio dejar ayudar hacer trabajar.
Algunos verbos exigen acusativo, otros dativo. Supongamos que los acusativos fueran primero, después los dativos: tenemos palabras de la forma
A*n.B*m.C*n.D*m
donde A = frase nominal en acusativo, B = frase nominal en dativo, C = verbo que exige acusativo, D = verbo que exige dativo.
Este lenguaje no es independiente del contexto.
Generaciones de lenguajes
1. FORTRAN
| COBOL
ALGOL 60 --------|
--------|-----------------------------------------------------------------
| | | || | | |
BASIC ALGOL 68 Pascal PL/I | SIMULA BCPL
------------------ ----------|--------|--------|------------- |
|---|-----|------|---| | | | | |
CLU | Modula | | | Smalltalk 72 | C
| | | | -----|------------|---|---------
Ada | | | | Smalltalk 80 |---|--------|
Object Pascal | | | |----------------| |
| |Eiffel Smalltalk V Objective C C++
|--------|----------------------------------|
| |
OOPL/I OOCOBOL
2. LISP
---------------------------
| | | |
LOOPS Plasma INTERLISP Scheme
APL SNOBOL BLISS FORTH Rexx
--------------------------- | |
| | | | |
Mathematica APL2 J SL5 OORexx
1980
COBOL 47.3%
RPG 14.8%
FORTRAN 8.9%
Simbólicos 8.4%
BASIC 5.4%
PL/I 4.8%
Pascal 1.2%
Otros 8.9%
Símbolos.
Técnica del Bootstraping.
-------------------
| A B |
|------- -------|
| C |
|---|
-----
| A |
| |
| C |
|---|
-------------------
| A B |
|------- -------|
| C | -----
|---| | B |
| |
| C |
|---|
----- ----------- -------------------
|L | | | | A B |
| A | | | |------- -------|
..... | | | C |
|---------| |---|
-------------------------------------------
| ------------ ------------ ------------ |
| |A.Morfo. | |A.Semán. | |Optimiza. | |
| |----------| |----------| |----------| |
/------- | ------------------------- ------------ | /-------
|Fuente|-|--|A.Sintáctico |-|G.Código |-|-|Objeto|
|------| | |-----------------------| |----------| | |------|
| -------------------------------------- |
| |Tablas de Información | |
| |------------------------------------| |
|-----------------------------------------|
En los compiladores de un solo paso suele fundirse el analizador semántico con el generador de código.
-------------------------------------------
| ------------ ------------ |
| |A.Morfo. | |A.Semán. | |
| |----------| |----------| |
/------- | ------------------------- ------------ |
|Fuente|--|--|A.Sintáctico |-|E.Código | |
|------| | |-----------------------| |----------| |
| -------------------------------------- |
| |Tablas de Información | |
| |------------------------------------| |
|-----------------------------------------|
Analizador lexical, preprocesador, "scanner".
Genera una unidad sintáctica o un vector de unidades sintácticas.
Realiza la primera fase de la reducción al axioma de la gramática.
Elimina espacios en blanco y comentarios.
Lenguaje regular.
Unidades sintácticas:
Detección de errores morfológicos:
"Parser".
Gobierna todo el proceso.
Utiliza los demás como subrutinas.
Realiza el resto de la reducción al axioma de la gramática para comprobar que la instrucción en cuestión es correcta.
Lenguaje independiente del contexto.
Comprueba la corrección semántica de la instrucción.
Ejemplo: compatibilidad de tipo de las variables en una expresión.
Almacena información semántica en las tablas.
Traduce el programa fuente al lenguaje objeto.