UNIDAD IV ANALISIS SINTACTICO

4.1 INTRODUCCIÓN A LAS GRAMÁTICAS LIBRES DE CONTEXTO Y ÁRBOLES DE DERIVACIÓN.

Gramática

_ Permite definir un lenguaje mediante reglas que nos permiten generar o producir cadenas de un lenguaje.

_ Estas gramáticas son similares a las gramáticas de los lenguajes naturales, pero mucho más restrictivas y sencillas.

_ Un ejemplo de regla de una gramática:

Oración _ Sujeto predicado

_ Estas reglas se suelen llamar reglas de reescritura: el símbolo Oración se puede reescribir por el símbolo Sujeto seguido del símbolo Predicado.

Autómata:

Al igual que con los lenguajes regulares podemos definir un autómata como una máquina reconocedora de cadenas (palabras) de un determinado lenguaje.

Los autómatas con los que trabajaremos en este tema son algo más complejos que los AF.

UN EJEMPLO

ORACIÓN à SUJETO PREDICADO | PREDICADO

SUJETO à ARTÍCULO NOMBRE

ARTICULO à el | la

NOMBRE à casa | niño

PREDICADOà VERBO COMPLEMENTO

VERBO àcorre | es

COMPLEMENTO àbien | obediente | bonita

ÁRBOLES DE DERIVACION

Derivaciones por la izquierda y derecha:

Existen básicamente dos formas de describir como en una cierta gramática una cadena puede ser derivada desde el símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por la izquierda. Por ejemplo, si tomamos la siguiente gramática:

(1) S → S + S

(2) S → 1

4.2 DIAGRAMAS DE SINTAXIS

Es otra forma (al igual que los árboles de derivación) de especificar gramáticas del tipo

La característica de este esquema es que permite ver las derivaciones al Instante de que ocurren.

Todo diagrama de sintaxis posee un origen y un destino, que no se suelen representar explícitamente, sino que se asume que el origen se encuentra a la izquierda del diagrama y el destino a la derecha.

