INTRODUCCION |INGENIERIA DE SOFTWARE |CASE
LENGUAJES DE PROGRAMACION |AUTOMATAS FINITOS DETERMINISTAS
GRAMATICAS DESCENDENTES |GRAMATICAS AMBIGUAS |GENERANDO PATRONES EN LEXER |ANALISIS LRH y LR1 |EDITOR HTML

INGENIERIA DE SOFTWARE

¿Qué es la ingeniería del software?

1)"es el establecimiento y uso de principios de ingeniería orientados a obtener software económico, que sea fiable y funcione de manera eficiente sobre máquinas reales..."  Fritz Baver, 1963.

Las herramientas de la ingeniería del software proporcionan un soporte automático o semi-automático para el proceso y para los métodos. Cuando se integran herramientas para que la información creada por una herramienta la pueda utilizar otra, se establece un sistema de soporte para el desarrollo del software llamado ingeniería del software asistida por computadora y le denominamos herramientas CASE, Computer Aided Software Engineering.

CASE

LENGUAJES DE CUARTA GENERACION

El proceso de desarrollo de software implica una metodología de diseño e implementación, si bien las necesidades de una empresa requieren del diseño de software flexible con calidad, menos costoso y confiable, también es importante determinar el tipo de aplicación y la tecnología de información disponible para el tipo software.

El diseño de software se puede llevar a cabo usando las fases del ciclo de vida de un sistema, análisis, diseño e implementación; o las etapas en espiral, en la que los requerimientos y el diseño se reestructuran conforme se desarrolla la aplicación y las necesidades del usuario y del sistema son resueltas y continuamente se corrige el análisis, diseño y la implementación.

Un proceso de desarrollo de software involucra también lenguajes y ambientes de desarrollo. Editores interactivos para crear y guardar programas; compiladores y ligadores; bibliotecas de módulos de programas; depuradores, etc. Un ambiente integral de desarrollo de software debería de apoyar todas las fases y actividades del procesos de software:

• Especificación de requisitos
• Diseño
• Implementación
• Verificación
• Validación
• Mantenimiento

Las heramientas CASE (computer Aided Software Engineering) ofrecen al ayuda automatizada al desarrollo de software, es decir, ofrecen soluciones puntuales en cada una de las etapas del desarrollo del software.

Los lenguajes y métodos de diseño son la guía para producir el diseño de un sistema.

Un método de diseño el la forma de producir el diseño de un sistema. Los métodos más usados son: estructurado, diseño "desde arriba hacia abajo" (top-down) y diseño orientado a objetos.

No obstante estas metodologías de diseño, dentro de los lenguajes es común encontrar paradigmas de programación. Los lenguajes que soportan un paradigma específico de computación se puede clasificar como orientado al paradigma de computación. Así, se encuentra FORTRAN y Pascal, definidos originalmente como lenguajes procedurales porque utilizan el concepto de rutina como la unidad de modularización. Eiffel y Smalltalk son lenguajes orientados a objetos, su programas se expresan en términos de clases y objetos como unidades de modularización. En general, ésta relación puede no ser uno a uno. Se puede disponer de C++ que soporta el paradigma procedural y el orientado a objetos. Y podemos clasificarlo como neutral al paradigma.

Si el método de diseño y el paradigma del lenguaje coinciden, entonces el mapeo entre las abstracciones del diseño y las del lenguajes es directo, en el caso contrario, los costos del mapeo pueden ser muy altos.

¿Qué significa entonces, saber la aplicación o paradigma de un lenguaje de programación?.

Al manejar uno de estos lenguajes dentro del diseño de software implica un costo para mapear la relación software – lenguaje. De manera que para problemas científicos y métodos numéricos FORTRAN y LENGUAJE C son la mejor alternativa por aritmética de punto flotante y soporte para varias plataformas. De la misma, forma, tendría la posibilidad de usar Java para aplicaciones de telecomunicaciones, en este caso, html y acceso a datos vía Internet. Manejar C++ o Visual Basic para el manejo de registros de una base de datos, o LISP y PROLOG para inteligencia artificial.

Los paradigmas de lenguajes por citar algunos:

• Programación declarativa: la descomposición de un problema hasta su implementación algorítmica.
• Programación por módulos: enfatiza el concepto de módulo como agrupación de variables, procedimientos, funciones y tipos. El programa se compone de un conjunto de módulos.
• Programación genérica: este estilo enfatiza la definición de módulos genéricos, los cuales pueden ser instanciados, a la hora de compilación o en tiempo de ejecución, es el caso de C++ y Ada.

Un pagadigma que corresponde a los lenguajes de cuarta generación es la inteligencia artificial, que se ha resuelto con lenguajes de programación como PROLOG y LIPS, el primero, desarrollado en 1956-1962 por J. McArthy y el segundo por A. Colmerauer en 1972, para el desarrollo de inteligencia artificial, que corresponden ambos definición de lenguajes funcionales o aplicativos. El LISP puro es libre de conceptos Von Newmann, como las variables cuyos valores se modifican, instrucción de asignación, instrucción de goto, etc. La lista es el único tipo de estructura de datos que permite LISP. Los programas de LISP también son listas. Esta uniformidad entre la estructura de datos y los programas permite definir intérpretes de LISP en LISP de una manera sencilla. Este lenguaje incluyó conceptos menos consolidados en esa época, como son el manejo de excepciones y las multi-tareas.

APL es otro lenguaje basado en las matemáticas. Contiene un conjunto nutrido de operadores sobre arreglos que eliminan la programación tediosa de ciclos.

SNOBOL4 también es ejemplo de un lenguaje no convencional. Proporciona facilidades para la manipulación de cadenas (stings) y aparcamiento de patrones (pattern matching). Apoya la programación declarativa.

LISP, APL y SNOBOL4 son grandes consumidores de recursos computacionales (tiempo y espacio) por lo tanto se dificulta su eficiencia en máquinas convencionales. A pesar de esto, han llegado a ser muy exitosos para cierto tipo de aplicaciones y tienen sus usuarios devotos. Por ejemplo, LISP es ampliamente usado en aplicaciones de Inteligencia Artificial. APL se usa para hacer prototipos rápidos en aplicaciones financieras o científicas que implican el uso de operaciones sobre matrices.

La mayor contribución de LISP y SNOBOL4 fue el énfasis en la computación simbólica. En la mayoría de las aplicaciones actuales sólo una pequeña parte de ellas está dedicada a los cálculos numéricos. El resto, en su mayoría, ocupa el procesamiento simbólico tal como el manejo de bases de datos o el procesamiento de textos.

LISP ha seguido desarrollandose en la versión del lenguaje SCHEME, el cual fue diseñado como lenguaje educativo para cursos introductorios y como una alternativa de comparación con los lenguajes convencionales.

Otra nueva definición de lenguajes de programación ha propiciado el desarrollo de la tecnología, el procesamiento en paralelo, y los biochips en lo que se denomina Quinta Generación, paradigma inicialmente desarrollado en Japón en la década de los 80’s y que durante los 90’s alcanzaría su máximo desarrollo en lo que se conoce como robótica y los sistemas expertos. Bajo esta suposición PROLOG fue seleccionado por el gobierno de Japón para su proyecto. Se han diseñado e implementado aplicaciones en PROLOG bajo la suposición que máquinas paralelas de la nueva generación ejecutarían eficientemente los programas lógicos. Aunque estas predicciones no se cumplieron, sin embargo, PROLOG y otros lenguajes lógicos han encontrado su penetración de mercado, en particular en sistemas expertos.

Ambos tienen fundamento en las matemáticas y no en la arquitectura subyacente del hardware (modelo Von Newman).

Clasificación por modelo computacional

• Lógicos
• Funcionales
• Imperativos

En este caso, ML es el lenguaje basado en el modelo computacional funcional.

En el desarrollo tecnológico de la informática el hardware siempre ha estado adelante del software, de manera que es imprescindible el desarrollo y manejo de lenguajes para apuntalar las ventajas que ofrece una aplicación: funcionalidad, facilidad de estructura, seguridad y robustecimiento; un lenguaje que propicie estas características permitirá desarrollar herramientas que controlen un robot, un biochip, un procesamiento en paralelo o una red neuronal.

Fuente: Apuntes de la maestría en Computación impartido por la Dra. Hanna Oktaba y Mat. Carlos Velarde. IIMAS, UNAM, 1999

---

AUTOMATAS FINITOS DETERMINISTAS

Un autómata finito determinista consiste en una quíntupla (S, S , d , i , F) dónde:

1. S es un conjunto finito de estados.
2. S es el alfabeto de la máquina.
3. d es una función (llamada función de transición) de SxS a S
4. i (un elemento de S) es el estado inicial
5. F (un subconjunto de S) es el conjunto de estados de aceptación

 La interpretación de la función de transición de d , de un autómata finito determinista es que d (p,x)=q si y sólo si la máquina puede pasar de un estado p a un estado q al leer el símbolo x. Así, un diagrama de transición. Así, un diagrama de transición para un autómata finito determinista no es más que una representación gráfica de la función de transición de la máquina. De aquí se desprende que el autómata (S, S , d , i , F) acepta la cadena no vacía X1, X2,...Xn si y sólo si existe una serie de estados S0, S1,..,Sn tal que, S0=i , Sn Î F, y para cada entero j de 1 a n, d (Sj-1,x)=Sj. Un AFD es un caso particular de automatas finitos no deterministas.

a)Diagrama de transiciones para un AFND

b)diagrama de transiciones para un AFD equivalente, construido de acuerdo con la demostración del teorema citado.

¿Cómo convertir un AFND a un AFD?

"Para cualquier ruta en M que vaya de a un estado de aceptación y recorra arcos rotulados w1, w2,..,wn, debe existir una ruta en M’, de i ’ a un estado de aceptación, que siga los arcos rotulados w1, w2,..., wn y viceversa. Por lo tanto M y M’ deben aceptar el mismo lenguaje".*

Autómata Finito no Determinista

Un autómata finito no determinista es una quíntuple M = (Q, S, d, q₀, F), donde Q es un conjunto finito de estados, S es un conjunto finito llamado el alfabeto, q₀ Î Q un estado llamado el estado inicial, F un subconjunto de Q llamado los estados finales o aceptantes y d una función total de Q ´ S a P(Q) conocida como la función de transición. El símbolo |— es utilizado para indicar las operaciones efectuadas por el AFND.

Consideremos el siguiente AFND.

M: Q = { q₀, q₁, q₂ }
S = { a, b }
F = { q₂ }

d	a	b
q0	{ q0 }	{ q0, q1}
q1	Æ	{ q2 }
q2	Æ	Æ

Encontrar las operaciones posibles para la cadena ababb.

Una cadena de entrada es aceptada si hay una operación que procesa la cadena completa y termina en un estado de aceptación. Una cadena está en el lenguaje de la máquina no determinista si hay una operación que la acepta.

El lenguaje de un AFND M, denotado L(M), es el conjunto de cadena aceptadas por M. Esto es, L(M) = { w | hay una operación [q₀, w] |—* [q_i, l] con q_i Î F }.

El diagrama de estados de un AFND M = (Q, S, d, q₀, F) es un grafo dirigido etiquetado G definido por las siguientes condiciones:

1. Los nodos de G son elementos de Q.
2. Las etiquetas en los arcos de G son elementos de S.
3. q₀ es el nodo inicial.
4. F es el conjunto de nodos aceptantes.
5. Hay un arco del nodo q_i a q_j etiquetado con a si q_j Î d (q_i, a).

Ejercicios

1. Obtén un diagrama de estados para AFND antes mencionado. Encuentra el lenguaje denotado por AFND, representándolo con expresiones regulares.
2. Encuentra un AFND para el lenguaje denotado por (a | b)*bb(a | b)*.
3. Encuentra un AFND para el lenguaje formado por cadenas que contiene como subcadena aa o bb.
4. Encuentra un AFND para el lenguaje formado por las cadenas que contiene la subcadena abba.
5. Para cada uno de los siguientes lenguajes obten el diagrama de un AFND y representa el AFND de manera formal.
   1. (ab)* | a*
   2. (ba | bb)* | (ab | aa)*
   3. ((ab+)a)+

Transiciones Lambda

Un AFND puede permitir transiciones sin requerir una entrada para que sea procesada, una transición de esta forma es llamada transición lambda. La clase de máquinas no deterministas que utilizan transiciones lambda es denotada AFND-l.

Un AFND con transiciones lambda es una quíntuple M = (Q, S, d, q₀, F), donde Q, d, q₀ y F son lo mismo que un AFND. La función de transición es una función de Q ´ (S È {l}) a P(Q).

