En un compilador, el análisis lineal se llama análisis lineal o exploración. Por análisis lineal entendemos la cadena de caracteres que constituye el programa fuente se lee de izquierda a derecha y se agrupan en componentes léxicos, que son secuencias de caracteres que tiene un significado colectivo. Por ejemplo, en análisis léxico los caracteres de las siguientes proposiciones de asignación

 Los espacios en blanco (delimitadores) que separan los caracteres de estos componentes léxicos normalmente se eliminan durante el análisis léxico.

Una expresión regular denota un conjunto de secuencias de símbolos válidas que se construyen en base al alfabeto de un lenguaje. Generalmente estos conjuntos se representan como:

Es una expresión regular que denota el conjunto vacío (el conjunto no contiene secuencias de símbolos).

 

Una secuencia de símbolos S es una expresión regular que denota a un conjunto que contiene a S . Operaciones sobre Lenguajes

Es una expresión regular que denota al conjunto que contiene la secuencia vacía.

 

*S on una notación para definir lenguajes

*S e ha demostrado que pueden expresar la clase de los lenguajes regulares

* Permiten hacer una definición algebraica de un lenguaje

* S e expresa el lenguaje de manera declarativa

 Dadas dos expresiones regulares E1, E2, el resultado de aplicarcualquiera de estas tres operaciones, da como resultado otra expresión regular:

*Unión (E1 E2) = {x | x E1 ´ox E2 ´o x E1 ∪ ∈ ∈ ∈ ∩E2}.*Concatenación E1 ・ E2 = {xy | x E1, y E2}∈ ∈*Clausura o Estrella de Kleene (E1* ) = ∪i>=E1i

Construir una expresión regular es realizar operaciones sobre el alfabeto de un lenguaje. Podemos decir que el lenguaje, en su aspecto de léxico, está conformado por las operaciones

 Unión de L y M.LUM = { S | S está en L ó S está en M }Concatenación de L y M.LM = { st | s está en L y t está en M}

 Cerradura Kleene.

(L se repite de 0 a infinito)Cerradura Positiva.

( L se repite de 1 a infinito).

 

Como se ve, las expresiones regulares son operaciones que se realizan sobre conjuntos de símbolos que pertenecen al alfabeto de un lenguaje. Estos conjuntos se describen colocando a los símbolos que pertenecen a ellos entre llaves. Por ejemplo, los caracteres que ubicamos como letras podrían conformar el conjunto

{A B CDEFGHIJKLMNOPQRS TUV WXY Zabcdefghijklmnopqrstuvwxyz}

 

S i los elementos del conjunto tienen un orden conocido o asociado al código A S CII se puede describir colocando el primer símbolo y el último separados por un guión (-) como{A -Z a-z}

Para hacer más simple la construcción de una expresión regular, se designa bajo un nombre al conjunto con el cual se trabajará. así el conjunto letra se puede describir comoL = {A -Z a-z}

 Cuando a un conjunto o a una expresión regular se le da un nombre, ésta recibe el nombre de definición regular. A sí, la expresión regular para un identificador será:

ID=L (L | D | G) *si las definiciones sobre las cuales está construida son:L= {A -Z a-z}D = {0123456789}G = {_}

 

Por ejemplo, en A da los identificadores están formados por letras, dígitos o guiones, pero el guión no puede ser el último caracter. La expresión regular con la cual se puede conformar el patrón para esta unidad de léxico puede ser:ID_ada = L (L | D) * (G (L | D ) + ) *Una expresión regular es un método formal para describir un patrón y puede ser empleada para construir un analizador léxico que lo reconozca en una computadora. De hecho, la expresión sufre una serie de transformaciones para llegar a ser explotada como tabla:

 

 Expresión Regular se convierte en Autómata Finito No deterministico (NFA)

 se convierte en Autómata Finito Deterministico (DFA)

 que se representa como 

 Tabla

 

 Un autómata finito es un conjunto de nodos y aristas que representan trayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito. Los autómatas finitos se clasifican en:

* A utómatas finitos no determinísticos. NFA

*A utómatas finitos determinísticos. DFA

 Un NFA esa un modelo matemático que consiste de: 1.- Un conjunto de estados. 2.- Un conjunto de símbolos de entrada. 3.- Una función de transición que corresponde pares estado-símbolo a conjuntos de estados. 4.- Un estado S o que denota como el estado inicial. 5.- Un conjunto de estados F que denotan los estados de aceptación o finales. Un NFA no tiene restricciones para que exista mas de una transición con el mismo nombre a diferentes estados

 

