Taller 4 - Lenguajes Formales PDF

Preview

Summary

Ultimo taller de lenguajes formales...

Description

TALLER 4. LENGUAJES FORMALES 2. Leyendo… ando ¿Qué es un autocompilador y cuál es su funcionamiento? Es un compilador escrito en el mismo lenguaje que compila. Cuando se extiende entre muchas máquinas diferentes el uso de un compilador y éste se desea mejorar, el nuevo compilador se escribe con el antiguo, de manera que pueda ser compilado por todas esas máquinas diferentes y dé como resultado un compilador más potente de ese mismo lenguaje. ¿Qué es un metacompilador y cuál es su funcionamiento? Un metacompilador es un compilador de compiladores. Se trata de un programa que acepta como entrada la descripción de un lenguaje y produce el compilador de dicho lenguaje. Hoy en día no existen metacompiladores completos, pero si parciales en los que se acepta como entrada una gramática de un lenguaje y se genera un autómata que reconoce cualquier sentencia del lenguaje. A este autómata podemos añadirle código para completar el resto del compilador. Entre los metacompiladores más conocidos se encuentran: Lex, YACC, FLex, JavaCC, JLex, JFlex, CUP, Bison, JavaCC, PCCTS, MEDISE etc. LEX: generador de analizadores léxicos YACC: generador de analizadores sintácticos desarrollados para UNIX. Los inconvenientes que tienen son que los analizadores que generan no son muy eficientes. Los metacompiladores se suelen dividir entre los que pueden trabajar con gramáticas de contexto libre y los que trabajan con gramáticas regulares. Los primeros se dedican a reconocer la sintaxis del lenguaje y los segundos dividen los archivos fuentes y los dividen en palabras. Un metacompilador es un programa que acepta la descripción de un lenguaje y obtiene el compilador de dicho lenguaje, es decir, acepta como entrada una gramática de un lenguaje y genera un autómata que reconoce cualquier sentencia del lenguaje. A este autómata podemos añadir código para realizar el compilador. Unos metacompiladores pueden trabajar con gramáticas de contexto libre y otros trabajan con gramática regular. Los que trabajan con gramáticas de contexto libre se dedican a reconocer la sintaxis del lenguaje y los de gramática regular trocean la entrada y la dividen en palabras.

El PCLEX es un metacompilador cuya función es generar un programa que es la parte del compilador que reconoce las palabras reservadas. El PCYACC es un metacompilador cuya función es generar un programa que es la parte del compilador que indica si una sentencia del lenguaje es válida o no. ¿Qué es un descompilador y cuál es su funcionamiento? Un descompilador realiza una labor de traducción inversa, esto es, pasa de un código máquina al equivalente en el lenguaje que lo genera. Cada descompilador trabaja con un lenguaje de alto nivel concreto. La descompilación suele ser una labor casi imposible, porque al código máquina generado casi siempre se le aplica una optimización en una fase posterior, de manera que un mismo código máquina ha podido ser generado a partir de varios códigos fuentes. Es por esta razón que en la actualidad solo existen descompiladores de aquellos lenguajes en los que existe una relación biyectiva entre el código destino y el código fuente. Estos pasan de un código máquina (o programa de salida) al lenguaje que lo generó (o programa fuente). Cada descompilador trabaja con un lenguaje de alto nivel concreto. Es una operación casi imposible, porque al código máquina casi siempre se le aplica una optimización. Por eso lo que hay suelen ser desensambladores, ya que existe una biyección entre cada instrucción máquina y cada instrucción ensamblador. Se utilizan especialmente cuando el código máquina ha sido generado con opciones de depuración y contiene información adicional de ayuda a la depuración de errores (puntos de ruptura, opciones de visualización de variables, etc) También se emplea cuando el compilador original no generó código máquina puro, sino pseudocódigo (para ejecutarlo a través de un pseudo intérprete). 3. Expresiones Regulares y autómatas En este punto se solicita establecer, tanto las expresiones regulares, como los autómatas, para los siguientes juegos binarios: ● 0 o 11 o 101 R1 = (0 + 11 + 101)+ A1 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 , q 4}

Σ = {0, 1} δ (q 0 , 0) = q 1 δ (q 2 , 0) = q 4 Qa = {q 1, q 3}

δ (q 0 , 1) = q 2 δ (q 4 , 1) = q 3

δ (q 2 , 1) = q 3

● Cualquier cadena en binario R2 = (0 + 1) * A2 = (Q, Σ, δ , q 0, Qa ) Q = {q 0 , q 1} Σ = { λ , 0, 1 } δ (q 0 , λ) = q 1 Qa = {q 1}

δ (q 1 , 0) = q 1

δ (q 1 , 1) = q 1

● Cualquier cadena en binario exceptuando una vacía R3 = (0 + 1)+ A3 = (Q, Σ, δ , q 0, Qa ) Q = {q 0 , q 1} Σ = { 0, 1} δ(q 0, 0) = q 1 δ (q 1 , 1) = q 1 Qa = {q 1}

δ (q 0 , 1) = q 1

δ (q 1 , 0) = q 1

