p. 1

procesadores de lenguajes ingeniería técnica superior de ingeniería informática departamento de lenguajes y sistemas informáticos análisis léxico formalización y desarrollo javier vélez reyes jvelez@lsi.uned.es departamento de lenguajes y sistemas informáticos uned

[close]

p. 2

análisis léxico formalización y desarrollo objetivos objetivos conocer las responsabilidades de un analizador léxico aprender cómo funciona entender los diferentes tipos de patrones que reconoce aprender a especificar formalmente analizadores léxicos a través de gramáticas formales a través de expresiones regulares a través de autómatas finitos estudiar la implementación de analizadores léxicos conocer las distintas estrategias de implementación entender las posibles relaciones con la tabla de símbolos estudiar la generación de errores léxicos javier vélez reyes jvelez@lsi.uned.es

[close]

p. 3

análisis léxico formalización y desarrollo Índice Índice introducción token patrón léxico lexema lenguaje regular dirigida por tabla guiada por herramientas estrategias de implementación gestión de errores construcción de a léxicos en en la práctica ¿qué es jflex ¿cómo funciona jflex ¿cómo se usa jflex gestión de errores en jflex desarrollo paso a paso especificación de analizadores léxicos lenguajes regulares gramáticas lineales expresiones regulares autómatas finitos conversión de formalismos bibliografía implementación de analizadores léxicos basada en casos javier vélez reyes jvelez@lsi.uned.es

[close]

p. 4

análisis léxico formalización y desarrollo introducción introducción el primer paso para procesar un programa es convertir la colección de caracteres del mismo en una colección de componentes léxicos con significado único dentro del lenguaje llamados tokens de eso se encarga el analizador léxico o escáner · i · h · w ¿cómo se formaliza un analizador léxico el analizador sintáctico va pidiendo nuevos tokens al analizador léxico y éste los sirve bajo demanda formalismos conversión entre formalismos while a b do a a 1 foco de atención analizador léxico ¿cómo se implementa un analizador léxico

[close]

p. 5

análisis léxico formalización y desarrollo introducción introducción el primer paso para procesar un programa es convertir la colección de caracteres del mismo en una colección de componentes léxicos con significado único dentro del lenguaje llamados tokens de eso se encarga el analizador léxico o escáner definición de token un token es una unidad léxica indivisible con significado único dentro del lenguaje desde el punto de vista tecnológico se trata de una estructura de datos que contiene información sobre id tipo del token número de línea número de columna lexema valor categorías de token los tipos de tokens existentes en un lenguaje son una característica intrínseca al mismo no obstante pueden encontrarse categorías generales categoría delimitadores palabras reservadas identificadores números enteros números flotantes simbolos especiales cadenas ejemplos while true do if for index f iseven 3 -4 55 0 7658 4.5 .3 0.5 8.4e-5 hola mundo javier vélez reyes jvelez@lsi.uned.es

[close]

p. 6

análisis léxico formalización y desarrollo introducción introducción cada tipo de token representa a un conjunto de tokens construcciones léxicas diferentes con unos mismos propósitos dentro del lenguaje estos tipos se definen a través de un patrón léxico al que se adscriben los lexemas del tipo definición de patrón léxico un patrón léxico es una expresión abstracta llamada expresión regular que permite identificar unívocamente un tipo de token y referenciar al conjunto de todos los tokens que se ajustan a él definición de lexema la cadena de caracteres específica de un token que se ajusta al patrón léxico de su tipo se llama lexema existen dos tipos de lexemas cadena propia lexema idéntica al patrón cadena no propia lexema encaja con patrón tipo de token while enteros división identificador patrón léxico while digito letra letra |digito ejemplos de lexema while 12 123 0 45 index f iseven cadena propia si no si no javier vélez reyes jvelez@lsi.uned.es

[close]

p. 7

