Compiladores Trabajo WORD

EXPRESIONES REGULARES

FUNDAMENTO MATEMÁTICO

Una expresión regular se trata de expresiones algebraicas de la forma que presentan las cadenas de un lenguaje regular. Es además un equivalente algebraico para un Autómata. Podemos decir también que:
Son utilizadas en muchos lugares como un lenguaje para describir patrones en texto que son sencillos pero muy útiles
Pueden definir exactamente losmismo lenguajes que los autómatas pueden describir: Lenguajes Regulares.
Ofrecen algo que los autómatas No: Manera declarativa de expresar las cadenas que queremos aceptar.
Ejemplos de sus usos:
Comandos de Búsqueda, ejemplo grep de Unix y PowerGrep de Windows
Sistemas de formateo de texto: Usan notación de tipo expresión regular para describir patrones.
Convierte la expresión regular a un DFA(“Deterministic Finite Automaton” - Autómata Finito Determinista) o un NFA (“Nondeterministic Finite Automaton” – Autómata Finito No Determinista) y simula el autómata en el archivo de búsqueda.
Generadores de analizadores léxicos como Lex o Flex
Los analizadores léxicos son parte de un compilador, dividen el programa fuente en unidades lógicas (tokens). Tokens como while, números, signos (+,-,<,etc)Produce un DFA que reconoce el token

Las expresiones regulares denotan lenguajes. Por ejemplo, la expresión regular: 01* + 10* denota todas las cadenas que son o un 0 seguido de cualquier cantidad de 1's o un 1 seguida de cualquier cantidad de 0's.

Operaciones de los lenguajes

Unión: Si L y M son dos lenguajes, su unión se denota por L ∪ M
Concatenación: La concatenación es: LM o L.M
Cerradura (ocerradura de Kleene): Si L es un lenguaje su cerradura se denota por: L*

Si E es una expresión regular, entonces L(E) denota el lenguaje que define E. Las expresiones regulares se construyen de la manera siguiente:
1) Las constantes ε y ø son expresiones regulares que representan a los lenguajes L(ε) = {ε} y L(ø) = ø respectivamente
2) Si a es un símbolo, entonces es una expresión regular querepresentan al lenguaje: L(a) 0 {a}

Operandos

1) Si E y F son expresiones regulares, entonces E + F también lo es denotando la unión de L(E) y L(F). es decir L(E+F) = L(E) ∪ L(F)
2) Si E y F son expresiones regulares, entonces EF también lo es denotando la concatenación de L(E) Y L(F). es decir L(EF) = L(E)L(F).
3) Si E es una expresión regular, entonces E* también los es y denota la cerradura deL(E). Osea L(E*) = (L(E))*
4) Si E es una expresión regular, entonces (E) también lo es. Formalmente: L((E)) = L (E)

Precedencia de Operadores

1) El asterisco de la cerradura tiene la mayor precedencia
2) Concatenación sigue en precedencia a la cerradura, el operador “dot”. Concatenación es asociativa y se sugiere agrupar desde la izquierda. ejemplo 012 se agrupa (01)2)
3) La unión (operador +)tiene la siguiente precedencia, tambien es asociativa.
4) Los paréntesis pueden ser utilizados para alterar el agrupamiento.

Leyes Algebraicas de las expresiones regulares

Existen un conjunto de leyes algebraicas que se pueden utilizar para las expresiones regulares:
Ley conmutativa para la unión: L+M=M+L
Ley asociativa para la unión: (L+M) +N=L+ (M+N)
Ley asociativa para la concatenación:(LM)N=L(MN)

NOTA: La concatenación no es conmutativa, es decir LM ≠ ML

Identidades y aniquiladores:

- Una identidad para un operador es un valor tal que cuando el operador se aplica a la identidad y a algún otro valor, el resultado es el otro valor.
- 0 es la identidad para la adición: 0 + X = X + 0 = X
- 1 es la identidad para la multiplicación: 1 x X = X x 1 = X
- Un aniquilador para un operador esun valor tal que cuando el operador se aplica al aniquilador y algún otro valor, el resultado es el aniquilador
- 0 es el aniquilador para la multiplicación: 0 x X = X x 0 = 0
- NO hay aniquilador para la suma
- ø es la identidad para la unión: ø +L = L+ ø = l
- ε es la identidad para la concatenación: εL = L ε = L
- ø es el aniquilador para la concatenación: øL = L ø = ø

Leyes...