Download Parte 1 - Lenguajes de Programación

Lenguajes de Programación
Generación de código ejecutable - Parte I
Manuel Soto Romero
Universidad Nacional Autónoma de México
Facultad de Ciencias
3 de marzo de 2017
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
1 / 12
Análisis para obtener código ejecutable
Para obtener código ejecutable dado un código fuente, pasamos por
distintos análisis:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
2 / 12
Análisis para obtener código ejecutable
Para obtener código ejecutable dado un código fuente, pasamos por
distintos análisis:
I
Análisis léxico
I
Análisis sintáctico
I
Análisis semántico
I
Optimizaciones
En esta sesión revisaremos el análisis léxico y sintáctico
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
2 / 12
Sintaxis concreta
Nos referimos con sintaxis concreta a cómo se escriben las
expresiones de un determinado lenguaje.
Lo usual es describir estas reglas usando EBNF:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
3 / 12
Sintaxis concreta
Nos referimos con sintaxis concreta a cómo se escriben las
expresiones de un determinado lenguaje.
Lo usual es describir estas reglas usando EBNF:
Lenguaje WAE
<expr> := <id>
| <num>
| {<binop> <expr> <expr>}
| {with {<id> <expr>} <expr>}
<id> := a | b | c | ...
<num> := 1 | 2 | 3 | ...
<binop> := + | - | * | /
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
3 / 12
Análisis léxico
Una expresión en sintaxis concreta, es realmente una cadena. El
primer análisis por el que pasa un código consiste en tomar una
cadena y separarla en lexemas.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
4 / 12
Análisis léxico
Una expresión en sintaxis concreta, es realmente una cadena. El
primer análisis por el que pasa un código consiste en tomar una
cadena y separarla en lexemas.
Por ejemplo, en la expresión:
a = a + b
Los lexemas son: a, =, a, + y b.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
4 / 12
Análisis léxico
Una expresión en sintaxis concreta, es realmente una cadena. El
primer análisis por el que pasa un código consiste en tomar una
cadena y separarla en lexemas.
Por ejemplo, en la expresión:
a = a + b
Los lexemas son: a, =, a, + y b.
Analizadores léxicos más avanzados regresan parejas de la forma
(tipo, valor).
[(id,a),(asig,=),(id,a),(op,+),(id,b)]
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
4 / 12
Notación quote
Para ahorrarnos el trabajo de obtener los átomos de una expresión,
hacemos uso de una primitiva típica de los descendientes de Lisp
llamada quote.
Esta notación permite escribir expresiones complejas, evitando que el
intérprete las evalúe, lo que permite trabajar con ellas como si fueran
símbolos o listas.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
5 / 12
Notación quote
Para ahorrarnos el trabajo de obtener los átomos de una expresión,
hacemos uso de una primitiva típica de los descendientes de Lisp
llamada quote.
Esta notación permite escribir expresiones complejas, evitando que el
intérprete las evalúe, lo que permite trabajar con ellas como si fueran
símbolos o listas.
Tómalo literal, no lo interpretes
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
5 / 12
Ejemplo
En la frase
El perro del ayudante
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
6 / 12
Ejemplo
En la frase
El perro del ayudante
Si usamos quote:
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
6 / 12
Ejemplo
En la frase
El perro del ayudante
Si usamos quote:
¡Tómalo literal!
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
6 / 12
Ejemplo
En la frase
El perro del ayudante
Si usamos quote:
¡Tómalo literal!
Manuel Soto Romero (UNAM)
¡No lo interpretes!
Lenguajes de Programación
3 de marzo de 2017
6 / 12
Ejemplo (serio)
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
7 / 12
Ejemplo (serio)
Si tenemos la expresión {+ 17 29}
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
7 / 12
Ejemplo (serio)
Si tenemos la expresión {+ 17 29}
Sin quote:
46
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
7 / 12
Ejemplo (serio)
Si tenemos la expresión {+ 17 29}
Sin quote:
46
Con quote:
’{
Manuel Soto Romero (UNAM)
+
17
29
first
second
third
Lenguajes de Programación
}
3 de marzo de 2017
7 / 12
Ejemplo (serio)
Si tenemos la expresión {+ 17 29}
Sin quote:
46
Con quote:
’{
+
17
29
first
second
third
}
Nos regresa una lista que incluye todos los lexemas de la expresión. Si
tuvieramos una expresión con sólo un lexema, nos regresa un símbolo.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
7 / 12
Ejemplo (serio)
Si tenemos la expresión {+ 17 29}
Sin quote:
46
Con quote:
’{
+
17
29
first
second
third
}
Nos regresa una lista que incluye todos los lexemas de la expresión. Si
tuvieramos una expresión con sólo un lexema, nos regresa un símbolo.
La primitiva read toma expresiones ingresadas por el usuario y les
aplica automáticamente quote.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
7 / 12
Análisis sintáctico
La fase de análisis sintáctico, consiste en, a partir de las expresiones
devueltas por el analizador léxico construir el árbol de sintaxis
abstracta correspondiente.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
8 / 12
Análisis sintáctico
La fase de análisis sintáctico, consiste en, a partir de las expresiones
devueltas por el analizador léxico construir el árbol de sintaxis
abstracta correspondiente.
¿Por qué no trabajamos directamente con la sintaxis concreta del
lenguaje?
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
8 / 12
Análisis sintáctico
La fase de análisis sintáctico, consiste en, a partir de las expresiones
devueltas por el analizador léxico construir el árbol de sintaxis
abstracta correspondiente.
¿Por qué no trabajamos directamente con la sintaxis concreta del
lenguaje?
Sintaxis concreta:
+ 2 3
2 + 3
2 3 +
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
8 / 12
Análisis sintáctico
La fase de análisis sintáctico, consiste en, a partir de las expresiones
devueltas por el analizador léxico construir el árbol de sintaxis
abstracta correspondiente.
¿Por qué no trabajamos directamente con la sintaxis concreta del
lenguaje?
Sintaxis concreta:
+ 2 3
2 + 3
2 3 +
Sintaxis abstracta:
(add (num 2) (num 3))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
8 / 12
WAE en sintaxis abstracta
(define-type WAE
[id (i symbol?)]
[num (n number?)]
[binop (f procedure?) (l WAE?) (r WAE?)]
[with (name symbol?) (named-expr WAE?) (body WAE?)])
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
9 / 12
WAE en sintaxis abstracta
(define-type WAE
[id (i symbol?)]
[num (n number?)]
[binop (f procedure?) (l WAE?) (r WAE?)]
[with (name symbol?) (named-expr WAE?) (body WAE?)])
Este TDA nos permite definir el árbol de sintaxis abstracta, en forma
de lista.
Por ejemplo, para representar el árbol de {+ 17 29} tenemos
(binop + (num 17) (num 29)). Un árbol ternario en este caso.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
9 / 12
La función parse
(define (parse sexp)
...)
Esta función toma el valor regresado por el analizador léxico y
construye el árbol de sintaxis abstracta.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
10 / 12
La función parse
(define (parse sexp)
...)
Esta función toma el valor regresado por el analizador léxico y
construye el árbol de sintaxis abstracta.
I
La conversión de números e identificadores es trivial pues quote
regresa simplemente un número o símbolo en estos casos.
I
Para convertir operaciones binarias y asignaciones locales,
tenemos que procesar la lista, usando las primitivas car y cdr.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
10 / 12
La función parse
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
11 / 12
La función parse
(define (parse sexp)
(cond
[(symbol? sexp) (id sexp)]
[(number? sexp) (num sexp)]
[(list? sexp)
(case (car sexp)
[(+) ...]
[(with) ...])]))
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
11 / 12
Ejercicios
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
12 / 12
Ejercicios
Los ejercicios se encuentran en
http://lenguajesfc.com/laboratorio.html
Sólo pueden entregar aquellos alumnos que aparezcan en la lista
de asistencia de la sesión. No es válido apuntar a miembros del
equipo que no estén presentes.
Manuel Soto Romero (UNAM)
Lenguajes de Programación
3 de marzo de 2017
12 / 12