Gramáticas y uso de cup

Universidad de San Carlos
Facultad de Ingeniería
Lab. De Organización de Lenguajes y Compiladores 1
Aux. Rodely Navarro

Investigación de Laboratorio

Diego Fernando Valle Morales
Carné 200611243
Guatemala, 26 de diciembre de 2010

Introducción

El análisis sintáctico es el segundo paso en el proceso de compilación, se basa fundamentalmente en seguir un orden específico de tokens,que conocemos como gramática.
La gramática como tal, está estructurada en producciones, la cual a su vez contiene terminales y no terminales, los cuales son los distintos elementos de la gramática, podríamos decir que los no terminales, son representados por los distintos tokens derivados del análisis léxico.
Java Cup es la herramienta que nos permitirá programar de una forma sencilla lagramática e incluirle código java, ya que Cup, genera nuestra gramática, unida al resto de elementos genera las clases de Java que son necesarias para realizar un parser.

Análisis Sintáctico
Es el proceso mediante el cual se realiza la segunda fase del proceso de compilación, incluido dentro de la fase de análisis.
Gramática Independiente del contexto
Es aquella gramática que contiene cuatroelementos básicos:
1. Símbolos terminales: Son conocidos como tokens de la gramática.
2. No terminales: Son los elementos del lado izquierdo de una producción, antes de la flecha "->".
3. Producciones: Son las sentencias que se escriben en la gramática del lado derecho de la producción.
4. Símbolo inicial: Es el primer elemento de la gramática.
Ejemplo
Hacer una gramática que genere un conjuntode 1 seguido de un conjunto de 0, donde el número de 0’s debe ser par.
Exp -> unos ceros
ceros -> ceros 00 | 00
unos -> 1
|
|

Derivación
Es el proceso mediante el cual se revisa a través de una gramática, si se puede construir una expresión válida para el lenguaje. Hay dos formas de realizar este proceso:
1. Derivación por la derecha
2. Derivación por la izquierdaDerivación por la Derecha
Consiste en realizar el proceso de derivación iniciando con los no terminales de más a la derecha.
Derivación por la Izquierda
Consiste en realizar el proceso de derivación iniciando con los no terminales ubicados más a la izquierda.
Ejemplo
Con la gramática:
S ->E
E->E+E
| E-E
| E*E
| E/E
| id
| num
Realice el proceso de derivación por laizquierda y por la derecha para la siguiente cadena:
5/3-2

Por la Izquierda
S-> E
S-> E/E
S->num/E-E
S->num/num-E
S->num/num-num
Por la Derecha
S->E
S->E-E
S->E/E-num
S->E/num-num
S->num/num-num

Ambigüedad
Si una gramática genera más de una estructura a partir de la misma raíz con la misma cadena, dicha gramática es ambigua.
En el ejemplo anteriorvemos el resultado de una gramática ambigua, esto se puede apreciar con los árboles de derivación.
Ejemplo

Por la izquierda

Por la derecha

En conclusión podemos decir que la gramática es ambigua, ya que el árbol de derivación es distinto.

Java Cup
Es una herramienta desarrollada en Java para crear analizadores Sintácticos LALR. Después de crear un archivo cuya extensión es .cup y quecontiene las especificaciones del analizador, este genera dos clases en Java después de realizar su compilación: sym.java y parser.java
Sym.java
Es el que declara los símbolos terminales definidos dentro de la gramática, cada símbolo es representado por un número.
Parser.java
Es la clase en java que contiene todos los elementos necesarios para realizar un análisis tipo LALR.
Estructura de unarchivo .cup
La estructura general de este archivo se divide en cinco secciones:
1. Paquetes y sentencias: En esta sección se incluyen las librerías de CUP, y otras creadas por el usuario, si son necesarias, para la implementación de alguna función particular.
-------------------------------------------------
import java.io.*;
import java_cup.runtime.Symbol;
2. Código de Usuario: En...