Lenguajes Formales

Por qué utilizamos lenguajes formales

Como acabamos de comentar, para transformar la secuencia de caracteres de entrada en una

Secuencia de componentes léxicos utilizamos autómatas de estados finitos. Sin embargo, estos

Autómatas los especificaremos utilizando expresiones regulares

Por qué utilizamos lenguajes formales

Como acabamos de comentar, para transformar la secuencia de caracteres de entrada en una

Secuencia de componentes léxicos utilizamos autómatas de estados finitos. Sin embargo, estos

Autómatas los especificaremos utilizando expresiones regulares

Conceptos básicos

Para que el analizador léxico consiga el objetivo de dividir la entrada en partes, tiene que poder

Decidir por cada una de esas partes si es un componente separado y, en su caso, de que tipo.

De forma natural, surge el concepto de categoría léxica, que es un tipo de símbolo elemental

Del lenguaje de programación. Por ejemplo: identificadores, palabras clave, números enteros, etc.

Palabras clave Palabras con un significado concreto en el lenguaje. Ejemplos de palabras clave

En C son while, if, return. . . Cada palabra clave suele corresponder a una categoría léxica.

Palabras clave Palabras con un significado concreto en el lenguaje. Ejemplos de palabras clave

En C son while, if, return. . . Cada palabra clave suele corresponder a una categoría léxica.

Fin de entrada Se trata de una categoría ficticia emitida por el analizador léxico para indicar

Que no queda ningún componente pendiente en la entrada. Autómatas finitos deterministas

Un autómata finito determinista es una quíntupla (Q, Σ, E, q0, F) donde:

Q es un conjunto finito de estados.

Σ es un alfabeto.

E ⊆ Q×Σ×Q es un conjunto de arcos tal que si (p, a, q) y (p, a, q0) pertenecen a E, se tiene

Que q = q 0 (condición de determinismo).

q0 ∈ Q es el estado inicial.

F ⊆ Q es el conjunto de estados finales. Construcción de un AFD a partir de una expresión regular

Podemos construir un AFD a partir de una expresión regular. La idea básica es llevar en cada

Estado del autómata la cuenta de en qué parte de la expresión “estamos”. Para esto, emplearemos

Lo que llamaremos ´ítems, que serán expresiones regulares con un punto centrado (•).

Analizadores LR

Vamos a analizar una técnica eficiente de análisis sintáctico ascendente que se puede

Utilizar para analizar una amplia clase de gramáticas de contexto libre. La técnica se denomina

Análisis sintáctico LR (k) Cuando se omite, se asume que k, es 1. El análisis

LR es atractivo por varias razones.

• Pueden reconocer la inmensa mayoría de los lenguajes de programación que puedan ser

Generados mediante gramáticas

...