La sintaxis de un lenguaje de programación describe las combinaciones de simbolos que

forman un programa sintácticamente correcto.

Los lenguajes formales están formados por PALABRAS, las palabras son CADENAS y las cadenas
están constituidas por CARACTERES de un ALFABETO.

Caracteres y alfabetos
Un CARÁCTER o SIMBOLO es el elemento constructivo básico, es la entidad fundamental
indivisible a partir del cual se forman los alfabetos.

Un ALFABETO es un conjunto finito de caracteres. Se lo identifica, habitualmente, con la letra

griega ε (épsilon), y con sus caracteres se construyen las cadenas de caracteres de un Lenguaje
Formal.

Un carácter de un alfabeto puede ser “múltiple” (como por ejemplo ab, cde) ab es un carácter
y cde es otro.

Cadenas
Un CADENA es una secuencia finita de caracteres tomados de cierto alfabeto y colocados uno
a continuación de otro.

Para los conocedores del Lenguaje de Programación C: recuerden la diferencia que existe entre
‘a’ y “a”. Es la misma diferencia que existe entre un carácter de un alfabeto y una cadena
compuesta por ese único carácter

Longitud de una cadena

Es la cantidad de caracteres que lo componen, se representa como |S|.

CADENA VACÍA
La cadena vacía es la cadena que no tiene caraceteres, formada con la letra griega épsilon. Su
longitud es 0.

Potenciación
Cuando una cadena contiene un carácter que se repite un número indefninido de veces,
podemos utilizar la potenciación con le objetivo de simplificar a la cadena.

Para un carácter no existe la “potencia” 0

Con la pontenciación se obtienen cadenas mas claras y entendibles.

Concatenación
La concatenación de 2 cadenas, produce una nueva cadena formada por los caracteres de la
primera cadena seguida inmediatamente por los de la segunda.
La concatenación se extiende rápidamente a mas de 2 cadenas.
La concatenación no es conmutativa, salvo en casos excepcionales (Por ejemplo que S1 = ab y
S2= ab => S1.S2 = abab y S2.S1 = abab)

Casos posibles
Caso 1: Si ambas cadenas son idénticas, entonces la concatenación es conmutativa.
Caso 2: Cuando ambas cadenas están compuestas por una repetición del mismo carácter,
entonces son conmutativas.
Caso 3: La cadena vacía es la identidad para la concatenación. S*e = e*S = S

Potencia de una cadena

La potencia de una cadena es igual que en el otro caso, es el resultado de concatenar la cadena
S n veces
Sn
S0 = ε (cadena vacía, para cualquier cadena)
S1 = S
S2 = SS

Un caso particular es que ε n ¿ ε para cualquier valor entero de n >=0

Lenguaje Natural
Se llama lenguaje natural a todo lenguaje hablado y/o escrito que es utilizado por los seres
humanos para comunicarse.

Estos tienen 4 caracteristicas fundamentales

1) EVOLUCIONAN con el paso del tiempo, incorporando nuevos términos y nuevas reglas
gramaticales para mejorar y actualizar la comunicación.

2) Sus REGLAS GRAMATICALES surgen después del desarrollo del lenguaje, para poder explicar
su sintaxis.

3) el SIGNIFICADO (semántica) de cada palabra, de cada oración, y de cada frase de un

Lenguaje Natural es más importante que su composición sintáctica.

4) Los lenguajes naturales son intrinsecamente ambiguos

Por otro lado un Lenguaje Formal, es un conjunto de cadenas formadas con caracteres de un
alfabeto dado, y tiene dos características fundamentales.
1) las cadenas que constituyen un Lenguaje Formal no tienen una semántica asociada, solo
tiene una sintaxis dada por la ubicación de los caracteres dentro de esta cadena.
2) un Lenguaje Formal nunca es ambiguo.

Un lenguaje regular nunca puede evolucionar por que están definidas por reglas gramaticales
PRESTABLECIDAS y se deben ajustar rigurosamente a ellas.

Palabra
Una cadena es vacía o bien está compuesta por una sucesión de uno o más caracteres que
pertenecen a un alfabeto dado, como hemos visto ya en muchos ejemplos.

Si una cadena pertenece a un determinado Lenguaje Formal, decimos que la cadena es una
PALABRA de ese lenguaje.

Un Lenguaje Formal puede ser descripto por extensión, por comprensión, mediante una frase
en un Lenguaje Natural (castellano, en nuestro caso) o mediante otras formas especiales que
veremos más adelante.

