Tema 1 - Lexicogràfic (2017)

Resumen Catalán
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Ingeniería Informática - 3º curso
Asignatura Compiladors
Año del apunte 2017
Páginas 6
Fecha de subida 14/09/2017
Descargas 0
Subido por

Vista previa del texto

Compiladors Curs 2016-2017 Pau Acedo Tema 1 – Anàlisi lexicogràfic Programa font (seqüència de caràcters) Scanner (Autòmat fini determinista o específic) Seqüència de Símbols Scanner: Troba les paraules i les separa, determina la importància dels símbols.
Símbols (tokens o paraules del llenguatge): Conjunt de caràcters (string) del programa font amb significat propi (són reservats). Descripció formal: Expressions regulars  Identificador: Una lletra seguida de lletres o números. A1, dff, ...
o Atribut nom: seqüència de l’identificador en majúscules: “A”, “B1”, “C3D”  Número: Seqüència de dígits que pot començar amb el signe menys i pot tenir un punt o Atribut valor: double amb el valor numèric (enter o real)  Punt i coma. “;”  Paraula clau if. “if”, “iF”, “If”, “IF”  Fi de fitxer: “#” Separadors entre símbols: No formen part de la seqüència de símbols. Comentaris, salts de línia, espais, tabuladors Expressions regulars -: El més simple és el conjunt buit -: Conjunt que conté un element, el conjunt buit -S: Expressió que representa conjunt que només conté s -V: És el conjunt de tots els caràcters (vocabulari) 1 Compiladors Curs 2016-2017 Pau Acedo Exemples: -dígit d=0|1|2|3 -sencer_sense_signe=d+ -sencer =(+|-| )d+ - real=(+|-|)d+.d+(|e(+|-|) d+) -lletra l=a|...|z|A|...|Z -identificador = 10l(l|d)* -string= “ “ ” (V-“ ” ” )* “ ” ” Resultat: 10, 30, 1, 999 Ens permet posar signe: +30, -30, 30 Número real: -30 45 e15 Resultat: Qualsevol lletra “Casa” , Problema: “Casa”Hola” -comentari = /* (V*-( V* */ V*)) */ Comença amb barra /, vocabulari repetit n vegades, acaba amb barra / S’ha de treure qualsevol seqüència de caràcters amb * / (*/a, a*/, */) Autòmats Finits -Autòmat finit determinista AFD. Més fàcil d’executar. Només podem estar en un estat a la vegada.
-Autòmat finit no determinista AFND: Quan llegeixo un caràcter no vaig a un únic estat, sinó a múltiples (podem estar en més d’un estat al mateix temps). Es pot passar de determinista a No determinista.
Expressions regulars AFND AFD Modificació Scanner 2 Compiladors Curs 2016-2017 Pau Acedo Crear AFND a partir d’Expressió regular. Exemple: Pas d’AFND a AFD 1.Conjunt d’estats del nou AFD és el conjunt de les parts del conjunt d’estats del AFND 2.L’estat inicial de l’AFD és el mateix que el de l’AFND 3.Un estat de l’AFD és final si conté algun estat final de l’AFND 4. Càlcul del conjunt de transicions 4.1. Estat inicial al conjunt d’estats K de l’AFD. Conjunt de transicions M =  4.2. Repetir fins que K i M no varien. Per a cada estat de K i caràcter d’entrada aplicar les transicions possibles de AFND i acumular en K i M el nou estat i la nova transició.
3 Compiladors Curs 2016-2017 Pau Acedo Taula de transició AFND Inicial S (transició 1 A 2 B 4 C AFD I 1 2,4 2,4 4 S A C B C Final {2,4} {3} {4} F 2,4 4 3 4 Taula de transicions 0 1 2 3 a 2,4 (1) E E E 1 2,4 3 4 b E 3 (2) E E c E 4 (3) E 4 (3) El Scanner no és un AFD: -El AFD llegeix fins que arriva a final de seqüència o error -El Scanner llegeix un símbol sebse arribar al final de seqüència “+” “*” “[“ “{“ -> Un o més d’un -> Zero o varis -> 0 o 1 -> 0 o n vegades 4 Compiladors Curs 2016-2017 Pau Acedo EXERCICIS    Expressions regulars Autòmates finits deterministes / no deterministes Scanner 1. Representa els comentaris en C /*...*/ (V és qualsevol caràcter d’entrada) /* V* */ Com V engloba tot el vocabulari hem de restringir l’expressió “*/” /* Entrada comentari V* - (V* */ V*) Tot V menys tot el V seguit de */ seguit de V */ Tancament comentari 2. Donat un autòmat de Scanner que llegeix el símbol do i el símbol downto. Quantes crides ha de fer el Scanner per llegir dodownto# i quins caràcter llegeix en cada crida.
Si inclouen # dins de l’autòmat haurem de considerar una crida més.
La segona crida comença a llegir a partir de l’últim estat final .
Entrada: dodownto# Crida Caràcters llegits 1 dod 2 downto# Retorna a l’entrada do downto Entrada: dowo Crida Caràcters llegits 1 dowo 2 w 3 o Retorna a l’entrada do RES RES 3. Donades les següents definicions de símbol i separador Entrada: =====># Crida Símbols llegits 1 === 2 === 3 === 4 ==> 5 # Retorna a l’entrada = = = ==> # 5 Compiladors Curs 2016-2017 Pau Acedo 4. Automata finit determinista Entrada: fora# Crida Símbols llegits 1 Fora# 2 # Retorna a l’entrada fora RES 6 ...

Comprar Previsualizar