Compilador Diseño - Expresiones Regulares
El analizador léxico debe analizar e identificar sólo un conjunto finito de cadena válida/token/lexeme que pertenecen al lenguaje de la mano. Busca el modelo definido por las normas del lenguaje.
Las expresiones regulares tienen la capacidad de expresar finito idiomas definiendo un modelo finito de cadenas de símbolos. La gramática definida por las expresiones regulares es conocido como gramática regular. El idioma definido por gramática regular se conoce como idioma habitual.
Expresión regular es una notación para importante especificación de patrones. Cada patrón coincide con un conjunto de cadenas, de modo que las expresiones regulares como nombres para un conjunto de cadenas. Fichas lenguaje de programación puede ser descrita por los idiomas. La especificación de las expresiones regulares es un ejemplo de una definición recursiva. Lenguajes regulares son fáciles de comprender y tener eficacia en su aplicación.
Hay una serie de leyes algebraicas que son obedecidas por las expresiones regulares, que puede ser usado para manipular las expresiones regulares en formas equivalentes.
Operaciones
Las diferentes operaciones sobre los idiomas disponibles son:
Unión de dos idiomas L y M se escribe como
L U M = {s | s en L o s es en M}
La concatenación de dos lenguajes L y M se escribe como
LM = {st | s es en L y t se encuentra en M}
La clausura de Kleene un lenguaje L es escrito como
L* = cero o más apariciones del lenguaje L.
Anotaciones
Si r y s son expresiones regulares denotando las lenguas L(r) y L(s), a continuación,
Unión: (r) | (s) es una expresión regular que denota L(r) U L(s)
Concatenación: (r)(s) es una expresión regular que denota L(r)L(s)
Cierre Kleene : (R)* es una expresión regular que denota (L(r))*
(R) es una expresión regular que denota L(r)
Precedencia y asociatividad
- *, La concatenación (.), y | (pipe) son asociativo
- * Tiene la mayor prioridad
- La concatenación (.) tiene la segunda mayor prioridad.
- | (Pipe) tiene la menor prioridad de todos.
Tokens válidos representan una lengua en expresiones regulares
Si x es una expresión regular, entonces:
X * significa cero o más apariciones de x.
Es decir, puede generar { e, x, xx, xxx, xxxx, ... }
X+ significa una o más apariciones de x.
Es decir, puede generar { x, xx, xxx, xxxx ... } o x.x*
X? Medios de una ocurrencia más de x
Es decir, se puede generar un {x} o {e}.
[A-z] es todo en mayúsculas y minúsculas del alfabeto inglés.
[A-Z] mayúsculas alfabetos de idioma inglés.
[ 0-9] es natural dígitos utilizados en matemáticas.
De aparición de símbolos mediante expresiones regulares
Letra = [a - z] o [A - Z]
Dígito = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 o [ 0-9]
Signo = [ + | - ]
Fichas de idioma usando expresiones regulares
Decimal = (signo)?(dígito)+
Identificador = (carta) (letra | digit) *
El único problema con el analizador léxico es la forma de verificar la validez de una expresión regular que se utiliza para especificar los patrones de palabras clave de un lenguaje. Una solución es utilizar autómatas finitos para verificación.