Dado que una palabra es una cadena que pertenece a un determinado Lenguaje Formal, todos
los conceptos sobre cadena explicados se aplican a las palabras.
Sea el lenguaje
L = {(abc)n / 0  n  3} = {, abc, abcabc, abcabcabc}.
Entonces:
– La longitud de la palabra abc es |abc| = 3.
– La palabra vacía  es un miembro de este lenguaje.
– La concatenación de las palabras abc y abcabc produce otra palabra de este lenguaje:
abcabcabc. En cambio, la concatenación de la palabra abcabc consigo misma produce la
cadena abcabcabcabc, que no es una palabra de este lenguaje.
– La potencia (abc)2 es una palabra del lenguaje.

La concatenación de dos palabras produce una cadena que no siempre es una palabra del
lenguaje.

Cardinalidad de un Lenguaje Formal es la cantidad de palabras que lo componen

Ejemplo 33 L = {a, ab, aab} es un lenguaje de cardinalidad 3 sobre el alfabeto {a, b}. Ejemplo 34
El lenguaje L = {} es un lenguaje muy especial, pues está formado solo por la palabra vacía. Su
cardinalidad es 1, ya que contiene una palabra.

SUBLENGUAJES

un SUBLENGUAJE es un subconjunto de un Lenguaje Formal dado.

El sublenguaje vacío, habitualmente representado con el símbolo ø, es un sublenguaje de

cualquier Lenguaje Formal.

No se debe confundir el sublenguaje vacío, que tiene cardinalidad 0, con el lenguaje que solo
contiene la palabra vacía, que tiene cardinalidad 1.

Lenguajes formales infinitos Son aquellos que tienen una cantidad infinita de palabras,
aunque cada una de ellas tiene una longitud finita.
No existen las palabras de longitud infinita.

Cerrado bajo concatenación: cuando dos palabras de un lenguaje concatenadas generan

siempre otra palabra del mismo lenguaje.

Dado un alfabeto , el LENGUAJE UNIVERSAL sobre este alfabeto es un Lenguaje Formal

infinito que contiene todas las palabras de que se pueden forman con los caracteres del
alfabeto , más la palabra vacía.
Se lo representa con la notación *

Una propiedad fundamental del Lenguaje Universal es que es cerrado bajo concatenación.

Ciertos Lenguajes Formales están relacionados con la sintaxis de los Lenguajes de

Programación.
Un Lenguaje de Programación (LP) tiene palabras reservadas, nombres creados por el
programador, constantes enteras y reales, caracteres de puntuación, operadores aritméticos,
operadores lógicos, declaraciones, expresiones, sentencias, etc.
Todos estos elementos constituyen diferentes Lenguajes Formales, algunos infinitos y otros
finitos.

Una Gramática Formal es, básicamente, un conjunto de PRODUCCIONES, es decir: reglas de

reescritura que se aplican para obtener las palabras del Lenguaje Formal que la Gramática
Formal en cuestión genera. Una Gramática Formal genera un determinado Lenguaje Formal,
único.

Para construir las PRODUCCIONES de una Gramática Formal se requieren tres tipos de
símbolos: – los símbolos “productores”, como es S en el Ejemplo 1; – los símbolos que forman
las palabras del lenguaje generado, como son los caracteres a, b y c en el Ejemplo 1; y – ciertos
símbolos especiales que llamaremos metasímbolos, como -> (OPERADOR DE PRODUCCIÓN)

Una Gramática Formal puede tener, entre sus producciones, una muy particular que se
denomina PRODUCCIÓN-ÉPSILON y que se escribe, por ejemplo: S -> ε. Esta notación significa
que S es reemplazada por “nada” o que genera la palabra vacía.

Definición Formal de una gramática formal

Toda Gramatica Formal es una 4-upla(Vn,Vt,P,S) donde:

Vn = es el vocabulario de no terminales, conjunto finito de productores

Vt = es el vocabulario de terminales, caracteres del alfabeto sobre el cual se construyen las
palabras del lenguaje formal que es generado por la gramática descripta
P = es el conjunto finito de productores
S e Vn es un no terminal especial llamado axioma. Es el no-terminal a partir del cual siempre
deben comenzar a aplicarse las producciones

Una Gramatica Formal genera un lenguaje Formal, significa que esa gramática es capaz de
generar todas las palabras del Lenguaje Formal, pero no genera las cadenas que están fuera
del lenguaje.

G = ( {S, T}, {a, b}, {S -> aT, T -> a, T -> b}, S )

Vn = {S,T}

Vt = {a,b}

P = {S -> aT, T-> a, T -> b}

S=S

La jerarquia de Chomsky establece una clasificación de cuatro tipos de Gramatica Formales

que, a su vez, generan cuatro tipos diferentes de Lenguajes Formales.

Las Gramáticas Formales se clasifican según las restricciones que se imponen a sus
producciones, y la Jerarquía de Chomsky establece estos cuatro niveles:

Clasificación

– Gramáticas Regulares o Gramáticas Tipo 3

– Gramáticas Independientes del Contexto o Gramáticas Tipo 2