Este tipo de autómatas nos permiten convertir una expresión regular a un AFND-l aplicando el método de Thompson, el cual se aplica de la siguiente manera:

*BROOKSHEAR, J. GLENN. TEORIA DE LA COMPUTACION. ADDISON-WESLEY IBEROAMERICANA. MEXICO 1993. PP 45-47.

GRAMATICAS DESCENDENTES

Recuerde que un analizador LL(k) un autómata de pila construido a partir de una gramática independiente al contexto; esta construcción se basa en el proceso descrito en la axioma del teorema de un autómata de pila.

Gramáticas LR(k)

Un parser ascendente (bottom-up) genera una secuencia de cambios y reducciones para analizar la cadena de entrada hasta llegar al símbolo inicial de la gramática. Un parser determinístico debe incorporar información adicional en el proceso para seleccionar la alternativa correcta cuando más de una operación es posible. Una gramática es LR(k) si k-símbolos (lookahead) proveen información suficiente para hacer dicha selección. LR significa que las cadenas son analizadas de izquierda-a-derecha para construir derivaciones más hacia la derecha. Las condiciones que debe cumplir una gramática para que sea LR son: Símbolo inicial no recursivo y que todos los símbolos en la gramática son usados (no inútiles).

Un analizador ascendente trata de construir una derivación más hacia la derecha de una cadena de entrada p, donde la determinación de la aplicación de una regla dependerá del símbolo que se analiza (cambios) pero la reducción requiere del siguiente símbolo del que se está analizando para determinar a que regla regresa para continuar con el análisis, es decir, si tenemos reglas de la forma A à uBw y B à a, con p = uaw y se está analizando a, entonces para determinar a que regla se debe regresar, la cual contenga B en el lado derecho, es necesario conocer cual símbolo le sigue a a, que en este caso es w (lookahead) y de esta manera sabemos con exactitud a donde se debe regresar. Los conjuntos de lookahead’s de w e V U S, son determinados por el cálculo de Primero y Siguiente.

Para garantizarnos que si se requieren k-símbolos para hacer el análisis, entonces debemos concatenar al final de la cadena de entrada k-símbolos de terminación ($^k) y como las gramáticas LR(k) requieren de una gramática aumentada G’, la cual es obtenida a partir de G agregando la regla S’ à S, donde S es el símbolo inicial de G y S’ será el símbolo inicial de G’, entonces se debe concatenar k-símbolos de terminación al final de cada regla de la forma S’ à w, donde S’ es el símbolo inicial. Esta concatenación en la práctica se hace ficticiamente.

Una gramática libre de contexto puede interpretarse como una relación de estados donde la ocurrencia de los símbolos gramaticales genera una transición de un estado a otro, como ocurre en un autómata para una expresión regular, solo que el comportamiento para guiar al analizador sobre esta gramática es substancialmente distinto a un analizador de léxico, ya que en analizador gramatical, el cumplimiento de reglas provoca estar en diferentes situaciones no alcanzadas a través de símbolos terminales exclusivamente. En el caso de un analizador gramatical ascendente esto recibe el nombre de reducción y provoca el cambio de situaciones hasta encontrar el axioma o determinar que hay error.

El primer paso para construir el autómata que representa a la gramática es agregar un nuevo noterminal (conocido como el noterminal aumentado) que generará la producción de tener al axioma de la gramática seguida de la marca de fin de archivo. A esta gramática nueva se le conoce como gramática aumentada. La siguiente es la gramática aumentada para la gramática de las expresiones aritméticas:

N2' à N2
N2 à N2 opsr SN
N2à SN
SN à SN opmd OPDO
SN à OPDO
OPDO à id
OPDOà num
OPDOà ( N2 )

A esta gramática se genera un primer estado (Estado 0) en donde colocaremos un punto antes del axioma para el noterminal aumentado. Esta primera situación representa la situación inicial del analizador gramatical: el estar a punto de ver al axioma de la gramática. Por medio de la función Cerradura determinamos qué significa estar en esta situación (es decir, a punto de ver el axioma N2) y agregamos estas situaciones al Estado 0, hasta que no sea posible agregar una nueva. Cada producción que hemos agregado (y que posee un punto en algún lugar) se le conoce como artículo.

El estado 0 queda conformado como sigue:

