INGENIERÍA

CIVIL INFORMÁTICA
UNIVERSIDAD DEL BÍO-BÍO

FUNDAMENTOS DE CIENCIAS DE LA COMPUTACION

PARSING Bottom Up
(SABLECC)

Luis Gajardo
lgajardo@ubiobio.cl
 RECORDANDO - TIPOS DE PARSING

Análisis Sintáctico
(Parsers)

Ascendente (Bottom-Up) Descendente (Top-Down)

Traductor Precedencia LR(K) LL(K) Esquema de

con pila traducción
autómata de
pila
Simple Operador SLR LR LALR LL(1)
canónico
 RECORDANDO - ¿QUÉ ES EL PARSING?
• También llamado análisis sintáctico, es el proceso por el cual se analiza
una secuencia de tokens o palabras para determinar su estructura
gramatical respecto a una gramática formal.

Tokens
…
int
suma
int suma(int x, int y) { int z = x + y;
int z; x
z = x + y; Análisis Análisis
return z; Léxico Sintáctico
int
}
y
)
… {
… Arbol de análisis
} sintáctico

Programa fuente
(cadena de entrada)
…
exp → exp + term ;
…

Gramática Libre de
Autómata Finito Contexto
Determinístico (reglas del lenguaje)
 ¿QUÉ ES SABLECC?

• SableCC fue creado por Etienne Gagnon como tesis de magister

en la Universidad de McGill, Canada.

• Es un entorno orientado a objeto que permite la construcción de analizadores

sintácticos o compiladores usando el lenguaje Java.

• Los compiladores construidos son de tipo Ascendentes (Bottom-Up o LR).

• SableCC provee:
• Generador de Lexer (analizador léxico) usando AFD.
• Generador de Parser (analizador sintáctico) usando gramáticas LALR(1).
• Genera las clases java que representan el árbol de parsing (o derivación).
• Genera un visitador para el árbol.
• Generador de Pretty-printer

• SableCC es multiplataforma.

• El sitio web de este proyecto es http://www.sablecc.org

 INSTALACIÓN DE SABLECC
• Descargar el archivo sablecc-3.7.zip desde el sitio web.

• La distribución sirve tanto para Windows como para Linux.

• En Windows:
• Descomprimir el archivo en la raíz del disco C (u otro seleccionado)
• Agregar a la variable PATH la siguiente ruta: c:\sablecc-3.7\bin
• Editar el archivo sablecc.bat ubicado dentro de la carpeta bin y escribir
en el la siguiente ruta absoluta:
c:\sablecc-3.7\lib\sablecc.jar
• Ejecutar sablecc desde cualquier directorio.

• En Linux:
• Descomprimir el archivo en HOME
• Agregar a la variable PATH la siguiente ruta: $HOME/sablecc-3.7/bin
• Editar el archivo sablecc ubicado en la carpeta bin y colocar la ruta
absoluta a sablecc.jar.
 ETAPAS AL DESARROLLAR CON SABLECC

• Para construir un compilador con SableCC se requieren los siguientes pasos:

1. Crear un archivo de especificación

de SableCC que contenga la
definición léxica y gramatical del
lenguaje a construir.

2. Ejecutar SableCC con el archivo con

la especificación para generar el
entorno de desarrollo.

3. Crear una o más clases,

posiblemente heredadas de las
clases de SableCC. (opcional)

4. Crear una clase inicial con un

método main() para el analizador
construido.

5. Compilar con java.

 EJEMPLO – GRAM. DE UNA CALCULADORA

• De aquí en adelante utilizaremos un caso práctico con una gramática.

• Crearemos una gramática para una calculadora (suma, resta, multiplicación,

división y módulo).

• Ejemplo de expresiones válidas:

• 3 + 20
• 45 * 2 - 10
• 10 % 2
• (45 + 36/2) * 3 + 5 * 2