– Gramáticas Sensibles al Contexto o Gramáticas Tipo 1

– Gramáticas Irrestrictas o Gramáticas Tipo 0

Por otro lado, estos cuatro tipos de gramáticas generan los siguientes tipos de Lenguajes
Formales

Gramatica Regular
Sus producciones tienen las siguientes restricciones
- El lado izquierdo debe tener un solo no-terminal
- El lado derecho debe estar formado por:
a) un solo terminal, o
b) un terminal seguido de un no-terminal, o
c) épsilon

También es válida una GR en la que se invierte el orden en el lado derecho de aquellas

producciones que tienen dos símbolos.
Restricciones:
- el lado izquierdo debe tener un solo no-terminal,
- el lado derecho debe estar formado por:
a) un solo terminal, o b)
b) un no-terminal seguido de un terminal, o
c) “épsilon”

Gramática regular que genera un lenguaje regular infinito

Compuestas por las llamadas PRODUCCIONES RECURSIVAS: producciones en las que el no

terminal que figura en el lado izquierdo también figura en el lado derecho.

Por ejemplo:
La producción T -> aT, es una producción recursiva

Dos Gramáticas Formales son EQUIVALENTES si generan el MISMO Lenguaje Formal.

Gramatica independientes de contexto (GIC)

No tiene restricciones con respecto al lado derecho de sus producciones, aunque si requiere
que el lado izquierdo de cada producción siga siendo un único no-terminal.

Por las restricciones establecidas sobre los 2 tipos de Gramaticas Formales, es fácil notar que
toda GR es una GIC, pero la inversa no es cierta.

La frase “independiente de contexto” relfeja que, como el lado izquierdo de cada producción
solo puede contener un único no-terminal, toda producción de una GIC puede aplicarse sin
importar el contexto donde se encuentre dicho no-terminal.
Gramatica Irrestricta
Sus producciones tienen la forma general: α -> β, donde tanto α como β pueden ser secuencias
de no-terminales y/o terminales, con α ≠ ε.

Ejemplo:
G = ( {S, A, B, C, D, E}, {a}, {S -> ACaB, Ca -> aaC, CB -> DB, CB -> E,
aD -> Da, AD -> AC, aE -> Ea, AE -> ε}, S )

Gramática sensible al contexto

Una GSC es una gramática irrestricta, pero con una sola condición entre las longitudes
|α| ≤ |β|

Derivacion
La derivación es el proceso que permite obtener cada una de las palabras de un Lenguaje
Formal a partir del axioma de una Gramatica Formal que lo genera, y aplicando
sucesivamente, las producciones convenientes de esa gramática. El mismo proceso también
permite descubrir si una cadena es una palabra o no del Lenguaje.

Existen diferentes formas de representar una derivación:

1) en forma horizontal, utilizando el símbolo => para relacionar un paso de la derivación con el
paso

siguiente;

2) en forma vertical, reemplazando, en cada paso, un noterminal por su lado derecho para
producir

una nueva línea de esta derivación;

3) en forma de árbol, donde el axioma de la gramática es la raíz del árbol.

Derivacion Vertical

DERIVACIÓN VERTICAL A IZQUIERDA: en cada paso de la derivación se reemplaza el noterminal

que se encuentra primero (de izquierda a derecha) en la cadena de derivación.
 DERIVACIÓN VERTICAL A DERECHA: en cada paso de la derivación se reemplaza el noterminal
que se encuentra primero (de derecha a izquierda) en la cadena de derivación.

Entre ambas se obtiene la misma palabra

Sintaxis y BNF

Un lenguaje de Programación es una notación utilizada para describir algoritmos y estructuras

de datos que resuelvan problemas computacionales.

Un lenguaje de programación está formado, básicamente, por un conjunto de LRs y un

conjunto de LICs.

Las categorías LEXICAS o TOKENS (palabra en inglés muy utilizada) como son los
identificadores, los números enteros, lo reales, los caracteres, las cadenas constantes, los
operadores y los caracteres de puntuación, constituyen diferentes LRs. Algunos de ellos son
finitos ( como los operadores) y otros infinitos( como los identificadores y los números).

Por otro lado, las expresión y las sentecias de un LP son, en general, LICs. Los llamaremos
CATEGORíAS SINTÁCTICAS. Como tales, estos lenguajes no pueden ser generador por GRs ni
por GQRs.

Una Gramatica Formal no sólo describe un Lenguaje Formal, si no que también se la puede
utilizar para DESCRIBIR la sintaxis de un lenguaje que genera. La sintaxis de un LP debe
describirse con precisión, utilizando una notación sin ambigüedades. La notación utilizada se
denomina BNF.

El elemento más utilizado en todo LP es el IDENTIFICADOR: una secuencia de uno o más

