REP PRAC LENG AUTÓMATAS TEMA 5 ACTIVIDADES - Mauricio axel 20

Vista previa del material en texto

TECNOLÓGICO NACIONAL DE MÉXICO
INSTITUTO TECNOLÓGICO DE ACAPULCO
REPORTE DE PRACTICAS/ACTIVIDADES DE APRENDIZAJE DEL TEMA 5
TEMA 5 ANÁLISIS SINTÁCTICO
FECHA DE ENTREGA JUEVES 10 DE DICIEMBRE DE 2020
INTEGRANTES					 NO CONTROL
1. ABARCA LOPEZ ALBERTO JOSUE		 18320789
2. CANTU PALACIOS CARLOS ALBERTO 18320820
3. LOPEZ ANSELMO MAURICIO AXEL	 18320904
4. RAMOS PÉREZ GUADALUPE INES		 17320952
SILVESTRE BEDOLLA SOLANO
HORARIO: 3:00 – 4:00 PM		
GRUPO: IS3
INGENERIA EN SISTEMAS COMPUTACIONALES
LENGUAJES Y AUTOMATAS I
INTRODUCCIÓN
5. ANÁLISIS SINTÁCTICO
5.1 DEFINICICÓN Y CLASIFICACIÓN DE GRAMÁTICAS
5.2 GRAMÁTICAS LIBRES DE CONTEXTO (GLC)
5.3 ÁRBOLES DE DERIVACIÓN
5.4 FORMAS NORMALES DE CHOMSKY
5.5 DIAGRAMAS DE SINTAXIS
5.6 ELIMINACIÓN DE LA AMBIGÜEDAD
5.7 TIPOS DE ANALIZADORES SINTACTICOS
5.8 GENERACIÓN DE MATRIZ PREDICTIVA (CÁLCULO FIRST Y FOLLOW)
5.9 MANEJO DE ERRORES
5.10 GENERADORES DE ANALIZADORES SINTACTICOS
ACTIVIDAD 1. IDENTIFICAR LA NOTACIÓN FORMAL DE UNA GRAMÁTICA
ACTIVIDAD 2. BUSCAR LA SINTAXIS DE LA CONSTRUCCIÓN DE LOS LENGUAJES DE PROGRAMACIÓN POR MEDIO DE GLC O UTILIZANDO NOTACIÓN BNF (BACKUS-NAUR-FORM)
ACTIVIDAD 3. INVESTIGAR LAS FORMAS NORMALES DE CHOMSKY
ACTIVIDAD 4. CONOCER LA NOTACIÓN DE LOS DIAGRAMAS DE SINTAXIS
ACTIVIDAD 5. CONSTRUIR DIAGRAMAS DE SINTAXIS DE UN LENGUAJE
ACTIVIDAD 6. CONSTRUIR UNA GLC A PARTIR DE LOS DIAGRAMAS DE SINTAXIS
ACTIVIDAD 7. ELIMINAR LA AMBIGÜEDAD DE UNA GRAMÁTICA
CONCLUSIÓN
REFERENCIAS
INTRODUCCIÓN
El análisis sintáctico describe las funciones de ciertas unidades gramaticales (palabras y oraciones) insertas en una unidad superior, la oración. Se trata de explicar qué papel desempeñan para que la oración posea significación completa e independencia estructural. Esta presentación sigue la gramática clásica. Se debe tener en cuenta porque se pueden encontrar otras aproximaciones razonables, en las que además cambia la nomenclatura. El rendimiento pedagógico de este tema es más que dudoso, pero como los programas de estudio lo exigen imperativamente, lo ofrecemos aquí como complemento de alumnos y profesores. Acaso les ayude a adquirir unas destrezas analíticas suficientes. La presentación busca la claridad y brevedad, de modo que no ha lugar a una casuística minuciosa, excepciones mínimas o disquisiciones teóricas. La fase de análisis sintáctico tiene por objetivo solicitar tokens al analizador léxico y construir una representación arborescente de todo el código fuente. Este proceso se encuentra dirigido por el conocimiento gramatical que del lenguaje tiene el analizador sintáctico.
5. ANÁLISIS SINTÁCTICO
Todo lenguaje de programación tiene reglas que describen la estructura sintáctica de programas bien formados. En Pascal, por ejemplo, un programa se compone de bloques, un bloque de proposiciones, una proposición de expresiones, una expresión de componentes léxicos, y así sucesivamente. Se puede describir la sintaxis de las construcciones de los lenguajes de programación por medio de gramáticas de contexto libre o notación BNF (Backus-Naur Form).
· Las gramáticas ofrecen ventajas significativas a los diseñadores de lenguajes y a los desarrolladores de compiladores. 
· Las gramáticas son especificaciones sintácticas y precisas de lenguajes de programación. 
· A partir de una gramática se puede generar automáticamente un analizador sintáctico.
· El proceso de construcción puede llevar a descubrir ambigüedades.
· Una gramática proporciona una estructura a un lenguaje de programación, siendo más fácil generar código y detectar errores.
· Es más fácil ampliar/modificar el lenguaje si está descrito con una gramática.
¿QUÉ ES EL ANALIZADOR SINTÁCTICO?
Es la fase del analizador que se encarga de chequear el texto de entrada en base a una gramática dada. Y en caso de que el programa de entrada sea válido, suministra el árbol sintáctico que lo reconoce. En teoría, se supone que la salida del analizador sintáctico es alguna representación del árbol sintáctico que reconoce la secuencia de tokens suministrada por el analizador léxico. En la práctica, el analizador sintáctico también hace: 
· Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico).
· Chequeo de tipos (del analizador semántico).
· Generar código intermedio.
· Generar errores cuando se producen. En definitiva, realiza casi todas las operaciones de la compilación. Este método de trabajo da lugar a los métodos de compilación dirigidos por sintaxis.
MANEJO DE ERRORES SINTÁCTICOS
Si un compilador tuviera que procesar sólo programas correctos, su diseño e implantación se simplificarían mucho. Pero los programadores a menudo escriben programas incorrectos, y un buen compilador debería ayudar al programador a identificar y localizar errores. Es más, considerar desde el principio el manejo de errores puede simplificar la estructura de un compilador y mejorar su respuesta a los errores. Los errores en la programación pueden ser de los siguientes tipos:
· Léxicos, producidos al escribir mal un identificador, una palabra clave o un operador.
· Sintácticos, por una expresión aritmética o paréntesis no equilibrados.
· Semánticos, como un operador aplicado a un operando incompatible.
· Lógicos, puede ser una llamada infinitamente recursiva. 
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.
· Tenemos varias estrategias para corregir errores, una vez detectados:
· Ignorar el problema (Panic mode): Consiste en ignorar el resto de la entrada hasta llegar a una condición de seguridad. 
· Una condición tal se produce cuando nos encontramos un token especial (por ejemplo, un ‘;’ o un ‘END’). 
· A partir de este punto se sigue analizando normalmente.
FUNCIONES DEL ANALIZADOR SINTÁCTICO
Comprobar si la cadena de componentes léxicos proporcionada por el analizador léxico puede ser generada por la gramática que define el lenguaje fuente (Gramática Independiente del Contexto, GIC). Construir el árbol de análisis sintáctico que define la estructura jerárquica de un programa y obtener la serie de derivaciones para generar la cadena de componentes léxicos. El árbol sintáctico se utilizará como representación intermedia en la generación de código. Informar de los errores sintácticos de forma precisa y significativa y deberá estar dotado de un mecanismo de recuperación de errores para continuar con el análisis.
5.1 DEFINICICÓN Y CLASIFICACIÓN DE GRAMÁTICAS
Una gramática ("G") desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.
Una gramática es una estructura algebraica formada por cuatro elementos fundamentales: G = { NT, T, S, P }
Donde: 
· NT es el conjunto de elementos No Terminales
· T es el conjunto de elementos Terminales
· S es el Símbolo inicial de la gramática
· P es el conjunto de Reglas de Producción
CLASIFICACIÓN DE GRAMÁTICAS
Según Padilla las gramáticas se clasifican de acuerdo a las reglas de sustitución y nunca se pasa autómatas 2. En el campo de la informática, el concepto de Gramática Formal adquirió gran importancia para el desarrollo de lenguajes de programación, consiguientemente el desarrollo de autómatas y máquinas de Turing cobró vida en las últimas décadas, fortaleciendo el vínculo entreElectrónica e Informática, creando máquinas cada vez más sofisticadas y menos complicadas para el usuario final.
SÍMBOLO: Es una entidad abstracta, que no se va a definir. Normalmente los símbolos son letras (a, b, c, …z), dígitos (0,1,2…9) y otros caracteres (+, *, /, -, ?, ...). Un símbolo también puede estar formado por varias letras o caracteres, como las palabras reservadas de un lenguaje de programación son símbolos de dicho lenguaje. Ejemplo: a, b, c, #, +, -, *, then, begin, end, else, …
VOCABULARIO O ALFABETO: Un vocabulario o alfabeto es un conjunto finito de símbolos, no vacío. Para definir que un símbolo a pertenece a un alfabeto V, se utiliza la siguiente notación aÃŽV. Los alfabetos se definen por enumeración de los símbolos que contienen, podemos ver los siguientes ejemplos:
· V1 = {A, B, C, D, E, F, ….., X,Y,Z}
· V2 = {a, b, c, d,0,1,2,3,4, *, #, +}
· V3 = {0,1}
· V4 = {if, then, begin, end, else, a, b; =, >}
También se pueden definir las tablas ASCII y EBCDIC como los alfabetos de distintos ordenadores.
CADENA: Una cadena es una secuencia finita de símbolos de un determinado alfabeto. Ejemplo: Tomando en cuenta los alfabetos o vocabularios definidos anteriormente, podemos decir que:
· abcb es una cadena del alfabeto V2
· a+2*b es una cadena del alfabeto V2
· 000111 es una cadena del alfabeto V3
· If a>b then b=a; es una cadena del alfabeto V4
LONGITUD DE CADENA: La longitud de una cadena consiste en el número de símbolos pertenecientes a la cadena. Ejemplo: Tomando en cuenta los ejemplos de cadena podemos decir que:
· |abcb| es de longitud 4
· |a + 2*b| es de longitud  5
· |000111| es de longitud  6
· |if a>b then a=b;| es de longitud  9
CADENA VACÍA: Se denomina cadena vacía, que no tiene símbolos y se denota con l, por lo que su longitud es: | l | ® 0
CONCATENACIÓN DE CADENAS: Sean A y B dos cadenas cualesquiera, se denomina concatenación de A y B a una nueva cadena AB constituida por los símbolos de la cadena A seguidos por los de la cadena B. El elemento neutro de la concatenación es l: A l =  lA = A
UNIVERSO DEL DISCURSO: El conjunto de todas las cadenas que se pueden formar con los símbolos de un alfabeto, se denomina universo del discurso V y se representa por W(V). Evidentemente W(V) es un conjunto infinito. La cadena vacía pertenece a W(V). Ejemplo: Sea un alfabeto con una sola letra V={a}, entonces el universo del discurso es: W(V) = {l, a, aa, aaa, aaaa, ….} que contiene infinitas cadenas.
GRAMÁTICA: Veamos algunos conceptos que nos ayuden a formular el concepto de gramática: (Del lat. gramática, y este del gr. γραμματική). f. Ciencia que estudia los elementos de una lengua y sus combinaciones. Arte de hablar y escribir correctamente una lengua. Estudio de una lengua regido por el principio de que todos sus elementos mantienen entre sí relaciones sistemáticas. La que trata de formular una serie de reglas capaces de generar o producir todas las oraciones posibles y aceptables de un idioma o lenguaje. Una definición un tanto técnica: " La gramática es un ente formal para especificar, de una manera finita, el conjunto de cadenas de símbolos que constituyen un lenguaje" . La gramática genera o describe un lenguaje.
AUTÓMATA: (Del latin. automăta, t. f. de -tus, y este del gr. αὐτόματος, espontáneo). m. Instrumento o aparato que encierra dentro de sí el mecanismo que le imprime determinados movimientos o respuestas. Máquina que imita la figura y los movimientos de un ser animado. Microsoft® Encarta® 2007. © 1993-2006 Microsoft Corporation. Reservados todos los derechos. En el caso de los Procesadores de Lenguaje un autómata es una construcción lógica que recibe como entrada una cadena de símbolos y produce una salida indicando si dicha cadena pertenece o no a un determinado lenguaje.
LENGUAJE: Conjunto de sonidos articulados con que el hombre manifiesta lo que piensa o siente. Sistema de comunicación verbal. Manera de expresarse. Conjunto de señales que dan a entender algo. El lenguaje de los ojos, el de las flores. En Informática Conjunto de signos y reglas que permite la comunicación con un ordenador. Podemos expresarlo de manera más sencilla como un conjunto de palabras ó cadenas de símbolos (palabras, oraciones, textos o frases) de un determinado alfabeto.
LENGUAJE VACÍO: Existe un lenguaje denominado lenguaje vacío, que es un conjunto vacío y que se denota por {Ø}. El lenguaje vacío no debe confundirse con un lenguaje que contenga una sola cadena, y que ésta sea la cadena vacía, es decir {l}, ya que el número de elementos (cardinalidad) de estos dos conjuntos es diferente.
· Cardinal ({ Ø }) = 0
· Cardinal ({ l }) = 1
TIPO DE GRAMÁTICA QUE ACEPTA UN ANALIZADOR SINTÁCTICO
Nosotros nos centraremos en el análisis sintáctico para lenguajes basados en gramáticas formales, ya que de otra forma se hace muy difícil la comprensión del compilador, y se pueden corregir, quizás más fácilmente, errores de muy difícil localización, como es la ambigüedad en el reconocimiento de ciertas sentencias.
La gramática que acepta el analizador sintáctico es una gramática de contexto libre:
Gramática: 
· G (N, T, P, S) N = No terminales. 
· T = Terminales. 
· P = Reglas de Producción. 
· S = Axioma Inicial. 
Ejemplo: Se considera la gramática que reconoce las operaciones aritméticas.
1. E E + T 
2. | T 
3. T T * F 
4. | F 
5. F ID 
6. | NUM 
7. | ( E ) 
En el que: 
· N = {E, T, F} están a la izquierda de la regla. 
· T = {ID, NUM, ( ,) ,+ ,*} 
· P = Son las siete reglas de producción. 
· S = Axioma inicial. 
· Podría ser cualquiera, en este caso es E.
5.2 GRAMÁTICAS LIBRES DE CONTEXTO (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.3 ÁRBOLES 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 nodos 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:
5.4 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:
1. Variables accesibles:
· Si existe una derivación desde el símbolo inicial que contiene X, es decir, existe $ → * α Xβ donde α, β Є∑*
2. Variables generativas:
· Si existe una derivación desde el la variable que produce una sentencia, es decir, existe X →* ω donde ω Є *T.
3. 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.5 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.6 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.
5.7 TIPOS DE ANALIZADORES SINTACTICOS
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 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.9 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.
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 enla sobrecarga.
· Funciones polimórficas: Son aquellas que trabajan con argumentos cuyo tipo puede cambiaren distintas llamadas a la función.
5.10 GENERADORES DE ANALIZADORES SINTACTICOS
ANTLR: (ANother Tool for Language Recognition; en español "otra herramienta para reconocimiento de lenguajes") es una herramienta creada principalmente por Terence Parr, que opera sobre lenguajes, proporcionando un marco para construir reconocedores (parsers), intérpretes, compiladores y traductores de lenguajes a partir de las descripciones gramaticales de los mismos (conteniendo acciones semánticas a realizarse en varios lenguajes de programación).
GNU bison: Es un programa generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos, se usa normalmente acompañado de flex aunque los analizadores léxicos se pueden también obtener de otras formas.
Grammatica: Es un generador de analizadores sintácticos de C# y Java libre. Es similar a otras herramientas como Yacc o ANTLR. Grammatica soporta el algoritmo LL(k) para gramáticas con un número ilimitado de tokens de anticipación. Está bastante bien probado, y ha sido auto compilado desde la versión 0.1. La documentación contiene una lista completa de características, así como una comparación con otros generadores de analizadores.
JavaCC: (Java Compiler Compiler) es un generador de analizadores sintácticos de código abierto para el lenguaje de programación Java. JavaCC es similar a Yacc en que genera un parser para una gramática presentada en notación BNF, con la diferencia de que la salida es en código Java. A diferencia de Yacc, JavaCC genera analizadores descendentes (top-down), lo que lo limita a la clase de gramáticas LL (K) (en particular, la recursión desde izquierda no se puede usar). El constructor de árboles que lo acompaña, JJTree, construye árboles de abajo hacia arriba (bottom-up).
Yacc: Es un programa para generar analizadores sintácticos. Las siglas del nombre significan Yet Another Compiler-Compiler, es decir, "Otro generador de compiladores más". Genera un analizador sintáctico (la parte de un compilador que comprueba que la estructura del código fuente se ajusta a la especificación sintáctica del lenguaje) basado en una gramática analíticaescrita en una notación similar a la BNF. Yacc genera el código para el analizador sintáctico en el Lenguaje de programación C.
ACTIVIDAD 1. IDENTIFICAR LA NOTACIÓN FORMAL DE UNA GRAMÁTICA
Una gramática formal es un conjunto de reglas para reescribir cadenas de caracteres, junto con un símbolo inicial desde el cual debe comenzar la reescritura. Por lo tanto, una gramática formal generalmente se piensa como una generadora de lenguajes. Sin embargo, a veces también puede ser usada como la base para un "reconocedor": una función que determina si una cadena cualquiera pertenece a un lenguaje o es gramaticalmente incorrecta.
Hay distintos tipos de gramáticas formales que generan lenguajes formales Imaginemos una gramática con estas dos reglas:
A → bA
A → c
El elemento en mayúsculas es el símbolo inicial. Los elementos en minúsculas son los símbolos terminales. Para generar cadenas de caracteres, la idea es sustituir el símbolo inicial de la izquierda por los símbolos de la derecha, y luego repetir el proceso hasta que sólo haya símbolos terminales. Por ejemplo:
A → bA → bbA → bbbA → bbbc
Esta gramática da lugar a un lenguaje formal que consiste en el conjunto de todas las cadenas de caracteres que pueden ser generadas por medio ellas. Por ejemplo: bbbc, bbbbbbbbc, c, bc, etc.
Veamos que existen unas definiciones especiales como ORACIÓN, SUJETO, etc. que no aparecen en la frase final formada. Son unas entidades abstractas denominadas "categorías sintácticas" que no son utilizables en una oración (tienen un papel similar al de las categorías gramaticales de las lenguas naturales). E igualmente el mismo sistema permite derivar otras oraciones similares usando formas las formas léxicas entre paréntesis:
	Det
	N
	V
	COMP
	El
	niño
hombre
anciano
	duerme
ríe
come
	plácidamente
intranquilo
Las categorías sintácticas definen la estructura del lenguaje representando porciones más o menos grandes de las frases. Existe una jerarquía interna entre las categorías sintácticas.
La categoría superior sería la FRASE que representa una oración válida en lengua castellana.
Por debajo de ella se encuentran sus componentes. Ninguna de estas categorías da lugar a frases válidas solo la categoría superior.
Al finalizar toda la jerarquía llegamos a las palabras que son las unidades mínimas con significado que puede adoptar una frase.
Aplicando las jerarquías y sustituyendo elementos, llegamos al punto en donde todas las categorías sintácticas se han convertido en palabras, obteniendo por tanto una oración válida; como por ejemplo: El niño corre. Este proceso se llama producción o generación.
ACTIVIDAD 2. BUSCAR LA SINTAXIS DE LA CONSTRUCCIÓN DE LOS LENGUAJES DE PROGRAMACIÓN POR MEDIO DE GLC O UTILIZANDO NOTACIÓN BNF (BACKUS-NAUR-FORM)
La notación de Backus-Naur, también conocida por sus denominaciones inglesas Backus-Naur form (BNF), Backus-Naur formalism o Backus normal form, es un metalenguaje usado para expresar gramáticas libres de contexto: es decir, una manera formal de describir lenguajes formales.
El BNF se utiliza extensamente como notación para las gramáticas de los lenguajes de programación, de los sistemas de comando y de los protocolos de comunicación, así como una notación para representar partes de las gramáticas de la lengua natural (por ejemplo, el metro en la poesía de Venpa). La mayoría de los libros de textos para la teoría o la semántica del lenguaje de programación documentan el lenguaje de programación en BNF.
Algunas variantes, tales como la Augmented Backus-Naur Form (ABNF) y la Extended Backus–Naur Form (EBNF), tienen su propia documentación.
Una especificación de BNF es un sistema de reglas de derivación, escrito como:
<símbolo>:: = <expresión con símbolos>
donde <símbolo> es un no terminal, y la expresión consiste en secuencias de símbolos o secuencias separadas por la barra vertical, '|', indicando una opción, el conjunto es una posible substitución para el símbolo a la izquierda. Los símbolos que nunca aparecen en un lado izquierdo son terminales.
Ejemplo
Como ejemplo, considere este BNF para una dirección postal de los EE.UU.
<dirección postal> ::= <nombre> <dirección> <apartado postal>
<nombre> ::= <personal> <apellido> [<trato>] <EOL> 
 | <personal> <nombre>
<personal> ::= <primer nombre> | <inicial> "."
<direccion> ::= [<dpto>] <numero de la casa> <nombre de la calle> <EOL>
<apartado postal> ::= <ciudad> "," <código estado> <código postal> <EOL>
Esto se traduce a español como:
· Una dirección postal consiste en un nombre, seguido por una dirección, seguida por un apartado postal.
· Una parte «personal» consiste en un nombre o una inicial seguido(a) por un punto.
· Un nombre consiste de: una parte personal seguida por un apellido seguido opcionalmente por una jerarquía o el trato que se la da a la persona (Jr., Sr., o número dinástico) y un salto de línea (end-of-line), o bien una parte personal seguida por un nombre (esta regla ilustra el uso de la repetición en BNFs, cubriendo el caso de la gente que utiliza múltiples nombres y los nombres medios o las iniciales).
· Una dirección consiste de una especificación opcional del departamento, seguido de un número de casa, seguido por el nombre de la calle, seguido por un salto de línea (end-of-line).
· Un apartado postal consiste de una ciudad, seguida por una coma, seguida por un código del estado (recuerde que es un ejemplo que ocurre en EE.UU.), seguido por un código postal y este seguido por un salto de línea (end-of-line).
ACTIVIDAD 3. INVESTIGAR LAS FORMAS NORMALES DE CHOMSKY
Diremos que una gramática incontextual G=(N,T,P,S) que no genera la cadena vacía, está en FNC cuando todas sus reglas son de la forma:
· A → BC con A,B,C ∈ N
· A → a, conA,B ∈ N y a ∈T
Teorema. Todo lenguaje incontextual L que no incluye la cadena vacía, es generado por una gramática en FNC. Una gramática libre de contexto G=(N,T,P,S) se dice estar en forma normal de Chomsky si sus producciones son de cualquiera de las dos formas:
Toda gramática libre de contexto G=(V,T,P,S) que no genere a la palabra vacía se puede transformar en una gramática libre de contexto G'=(V',T,P',S') en forma normal de Chomsky. En efecto, dada una gramática G, apliquemos el último procedimiento de la sección anterior para transformar a G en una gramática G'' sin variables inútiles ni producciones vacías ni producciones unitarias equivalente a G. A las producciones que quedasen de la forma con y las dejamos sin cambio alguno. A cada producción de la forma, con y, la transformamos en una sucesión de producciones de la forma siguiente: A cada símbolo terminal que aparezca en la palabra le asociamos una variable nueva Xa e incorporamos la producción. Así pues, las producciones que no sean de la forma con X variable y a terminal, han de ser de la forma, con todos variables. Para cada una de estas últimas producciones introducimos k-2 nuevas variables e incorporamos la sucesión de producciones.
PASOS PARA LA TRANSFORMACIÓN DE UNA GRAMÁTICA A LA FNC
1º Eliminamos reglas unitarias.
· A -> Ac
· A -> w
Primero verificamos si en la gramática no hay reglas unitarias que obstruyan el desarrollo de FNC. Un ejemplo de una regla unitaria seria:
· A -> X
· X -> z
Como se puede observar, un No Terminal A deriva en otro No Terminal X, que a su vez deriva en un Terminal z, esto es redundante y por lo tanto se procede a eliminar el No Terminal X y pasando el Terminal z al No Terminal A
2º Eliminamos reglas no productivas
Una regla no productiva consiste en un No Terminal que nunca es accesible desde el No Terminal principal y sus respectivas derivaciones, del mismo o de las que provoquen sus No Terminal que se encuentren en su propia derivación. Un ejemplo de una regla no productiva seria:
· A -> AZ
· W -> X
· Z -> c
En el ejemplo anterior el No Terminal W es una regla no productiva porque no es accesible desde el No Terminal principal que es A, ni de su derivación correspondiente que es AZ.
Nota: Este paso es omitido en el programa, por lo que no se verifica si un No Terminal es improductivo, por lo tanto, el usuario debe asegurarse de no introducir éste tipos de reglas.
3º Se procede a dar el formato correspondiente de la FNC.
La FNC (Forma Normal de Chomsky) sigue dos reglas básicas y únicas para tener el formato debido, estás son:
1. Un No Terminal solo puede derivarse en otros dos No Terminales.
2. Un No Terminal solo puede derivar en un Terminal.
Para la explicación de estas dos propiedades procedemos con un ejemplo: Tenemos la siguiente gramática:
· A -> cB+
· B -> q
Nota: La gramática anterior no tiene ni reglas unitarias ni reglas no productivas, con lo que procedemos con el paso 3º. Observemos la primera producción: A -> cB+
1) Este No Terminal A deriva en cB+ donde como primer elemento de esta es un elemento Terminal, entonces procedemos a crear un No Terminal nuevo con este elemento y se lo agregamos al no Terminal A, respetando el orden de la gramática.
· A -> ZB+
· Z -> c
2) Una de las propiedades para la FNC es que un No Terminal solo puede derivar en otros dos No terminales, en nuestro ejemplo, tenemos el No Terminal A que deriva en ZB+, este contiene otro elemento terminal más, creamos un nuevo No Terminal para respetar la propiedad anteriormente descrita.
· A -> ZY
· Z -> c
· Y -> B+
3) Podemos ver que los No Terminal A y Z cumplen con las propiedades de la FNC, excepto el No Terminal Y que deriva en un No Terminal y un Terminal, por lo que procedemos a crear el último No Terminal que cumpla la FNC.
· A -> ZY
· Z -> c
· Y -> BX
· X -> +
Por lo que se obtiene como resultado:
· A -> ZY
· Z -> c
· Y -> BX
· X -> +
· B -> q
ACTIVIDAD 4. CONSTRUIR UNA GLC A PARTIR DE LOS DIAGRAMAS DE SINTAXIS
ACTIVIDAD 5. ELIMINAR LA AMBIGÜEDAD DE UNA GRAMÁTICA
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 árboles de derivación. En caso de que toda cadena w Î L(G) tenga un único árbol de derivación, la gramática no es ambigua.
La gramática S ® aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda S Þ aS Þ aa S Þ Sa Þ aa 
Esta gramática genera el lenguaje a+ que también es el lenguaje generado por la gramática no ambigua S ® aS | a.
Para eliminar la ambigüedad:
· No existe un algoritmo que nos indique si una GIC es ambigua
· Existen LIC que sólo tienen GIC ambiguas: inherentemente ambiguos
· Para las construcciones de los lenguajes de programación comunes existen técnicas para la eliminación de la ambigüedad
Ejemplo: causas de ambigüedad en la siguiente gramática
• No se respeta la precedencia de operadores
• una secuencia de operadores idénticos puede agruparse desde la izquierda y desde la derecha. Lo convencional es agrupar desde la izquierda.
Ejemplo: modificamos la gramática para forzar la precedencia
ACTIVIDAD 6. CONOCER LA NOTACIÓN DE LOS 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).
Constan de una serie de cajas o símbolos geométricos conectados por arcos dirigidos. Veamos las reglas que rigen la construcción de cada grafo:
 
 1. Cada símbolo terminal se representa por su nombre encerrado en un círculo o en una caja de bordes circulares.