análisis léxico formalización y desarrollo introducción introducción desde la perspectiva léxica un programa es una familia ordenada de tokens de varios tipos cada tipo a través de su patrón léxico define un micro lenguaje formado por todos aquellos lexemas que encajan con el patrón léxico este tipo de lenguajes sencillos se llaman lenguajes regulares program burbuja uses crt const n 5 var i,j,temp:integer a:array[1 n of integer begin for i 1 to n do readlna[i for j n 1 downto 1 do for i 1 to j do if a[i a[i+1 then begin temp a[i a[i a[i+1 a[i+1 temp end writeln el resultado es for i 1 to n do writeln a[i readln end javier vélez reyes jvelez@lsi.uned.es definición de lenguaje regular un lenguaje regular describe una familia de tokens que se ajustan a un determinado patrón léxico lenguaje de delimitadores de pascal lenguaje de palabras reservadas de pascal program uses const var intger of array begin for to do downti if then end lenguaje de identificadores pascal burbuja ctr n i j temp a readln writeln

[close]

p. 8

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación de lenguajes regulares además de la declaración extensiva ­ sólo viable en los lenguajes finitos ­ existen 3 diferentes maneras de definir formalmente un lenguaje regular a lo largo de esta sección estudiaremos cada una de ellas en detalle y veremos cómo se puede pasar de cada una a las otras 2 gramáticas lineales elementos gramáticas lineales expresiones regulares autómatas finitos transformaciones de gramáticas a expresiones de gramáticas a autómatas de expresiones a gramáticas de expresiones a autómatas de autómatas a gramáticas de autómatas a expresiones lenguajes regulares expresiones regulares autómatas finitos javier vélez reyes jvelez@lsi.uned.es

[close]

p. 9

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante gramáticas lineales una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal que describe todas las reglas que se pueden aplicar para la construcción de lexemas que pertenecen al lenguaje regular definición de gramática lineal una gramática lineal es un conjunto de 4 elementos g t n s p donde t es un conjunto de símbolos terminales n es un conjunto de símbolos no terminales s n axioma gramatical p un conjunto de reglas de producción de la forma 1 a b x 2 a x b 3 a x donde a b n donde a b n donde x t u y y xt xt tipos de gramáticas lineales existen en realidad 2 tipos de gramáticas lineales en función de la forma del conjunto de reglas de producción podemos distinguir entre gramáticas lineales por la izquierda usan reglas a b x usan reglas a x gramáticas lineales por la derecha usan reglas a x b usan reglas a x a veces t se elide n se deduce de los antecedentes de las reglas de p y se asume que el antecedente de la primera regla es s con lo g sólo a través de p representa la cadena vacía ausencia de terminal dada una gramática g lineal por la izquierda siempre se puede encontrar una gramática g lineal por la derecha y recíprocamente javier vélez reyes jvelez@lsi.uned.es

[close]

p. 10

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante gramáticas lineales una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal que describe todas las reglas que se pueden aplicar para la construcción de lexemas que pertenecen al lenguaje regular derivación gramatical una gramática debe interpretarse como un conjunto de reglas de reescritura o transformación de elementos no terminales en elementos terminales o no terminales la primera transformación parte del axioma en cada paso se aplica una única regla las reglas pueden extender la transformación a b x a x b las reglas pueden ser recursivas a a x a x a las reglas pueden ser terminales a x ejemplo lg {a b sea g t n a p con t {a b n {a b p a a b a a b b b b b el proceso debe ser convergente javier vélez reyes jvelez@lsi.uned.es

[close]

p. 11

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante gramáticas lineales una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal que describe todas las reglas que se pueden aplicar para la construcción de lexemas que pertenecen al lenguaje regular derivación gramatical el problema ahora se traduce en dada una cadena formada por una secuencia de elementos terminales de t demostrar que dicha cadena pertenece al lenguaje definido por la gramática cadena de derivación axioma ejemplo lg {a b sea g t n a p con t {a b n {a b p asidero a a b a a b b b b b a ab abb abbb abbb paso de derivación forma de frase frase javier vélez reyes jvelez@lsi.uned.es

[close]

p. 12

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante gramáticas lineales una forma de definir formalmente un lenguaje regular es utilizar una gramática lineal que describe todas las reglas que se pueden aplicar para la construcción de lexemas que pertenecen al lenguaje regular ejercicios definir formalmente a través de una gramática lineal los siguientes lenguajes descritos informalmente l1 conjunto de todas las palabras sobre {a b que empiezan por a l2 conjunto de todas las palabras sobre {a b que empiezan por a y continúan con secuencias ab l3 números fraccionarios l4 identificadores l1 gd t n a p con t {a b n {a b p a a b b a b b b b b javier vélez reyes jvelez@lsi.uned.es gi t n a p con t {a b n {a b p a a a a a b a a

[close]

p. 13

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante expresiones regulares otra forma de definir lenguajes regulares es a través del uso de expresiones regulares una expresión regular utiliza los términos del alfabeto de terminales operados a través de operaciones con una semántica especifica definición de expresión regular una expresión regular sobre un conjunto t es un conjunto er t · que cumple las siguientes propiedades Ø es una expresión regular que define el lenguaje l Ø cadena vacía es una expresión regular que define el lenguaje l cualquier símbolo a t es una expresión regular que define el lenguaje l a a si x y son dos expresiones regulares x·y es una expresión regular que define l x·y l x l y si x y son dos expresiones regulares x y es una expresión regular que define l x y l x u l y si x es una expresión regular x es una expresión regular que define l x u l x i i =0 i si x es una expresión regular x es una expresión regular que define el lenguaje l x u l x i =1 no existen más expresiones regulares javier vélez reyes jvelez@lsi.uned.es

[close]

p. 14

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante expresiones regulares otra forma de definir lenguajes regulares es a través del uso de expresiones regulares una expresión regular utiliza los términos del alfabeto de terminales operados a través de operaciones con una semántica especifica ejercicios definir los siguientes lenguajes regulares utilizando para ello expresiones regulares l1 lenguaje de identificadores l2 lenguaje de números naturales l3 lenguaje de números fraccionarios l4 lenguaje de números enteros con exponente l5 lenguaje de números fraccionarios con exponente l6 lenguaje de números pares l7 lenguaje de las cuentas de correo l8 lenguajes de las url l1 l l d l {a z d {0 9 l3 d d l6 d p d {0 9 d {0 9 p {0 2 4 6 8 l7 nombre host nombre l1 l1 host l1 l1 javier vélez reyes jvelez@lsi.uned.es

[close]

p. 15

análisis léxico formalización y desarrollo especificación formal de analizadores léxicos especificación mediante autómatas finitos la tercera forma de definir lenguajes regulares es a través del uso de autómatas finitos un autómata finito reconoce una cadena de entrada si consumidos todos los caracteres de la misma acaba en un estado final de aceptación autómata finito determinista un autómata finito determinista es un conjunto afd t q f q f donde t es un alfabeto de símbolos terminales de entrada q es un conjunto de estados finito no vacío f qxtq es una función de transición q q es un estado inicial o estado de arranque f c q es un subconjunto de estados finales de aceptación interpretación gráfica gráficamente un autómata finito determinista es una colección de estados unidos por arcos donde para cada estado existe un arco etiquetado con cada elemento de t el estado inicial tiene una flecha entrante y los estados finales tienen un doble borde letra dígito 0 letra dígito 1 2 letra dígito letra [a z dígito [0 9 javier vélez reyes jvelez@lsi.uned.es

[close]