caracteres que nombra diferentes entidad de un LP (varia bles, funciones, procedimientos,
constantes, tipos, etc). Los identificadores constituyen un LR infinito.
Representación de las Prioridades de los Operadores en una GIC: Cuánto más cerca del
axioma, menor es la prioridad de un operador.

La reducción es el proceso inverso a la derivación. Va de derecha a izquierda.

La notación BNF consiste en un conjunto de REGLAS que definien, con precision, la sintaxis de
los componentes y de las estrucutras de un LP dado.
Cada BNF se forma con elementos provenientes de tres conjuntos disjuntos
El simbolo ::= se puede leer como “ES”
-metavariables o no-terminales: palabras o frases encerradas entre corchetes angulares.
<identificador>
-terminales: caracteres del alfabeto o palabras del lenguaje sobre los cuales se constituye un
LP.

Metasimbolos: caracteres o grupos de caracteres que ayudan a representar estas reglas.

BNF Y ANSI C
1) Los noterminales (categorías lexicas y sintacticas) estan escritos en italica, eliminandose los
metasimbolos < y >
2) El operador “es” está representado por : (dos puntos)
3) No existe el metasímbolo | (“ó”), sino que cada lado derecho de un determinado no
terminal se escribe en una linea separada
4) En algunos casos de usa el metasímbolo uno de para representar varios lados derechos que
son caracteres par aun no terminal.
5) Los terminales se escriben en negritas
6) Un Símbolo opcional esta indicado con un subíndice op
7) El lado derecho de una regla recursiva se representa como en el BNF original

Categorías lexicas o tokens de ANSI C

las palabras reservadas, los identificadores, las constantes, las cadenas literales, los operadores
y los caracteres de puntuación. Estos tokens son LRs.}
Los elementos que componen un LR se denominan palabras, en el area de Lenguajes Formales.
Aquí los llamaremos lexemas.
Un Lexema puede ser una palabra de un LR (token) o también una cadena que no pertenece a
ningun LR.

Los comentarios y las directivas del preprocesador no pertenecen al lenguaje ANSI C, los
eliminamos en el proceso de deteccion de lexemas.

Tokens

Palabras reservadas: El ANSI C posee 32 palabras reservadas, que constituyen los elementos
de un LR finito: el token palabraReservada

palabraReservada: una de char do double else float for if int long return sizeof struct typedef
void while

Identificadores: Los identificadores en C tampoco pueden comenzar con un digito. Un

identificador puede comenzar con una letra minúscula o un guión bajo.
Su BNF es el siguiente

Constantes:
constante: una de constanteReal constanteEntera constanteEnumeración constanteCarácter

literalCadena: El token literalCadena corresponde a todas las cadenas de caracteres que se

pueden representar en

ANSI C, como "abc"; como se observa, los DELIMITADORES son comillas.

Operadores y caracteres de puntuación:

operador: uno de ++ * + & ! sizeof / % < <= == != && || ?: = +=

carácterPuntuación: uno de ( ) { } , ;
Las llamadas directivas al preprocesador no forman parte del lenguaje, un ejemplo es #include
<stdlib.h>

Categorias gramaticales

1) Expresiones: las expresiones constituyen un importantisimo LIC en cualquier lenguaje de

programación, una EXPRESION es una secuencia de operandos y operadores más el posible
uso de paréntesis. Tengase en cuenta que siempre una constante, variable o invocación de
una función son casos particulares y mínimos en una expresión.
En ANSI C no existen las constantes booleanas como TRUE y FALSE, ni tampoco el tipo
 boolean.
Tiene más de 40 operadores
Hay que tener en cuenta la prioridad de los operadores, la asociatividad (que puede ser a
derecha o a izquierda con una diferencia que es determinada por el formato de la
producción: recursiva a izquierda para el primer caso y recursiva a derecha para el segundo
caso.
Objeto: es una región de la memoria de la computadora, compuesta por una secuencia de
uno o mas bytes consecutivos, que tiene la capacidad de contener la representación de
valroes. Una variable es un objeto, una expresión no lo es.
Lvalue: es una expresión que designa un objeto

En algunos casos la BNF describe situaciones que son sintacticamente incorrectas. Esto se debe
a que la BNF también es utilizada para la construcción del compilador y ciertas detecciones las
hace este programa para mayor eficiencia.

2) Declaraciones y definiciones
Una definición es como una declaración, pero provoca una reserva de memoria para el
objeto o la función definidos.

Por ejemplo un prototipo es una declaración de una función y cuando se define la función
podemos decir que es una “definición”

Sentencias
Las sentencias especifican acciones que llevará a cabo la computadora en tiempo de
ejecución.

La sentencia compuesta queda definida por las llaves y lo que ellas encierran. Notar que
primero van, si existen, las declaraciones y luego las sentencias.

SEMANTICA

Objeto: es una región de almacenamiento de datos en memoria cuyo contenido puede