Terminal: Un símbolo es terminal cuando tiene entidad propia y se describe por sí mismo.
2. Cada símbolo no terminal se representa por su nombre encerrado en un rectángulo.
No Terminal: Un símbolo es no terminal cuando requiere una explicación mediante una regla o producción.
3. Para las producciones que tengan varias alternativas, el grafo resultante será del tipo:
4. Para las producciones que contengan una serie concatenada de símbolos terminales y/o no terminales, bastara simplemente con conectar simplemente a continuación del otro grafo de cada símbolo.
5. Para las producciones que tengan cero, una o más repeticiones de un símbolo la representación será: 
Ejemplo: Diagrama sintáctico para expresiones aritméticas.
CONCLUSIÓN
El trabajo descrito en esta tesis representa una aportación significativa y original al análisis sintáctico de los lenguajes de adjunción de árboles y por extensión al procesamiento del lenguaje natural, a la inteligencia artificial, y a la teoría de autómatas y lenguajes formales. El panorama al comenzar el trabajo que daría lugar a esta memoria consistía en un grupo disperso de algoritmos para el análisis sintáctico de gramáticas de adjunción de árboles y apenas un par de algoritmos para el análisis sintáctico de las gramáticas lineales de índices. En esta memoria se ha mostrado que es posible establecer un camino evolutivo continuo en el que se sitúan los algoritmos de análisis sintáctico que incorporan las estrategias de análisis más importantes, tanto para el caso de las gramáticas de adjunción de árboles como para el caso de las gramáticas lineales de índices. Los diferentes algoritmos se han definido con esquemas de análisis sintáctico, de tal modo que los algoritmos más complejos se derivan a partir de los menos complejos aplicando una secuencia de transformaciones simples. En el caso de las gramáticas lineales de índices el resultado es doblemente interesante, pues si bien se ha esgrimido a su favor su adecuación como formalismo intermedio para el análisis de gramáticas de adjunción de árboles, lo cierto es que numerosas estrategias de análisis para estas últimas no se hallaban incorporadas a ningún algoritmo de análisis sintáctico para gramáticas lineales de índices. En consecuencia, era necesario sacrificar la estrategia de análisis sise optaba por este enfoque, lo que limitaba enormemente su aplicación práctica. Con el trabajo desarrollado en esta memoria hemos salvado ese obstáculo definiendo algoritmos de análisis sintáctico para gramáticas lineales de índices que incorporan la versión equivalente de las estrategias de análisis más populares para gramáticas de adjunción de árboles.
REFERENCIAS
Aho, A. S. (1990). Compiladores: principios, tecnicas y herramientas. 
Introducción al análisis sintáctico. (16 de octubre de 2016). Obtenido de Leer y escribir: https://leeryescribirblog.wordpress.com/2016/10/16/introduccion-al-analisis-sintactico/
lenguajes y automatas. (05 de JUNIO de 2018). Obtenido de UNIDAD 5 5. Gramáticas: http://robertomartinezlopeslya.blogspot.com/2018/06/unidad-5.html
Louden, K. (1997). Compiler Construction: Principles and Practice. 
Lovelle, J. M. (Oviedo, Abril 1995). ANÁLISIS SINTÁCTICO EN PROCESADORES DE LENGUAJE (2ª Edición ed.). (U. d. Departamento de Matemáticas, Ed.) Catedrático de E.U. de Lenguajes y Sistemas Informáticos. Recuperado el 09 de DICIEMBRE de 2020, de http://di002.edv.uniovi.es/~cueva/publicaciones/monografias/Cuaderno-61-Matematicas-Sintactico.pdf
Reyes, J. V. (s.f.). Análisis Sintáctico. Obtenido de https://www.cartagena99.com/recursos/alumnos/apuntes/PDL_06_Tema%203_Analisis%20sintactico.pdf
Rojas, M. d. (s.f.). Tema 3. Análisis Sintáctico. Obtenido de http://www.lcc.uma.es/~galvez/ftp/tci/tictema3.pdf
Rufino, M. J. (s.f.). INTRODUCCIÓN AL ANÁLISIS SINTÁCTICO. Obtenido de https://www.hf.uio.no/ilos/tjenester/kunnskap/sprak/nettsprak/spansk/portal/introsintax2.pdf
TEMA 3. INTRODUCCION AL ANALISIS SINTACTICO. (s.f.). Obtenido de http://informatica.uv.es/docencia/iiguia/asignatu/2000/PL/2007/tema3.pdf