• Nuestro archivo puede llamarse: postfix.grammar

 ETAPA 1: ARCHIVO DE ESPECIFICACIÓN
• postfix.grammar es un archivo de texto ASCII.

• Contiene las definiciones léxicas (tokens) y especificación de producciones

(reglas) de la gramática.

[<package declaration>]

[<helper declarations>]

[<states declarations>]

[<token declarations>] SableCC

[<ignored tokens>]

[<productions>]

States declarations típicamente no se utiliza.

 ARCHIVO: PACKAGE DECLARATION

• Permite definir el directorio raíz a partir del cual SableCC generará los
archivos y subdirectorios de nuestro proyecto.

• Ejemplo: suponiendo que nuestra aplicación se llama simplyc

Package tarea.java.cc.simplyc;

Esto generará la siguiente estructura de directorios:

Estos directorios son

generados por SableCC
 ARCHIVO: HELPER DECLARATIONS

• Esta sección del archivo permite definir expresiones que nos ayudan a definir
otras más complejas.

• Ejemplo: supongamos que tenemos ya • Otros ejemplos:

definida la siguiente expresión regular:
id = [‘a’ .. ‘z’] ([‘a’ .. ‘z’] | [‘0’ .. ‘9’])* a = ‘a’ | ‘A’ ;
b = ‘b’ | ‘B’ ;
e = ‘e’ | ‘E’ ;
• Desearíamos tener una forma más g = ‘g’ | ‘G’ ;
abreviada de representar lo mismo. …
w = ‘w’ | ‘W’;
cr = 13 ; // retorno de carro o enter
• Si declaramos en la sección Helper lo lf = 10 ; // alimentación de línea
siguiente: tab = 9 ; // tabulador
ascii_char = [32 .. 127] ;
letter = [‘a’ .. ‘z’]; blank = ‘ ’ ;
digit = [‘0’ .. ‘9’]; digit = [‘0’ .. ‘9’] ;
letter = [[‘a’ .. ‘z’] + [‘A’ .. ‘Z’]] ;
l_brace = ‘{’ ;
• Podríamos usar en Token declarations r_brace = ‘}’ ;
la siguiente expresión: l_paren_star = ‘(*’ ;
r_paren_star = ‘*)’ ;
id = letter (letter | digit)*
 ARCHIVO: TOKEN DECLARATIONS
• Esta sección permite definir los tokens o símbolos terminales más importantes
de nuestra gramática.

• Se debe decidir que declaraciones colocar en Helper y cuales, en Token,

aunque podríamos tenerlas todas en Tokens.

• Ejemplos de tokens:

Tokens
while = 'while';
begin = 'begin';
end = 'end';
do = 'do';
if = 'if';
then = 'then';
else = 'else';
semi = ';';
assign = '=';
whitespace = (' ' | '\t' | '\n')+;
id = ['a'..'z'](['a'..'z']|['0'..'9'])*;
 ARCHIVO: IGNORED TOKENS
• Permite indicar cuáles tokens ignorar.

• Ejemplo:

Ignored tokens Helper

tab = 9
blank cr = 13
comment lf = 10
ignorar los
eol = cr lf | cr | lf espacios en
blank = (‘ ‘ | tab | eol)+ blanco

• La definición de blank y comment puede ubicarse en la sección Helper.

Típicamente un lenguaje de programación ignora los comentarios y no forman
parte del proceso de compilación, es decir, no son procesados por lo cual en
este caso esta sección es muy útil.
 ARCHIVO: PRODUCTIONS

• En esta sección se definen las producciones o reglas de la gramática del

lenguaje.

• Esta definición se realiza utilizando el formato BNF (Backus Naur Form)

• Ejemplo:

Productions

expression =
{plus} expression plus number |
{minus} expression minus number | Permite definir alternativas
{number} number;
Otorga un nombre a cada alternativa de la producción
 ETAPA1 EJEMPLO

• Según la estructura descrita, la gramática de la calculadora quedaría así:

• Este archivo debe ser guardado en el directorio raíz de nuestro proyecto.

 ETAPA 2: EJECUTAR SABLECC
• Para generar el entorno de desarrollo ejecutamos el siguiente comando:
$sablecc postfix.grammar
...
-- Generating parser for postfix.grammar in E:\sw-en-uso\sablecctest
Adding productions and alternative of section AST.
Verifying identifiers.
Verifying ast identifiers.
Adding empty productions and empty alternative transformation if necessary.
Adding productions and alternative transformation if necessary.
computing alternative symbol table identifiers.
Verifying production transform identifiers.
Verifying ast alternatives transform identifiers.
Generating token classes.
Generating production classes. • Estructura de directorios
Generating alternative classes.
Generating analysis classes.
generada:
Generating utility classes.
Generating the lexer.
State: INITIAL
- Constructing NFA.
.......................
- Constructing DFA.
......................................
............
- resolving ACCEPT states.
Generating the parser.
..................
..................
..................
 ETAPA 4: CREAR CLASE INICIAL

• La clase inicial, será aquella que contenga el método estático main(), nuestro
punto de enlace con el exterior. En este caso la clase se llama Analizer.

Ejemplo para leer

un archivo
 ETAPA 5: COMPILAR Y EJECUTAR

• Para compilar el programa:

$javac postfix\Analizer.java

• Para ejecutar el compilador

$java postfix.Analizer
$(45+36/2)*3+5*2 enter ctrl z enter

• Si la expresión es aceptada, entonces el analizador no debería hacer

nada visualmente, ya que aún no hemos programado la semántica
asociada.

• Si la expresión no es aceptada debería retornar algún error, incluso

terminar abruptamente debido a que tampoco hemos implementado el
manejo de errores.
 AGREGAR FUNCIONALIDAD ADICIONAL
• Es posible agregar comportamientos distintos cuando se ejecuta la clase
Analizer (la inicial).

• Por ejemplo:
• Permitir que se calcule la expresión aritmética entregando el resultado
final.
• Imprimir el árbol de derivaciones para la expresión

• Para lograr lo anterior, se acostumbra a trabajar con un árbol de parsing, el

cual se puede recorrer e ir realizando las operaciones necesarias en cada
nodo.
 ÁRBOL DE PARSING
• SableCC construye automáticamente un conjunto de clases que representan
los nodos del árbol de parsing.

• Un ejemplo del árbol real que se crea en memoria para un programa analizado
es el siguiente:
 CLASES CREADAS POR SABLECC
• Las clases generadas automáticamente por SableCC se organizan en 4
directorios:

 contiene las clases que implementan un patrón de diseño llamado Visitor

(visitador) que permite recorrer todos los nodos del árbol realizando alguna
analaysis
actividad que defina el usuario. La clase DepthFirstAdapter constituye la clase
abstracta base del visitador, extendiéndola podemos reescribir los métodos que
necesitemos para realizar alguna acción sobre algún nodo específico.


lexer
contiene la clase Lexer, entre otras, la cual implementa el analizador léxico, este
es el primero que debe ser invocado al comenzar la compilación.


node
contiene todas las clases que representan la gramática, estas clases se utilizan
para construir el árbol de parsing.


parser
contiene la clase Parser, entre otras, la cual permite realizar el análisis
sintáctico (chequeando el programa de entrada contra las producciones de la
gramática).
 CLASES DEL ÁRBOL GENERADO

• Por defecto SableCC provee dos clases para recorrer el árbol:

• DepthFirstAdapter: que lo recorre primero en profundidad

• ReversedDepthFirstAdapter: que lo recorre primero en horizontal y luego
en vertical (o profundidad).

• Consideremos la primera clase del árbol (la raíz) llamada Start.

Start
PExpr EOF

• Esta clase posee dos atributos, Una expresión PExpr y un fin de archivo
EOF.