N2' à · N2
N2 à · N2 opsr SN
N2 à · SN
SN à · SN opmd OPDO
SN à · OPDO
OPDO à · id
OPDO à · num
OPDO à · ( N2 )

Al completar el estado inicial 0, se analiza cada situación posible de transición sobre cada símbolo a la derecha del punto en cada artículo del conjunto de artículos en el estado 0. Cada símbolo derivará una situación nueva que conformará un nuevo estado o hará referencia a uno ya existente.

A esto se le conoce como función de transferencia. Mientras se pueda agregar una nueva situación de transición, se agregará un nuevo conjunto o estado al autómata de la gramática. Este proceso se le conoce como la creación de los Conjuntos de artículos. Para la gramática:

se obtienen los siguientes conjuntos

que podemos visualizar como el siguiente autómata:

Función Cerradura( I )

1. Inicialmente todo artículo en I se agrega a Cerradura( I ).
2. Si A à a ·B b está en Cerradura( I ) y B à g es una producción, entonces agregar el artículo B à ·g a I, si aún no está. Aplicamos esta regla hasta que no haya nuevos artículos para agregar a Cerradura( I ).

Función Transferencia( I, X )

I es un conjunto de artículos.
X es un símbolo de la gramática.

Esta función se define como la cerradura del conjunto de todos los artículos.

[ A à a X ·b ] | [ A à a · X b ] e I

Conjunto de Artículos

1. C = Cerradura( { S´ à · S } )
2. Repetir

Por cada conjunto de artículos I en C y cada símbolo X de la gramática tales que Transferencia( I, X ) no sea vacía y no esté en C.
Agregar Transferencia( I, X ) a C.

Hasta que ningún conjunto de artículos pueda agregarse a C.

Construcción de la Tabla LR

Un analizador gramatical ascendente utiliza la información que existe en el autómata que representa a la gramática de un lenguaje para guiar su comportamiento. De manera similar a la tabla que emplea un analizador de léxico, el analizador gramatical representa al autómata de la gramática como una tabla de estados, solo que ésta está dividida en dos secciones: la sección de acciones (que se realizan sobre terminales) y la sección de transferencia (que se realiza sobre no terminales). Las acciones posibles son:

• Cambiar a un nuevo estado al encontrar un terminal.
• Reducir un conjunto de símbolos gramaticales por un no terminal y cambiar al estado que éste representa en el autómata.
• Aceptar, al encontrar el axioma seguido de la marca de fin de entrada.
• Error, cuando ninguna acción de las anteriores está especificada para un terminal.

Para poder construir una tabla de la gramática es necesario tener el autómata de la gramática y los conjuntos de artículos; al mismo tiempo debemos construir los conjuntos Primero y Siguiente de los símbolos de la gramática, ya que éstos últimos condicionan las acciones de reducción (la sustitución de un conjunto de símbolos por un no terminal) que el analizador gramatical debe realizar. La construcción de la tabla del analizador gramatical ascendente se guía por el siguiente algoritmo:

Construcción de Tablas LR

Entrada: Gramática aumentada G´
Salida: La tabla del analizador ascendente para G´
Método:

1. Construir C ={ I₀, I₁, ...., I_n}, la colección de conjuntos de artículos LR(0) para G ´.
2. El estado i se construye de I_i. Las acciones para el estado i se determina como sigue:

• Si [ A à a · a b ] está en I_i y Transferencia( I_i. , a ) = I_j entonces colocar en Acción[i, a] a cambia_a j, donde a es un terminal.
• Si [ A à a · ] está en I_i entonces colocar en Acción[i, a] a reduce A à a para todo a en Siguiente( A ), donde A es diferente de S´.
• Si [ S´ à S · ] está en I_i entonces colocar en Acción[i, $] aceptar

3. Las transiciones de estado i. en TRANSFERENCIA se construyen para todos los no terminales A usando la regla:

• Si Ttransferencia( I_i, A ) = I_j entonces Transferencia[ i, A ] = j

4. Todas las entradas no definidas en 2 y 3 causan error.

Cálculo de Primero( X )

