Unidad V Analisis Sintactico

ANALISIS SINTACTICO

5.1 GLC.

Gramáticas Libres de Contexto (GLC), o de tipo 2: las reglas son de la forma X → α, donde X es una variable y α es una cadena que puede contener variables y constantes. Estas gramáticas producen los lenguajes Libres de Contexto (abreviado “LLC”)

• Capturan la noción de constituyente sintáctico y la noción de orden.
• Herramienta formal que puede ser vista tanto desde un punto de vista generador como estructurador.
• Propiedades computacionales interesantes: se puede reconocer en tiempo polinómico.

Una Gramática Libre de Contexto es una tupla con 4 parámetros:

• G = (V, T, P, S)
• V – conjunto de símbolos variables
• T – conjunto de símbolos terminales
• S Є V, símbolo inicial
• P – conjunto de reglas de producción: A → α, con α sucesión de símbolos de V U T, eventualmente vacía (α = ε)

Una GLC es un dispositivo generador.

Definimos el lenguaje LG generado por una gramática G del siguiente modo: G = { w / S →* w } , siendo ⇒* una “especie” de clausura transitiva de → y w una tira de terminales

5.2 Árbol de derivación.

Es una representación gráfica (en forma de árbol invertido) de un proceso de derivación en una gramática. Se define el árbol de derivación como sigue:

• la raíz del árbol será el símbolo inicial de la gramática
• los nodo interiores del árbol están etiquetados por los símbolos no terminales
• las hojas están etiquetadas por símbolos terminales
• si un nodo interior etiquetado por A, posee como hijos los nodos etiquetados por X1,X2, …Xn , entonces A→ X1,X2, …Xn es una producción de la gramática, en donde Xi , representa símbolo terminal o no terminal.

Sea la siguiente gramática:

G=( Σ={a, b}, N={S,A,B},S P ) P: S→aABAa , A→ε |aA , B→ε|bB la construcción de un árbol de derivación en el proceso de la generación de la palabra aa es el siguiente:

Propiedades de un árbol de derivación.

