: Analizador Léxico

¿Qué es un analizador léxico?

Es la primera fase de un compilador. Consiste en un programa que recibe como entrada el código fuente de otro programa.

¿Cuál es la función principal del analizador léxico?

Es leer el flujo de caracteres de entrada y transformarlo como una salida en una secuencia de componentes léxicos que utilizará el analizador sintáctico.

¿Cuáles son las otras funciones del analizador léxico?

Eliminar comentarios del programa, eliminar espacios en blanco y avisar de errores léxicos.

Funciones secundarias del analizador léxico

• Relacionar los mensajes de error del compilador con el programa fuente.
• Localizar el número de caracteres de una nueva línea detectada.

Proceso que lleva a cabo un analizador léxico

• El primer paso consiste en crear un escáner, el cual se encarga de verificar que no existan caracteres no presentes en el lenguaje.
• Finalmente, es un reconocimiento de caracteres de un lenguaje para generar una tabla de símbolos.

: Patrones, Lexemas y Componentes Léxicos

¿Qué es un patrón?

Es una regla que genera la secuencia de caracteres que puede representar a un determinado componente léxico.

¿Qué es un lexema?

Es una cadena de caracteres que concuerda con un patrón que describe un componente léxico.

Tipos de componentes léxicos

Las relaciones, los números y los identificadores son 3 tipos de componentes léxicos. (Nota: también está la constante y el literal)

¿Qué es un componente léxico?

Es la secuencia lógica y coherente de caracteres relativa a una categoría: identificador, palabra reservada, literales, operador o carácter.

: Tablas de Tokens y Símbolos

¿Qué es una tabla de tokens?

Una serie de renglones, de los cuales cada uno tiene una lista de valores.

¿Qué información provee una tabla de símbolos?

Da un identificador.

Qué información es asociada con un nombre.

Cómo se asocia la información con el nombre.

Cómo acceder a esta información.

¿Cuáles son las dos funciones que realizan las tablas de tokens?

Verificar que la semántica sea correcta.

Ayudar en la generación apropiada de código.

¿Qué es una tabla de símbolos?

Un componente necesario de un compilador.

¿Cuándo se debe construir una tabla de tokens?

Durante el paso de un análisis léxico por medio de un índice.

: Errores Léxicos

¿Cuáles son los tipos de errores léxicos?

Nombres ilegales de identificadores, números incorrectos, errores de ortografía en palabras reservadas y fin de archivo.

¿En qué consiste el método de recuperación de errores?

Se basan en saltarse caracteres en la entrada hasta que un patrón sea reconocido.

¿Cómo detectar errores léxicos?

Los errores léxicos se detectan cuando el analizador léxico intenta reconocer componentes léxicos.

¿Cuáles son las funciones principales y secundarias del analizador léxico en la interfaz de usuario?

Su función principal consiste en leer los caracteres de entrada y elaborar como salida. Sus funciones secundarias son eliminar del programa fuente comentarios y espacios en blanco.

¿Cuáles son las correcciones de la corrección “inteligente”?

Borrar los caracteres extraños, insertar un carácter que pudiera faltar, reemplazar un carácter incorrecto por uno correcto, conmutar.

: Alfabetos, Cadenas y Gramáticas

¿Qué es un alfabeto y cuál es el símbolo por el que está representado?

Un alfabeto es un conjunto finito no vacío cuyos elementos se denominan símbolos y está representado por el símbolo Σ.

¿Qué es una longitud de cadena y cómo está conformada?

Una longitud de cadena está dada por el número de símbolos que se encuentran en ella.

Cadena vacía y universo del discurso (agrega su representación)

Cadena vacía: que no tiene símbolos y se denota con l, por lo que su longitud es: | l | → 0. Universo del discurso V: conjunto de todas las cadenas que se pueden formar con los símbolos de un alfabeto, representa por W(V).

¿Cuál es la cardinalidad del conjunto vacío y cadena vacía?

Cardinalidad del conjunto vacío = 0

Cardinalidad de cadena vacía = 1

Conceptos para formular el concepto de gramática y una definición

Gramática: conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Lenguaje vacío: conjunto vacío y que se denota por {Ø}. No debe confundirse con un lenguaje que contenga una sola cadena, y que ésta sea la cadena vacía. Palíndromos: cadenas que se leen igual hacia delante, que hacia atrás.

: Gramáticas Libres de Contexto