1. Si X es un terminal, entonces Primero( X ) = { X }
2. Si X à l es una producción, entonces agregar l a Primero( X )
3. Si X es un no terminal y X à Y₁Y₂ ... Y_k es una producción, entonces coloque a en Primero( X ) si para alguna i, a esta en Primero( Y_i ) y l está en todos los Primero( Y₁ ) ... Primero( Y_i-1 ). Si l está en Primero( Y_j ) para j = 1, 2, … k, entonces agregar l a Primero( X ). Para calcular el Primero de cualquier cadena X₁X₂ ... X_n se agregan al Primero( X₁X₂ ... X_n ) todos los símbolos diferentes de l de Primero( X₁ ), se agregan los símbolos de Primero( X₂ ) si l está en Primero( X₁ ) y así sucesivamente.

Cálculo de Siguiente( A ), donde A es no terminal.

1. Coloque $ en Siguiente (S) donde S es el axioma de la gramática y $ la marca de fin de la línea de entrada.
2. Si hay una producción A à a B b entonces todo símbolo en Primero( b ), excepto l, se coloca en Siguiente( B ).
3. Si hay una producción A à a B o una producción A à a B b donde Primero( b ) contiene l entonces todo en Siguiente( A ) estará en Siguiente( B ).

Mecanismo del analizador Ascendente

Un analizador ascendente posee una pila donde registra los estados por los cuales ha transitado sobre el autómata y los símbolos que han provocado dichas transiciones. Se tiene un apuntador sobre W, que contiene la secuencia de tokens que el analizador de léxico envía junto con el fin de archivo. A medida que el análisis gramatical avanza, esta secuencia de tokens se va consumiendo. En la práctica, W puede no existir y el apuntador será empleado para direccionar al último token recibido.

Colocar ip apuntando al primer símbolo de w$
Repetir

Sea s el estado en la cima de la pila y a el símbolo apuntado a ip.
Si Acción[s, a] = cambia_a s’ entonces

Colocar a y s’ en la cima de la pila
Avanzar ip al siguiente símbolo

Sino

Si Acción[s, a] = reduce A à b entonces

Sacar de la pila los 2 * | b | símbolos
Sea s’ el estado en la cima de la pila
Colocar A y luego Transferencia[ s’, A] en la cima de la pila.
Sacar la producción A à b

Sino

Si Acción[s, a] = aceptar entonces

Regresar con éxito

Sino

Error

FinSi

FinSi

FinSi

FinRepetir

Ejercicios

Para las siguientes gramáticas encuentra la tabla LR y aplica el mecanismo de análisis para la cadena de entrada asociada.

Ambigüedad

Sea G = (V, S, P, S) una gramática libre de contexto. Una cadena w está en L(G) si y solo si, existe una derivación más hacia la izquierda de w a partir de S.
Una gramática libre de contexto G es ambigua si hay una cadena w e L(G) que pueda ser derivada por dos formas distintas utilizando derivaciones más hacia la izquierda. Una gramática que no es ambigua es denominada no-ambigua.< Ejercicios

Sea la gramática

S à aS | Sa | a

1. Determinar si aa es elemento de L(G).
2. Determinar si la gramática es ambigua.
3. Escribir una gramática no ambigua que reconozca L(G).

Determinar si la siguiente gramática es ambigua o no.

SI à if EXP then INS | if EXP then INS else INS

Determinar si la siguiente gramática es ambigua

E à E + E | E * E | (E) | id

probar con a+b*c+(d*a), escribir una gramática no ambigua.

Eliminación de Recursión a la Izquierda

Consideremos las derivaciones usando las reglas A à Aa | b. La aplicación repetitiva de la regla directamente recursiva A à Aa produce cadenas de la forma Aaⁱ, i >= 0. La derivación termina con la aplicación de la regla no recursiva A à b, generando esto ba*.

Para eliminar la recursión a la izquierda se requiere la adición de una nueva variable a la gramática. Esta variable introduce un conjunto de reglas recursivas hacia la derecha, lo cual causa que la variable recursiva ocurra como el símbolo más hacia la derecha en la derivación.

Para remover la recursión a la izquierda, las reglas A son divididas en dos categorías: la reglas recursivas:

A à Au₁ | Au₂ | … | Au_j

y las reglas

A à v₁ | v₂ | … | v_k

en la cual, el primier símbolo de cada v_i no es A.

Se construye primeramente las reglas v_i y posteriormente agregamos las reglas que producen el resto de las cadenas usando recursión a la derecha.

A à v₁ | v₂ | … | v_k | v₁Z | v₂Z | … | v_kZ

