|
Un Símbolo es una entidad abstracta que no necesitamos definir
formalmente, como por ejemplo una letra del alfabeto o un dígito.
Alfabeto : Cualquier conjunto finito de símbolos. Se designa por S.
String (cadena, palabra) : es una secuencia finita de símbolos
yuxtapuestos.
Por ejemplo:
If (a=b) or (b=c) then i:=i+1; es una palabra PASCAL El tamaño de un String w denotado por |w| es el número de símbolos que
componen el string.
Por ejemplo |abbca| = 5
El String vacío, denotado por e es el string que contiene 0 símbolos.
Así |e|=0
Una cadena de "i" símbolos "a" se denota por ai
Por ejemplo:
Definición. Se definen strings sobre un alfabeto S como:
a) e es un string sobre S
b) Si x es un string sobre S y a Î S entonces xa es un string sobre S
c) y es string sobre S ssi es obtenido mediante los pasos (a) y (b)
Substrings: Sean x,y,z, w = xyz strings arbitrarios sobre un alfabeto S.
Se llama al string y (x,z) substring del string xyz.
Un Prefijo de un string es cualquier substring del comienzo de ese
string; y un sufijo de un string es un substring del final de ese string.
Por ejemplo : El string abc tiene
Si el prefijo (sufijo) de un string es distinto del string mismo, el
prefijo (sufijo) se denomina prefijo (sufijo) propio del string.
Observación: e es substring, prefijo y sufijo de cualquier string.
Concatenación de 2 strings es el string formado por yuxtaposición de
strings escribiendo el primero seguido por el segundo sin espacios intermedios.
Por ejemplo: Sean x = abre, y = lata; entonces xy = abrelata que es
distinto de yx = lataabre.
e es la identidad del operador de concatenación, luego: "x, ex = xe
= x.
El reverso de un string x, denotado por xR ,es el string x
escrito en orden inverso:
Definición : Un lenguaje sobre un alfabeto S es un conjunto de strings
sobre S.
Definición : S* denota al conjunto que contiene todos los strings sobre
S, inclusive e.
Por ejemplo:
S = {0,1}
S* = {e,0,1,00,01,10,11,000,...}
Todo lenguaje L sobre S es un subconjunto de S*. Bajo concatenación (·)
S* es un monoide (S*,·,e)
LEXEMAS, EXPRESIONES REGULARES Y TOKENS.
Para ver las diferencias entre los conceptos de lexema, expresión
regular y token, veamos algunos ejemplos de ellos para la siguiente gramática: sent -> ID ASIG exp ';'exp -> exp '+' expexp -> exp '*' expexp ->
NUMENTEROexp -> NUMREALexp -> IDENT
EXPRESIONES REGULARES EN LEX Lex es un generador de
analizadores léxicos. Cada vez que Lex encuentra un lexema que viene definido por una
expresión regular, se ejecutan las acciones (escritas en C) que van al lado de la
definición de dicha expresión.
Lex crea code yylex /code, una variable que contendrá un número, el
cual se corresponde con el token de cada expresión regular. También, instancia una
variable global code yytext /code, que contiene el lexema que acaba de reconocer.
Así, por ejemplo, para el siguiente código fuente de entrada:
pre %% expresión1{acción1}expresión2{acción2}...
...expresiónn{acciónn}%%
Lex genera un programa en C (generalmente denominado lex.yy.c)
que incluye, entre otras, la función yylex():
int yylex(){ while(!eof()) { switch(...) { case -1: ... ; break;
Esta función recorre el texto de entrada. Al descubrir algún lexema
que se corresponde con alguna expresión regular, construye el token, y realiza la acción
corespondiente. Cuando se alcanza el fin de fichero, devolverá -1. La función yylex()
podrá ser invocada desde cualquier lugar del programa.
Las expresiones regulares (ER, de aquí en adelante) han de aparecer en
la primera columna.
Alfabeto de entrada: Caracteres ASCII al 127.
Concatenación: Sin carácter especial, se ponen los caracteres juntos.
Caracteres normales: Se representan a ellos mismos.
Caracteres especiales: Se les pone la barra '' delante. Éstos son:
* + ? | [ ] ( ) " \ . { } ^ $ / <>
Caracteres especiales dentro de los corchetes ( '[' y ']'):
- \ ^
Las equivalencias entre ER normales y las que se usan en Lex se
muestran con ejemplos en esta tabla:
|