por lo que en una representación tabular no es posible determinar de manera única el estado destino para un símbolo determinado. Por ejemplo, el siguiente diagrama representa la expresión (a | b)* a b b 

 Un DFA es un caso especial de NFA en el que ningún estado tiene transiciones para diversos estados bajo el mismo símbolo y no se permiten transiciones épsilon. Los diagramas de transición son autómatas determinísticos. Por ejemplo, el DFA de (a | b)* a b b puede ser:

que podría ser muy aproximado al diagrama de transición que construiríamos para la expresión.

 

La expresión regular del autómata es: a*b*.Existen muchas equivalencias con respecto a expresiones regulares basadas en las correspondientes igualdades de lenguajes. Por ejemplo sean r, s y t expresiones regulares sobre el mismo alfabeto . Entonces:4. (rs)t = r(st)5. r + s = s + r6. (r + s)t = rt + st7. (r*)* = r*8. r(s + t) = rs + rt

 Para la implementación de la tabla de símbolos, nos hemos ayudado de la librería STL. Hemos hecho uso del contenedor S TL_HA S HMA P. El acceso se realiza aplicando una función hash sobre el char * del identificador del símbolo. Para mayor legibilidad y facilidad, hemos implementado la clase c_tabla_simbolos. Realiza las operaciones que necesitamos, y se las implementa haciendo uso del citado contenedor hash.

 

Debido a que necesitaremos más de una tabla en determinados momentos, y a su vez, una jerarquía entre las tablas, hemos implementado también la clase c_almacen_tablas. Dicha clase hace uso del contenedor S TL_S TA CK. A continuación se muestran los diagramas de las clases implementadas en notación UML.

 

:

 

 

El método show de la clase c_tabla_simbolos sirve para llamar a los métodos show de cada símbolo almacenado. De esa manera se realiza el volcado pedido. En cuanto a la clase c_almacen_tablas, hemos implementado las operaciones avanzar, retroceder y enderezar. S irven para poder movernos dentro de la pila sin perder elementos. Esto significa, que en un momento dado, podemos ejecutar avanzar sobre la pila, y la cima pasa a ser la tabla de símbolos previa.

 

Hemos supuesto que esto puede ser provechoso para las operaciones en las que haya que buscar si un símbolo se encuentra en la tabla de símbolos actual o en cualquiera de las tablas previas de la jerarquía. A l utilizar internamente dos pilas, una llamada posterior a retroceder dejaría la pila en su situación original. Enderezar se utiliza para regresar la pila a su posición original desde cualquier posición.

 

La clase Parse::Lex nos permite crear un analizador léxico. La estrategia seguida es mover el puntero de búsqueda dentro de la cadena a analizar utilizando conjuntamente el operador pos() y el ancla \G. > cat -n tokenizer.pl 1 #!/usr/local/bin/perl 2 3 require 5.004; 4 #B EGIN { unshift @INC, "../lib"; } 5 6 $^W = 0; 7 use Parse::Lex; 8 print S TDERR "V ersion $Parse::A Lex::V ERS ION\n";

 

910 @token = (11 qw(12 A DDOP [-+]13 LEFTP [\(]14 RIGHTP [\)]15 INTEGER [1-9][0-9]*16 NEWLINE \n17 ),18 qw(S TRING), [qw(" (? :[^"]+|"")* ")],19 qw(ERROR .*), sub {

 

20 die qq!can\'t analyze: "$_[1]"\n!;21 }22 );2324 Parse::Lex->trace;25 $lexer = Parse::Lex->new(@token);2627 $lexer->from(\*DATA );

 

27 $lexer->from(\*DATA );28 print "Tokenization of DA TA :\n";2930 TOKEN:while (1) {31 $token = $lexer->next;32 if (not $lexer->eoi) {33 print "Record number: ", $lexer->line, "\n";34 print "Type: ", $token->name, "\t";35 print "Content:->", $token->text, "<-\n";36 } else {37 last TOKEN;

 

38 }39 }4041 __END__42 1+2-543 "This is a multiline44 string with an embedded "" in it"45 this is an invalid string with a "" in it"

 

Entrada: function main(){

/* Otra prueba mas ! */ var a = 3// var b = 2/* a debería estar en la tabla de símbolos, b no ! */

 var ivar v = new A rray (101)for (i=0; i<100; i+=5){

v[i]=i;}

 

 

for (i=0; i<100; i+=5){document.write(v[i], " ");

}document.write("\n");

} main();// Fin de la pruebaSalida: Leyendo del fichero 'prueba10'

 ANA RAQUEL GARCIA FALLA

YUDY MERCEDES LOSADA ROMERO

 

*En que se clasifica las expresiones autónomas finitas?

* Cual es la funcionalidad de las expresiones regulares?

 

* El lenguaje en su aspecto léxico esta compuesto de que operaciones y de ejemplo de cada una de ellas.