Diseño del compilador: expresiones regulares

El analizador léxico necesita escanear e identificar solo un conjunto finito de cadenas / token / lexemas válidos que pertenecen al idioma en cuestión. Busca el patrón definido por las reglas del idioma.

Las expresiones regulares tienen la capacidad de expresar lenguajes finitos definiendo un patrón para cadenas finitas de símbolos. La gramática definida por expresiones regulares se conoce comoregular grammar. El lenguaje definido por la gramática regular se conoce comoregular language.

La expresión regular es una notación importante para especificar patrones. Cada patrón coincide con un conjunto de cadenas, por lo que las expresiones regulares sirven como nombres para un conjunto de cadenas. Los tokens de lenguaje de programación se pueden describir mediante lenguajes regulares. La especificación de expresiones regulares es un ejemplo de definición recursiva. Los lenguajes regulares son fáciles de entender y tienen una implementación eficiente.

Hay una serie de leyes algebraicas que son obedecidas por expresiones regulares, que se pueden usar para manipular expresiones regulares en formas equivalentes.

Operaciones

Las distintas operaciones sobre idiomas son:

• La unión de dos idiomas L y M se escribe como

  LUM = {s | s está en L o s está en M}

• La concatenación de dos idiomas L y M se escribe como

  LM = {st | s está en L y t está en M}

• El cierre de Kleene de una lengua L se escribe como

  L * = Cero o más ocurrencia del lenguaje L.

Notaciones

Si rys son expresiones regulares que denotan los lenguajes L (r) y L (s), entonces

• Union : (r) | (s) es una expresión regular que denota L (r) UL (s)

• Concatenation : (r) (s) es una expresión regular que denota L (r) L (s)

• Kleene closure : (r) * es una expresión regular que denota (L (r)) *

• (r) es una expresión regular que denota L (r)

Precedencia y asociatividad

• *, concatenación (.) y | (signo de tubería) son asociativos a la izquierda
• * tiene la mayor precedencia
• La concatenación (.) Tiene la segunda prioridad más alta.
• | (signo de tubería) tiene la precedencia más baja de todas.

Representar tokens válidos de un idioma en expresión regular

Si x es una expresión regular, entonces:

• x * significa cero o más ocurrencias de x.

  es decir, puede generar {e, x, xx, xxx, xxxx,…}

• x + significa una o más ocurrencias de x.

  es decir, puede generar {x, xx, xxx, xxxx…} o xx *

• ¿X? significa como máximo una ocurrencia de x

  es decir, puede generar {x} o {e}.

[az] son ​​todos los alfabetos en minúscula del idioma inglés.

[AZ] son ​​todos los alfabetos en mayúsculas del idioma inglés.

[0-9] son ​​todos los dígitos naturales utilizados en matemáticas.

Representar la ocurrencia de símbolos usando expresiones regulares

letra = [a - z] o [A - Z]

dígito = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 o [0-9]

signo = [+ | -]

Representar tokens de lenguaje usando expresiones regulares

Decimal = (signo) ^? (dígito) ⁺

Identificador = (letra) (letra | dígito) *

El único problema que queda con el analizador léxico es cómo verificar la validez de una expresión regular utilizada para especificar los patrones de palabras clave de un idioma. Una solución bien aceptada es utilizar autómatas finitos para la verificación.