representar valores durante la ejecución del programa. Por ejemplo, una variable.

TIPO: Brinda el significado de un valor almacenado en un objeto o retornado por una función.
Por ejemplo al declarar una variable se especifica cual es su tipo y, en consecuencia, que
valores puede contener.

Automatas

Un automata es un mecanismo abstracto que tiene la capacidad de reconocer un LF. También

tiene la capacidad de rechazar toda cadena que no es una palabra del lenguaje.
En otras palabras: un AF es un modelo matemático de un sistema que recibe una cadena
constituida por caracteres de cierto alfabeto E y tiene la capacidad de determinar si esa cadena
pertenece al LR que el AF conoce.

NOTA: Una Gramatica Formal GENERA un determinado lenguaje formal y un automata

reconoce ese LF. Reconocer un LF es tener al capacidad de reconocer cada palabra del lenguaje
y de rechazar toda cadena que no es una palabra de ese lenguaje.
 G. Formal -> genera L. Formal -> reconocido por: Automata
GR LR Autómata Finito
GIC LIC Autómata Finito Con Pila
GSC LSC Máquina de Turing
G. Irrestricta L. Irrestricto Máquina de Turing

Según la tabla podemos definir 3 tipos de Automatas

-Los autómatas finitos, que solo reconocen lenguajes regulares
-Los autómatas Finitos con Pila, que reconocen lenguajes independientes de contexto
-Las Maquinas de Turing, que reconocen a los lenguajes sensibles al contexto y a los Lenguajes
Irrestrictos

Una de las multiples aplicaciones que disponen los autómatas es la construcción del modulo
del compilador llamado Analizador LExico

Esta tarea de reconocimiento se produce de la siguiente manera: el AF recorre carácter por

carácter la cadena con la que ha sido “alimentado”. Cada carácter procesado produce un
cambio de estado en el AF. Si al terminar de analizar todos los caracteres de la cadena, el AF se
encuentra en un estado especial llamdo ESTADO FINAL o ESTADO DE ACEPTACIÓN entonces se
afirma que el AF ha reconocido a la cadena y que, por lo tanto, esta es una palabra del
lenguaje, de lo contrario la cadena es rechazada porque no pertenece al LR tratado.
Un AF puede tener varios estados finales, pero un solo estado inicial.

Todo AF tiene asociado un digrafo, llamado DIAGRAMA DE TRANSICIONES (DT), que permite
visualizar con mayor claridad, el funcionamiento del AF. Los nodos del digrafo representan los
diferentes estados del AF, y los arcos representan las transiciones entre los estados. Estas
transicciones estarán etiquetadas con símbolos del alfabeto.

Cada estado del AF tiene un nombre, habitualmente representado por un número entero no
negativo o una letra, aunque puede ser cualquier otro. El estado inicial se distingue pq se le
agrega un - a su nombre y cada estado final se diferenciará de los otros ya que tiene un + en su
nombre.

Un AF puede tener éxito o puede fracasar, tiene éxito si reconoce a la cadena “dato” como
palabra del LR que el AF reconoce y fracasa en caso contrario.
Para que el AF tenga éxito, existe una única posibilidad: leer todos los caracteres que forman la
cadena y finalizar su actividad en un estado final. Si fracasa, en cambio, puede ser por tres
motivos
a) lee todos los caracteres de la cadena pero finaliza su actividad en un estado no final.
b) no puede leer todos los caracteres de la cadena
c) llega al estado final pero la cadena tiene más caracteres que el AF no puede procesar.

Cada AF reconoce un único LR, en cambio, para un LR pueden existir muchos AFs que lo
reconozcan.

Los AF se representan mediante ERs que utilizan tres operadores: concatenación, unión y
potencia (simplificador de la aplicación reiterada del operador concatenación).

El digrafo de transiciciones para el operador unión ( + )es un poco mas complicado porque
requiere que, desde un estado partan dos o más transiciones a diferentes estados.
El termino finito en un automata no singifica que las herramientas sean finitas, si no que el
número de estados de un autómata es finito.

Podemos tener en cuenta que una palabra de longitud 1 es reconocida por un autómata con
una transición y dos estados, una palabra de longitud 2 es aceptada por un automata de 2
transiciones y tres estados.

La implementación de un CLICLO en un automata es a través del operador estrella de kleene.

Este AF a pesar de tener un solo estado, es mucho mas poderoso que los autómatas con varios
estados, pues reconoce LR infinitos.
El LR que acepta este AF incluye a la palabra vacia

El otro operador que se utiliza en la construcción de ERs que representan LRs inifnitos es el
operador clausura positiva, representado con un supraindice +, que es una simplificación de
una operación conjunta entre una concatenación y una clasura de Kleene, como aa*

Si un AF reconoce a un Lenguaje Universal sobre cierto alfabeto, ninguna cadena podrá ser
rechazada