Cada arco con origen en " y destino en $ representa que el símbolo " puede ir seguido del $ (pudiendo ser " y $ tanto terminales como no terminales). De esta forma todos los posibles caminos desde el inicio del grafo hasta el final, representan formas sentenciales válidas.

Demostraremos que los diagramas de sintaxis permiten representar las mismas gramáticas que la notación BNF, por inducción sobre las operaciones básicas de BNF:

4.3 PRECEDENCIA DE OPERADORES

La precedencia de operadores es de vital importancia en el proceso de análisis sintáctico ya que nos representará la forma en que debe construirse el árbol de derivación.

En aritmética existen prioridades, por ejemplo: * y / tienen preferencia sobre + y -. () indican la máxima prioridad.

Prioridad de operadores

• La instrucción a = b + c / 2 en la mayoría de los lenguajes no se evalúa de la forma a = (b + c) /2, sino de la forma a = b + (c/2)

• La forma de evaluación depende de cómo se construyan los operadores, ya sea en infijo, postfijo o prefijo.

• Las operaciones se realizan de abajo hacia arriba.

4.4 ANALIZADOR SINTÁCTICO

Un analizador sintáctico (Parser) es un programa que reconoce si una o varias cadenas de caracteres forman parte de un determinado lenguaje. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto.

Los analizadores sintácticos fueron extensivamente estudiados durante los años 70 del siglo XX, detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación de programas generadores de analizadores sintácticos a partir de una especificación de la sintaxis del lenguaje, tales y como YACC, GNU bison y javacc.

Es el proceso de determinar si una cadena dada puede ser generada por una gramática.

Los analizadores sintácticos de lenguajes de programación suele hacerse de izquierda a derecha, viendo un componente léxico a la vez

Los analizadores pueden clasificarse dependiendo de la forma en como se construyen los nodos del árbol de derivación sintáctico: ascendentes y descendentes.

• Las gramáticas se pueden expresar en forma BNF (Backus-Naur Form).

• El análisis sintáctico impone una estructura jerárquica.

id1 :=

id2 +

id3 *

60

Tipos de analizadores sintácticos

• LL (left to left) leen la cadena de izquierda a derecha y derivan por la izquierda

• LR (left to right)

• SàaA

• AàaBbC

• Bàb

• Càc

Analizador descendente (LL)

• Existen diferentes métodos de análisis sintáctico. La mayoría caen en una de dos

categorías: ascendentes y descendentes.Los ascendentes construyen el árbol desde las hojas hacia la raíz. Los descendentes lo hacen en modo inverso.

• Un analizador ampliamente utilizado se denomina método de análisis predictivo descendente recursivo que es muy sencillo.

Derivación izquierda:

• SàAaàaaBbCàaabbCàaabbc (1234)

• SàaAàaaBbCàaaBbcàaabbc (3421)

• LL(k) traductores “top-down”

• Un análisis anticipado de k caracteres

.SàaS|cA

• AàbA|cB|vacia

• BàcB|a| vacia

Construir cadena acbb

• SàaS o SàcA; al anticipar el primer símbolo

L={anabcn | n>0}

• SàaSc|aabc

• Se requiere una anticipación de por los

menos tres símbolos LL(3)

• SàaaAc

• AàSc|abc LL(1)

4.5 ADMINISTRACIÓN DE TABLAS DE SÍMBOLOS

• La tabla de símbolos se crea durante la fase de análisis léxico a través de los componentes léxicos, pero en el proceso de análisis sintáctico sufren algunas

modificaciones.

• Generalmente se agregan valores de tipo y significado para el análisis sintáctico.

4.6 MANEJO DE ERRORES SINTÁCTICOS Y SU RECUPERACIÓN

• Si los traductores tuvieran que procesar programas correctas el proceso de implantación se simplificaría mucho.

• ¿Cómo debe de responder un compilador de pascal a un código Fortran?

• Ningún método de recuperación de errores resuelve todos los problemas

Tipos de errores

• Léxicos: como escribir mal un identificador, palabra clave u operador.

• Sintácticos: como una expresión aritmética con paréntesis no equilibrados.

• Semánticos: como un operador aplicado a un operadorando incompatible.

• Lógicos: como una llamada infinitamente recursiva

• La mayoría de los errores se centra en la fase de análisis sintáctico.

• El manejador de errores debe:

• Informar la presencia de errores con claridad y exactitud.

• Recuperar de cada error con la suficiente rapidez como para detectar errores posibles.

• No debe retrasar de manera significativa el procesamiento de programas correctos.

• Debe indicar la línea del error y algún mensaje informativo

Estrategias de recuperación de errores

• Modo Pánico

• Nivel de Frase

• Producciones de error

• Corrección global

Recuperación en modo pánico

• Es el más sencillo de implantar.

• El analizador sintáctico desecha componentes léxicos hasta encontrar un carácter de sincronización. Estos caracteres son el punto y como (;) entre otros.

Recuperación en modo pánico

int a.b,c;

struct c {

….

}

main()

{

int a;

}

Recuperación a nivel de frase

• Esta técnica utiliza una corrección de caracteres adyacentes, ya sea por inserción, eliminación o intercambio.

• Esta técnica permite sustituir , por ;, etc. Son traductores que corrigen errores. Desafortunadamente para muchos casos no aplican por lo que no se utilizan demasiados.

Producciones de error

• Se pueden generar gramáticas para generar producciones de error y así de esta forma seguir con el proceso.

• La dificultad radica en el sentido de encontrar esas reglas gramaticales para generar error. En algunos casos sería inclusiva más extensa que la gramática del propio lenguaje.

• for(i<3,>

Corrección global

• Idealmente, sería recomendable que un traductor hiciera el mínimo de cambios para procesar una entrada inválida. Este algoritmo genera menores costos globales para realizar cambios.

• El problema radica en que el implementar estas estrategias son muy costosas en tiempo y espacio.

4.7 GENERADORES DE CÓDIGO PARA ANALIZADORES SINTÁCTICOS: YACC, BISON, BYACC, ANTLR, JAVACC.

YACC (YET ANOTHER COMPILERCOMPILER): provee una herramienta general para describir la entrada de un programa de computación. El usuario de YACC especifica las estructuras de su entrada, junto con el código que será invocado en la medida en que cada una de esas estructuras es reconocida.

YACC/BISON

• YACC convierte esa especificación en una subrutina que maneja el proceso de entrada.

La subrutina de entrada producida por YACC llama a la rutina provista por el usuario para devolver el próximo ítem básico de la entrada.

• GNU Bison es un generador de parsers de propósito general que convierte una descripción gramatical desde una gramática libre de contexto LALR en un programa en C para hacer el parser.

• Es utilizado para crear parsers para muchos lenguajes, desde simples calculadoras hasta lenguajes complejos.

• GNU Bison tiene compatibilidad con Yacc: todas las gramáticas bien escritas para Yacc, funcionan en Bison sin necesidad de ser modificadas.

• Cualquier persona que esté familiarizada con Yacc podría utilizar Bison sin problemas. Es necesaria experiencia con C para utilizar Bison.