En esta publicación he incorporado la definición conceptos claves de la primera etapa del proceso de compilación, el analisis léxico. Los terminos a defenir en la guía son:
1. Token
2. Patrón
3. Lexema
4. Atributo
5. Gramática
6. Alfabeto
7. Símbolo
8. Expresión Regular
9. Diagrama y Tabla de
Transición
10. Autómata
11. Autómata Finito
12. Autómata Finito Determinista
13. Autómata Finito No
Determinista
14. Autómata de Pila
15. Autómata de Turing
Tambien puedes ver esta guía y descargarla desde mi cuenta de slideshare.
¿QUÉ ENTENDEMOS POR LEXICO?
El léxico de un lenguaje
natural está constituido por todas las palabras y símbolos que lo componen.
Para un lenguaje de programación la definición también es válida.
En un lenguaje de
programación el léxico lo constituyen todos los elementos individuales del
lenguaje, denominados frecuentemente en inglés tokens. Así son tokens: las palabras reservadas del lenguaje, los símbolos que denotan los distintos tipos de
operadores, identificadores (de
variables, de funciones, de procedimientos, de tipos, etc.), separadores de sentencias y otros.
¿QUÉ ENTENDEMOS POR SINTAXIS?
En lingüística, sintaxis es el estudio de la función que
desempeña cada palabra en el entorno de una frase. Mientras que semántica es el estudio del
significado de una palabratanto a nivel individual como en el contexto de una
frase.
En los
lenguajes de programación, sintaxis es un conjunto de reglas formales que
especifican la composición de los programas a base de letras, dígitos y otros
caracteres.Por ejemplo, las reglas
de sintaxis especifican en C/C++ que cada sentencia o línea de programa debe
terminar con un “;”, o que la declaración de tipos debe ir antes que la de variables.
(int var;)
¿QUÉ ENTENDEMOS POR SEMANTICA?
Semántica en los lenguajes
de programación es el conjunto de reglas que especifican el significado de
cualquier sentencia, sintácticamente correcta
y escrita en un determinado lenguaje. Por ejemplo en el lenguaje Pascal la
sentencia: suma:= 27/x Es sintácticamente correcta, ya que a la izquierda del
símbolo de asignación hay un identificador, y a la derecha una expresión.
Pero para que sea
semánticamente correcta hay que comprobar:
a) Lado debe ser
compatible con el operador “/” y con el operando 27.
b) Suma debe ser un tipo
compatible con el resultado de la operación.
El ANALIZADOR LEXICO
Un programa fuente es una
serie de símbolos (letras, símbolos,
caracteres especiales: +,*, !). Con estos símbolos se representan las
construcciones del lenguaje tales como variables, etiquetas, palabras
reservadas, constantes, etc. Es necesario que el compilador o traductor
identifique los distintos significados de estas construcciones, que los
creadores de lenguajes dan en la definición del lenguaje.
El programa fuente se
trata inicialmente con el analizador léxico (en inglés scanner), con el propósito de agrupar el
texto en grupos de caracteres con significado propio llamados tokens o
componentes léxicos, tales como variables, identificadores, palabras reservadas
y operadores. Por razones de eficiencia a cada token se le asocia un atributo
(o más de uno) que se representa internamente por un código numérico o por un
tipo enumerado.
Por ejemplo considerar la
siguiente sentencia es C/C++:
if sueldo == 1000 sueldo * 0.25;
El analizador léxico la separa en la siguiente
secuencia de tokens:
En
general, el análisis léxico es un análisis a
nivel de caracteres, su misión es reconocer los componentes léxicos o tokens,
enviando al analizador sintáctico (en la siguiente etapa)los tokens
y sus atributos.
CONCEPTOS ANALIZADOR LEXICO
Token
Es
el nombre que se le da a cada patrón definido, éste nombre debe usarse en todos
los procesos del análisis en todos los lexemas encontrados.
Patrón
Es
una representación lógica de una serie de agrupaciones de caracteres con
características comunes.
Lexema
Es
cada una de las combinaciones de caracteres que encajan en la definición de un
patrón o token. Ej. Variable1, x, a, edad, y2, etc.
Atributo
Características
propias de cada token, por tanto se les denomina atributos del token.
Gramática
Se
define como un ente formal para especificar de una manera finita el conjunto de
cadenas de símbolos que constituyen un lenguaje.
Alfabeto
Conjunto
finito de símbolos no vacío que conforman una gramática, se representan por ∑
(sigma).
Símbolo
Entidad
abstracta que no se va a definir pues se deja como axioma. Normalmente son
letras de alfabetos, números o caracteres especiales como +, -, *, /, etc. No
necesariamente serán uno solo, ya que un símbolo puede ser una combinación como
palabras reservadas de un lenguaje de programación then, end, beging, else,
while, etc.
Expresión Regular
Representan
patrones de cadenas de caracteres. Se conocen más como metalenguajes que sirven
para describir los lenguajes regulares.
Diagrama de Transición
Es
el conjunto de secuencias de entrada que representan gráficamente los símbolos
validos por la gramática, es una representación de los universales autómatas
que aparecen en la matemática y otras ciencias.
Tabla de Transiciones
Es
la manera más cercana de representar los autómatas, consta de filas que
representan los estados y las columnas que representan los símbolos de entrada.
Adicionalmente se agregan dos columnas para representar los tokens y para
indicar retrocesos.
Cadena
Se
define como una secuencia de símbolos de un lenguaje determinado. Por ejemplo
0001, abcd, a+4*b, 11000, etc. Una cadena siempre tiene una longitud que esta
denotada por la cantidad de símbolos independientes que la conforman.
|abcde| →5
|000111| →6
Cuando
la cadena es vacía se representa como |λ|→0.
Lenguaje
Un
lenguaje es un conjunto de palabras que se puede representar con un determinado
alfabeto.
Autómata
Es
una construcción lógica que recibe como entrada una cadena de símbolos y
produce una salida indicando si la salida es una cadena que pertenece a un
determinado lenguaje.
Autómata Finito
Son
formas matemáticas para describir las diferentes clases particulares de
algoritmos.En el mundo de la computación permiten reconocer cadenas de símbolos,
por eso se usan en la etapa de léxico de los compiladores.
Autómata Finito Determinista
Formalmente,
un autómata finito determinista M es una colección de cinco elementos:
1. Un alfabeto de
entrada S.
2. Una colección
finita de estados Q.
3. Un estado inicial
Q0.
4. Una colección
de estados finales o de aceptación Qf.
5. Una función f
: Q×S→ Q que determina el único estado siguiente para el par(Qi, S)
correspondiente al estado actual y la entrada.
Autómata Finito No Determinista
Si
se permite que desde un estado se realicen cero, una o más transiciones
mediante el mismo símbolo de entrada, se dice que el autómata finito es no
determinista. A veces es más conveniente diseñar autómatas finitos no
determinista.
Un
autómata finito no determinista es una colección de cinco objetos (Q,S, Q0,
Qf, f), donde:
1. Una colección finita de estados Q.
2. Un alfabeto de entrada S.
3. Un estado inicial Q0.
4. Una colección de estados finales o de
aceptación Qf.
5.
Una función f : Q×S→P(Q) que
determina un subconjunto de Q para el par(Qi, S) correspondiente al
estado actual y la entrada. P(Q) son los subconjuntos de Q. (AFN) en lugar de
deterministas.
Autómata de Pila
Formalmente
un autómata de pila es una séxtupla de la forma (S,S,é,T,i,F) donde:
S: Es una colección finita de estados
S: Es el alfabeto
de la maquina
é: Es la
colección finita de símbolos de pila
T: Es una colección finita de transiciones
i: Es el estado inicial (es un elemento de
S)
F: Es la colección de estados de aceptación
(es un subconjunto de S)
Autómata de Turing
Formalmente
una máquina de Turing es una
séxtupla de la forma (S, S, G, d, i, h) donde:
S: Colección finita de estados (por lo menos
2 uno de inicio y uno de parada).
S: Es un conjunto finito de símbolos distintos de espacio en
blanco (D), llamado alfabeto de la maquina.
G: Conjunto finito de símbolos, incluidos los de S,
que se conocen como símbolos de la maquina (incluye D)
d: Función de
transición de la maquina
i: Elemento
de S, llamado estado inicial
h: Elemento de S, llamado estado de parada.
Publicado por:
Pedro Antonio Villalta, perfil de Google+
https://plus.google.com/u/0/105223072803758915793/aboutPedro Antonio Villalta, perfil de Google+