Cuando un operador clausura de Kleene actúa sobre una concatenación ocurre lo siguiente:

Un Automata finito reconoce a un LR cuando acepta cada palabra del lenguaje y rechaza toda
cadena que no es una palabra del lenguaje.

Automatas finitos determinísticos: son aquellos cuya característica funciona es que para
cualquier estado en que se encuentre el automata en un momento dado, la lectura de un
carácter determina sin ambigüedades cual sera el estado de la próxima transición

Definición Formal de un AFD

E = sigma

Formalmente un AFD es una 5-upla (Q,E, T, qo, F) donde

-Q es un conjunto finito de estados
-E es el alfabeto de caracteres reconocidos por el autómata
-qo ε Q es el estado inicial (único)
-F ∁ Q es el conjunto de estados finales
- T: Q x E -> Q es la funcion de transiciones

Generalmente la función de transiciones es representada por medio de una TABLA DE

TRANSICIONES (TT)

Ejemplo 14
M = (Q, E, T, qo, F) donde:
Q = {0,1,2,3};
E = {a,b}
qo = 0
F = {2,3}
T = {0 => a =>1, 1 => a => 2, 1 => b => 3, 3 => a => 3}

TT A B
0- 1 -
1 2 3
2+ - -
3+ 3 -

Un AFD es completo si cada estado tiene exactamente una transición por cada carácter del
alfabeto

Un AFD es completo cuando su tabla de transiciones no tien “huecos” si los tiene, el AFD es
incopleto. Un hueco es – en la tabla.

Un AFD siempre tiene que estar completo para idferentes aplicaciones computacionales. Un
AFD se implementa mediante una matriz que representa la TT esta matriz, no puede contener
elementos sin información.

Pasos para completarlo:

(1) Se agrega unn nuevo estado al que denominamos ESTADO DE RECHAZO o ESTADO DE NO
ACEPTACIÓN
(2) Se reemplaza cada “hueco” que hay en la TT por una transición a este nuevo estado
(3) Se incorpora una nueva entrada en la TT para el estado de rechazo, en la que se
representarpan ciclos para todos los caracteres del alfabeto.

La lectura de un carcter erroneo provoca que le AFD transite al estado de rechazo, del cual
nunca podrá salir.
Luego de seguir esos pasos se obtiene un nuevo AFD con un nuevo conjunto de estados Q y
una nueva función de transiciones T.

Sabemos que 2 AFDs son EQUIVALENTES si reconocen el mismo LR.

UN AFD es una colección de tres conjuntos, como ya hemos apreciado en las secciones
anteriores:

1) Un conjunto finito de estados, uno de los cuales se designa como el estado inicial
(único) y otros (uno o más) como estados finales.
2) Un alfabeto de caracteres con los que se formas las cadenas que serán procesadas por
el AFD
3) Un conjunto finito de transiciones que indican, para cada estado y para cada carácter
del alfabeto, a que estado debe moverse el AF

Cuando existe una secuencia de caracteres que debemos procesar desde el primero hasta el
último carácter, necesitamos conocer cuando termina esa secuencia. Existen dos formas de
hacerlo:
a) conocemos la longitud de la secuencia.
b) la secuencia termina con un centinela.

El valor centinela indica ”fin de datos”, también es utilizado para separar cadenas.

Un compilador es un complejo programa que lee un programa escrito en un lenguaje
fuente, habitualmente un lenguaje de alto nivel y lo traduce a un programa equivalente
en un lenguaje objeto, normalmente mas cercano al lenguaje de máquina.
Automatas finitos con pila

Los AUTOMATAS FINITOS CON PILA son mas poderosos que los autómatas finitos,
pq además de reconocer a los LR tienen la capacidad de reconocer a los LICs (como
expresiones aritmeticas y las sentencias de un LP).

Una LIC es un LF que es generado por una GIC

noterminal -> (terminal + noterminal)*

Decimos que un AFP es mas poderoso que un AF ya que este ultimo solo tiene control
sobre los caracteres que forman la cadena a analizar, mientras que un AFP controla
los caracteres a analizar y la pila

Definicion formal: un AFP esta constituido por

a) un flujo de entrada (infinito en una dirección) que contiene la secuencia de
caracteres a analizar
b) un control finito formado por estados y transiciones (similar a un AF)
c= una pila abstracta, que establece la gran diferencia con los AFs. Esta pila se
representa como una secuenci ad esimbolos o caracteres tomados de cierto alfabeto,
diferente sobre el que se construye un LIC. En la pila, el primer carácter de la
secuencia es el que se encuentra en el tope de la pila.

Es una 7-upla M = (E, A, A’, T, e0, p0, F)