● Cualquier cadena que contenga al menos tres 1nos R4 = ((0 + 1)* 1 (0 + 1 )* 1 (0 + 1 )* 1 (0 + 1 )* ) A4 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 } Σ = { 0, 1} δ(q 0, 0) = q 0 δ(q 0 , 1) = q 1, q 0 δ (q 1 , 0) = q 1 δ(q 1 , 1) = q 1 , q 2 δ(q 1 , 1) = q 1, q 2 δ (q 2 , 0) = q 2 δ(q 2 , 1) = q 2 , q 3 δ (q 3 , 0) = q 3 δ (q 3 , 1) = q 3 Qa = {q 3}

● Cualquier cadena que contenga al menos tres caracteres y el tercero sea 1 R5 = ((0 + 1)(0 + 1) 1 (0 + 1)* ) A5 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 } Σ = { 0, 1} δ(q 0, 0) = q 1 δ (q 0 , 1) = q 1 δ (q 1 , 0) = q 2 δ (q 1 , 1) = q 2 δ (q 2 , 1) = q 3 δ (q 3 , 0) = q 3 δ (q 3 , 1) = q 3 Qa = {q 3}

4. Del Regex al autómata En este punto se solicita verificar el funcionamiento de las siguientes expresiones regulares, teniendo en cuenta la implementación de su lenguaje, árbol de derivación, autómata y descripción: ● (0|1) | (0|1)(0|1) | (0|1)(0|1)(0|1) A6 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 } Σ = { 0, 1} δ(q 0, 0) = q 1 δ (q 0 , 1) = q 1 δ (q 1 , 1) = q 2 δ (q 2 , 1) = q 3 Qa = {q 1, q 2 , q 3} n m L = {0 1 | 0 ≤ n ≤ 3 , 0 ≤ n ≤ 3 , 1 ≤ n + m ≤ 3}

δ (q 1 , 0) = q 2 δ (q 3 , 0) = q 3

● 1(0|1)*1|0(0|1)*0 A7 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 } Σ = { 0, 1} δ(q 0, 0) = q 1 δ(q 1 , 0) = q 1, q 3 δ (q 1 , 1) = q 1 δ (q 0 , 1) = q 2 δ (q 2 , 0) = q 2 δ(q 2 , 1) = q 2 , q 4 Qa = {q 3, q 4 } n m L7 = {0(0 1 )0 | 0 ≤ n , 0 ≤ m } ⋃ {1(0n 1m)1 | 0 ≤ n , 0 ≤ m }

● ((0|1)((0|1)(0|1))* A8 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 } Σ = { 0, 1} δ(q 0, 0) = q 1 δ (q 0 , 1) = q 2 δ (q 3 , 1) = q 1 δ (q 4 , 0) = q 2 Qa = {q 1, q 2 }

δ (q 1 , 0) = q 3 δ (q 2 , 0) = q 4 δ (q 3 , 0) = q 1

δ (q 1 , 1) = q 3 δ (q 2 , 1) = q 4 δ (q 4 , 1) = q 2

L8 = { 0(0n |1m) | n 2, m 2 para 0 ≤ n, m } ⋃ {1(0 n|1 m) | n 2, m 2 para 0 ≤ n, m}

● 0((0|1)(0|1))* | 1(0|1) ((0|1)(0|1))* A9 = (Q, Σ, δ , q 0, Qa ) Q = {q0 , q 1 , q 2, q 3 , q 4} Σ = { 0, 1} δ(q0 , 0) = q 2 δ (q 1 , 0) = q 4 δ (q 0 , 1) = q 1 δ (q 2 , 0) = q 3 δ (q 3 , 1) = q 2 δ (q 3 , 0) = q 2 δ (q 4 , 0) = q 1 Qa = {q 2, q 4}

δ (q1 , 1) = q 4 δ (q 2 , 1) = q 3 δ (q 4 , 1) = q 1

L9 = { 0(0n |1m) | n 2 − 1, m 2 − 1 para 0 ≤ n, m} ⋃ {1(0 n|1 m) | n 2, m 2 para 0 ≤ n, m}

CONCLUSIONES ● Las expresiones regulares definen reglas sintácticas para la evaluación de una cadena de texto y surgen de un lenguaje regular cumpliendo la propiedad de recursividad. ● Contrario a los compiladores que procesan instrucciones escritas en un lenguaje de programación de alto nivel y las convierten a lenguaje de máquina, los autocompiladores están escritos en el mismo lenguaje, así es posible generar un compilador más potente del mismo lenguaje. ● Así como hay autómatas semejantes existen expresiones regulares semejantes, es decir que pueden funcionar para validar la misma cadena de texto. ● En algunos casos es posible acotar el autómata porque la expresión regular puede validar palabras que el autómata no. ● La minimización de MyHill - Nerode se reafirma una vez más como técnica para encontrar autómatas semejantes de los que se genera el mismo lenguaje.

REFERENCIAS Definición de autocompilador, metacompilador y descompilador. Recuperado de: h  ttp://www.lcc.uma.es/~galvez/ftp/tci/tictema1.pdf Definición de autocompilador, metacompilador y descompilador. Recuperado de:http://manglar.uninorte.edu.co/bitstream/handle/10584/2109/1044421326.p df.txt;sequence=3...