¿Cómo se definen las gramáticas libres de contexto?

Como toda gramática, se definen mediante una cuádrupla G = (N, T, P, S), siendo:

• N es un conjunto finito de símbolos no terminales.
• T es un conjunto finito de símbolos terminales N ∩ T = ∅.
• P es un conjunto finito de producciones.

¿Qué función tiene la gramática libre de contexto?

Permiten describir la mayoría de los lenguajes de programación. De hecho, la sintaxis de la mayoría de lenguajes de programación está definida mediante estas gramáticas.

¿Qué pasa si una gramática no genera la cadena vacía?

Puede ser transformada en una equivalente (que genera el mismo lenguaje) en forma normal de Chomsky o en forma normal de Greibach.

¿Cuál sería la forma más simple de describir cómo en una cierta gramática una cadena puede ser derivada desde el símbolo inicial?

La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas.

¿De qué otra forma se le conoce a las gramáticas libres de contexto?

Este tipo de gramáticas son también conocidas como gramáticas de tipo 2 o gramáticas independientes del contexto. Son las que generan los lenguajes libres o independientes del contexto.

: Árboles de Derivación

¿Qué es un árbol de derivación?

Es un conjunto de puntos, llamados nodos, unidos por líneas, llamadas arcos. Un arco conecta dos nodos distintos.

¿Cómo se representa un símbolo no terminal y un símbolo terminal?

Se representa con una letra mayúscula el no terminal y con minúscula el terminal.

Propiedades para hacer un árbol un conjunto de nodos

• Hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior) que no tiene arcos incidentes.
• Todos los nodos están conectados al nodo raíz mediante un único camino.
• Los nodos que no tienen hijos se denominan hojas, el resto de los nodos se denominan nodos interiores.

¿Por qué está conformado un árbol de derivación?

Nodo raíz, nodos interiores y hojas.

¿Cómo está compuesto un árbol de derivación?

• El nodo raíz está rotulado con el símbolo distinguido de la gramática.
• Cada nodo interior corresponde a un símbolo no terminal.

: Forma Normal de Chomsky (FNC)

Reglas que necesita una GLC para que se encuentre en una Forma Normal de Chomsky (FNC)

• No tiene variables inútiles.
• No tiene producciones λ (excepto posiblemente S → λ).

Proceso de transformación de una GLC a una Forma Normal de Chomsky

• Agregar un nuevo símbolo inicial.
• Quitar las transiciones Є.

¿Cuál es una propiedad importante al realizar el árbol de derivación con la gramática FNC?

Una propiedad importante de la FNC es que cada rama del árbol sólo tiene dos hijos posibles, por ende, es un árbol de derivación binario.

¿A qué tipo de gramática pertenece la Forma Normal de Chomsky?

Pertenece a una gramática libre de contexto.

¿En qué consiste una Forma Normal de Chomsky?

La Jerarquía de Chomsky explora, de menor a mayor complejidad, las diferentes reglas a partir de las cuales es posible generar expresiones de un lenguaje.

: Diagramas de Sintaxis

¿Qué es un diagrama de sintaxis?

Un diagrama de sintaxis es un grafo dirigido con elementos terminales y no terminales.

¿De qué forma se representan los elementos terminales y no terminales dentro del grafo de un diagrama de sintaxis?

Terminales: con círculos y elipses.

No terminales: con rectángulos.

¿Qué es un símbolo no terminal?

Un símbolo es no terminal cuando requiere una explicación mediante una regla o producción.

¿Qué compone a un diagrama de sintaxis?

Constan de una serie de cajas o símbolos geométricos conectados por arcos dirigidos.

¿Qué significa BNF y EBNF?

BNF: Forma de Backus-Naur.

EBNF: Forma Extendida de Backus-Naur.

: Analizadores Sintácticos

¿Qué es un analizador sintáctico?

Es un programa informático que analiza una cadena de símbolos.

¿Cuál es el recorrido que hace el análisis descendente?

Es un recorrido de árbol desde la raíz hasta las hojas.

¿Cuál es el problema que presenta el análisis sintáctico por descenso recursivo?

Es un proceso no muy eficiente.

¿Para qué se utiliza un analizador sintáctico?

Para encontrar las estructuras presentes en su entrada.

¿Dónde es la aplicación más común de los analizadores sintácticos?

En los compiladores, forma parte de los compiladores de los lenguajes de programación.