-E es un conjunto finito de estados
-A es el alfabeto de entrada, cuyos caracteres se utilizan para formar la cadena a
analizar
-A’ es el alfabeto de la pila
-e0 es el estado incial
-p0 es el símbolo inicial de la pila que indica que la pila no tiene simbolos
-F es el conjunto de estados finales
-T es la función T: E x (A U {E}) x A’ -> conjuntos finitos de E x A’*

un AFP puede reconocer un LIC de dos maneras

1) por estado final, como en los AFs
2) por pila vacía

AUTOMATA FINITO CON PILA DETERMINISTICO (AFPD)

Definicion
-Un alfabeto de entrada A. Son los símbolos con los que se forman las palabras del
LIC a reconocer. Hay un símbolo especial que se llama fdc, que solo aparece al final
de la cadena de estudio para indicar la terminación de la misma
-Un flujo de entrada infinito en una dirección, que tiene la cadena a analizar
- Un alfabeto A’ de ismbolos de la pila. Hay un símbolo especial, al que llamaremos $
que indica pila vacía.
-Una pila infinita en una dirección. Inicialmente la pila está vacia (indicada con el
símbolo $)
-Un conjunto finito y no vacios de estados
- Un estado inicial
-Un conjunto de estados finales
- Una función de transiciones entre los estados definidos

Hayu 2 formas de moverse en una pila, y para asegurar que sea determinístico solo
podemos utilizar uno de ambos caminos

Primera forma de movimiento: Si a e A entonces T(e,a,R) = (e´, alfa) indica: si el AFPD

se encuentra en el estado e, lee el símbolo de entrada a y tiene el símbolo R en el
tope de la pila, entonces pasa al estado e’ y reemplaaz el símbolo R por la secuencia
de simbolos alfa, además adelanta un posición en el flujo de entrada.
Segunda forma de movimiento T(e, E,R ) = (e’, alfa) indica: si el aFPD se encuentra en
el etado e y tiene el símbolo R en el tope de la pila, entonces pasa al estado e’ y
reemplaza en la pila el símbolo R por la secuencia de simbolos alfa.

Una Tabla de movimientos es como una Tabla de eventos, pero con la diferencia que
no hablamos únicamente de estado sino que también hablamos de símbolo del tope
de la pila

Siempre que se pueda construir un AFPD que reconozca por estado final se podrá
construir un AFPD que reconozca por pila vacía y viceversa.

El programa que se debe compilar es una secuencia de caracteres que termina con un
centinela.
Un compilador es un complejo programa que lee un programa escritor en un lenguaje
fuente (habitualmente un lenguaje de alto nivel – es decir que es más fácil de entender
para los humanos) y lo traduce a un programa equivalente en un lenguaje objeto
(normalmente
Al programa original se lo llama programa fuente y al obtenido se lo denomina
programa objeto.
El proceso de compilación está formado por 2 partes

1) El ANÁLISIS, que a partir del programa fuente, crea representación intermedia del
mismo
2) La SÍNTESIS que a partir de esta representación intermedia, construye el programa
objeto.

El Análisis está formado por 3 fases

a) El análisis Léxico
b) El Analisis Sintactico
c) El análisis Semantico

El análisis lexico detecta los diferentes elementos básicos que constituyen un programa fuente,
como son: identificadores, palabras reservadas, constantes, operadores y caracteres de
puntuación. Por lo tanto el análisis elxico solo se ocupa de los lenguajes regulares que forman
parte del Lenguaje de Programación. Esta fase tiene como objetivo detectar palabras de estos
lenguajes, estas palabras son denominadas LEXEMAS y los LRs a los que pertenecen estos
lexemas se denominan CATEGORIAS LEXICAS o TOKENS.

El Analisis sintactico trabaja con los tokens detectados durante el análisis lexico (su entrada
son tokens). Esta etapa de análisis si conoce la sintaxis del LP y, en consecuencia tendrá la
capacidad de determinar si las contrucciones que componen el programa son sintácticamente
correctas. Pero no podrá determinar en su totalidad si el programa es sintácticamente
correcto.

Llamaremos Scaner -> al analizador lexico

Llamaremos Parser -> Analizador Sintactico

El Parser recibe tokens del Scanner y los agrupa en unidades, tal como está especificado por las
producciones de la GIC utilizada. Mientras se realiza el Analisis Sintactico, el PArser verifica la
corrección de la sintaxis y, si encuentra un error sintáctico, el Parser emite el diagnostico
correspondiente.

En la medida que las estructuras semánticas son reconocidas, el Parser llama a las
correspondientes rutinas semánticas que realizarán el análisis emanticos.

El análisis semántico realiza diferentes tareas, completando lo que hizo el análisis sintactico.
Una de estas imporantes tareas es la verificación de tipos, para que cada operador trabaje
sobre operandos permitidos se´gun la especificación del lenguaje de prog.