Sea G = (N, T, S, P) una gramática libre de contexto, sea A Є N una variable. Diremos que un árbol TA= (N, E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes:

• La raíz del árbol es un símbolo no terminal
• Cada hoja corresponde a un símbolo terminal o λ.
• Cada nodo interior corresponde a un símbolo no terminal.

Para cada cadena del lenguaje generado por una gramática es posible construir (al menos) un árbol de derivación, en el cual cada hoja tiene como rótulo uno de los símbolos de la cadena.

Árbol de derivación.

Ejemplo:

Sea G=(N, T, S, P) una GLC con P: S→ ab|aSb

La derivación de la cadena aaabbb será: S → aSb → aaSbb → aaabbb y el árbol de derivación:

Ejercicio:

EJERCICIO:

5.3 Formas normales de Chomsky.

Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción son de alguna de las siguientes formas:

A → BC o
A → a o

donde A, B y C son símbolos no terminales (o variables) y α es un símbolo terminal.

Todo lenguaje independiente del contexto que no posee a la cadena vacía, es expresable por medio de una gramática en forma normal de Chomsky (GFNCH) y recíprocamente. Además, dada una gramática independiente del contexto, es posible algorítmicamente producir una GFNCH equivalente, es decir, que genera el mismo lenguaje.

Sea G = (∑ N, ∑T, P, $) una gramática con P ⊂ ∑N X (∑N U ∑T)* y X Є ∑N un símbolo no-terminal (o una variable). Podemos clasificar tales símbolos X en tres clases:

Variables accesibles:

• Si existe una derivación desde el símbolo inicial que contiene X, es decir, existe $ → * α Xβ donde α, β Є∑*

Variables generativas:

• Si existe una derivación desde el la variable que produce una sentencia , es decir, existe X →* ω donde ω Є *T.

Variables útiles:

• Si existe una derivación desde el símbolo inicial usando que produce una sentencia ω, es decir, existe $ →* α X β →*ω donde α, β Є ∑* y ω Є ∑*T.

5.4 Diagramas de sintaxis

Los diagramas sintácticos, de sintaxis o diagramas del ferrocarril son una forma de representar una gramática libre de contexto. Representan una alternativa gráfica para la Forma de Backus-Naur (BNF, por sus siglas en inglés) o la Forma Extendida de Backus-Naur (EBNF, por sus siglas en ingles).

Los diagramas de ferrocarril son más comprensibles para la mayoría de la gente. Alguna parte de la popularidad del formato de intercambio de datos JSON se debe a su representación en los diagramas de ferrocarril.

Un segundo método alternativo para desplegar las producciones de ciertas gramáticas de tipo 2 es el diagrama de sintaxis. Ésta es una imagen de las producciones que permite al usuario ver las sustituciones en forma dinámica, es decir, verlas como un movimiento a través del diagrama. En la figura 10.5 se ilustrará los diagramas que resultan de la traducción de conjuntos de producciones típicos, que son, por lo general, todas las producciones que aparecen en el lado derecho de algún enunciado BNF.

5.5 Eliminación de la ambigüedad

Una GLC es ambigua si existe una cadena w Є L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más arboles de derivación .

En casi de y que toda cadena w Є L (G) tenga un único árbol de derivación no es ambigua.

Ejemplo: La gramática S → aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda S Þ aS Þ aa S Þ Sa Þ aa.

Tipos de Ambigüedad

Dentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:

Ambigüedad Inherente:

Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse para lenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, nunca se podrá eliminar completamente la ambigüedad que presentan:

Un lenguaje L es inherentemente ambiguo si todas sus gramáticas; si existe cuando menos una gramática no ambigua para L, L no es ambiguo.

• El lenguaje de las expresiones no es Ambiguo
• Las expresiones regulares no son ambiguas

Ejemplo de un lenguaje inherentemente ambiguo:

La gramática es ambigua: hay cadenas con más de una derivación más izquierda:

5.6 Generación de matriz predictiva (cálculo first y follow)

FIRST: Sea G := (V; ∑; Q0; P) una gramática libre de contexto. Para cada forma sentencial α Є (V U ∑)* y para cada k Є N definiremos la función.

En otras palabras, el operador F IRST k asocia a cada forma sentencial los primeros k símbolos de cualquier forma terminal alcanzable desde α mediante derivaciones “masa la izquierda".

FOLLOW: Con las mismas notaciones anteriores, para cada forma sentencial α Є (V U ∑)*  definiremos la función FOLLOWG GK (α) del modo siguiente.

De nuevo nos ocuparemos solamente de FOLLOW: = FOLLOW1. Obsérvese que FOLLOW k (α) ⊂ ∑* y que para cada x Є FOLLOW (α), Ixl ≤ k. Obsérvese que para cada variable A Є V, FOLLOW(A) son todos los símbolos terminales que pueden aparecer a la derecha de A en alguna forma sentencial de la gramática.


5.7 Tipos de analizadores sintácticos

Analizador Descendente:

Se construye el árbol de análisis sintético partiendo del símbolo inicial y aplicando las producciones mediante derivaciones por la izquierda, el símbolo a expandir es el que esta mas a la izquierda. 

Analizador Ascendente:

Se construye el árbol de análisis sintético partiendo de la frase a reconocer y aplicando las producciones mediante reducciones hasta llegar al símbolo inicial de la gramática.

Ejemplo:

G= ({+,*, ID, (,)}, {E, T, P},E, P)P={E:=E+T | T; T:=T*P | P; P:= ID | (E) }FraseID + ( ID * ID )

Ejemplo:

G= ({+,*, ID, (,)}, {E, T, P},E, P)P={E:=E+T | T; T:=T*P | P; P:= ID | (E) }FraseID + ( ID * ID )

5.8 Manejo de errores.

Un compilador es un sistema que en la mayoría de los casos tiene que manejar una entrada incorrecta. Sobre todo en las primeras etapas de la creación de un programa, es probable que el compilador se utiliza para efectuar las características que debería proporcionar un buen sistema de edición dirigido por la sintaxis, es decir, para determinar si las variables han sido declaradas antes de usarla, o si faltan corchetes o algo así.

Por lo tanto, el manejo de errores es parte importante de un compilador y el escritor del compilador siempre debe tener esto presente durante su diseño.

Hay que señalar que los posibles errores ya deben estar considerados al diseñar un lenguaje de programación. Por ejemplo, considerar si cada proposición del lenguaje de programación comienza con una palabra clave diferente (excepto la proposición de asignación, por supuesto). Sin embargo, es indispensable lo siguiente:

El compilador debe ser capaz de detectar errores en la entrada;

• El compilador debe recuperarse de los errores sin perder demasiada información;
• Y sobre todo, el compilador debe producir un mensaje de error que permita al programador encontrar y corregir fácilmente los elementos (sintácticamente) incorrectos de su programa.

MANEJO DE ERRORES (VIDEO). CLICK AQUI

Errores Sintácticos.

Muchos errores de naturaleza sintáctica Recuperación: Al producirse un error el compilador debe ser capaz de informar del error y seguir compilando. (Ideal).

El manejo de errores de sintaxis es el más complicado desde el punto de vista de la creación de compiladores. Nos interesa que cuando el compilador encuentre un error, se recupere y siga buscando errores. Por lo tanto el manejador de errores de un analizador sintáctico debe tener como objetivos:

• Indicar los errores de forma clara y precisa. Aclarar el tipo de error y su localización.
• Recuperarse del error, para poder seguir examinando la entrada.
• No ralentizar significativamente la compilación.

Un buen compilador debe hacerse siempre teniendo también en mente los errores que se pueden producir; con ello se consigue:

• Simplificar la estructura del compilador.
• Mejorar la respuesta ante los errores.

Errores semánticos.

Un lenguaje con comprobación fuerte de tipos es capaz de garantizar que los programas se pueden ejecutar sin errores de tipo, por lo que los errores de tipo se detectarán siempre en tiempo de compilación.
Como mínimo, ante un error, un comprobador de tipos debe informar de la naturaleza y posición del error y recuperarse para continuar con la comprobación del resto del programa a analizar.


Veamos algunas de las operaciones a tener en cuenta en una comprobación de tipos:

• Conversión de tipos: A veces es necesario transformar el tipo de una expresión para utilizar correctamente un operador o para pasar de forma adecuada un parámetro a una función.
• Coerción: Es una conversión de tipos que realiza de forma implícita el propio compilador. Si es el programador el que realiza la conversión se tratará entonces de una conversión explícita.
• Sobrecarga de operadores: La sobrecarga se resuelve determinando el tipo de cada una de las expresiones intervinientes en la sobrecarga.
• Funciones polimórficas: Son aquellas que trabajan con argumentos cuyo tipo puede cambiaren distintas llamadas a la función.

Unidad VI Maquinas de Turing

MAQUINAS DE TURING (CLICK AQUI)

6.1 Definición formal MT

La Máquina de Turing (MT) fue introducida por Alan M. Turing en 1936, y puede considerarse como un modelo abstracto que formaliza la idea Intuitiva de algoritmo.

(MT) Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.

Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta , borrando el símbolo , escribir el nuevo símbolo perteneciente al alfabeto de salida y finalmente avanza a la izquierda o a la derecha (solo una celda a la vez), repitiendo esto según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.

Esta constituida por los siguiente elementos:          
 

MT = ( E, A, B, e0, F, f)
 

E = Conjunto de estados, no vacío.

A = Conjunto de símbolos de entrada.

B = Conjunto de símbolos auxiliares.

e0 = Estado inicial.

F = Conjunto de estados finales.

f  = Función de control, definida:

donde:   f: ( E - F )   x   ( A È B )   Þ   E x  ( A È B)   x   ( I, O, D )
 

I = movimiento del cabezal a la izquierda.

O = movimiento nulo.

D = movimiento a la derecha.

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

 avanzar el cabezal lector/escritor para la derecha.

 avanzar el cabezal lector/escritor para la izquierda.

6.2 Construcción modular de una MT.

El objetivo de la creación modular de una maquina de Turing es poder desarrollar máquinas complejas a partir de bloques elementales, a partir de maquinas más pequeñas, mediante diagramas de transiciones. La construcción de máquinas de Turing se lleva a cabo mediante los diagramas de transición y combinarlos de manera parecida a lo que se realiza en la formación de la unión y concatenación de los autómatas finitos.

Pasos para la construcción de una máquina de Turing:

• Elimine las características de inicio de los estados iniciales de las maquinas, excepto la de aquel donde iniciara la maquina compuesta.
• limine las características de detención de los estados de parada de todas la maquinas e introduzca un nuevo estado de parada que nos se encuentre en ninguno de los diagramas que se combinan.
• Para cada uno de los antiguos estados de parada p y cada x en y.
  

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos.  En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído.

Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia;  recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.

6.3 Lenguajes aceptados por la MT.

Una máquina de Turing se puede comportar como un aceptador de un lenguaje. Si colocamos una cadena w en la cinta, situamos la cabeza de lectura/escritura sobre el símbolo del extremo izquierdo de la cadena w y ponemos en marcha la  máquina a partir  de su estado inicial. Entonces w es aceptada si, después de una secuencia de movimientos, la máquina de Turing llega a un estado final y para. Por tanto w es aceptada. Si qw  *  w1pw2 para algún estado final p y unas cadenas w1 y w2.

 Entonces, se obtiene la siguiente definición:

Sea M = (Q, S , G, q0=q1, B, F, d) una máquina de Turing. Entonces el lenguaje aceptado por M es: L(M) = {wÎ S*½q1w   *   w1pw2 para pÎF y wiÎG*}.

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden se computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing.

  Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.

Gramáticas estructuradas por frases:

• Parte   izquierda   de   las   reglas:   combinación   de   símbolos   terminales   y   no terminales, con al menos un no terminal.
• Parte derecha de las reglas: combinación de símbolos terminales y no terminales de cualquier longitud (incluso 0).
• Las máquinas de Turing aceptan lenguajes estructurados por frases.

La M.T. como generadora de lenguajes.

L={an b2n an, con n mayor o igual a 0}

Entrada:

Cinta1: ...BBB...

Cinta2: ...BBB...

Salida:

Cinta1: ...0000...

Cinta2: ...λ$abba$aabbbbaa$...

Proceso:

El proceso de la maquina es sencillo, consiste en generar 0's en la primera cinta y su correspondiente lenguaje en la segunda cinta. Este proceso será cíclico y sin fin, ya que estamos tratando con un generador.

Para ello utilizamos multicinta porque nos facilita de manera considerable el trabajo.

Ejemplifiques el funcionamiento de una Máquina de Turing.

Supongamos que tenemos Σ={a,b} y q_f y que representamos los enteros positivos mediante cadenas solo de “as”. Así el entero “n” estaría representado por a^n.

Se puede construir la MT que calcule la función f(n,m) = n+m, implementando la transformación 

a^n ba^m en a^(n+m) b

Solución:

Se recorren desde la izquierda todas las as hasta encontrar una “b”, esta se reemplaza por una “a”, cambiando de estado, en este mismo estado se recorren todas las “as” a la derecha y cuando se llega a un blanco se reemplaza por el mismo blanco se deja la cabecera a la izquierda y se reemplaza la “a” por un blanco para restarle la que adiciono y se mueve hacia la derecha y se cambia al estado final “q3”.

M=(Q,Σ,Γ,q_0,q_3,B,δ)

Donde la función se define así:

EJERCICIO MAQUINA DE TURING