2.4. Especificación de los Componentes Léxicos

Las expresiones regulares son una notación importante para especificar patrones. Cada patrón concuerda con una serie de cadenas, de modo que las expresiones regulares servirán como nombres para conjuntos de cadenas.

Cadenas y lenguajes

El término alfabeto o clase de carácter denota cualquier conjunto finito de símbolos. Ejemplos típicos de símbolos son las letras y los caracteres. El conjunto {0 , 1} es el alfabeto binario. Los códigos ASSCII y EBCDIC son dos ejemplos de alfabetos de computador.

Una cadena sobre algún alfabeto es una secuencia finita de símbolos tomados de ese alfabeto. En teoría del lenguaje, los términos frase y palabra a menudo se utilizan como sinónimos del término "cadena". La longitud de una cadena s, que suele escribirse lsl, es el número de apariciones de símbolos en s. Por ejemplo, camino es una cadena de longitud seis. La cadena vacía, representada por Є, es una cadena especial de longitud cero.

El término lenguaje se refiere a cualquier conjunto de cadenas de un alfabeto fijo. Esta definición es muy amplia, y abarca lenguajes abstractos como Ǿ, el conjunto vacío, o {Є} y el conjunto que sólo contiene la cadena vacía, así como al conjunto de todos los programas de Pascal sintácticamente bien formados y el conjunto de todas las oraciones en inglés gramaticalmente correctas, aunque los dos últimos conjuntos son mucho más difíciles de especificar.

Hay varias operaciones importantes que se pueden aplicar a los lenguajes. Para el análisis léxico, interesan principalmente la unión, la concatenación y la cerradura.