Las rutinas semánticas llevan a cabo dos funciones

1) Chequen la semántica estática de cada construcción, es decir, verifican que la

construcción analizada sea legal y que tenga un significado.
 2) Si la construcción es semánticamente correcta, las rutinas semanticas también hacen
la traducción; es decir, genera el código apra una maquina virutal, que atraves de sus
instrucciones implementan correctamente la construcción analizada

Las GICs sirven para especificar la sintaxis independiente del contexto.

La semántica estatica de un LP define las restricciones Sensibles al Contexto son

manejadas como situaciones semánticas. En consecuencia, el componente semántico de
un LP se divide, habitualmente, en 2 clases: semántica estática, que es la que nos interesa
en este momento, y semántica en tiempo de ejecución.

La semántica estática de un LP define las restricciones sensibles al contexto que deben

cumplirse para que el programa sea considerado correcto.

1) Todos los identificadores deben estar declarados

2) Los operadores y lo operandos deben tener tipos compatibles
3) Las rutinas procedimientos y funciones deben ser llamados con el número apropiado
de argumentos.

Variables en C

Puede contener letras y dígitos, pero el primer elemento debe ser una letra o _

Son case sensitive

Definición Formal de las Expresiones Regulares.

La ER original se construye utilizando solo los operadores básicos (+, ., *). Se los define
formalmente de la siguiente manera recursiva:

(1) Ø es una ER que representa al LR vacío (sin palabras, cardinalidad 0).

(2) ԑ es una ER que representa al LR que solo contiene la palabra vacía: {ԑ}
(3) Todo carácter x de un alfabeto corresponde a una ER x que representa a un LR que
solo tiene una palabra formada por ese carácter x. Ejemplo si ∑ = {a, b}, entonces a es
una Er que representa al LR {a} y b es una ER que representa al LR {b}.
(4) Una cadena s es una ER s que representa a un LR que contiene la palabra s. Ejemplo:
dada la cadena abc, la ER abc representa al LR {abc}.
(5) Si R1 y R2 son ERs, entonces R1+R2 es una ER.
(6) Si R1 y R2 Son ERs, entonces R1.R2 (R1R2) es una ER.
(7) Si R1 es una ER entonces R1* es una ER.
(8) Si R1 es una ER, entonces (R1) es una ER.
Estas es definición formal oficial de las ERs. Se amplía la definición con.

(9) Si R1 es una ER, entonces R1+ es una ER.

(10)Si R1 es una ER, entonces R1n (con n ≥ 0 entero) es una ER.
Los tokens se pasan como valores “simples”, por ejemplo: Identificador, Operador,
Constante, CaracterPuntuación, etc. Algunos tokens requieren algo más que su propia
identificación, por ejemplo, las constantes requieren su valor, los identificadores requieren
el String; es decir que el scanner debe realizar, a veces, una doble función: identificar el
token y evaluarlo.

En el proceso para detectar tokens, el scanner puede encontrar errores; a estos errores se
los denomina Errores Léxicos.

Errores léxicos típicos

1) Nombres ilegales de identificadores: un nombre contiene caracteres inválidos

2) Números incorrectos: un número contiene caracteres inválidos o no está formado
correctamente -> 3,14 en vez de 3.14

Los errores léxicos se deben a descuidos del programador. La recuperación de errores

léxicos es sencilla y siempre se traduce en la generación de un error de sintaxis que será
detectado mas tarde por el analizador sintáctico cuando el analizador léxico devuelve un
componente léxico que el analizador sintáctico no espera en esa posición.

Análisis sintactico

Todo lenguaje de programación tiene reglas que describen la estructura sintáctica de

programas bien formados.

Este impone una estructura jerarquica a la cadena de componentes léxicos, que se

representará por medio de arboles sintácticos.

Un árbol se construye con los tokens que envía el Scanner.

Existen 2 formas de análisis sintáctico

Descendente (Top-Down): construye el árbol desde la raíz S, hasta llegar a las hojas
Ascendente (Bottom-UP) : construye un árbol desde las hojas hacia la raíz (S)

Análisis semánticos: completa el trabajo del análisis sintactico. La tarea es realizada por las
rutinas semánticas ellas se encargan de chequear la semántica estática de cada
construcción, y generar código maquina.

Las rutinas semánticos son llamadas por el parser

El chequeo semántico se encarga por ejemplo de comprobar si los tipos de datos que
intervienen en las expresiones son compatibles, si los argumentos de una función o
procedimiento coinciden en tipo y cantidad con lso parámetros, si un identificador ha sido
detectado antes de utilizarlo, también verifica que no haya reclaraciones repetidas.

Estos errores son detectados en tiempo de compilación (semántica estática)

Existen otros tipos de errores, que se detectan en tiempo de ejecución, como la divisón
por 0 p un subíndice fuera de rango.