Capítulo 1: Gramáticas y Expresiones Regulares.
Conceptos Básicos:
Símbolo: Elemento mínimo de un lenguaje, un símbolo puede ser una letra un número o cualquier otra cosa, pero en su mínimo.
Alfabeto: Conjunto de símbolos que acepta el lenguaje.
Palabra: Conjunto de símbolos agrupados de una manera tal que signifique algo, Palabra es lo mismo que Token.
Lenguaje: Conjunto de palabras que en un determinado orden tienen un significado.especial
Expresiones Regulares.
Una expresión regular es una forma matemática definida por un conjunto de símbolos que aceptan una palabra o conjunto de palabras, por ejemplo: palabras reservadas, signos de puntuación, dígitos, etc.
Uso de las Expresiones Regulares.
Las expresiones regulares se convierten en reglas que forman parte del lenguaje, pero estas reglas sólo son léxicas, es decir, una E.R. sólo define la regla de cómo se forma una o más palabras; para esto son utilizados los siguientes símbolos:
* Significa que se hará 0 o más repeticiones del caracter o caracteres al que preceda.
+Significa que se hará 1 o más repeticiones del caracter o caracteres al que preceda
( ) Se utilizan para agrupar
[] Agrupa elementos opcionales
.. Se utiliza para definir intervalos de valores
| Se utiliza para marcar que habra una desición ( significa OR)
"" Lo que se encuentra entre comillas es un símbolo del lenguaje (un símbolo es el componente mínimo del lenguaje)
Nota: Cabe aclarar que estos no son todos los símbolos que se utilizan en la realización de E.R.'s pero con fines de hacer este tutorial sólo se explicarán estas a detalle.
Para entender su uso más detalladamente haremos ejemplos::
|
["+"|"-"]("0".."9")+
|
Esta E.R. tiene el símbolo de agrupación opcional, significa que puede tomar el valor de "+" o el valor de "-" o ninguno de ellos, seguido de esto, lleva un símbolo de agrupación precedido de +, esta parte significa que llevará repeticiones de símbolos del "0" al "9"; por lo menos debe de aceptar un sólo dígito. Algunas palabras que acepta: +95 Algunas palabras que no acepta: 5.2 No
está definido el símbolo "."
|
|
("0".."9")*"."("0".."9")+
|
Primero encontramos el símbolo de agrupación precedido de *, esto significa que aceptará repeticiones de los dígitos del "0" al "9" o que no recibirá nada, seguido encontramos un "." Cuando dos o mas partes de la E.R. que no sean símbolos de repetición, se obtiene una concatenación. Esto significa que deberá llevar forzosamente el caracter "."; luego de esto nos encontramos con otro símbolo de agrupación precedido de + esto significa que debe de aceptar por lo menos un dígito del "0" al "9". Algunas palabras que acepta: .05 Algunas palabras que no acepta 900 Forzosamente
debe de llevar el ".", además debe de llevar al menos
un dígito después del "."
|
|
("0".."9" | "A".."F")+
|
Esta E.R. acepta números exadecimales, nos encontramos con un símbolo de agrupación precedido por un +, ya sabemos que significa eso, dentro de la agrupación nos encontramos que puede ser un dígito del "0" al "9" ó un caracter de la "A" a la "F"
|
|
"h""o""l""a"
|
Acepta únicamente la palabra "hola" sin mas ni menos
|
|
"w""r""i""t""e"["l""n"]
|
Acepta las palabras "write" y "writeln"
|
Gramáticas Libres de Contexto.
Las gramáticas
son reglas sintácticas que de una manera formal nos describe el orden
lógico de un lenguaje, es decir, define el orden en el que deben ir los
lexemas (las palabras o tokens).
Símbolos utilizados:
ID Es un nombre variable escrito en mayúsculas, Es un No terminal, significa que tiene producción.
| Es una opción, es decir, se escoge entre lo que está a la izquierda o lo que está a la derecha.
::= Símbolo de Producción.
<E.R.> Terminales, los símbolos terminales que son expresiones regulares
"" Terminales, los símbolos terminales que son constantes
€ En realidad es el símbolo épsilo, pero por no poder sacar ese caracter colocaré este, significa nada
Veamos algunos ejemplos:
|
OPERACION ::= <digitos>SIGNOS<digitos>
|
En la gramática OPERACION podemos ver que se esperan dígitos seguidos de otra gramática denominada SIGNOS seguida de dígitos. Y en la gramática SIGNOS encontramos que espera un "+" o un "-" o un "/" o un "*" Algunas oraciones que acepta: 5 + 91 Algunas oraciones que no acepta: 999 + 55
/ 100 No existe
repetición
|
|
OPERACION2::= <digitos>SIGNOS OPERACION
|
Esta grámatica espera dígitos, seguido de SIGNOS seguido de OPERACION Algunas oraciones que acepta: 6 + 3 *
80 Algunas oraciones que no acepta: 3 / 2 La
gramática dice que al dígitos y dos signos deben de existir
|
|
OPERACION3::= <digitos> SIGNOS R
|
Esta es la gramática que acepta todas las repeticiones de dígitos y símbolos Algunas oraciones que acepta: 5 * 1
|
|
WRITE::= <write> "(" CONTENIDO ")" ";"
|
Gramática sencilla de la instrucción write/writeln. Cuando vimos E.R.'s nos encontramos con una que me aceptaba el write/writeln, bien la llamaremos <write>. entonces esta gramática acepta el write/writeln seguida de paréntesis que abren, seguida de una cadena o nada, seguida de paréntesis que cierran, finalizando con punto y coma Algunas oraciones que acepta: write("Hola"); Algunas oraciones que no acepta: write("Hola",variable,"¿cómo
estas?"); No está
definida ni la coma ni variables, |
Bueno, con esto queda entendido el uso de las gramáticas y las E.R.'s, ahora hagamos un lenguaje que acepte entradas y salidas.
Creación de un Lenguaje.
Bueno, primero que nada se tienen que definir los símbolos a utilizar, por ejemplo, nosotros usaremos los siguientes:
|
;
|
|
(
|
|
)
|
Luego saber cuales serán nuestras palabras
|
Lee
|
Escribe
|
Ahora bien, procedemos a hacer las E.R.'s que reconozcan estos tokens.
| <pyc> = ";" | <pa> = "(" |
| <pc> = ")" | <lee> = "L""e""e" |
| <escribe> = "E""s""c""r""i""b""e" | <cadena> = ("a".."z"|"A".."Z"|"0..9"|" ") |
Después las gramáticas que nos indicarán cómo se usará el lenguaje:
| LEER ::= <lee><pa><pc><pyc> | ESCRIBE::= <cadena><pa><cadena><pc><pyc> |
|
PROGRAMA::= LEER PROGRAMA | ESCRIBE PROGRAMA | € |
|
Bueno, explicaré un poco que hace el lenguaje, este lenguaje acepta lectura y escritura, los programas son por ejemplo como el siguiente:
|
escribe(hola); |