• La clase Start siempre será la primera, no importa la gramática que

utilicemos.
 ¿CÓMO FUNCIONA UN VISITADOR?
• Los métodos que visitan esta clase (Start) se ubican en el archivo
DepthFirstAdapter y tienen la siguiente forma:

public class DepthFirstAdapter extends AnalysisAdapter {

public void inStart(Start node) {

La palabra “case” se antepone a
defaultIn(node);
}
todos los métodos que representan
un nodo del árbol en el Visitor.
public void outStart(Start node) {
defaultOut(node); En este caso caseStart visita a una
} instancia de la clase Start del árbol:
public void defaultIn(Node node) { }
1. Primero se invoca a un método
public void defaultOut(Node node) { }
(in…) que ejecuta todo lo que
queramos hacer antes de ingresar
public void caseStart(Start node) { a los hijos de este nodo.
inStart(node); 2. Luego se visitan los hijos
node.getPExpr().apply(this); 3. Finalmente se invoca a otro
node.getEOF().apply(this); método (out…) que ejecuta todo lo
outStart(node);
que queramos hacer antes de salir
}
...
de la clase.
 EJEMPLO: RECORRER EL ÁRBOL GENERADO
• Un ejemplo sencillo podría recorrer el árbol y traducir la expresión aritmética
ingresada en infija a postfija.
Expresión infija: (45+36/2)*3+5*2
Expresión postfija: 45 36 2 / + 3 * 5 2 * +

1
TLPar No imprime El recorrido sería el siguiente:
nada

2 3 10

9 Debemos imprimir
5 los operadores
al salir de cada
expresión
8

7
4
6
EJEMPLO: RECORRER EL ÁRBOL GENERADO

• Primero creamos la clase traductora Translation (ubicada en postfix), la

cual extenderá de DepthFirstAdapter.

class Translation
extends DepthFirstAdapter

DepthFirstAdapter.java Translation.java

• Luego sobre-escribiremos aquellos métodos en los cuales se tenga que

traducir alguna parte de la expresión.
 EJEMPLO: RECORRER EL ÁRBOL GENERADO
package postfix;
import postfix.analysis.*; Se deben importar las clases para el
import postfix.node.*; análisis (visitor) y las clases del árbol

Se deben extender del

class Translation extends DepthFirstAdapter {
Visitor Base

4 public void caseTNumber(TNumber node) { Sobre escritura del

6 //Cuando encontremos un número, lo imprimimos método que representa
System.out.print(node); a un número
7 }

public void outAPlusExpr(APlusExpr node) {

3 //Al salir de {plus} en Expr, imprimimos el signo +
System.out.print(node.getPlus());
}

public void outAMinusExpr(AMinusExpr node) {

//Al salir de {minus} en Expr, imprimimos el signo -
System.out.print(node.getMinus());
}
 EJEMPLO: RECORRER EL ÁRBOL GENERADO
public void outAMultFactor(AMultFactor node) {
//Al salir de {mult} en Factor, imprimimos asterisco
System.out.print(node.getMult());
}

public void outADivFactor(ADivFactor node) {

5 //Al salir de {div} en Factor, imprimimos slash (/)
System.out.print(node.getDiv());
}

public void outAModFactor(AModFactor node) {

//Al salir de {mod} en Factor, imprimimos mod
System.out.print(node.getMod());
}
}

• Los métodos que no aparecen aquí no fueron sobre escritos y por lo tanto
permanecen igual que en la clase DepthFirstAdapter.
EJEMPLO: RECORRER EL ÁRBOL GENERADO
• En el método main() de Analizer se instancia e invoca la clase Translation,
así:
...
tree.apply (new Translation());
...

• Compilar:
>javac postfix\Analizer.java

• Ejecutar:
>java postfix.Analizer
Ingrese la expresion aritmetica:
(45+36/2)*3+5*2 infija
^Z
45 36 2 / + 3 * 5 2 * + posfija