si la cadena contiene una secuencia de u_i’s, son generadas por las reglas Z

Z à u₁Z | u₂Z | … | u_jZ | u₁ | u₂ | … | u_j

usando recursión a la derecha.

*BROOKSHEAR, J. GLENN. TEORIA DE LA COMPUTACION. ADDISON-WESLEY IBEROAMERICANA. MEXICO 1993. PP 152-175

GENERACION DE PATRONES EN LEXER

%{   /* Reconocedor de identificadores, enteros, reales, y símbolos de comparación */    %}

letra=[A-Z a-z];
letrae =[E|e];
digito = [0-9];
id = letra(letra|digito)*;
entero = digito;
real = entero \ . letrae(digito)*;

% { /* Función principal */ % }

main()
{
register int i;
char buffer [80];
extern char* token();

while(i=yylex())
{gettoken (buffer, sizeof buffer);
printf("yylex tiene el token" %d, token = \ " % S \ " \n, i, buffer);

if (i== LEXERR)
{error("LEXERR - aborta programa ");
   break;
}
}
}
% }

%%
if { printf ("yylex; id:\n");
   lexval=instala(),
   return(1); }

entero {printf("yylex: entero" \n);
   lexval=instala(),
   return(2); }

real {printf("yylex: real" \n);
   lexval=instala(),
   return(3); }

"<" printf("yylex: LT:\n"); return(4); }
"<=" printf("yylex: LE:\n"); return(5); }
"=" printf("yylex: EQ:\n"); return(6); }
"<>" printf("yylex: NE:\n"); return(7); }
">" printf("yylex: GT:\n"); return(8); }
">=" printf("yylex: GE:\n"); return(9); }
%%

char *

instala()
{register char * buffer; /* almacena token */
register char * inicio;
char * fin;
extern char * token();
inicio=token (&fin);

if((buffer=a|bc ((fin-inicio)++))=null)
{error ("No hay espacio en la tabla de símbolos");
   EXIT(1);
}

inicio=copy(buffer, inicio (fin-inicio));
*inicio = '\ ';

---

   return(buffer);
}
%{

---

/****************************************************************************
   parser.y   ParserWizard generated YACC file.
      Date: Jueves, 10 de Octubre de 2000
****************************************************************************/

#include "lexer.h"
%}

/////////////////////////////////////////////////////////////////////////////
// declarations section

// parser name
%name myparser

// class definition
{
   // place any extra class members here
}

// constructor
{
   // place any extra initialisation code here
}

// attribute type
%include {
#ifndef YYSTYPE
#define YYSTYPE int
#endif
}

// place any declarations here

%%

/////////////////////////////////////////////////////////////////////////////
// rules section

// place your YACC rules here (there must be at least one)

Grammar
   : /* empty */
   ;

%%

/////////////////////////////////////////////////////////////////////////////
// programs section

int main(void)
{
   int n = 1;
   mylexer lexer;
   myparser parser;
   if (parser.yycreate(&lexer)) {
      if (lexer.yycreate(&parser)) {
         n = parser.yyparse();
      }
   }
   return n;
}

---

%{
/*************************************************************************
   lexer.l   ParserWizard generated Lex file.
      Date: Jueves 10, de Octubre de 2000
*************************************************************************/

#include "parser.h"
%}

//////////////////////////////////////////////////////////////////////////
// declarations section
// lexical analyser name

%name mylexer

// class definition
{
   // place any extra class members here
}

// constructor
{
   // place any extra initialisation code here
}

// place any declarations here

%%

/////////////////////////////////////////////////////////////////////////////
// rules section

%{
// extract yylval for use later on in actions
YYSTYPE& yylval = *(YYSTYPE*)yyparserptr->yylvalptr;
%}

// place your Lex rules here

%%

//////////////////////////////////////////////////////////////////////////
// programs section


ANALISIS LRH y LR1

---

EDITOR HTML

CLICK PARA VER PROYECTO

 

---

What is Software Engineering?

WELCOME Computer-Aided Software Engineering

CASE Environments

Using Object ModelingCASE Tools

Interchange ideas or information

David Elias Martínez M.
[email protected]

Set your fingerprint

View My Guestbook

 

Copyright © 1999 David Elias Martínez Mercado

Hosted by www.Geocities.ws