Edición de «Demostraciones (Teoría de Lenguajes)»

__TOC__
{{Back|Teoría de Lenguajes}}

= Lenguajes Regulares =

{{:Demostraciones Lenguajes Regulares (Teoría de Lenguajes)}}

= Lenguajes libres de contexto =

== Propiedades ==

=== Union ===

'''Si L1 y L2 son LIC, entonces L1 U L2 tambien lo es.''' 

Dadas dos gramaticas que representen a los dos lenguajes que forman la union, basta con construir una nueva gramatica (suponiendo que la interseccion entre los no terminales es vacia) a partir de la union de los no terminales, terminales y producciones. Basta crear un nuevo simbolo distinguido ''S'' y producciones de la forma <math>S \rightarrow S_1</math> y <math>S \rightarrow S_2</math>.

=== Concatenacion ===

'''Si L1 y L2 son LIC, entonces L1L2 tambien lo es.''' 

La demostracion es analoga al caso anterior. Se construye una gramatica nueva uniendo los simbolos y producciones de G1 y G2, y se agrega un nuevo simbolo distinguido ''S'' con la produccion <math>S \rightarrow S_1 S_2</math>.

=== Repeticion ===

'''Si L1 es LIC, entonces L1+ tambien lo es.''' 

Para generar la gramatica que represente a L1+, basta añadir un nuevo simbolo distinguido ''S'' con las producciones <math>S \rightarrow S_1 S</math> y <math>S \rightarrow S_1</math>. Esto permite repetir el lenguaje tantas veces como se desee.

=== Interseccion ===

'''Si L1 y L2 son LIC, la interseccion puede no ser un lenguaje libre de contexto.'''

Un contraejemplo es tomar <math>L_1 = \{ a^n b^m c^l : n = m \}</math> y <math>L_2 = \{ a^n b^m c^l : m = l \}</math>, ambos LIC, mientras que su interseccion <math>L = \{ a^n b^m c^l : n = m = l \}</math> no lo es.

'''Si L1 es LIC y L2 es regular, la interseccion es LIC'''

La demostracion es analoga a la interseccion de lenguajes regulares, con la excepcion de que se añade una pila al automata generado, la cual esta controlada por L1. Notar que una demostracion equivalente no funciona para dos libres de contexto, pues seria necesario mantener dos pilas en simultaneo.

=== Complemento ===

'''Si L es LIC, su complemento puede no ser un lenguaje libre de contexto'''

Suponiendo que lo fuera, entonces como la union preserva indepedencia del contexto, podria escribirse la interseccion como composicion de union y complementacion usando De Morgan, y se estaria probando que la interseccion de LICs genera LICs, lo cual ya se demostro que es falso.

=== Lenguajes {ww} ===

'''El lenguaje de la forma ww no es independiente de contexto'''

Sea el lenguaje <math>L = \{ ww : w \in \Sigma ^*\}</math>, vale que L no es LIC. Puede demostrarse tomando el lenguaje L1 como la interseccion entre L y el lenguaje regular <math>a^*b^*a^*b^*</math>. Si L fuera LIC, entonces L1 tambien debiera serlo. Pero L1 resulta de la forma <math>a^n b^m a^n b^m</math>, que puede demostrarse por pumping que no es LIC.

Esto tiene como resultado que un lenguaje de programacion en el cual se use declaracion de variables no basta una gramatica independiente de contexto para especificarlo, pues no hay manera de reconocer, dado el uso de una variable, si esta ya fue declarada o no.

== Lema de Pumping (LIC) ==

=== Altura del árbol ===

La altura del árbol de derivación es la longitud del camino más largo en el árbol de derivación tal que comienza en la raíz y el final es una hoja (definicion natural de arbol). Vale que la hoja siempre es un terminal o <math>\lambda</math>. Notar que en el árbol de derivación, la base (hojas leídas en preorder) es igual a la cadena derivada.

Sea una gramatica donde <math>a</math> es la longitud del lado derecho más largo entre todas las producciones. Dado un árbol T para una cadena <math>\alpha</math>, vale que <math>| \alpha | \leq a^h</math>, donde <math>h</math> es la altura del arbol. 

La demostración se hace por inducción sobre la altura. El caso base con h = 0 es trivial (<math>\alpha = S \implies | \alpha | = 1 \leq a^0 = 1</math>). El paso inductivo para <math>h + 1</math> se basa en que la base correspondiente a la altura <math>h</math>, llamémosla <math>\gamma</math>, cumple la HI; y como <math>\alpha</math> se deriva a partir de <math>\gamma</math> expandiendo a lo sumo <math>| \gamma |</math> simbolos no terminales, entonces <math>| \alpha | \leq a * | \gamma | \leq a * a^h = a^{h + 1}</math>.

=== Pumping (LIC) ===

El lema de pumping para LIC es similar al de gramaticas regulares. La idea es que para toda cadena que supere una longitud critica ''n'' del lenguaje (puede tomarse <math>a^{|V_N|+1}</math>), la cadena pueda descomponerse en 5 partes ''r,x,y,z,s'' tal que puedan insertarse tantas repeticiones de ''x'' y ''z'' como se desee y que la cadena se mantenga en el lenguaje. Se pide ademas que la longitud de ''x+z'' sea no nula (para que haya algo a insertar) y que ''x+y+z'' no supere a '''n'''.

Decimos que un árbol de derivación mínimo T para la cadena <math>\alpha</math> es uno de altura mínima tal que no existe otro de la misma altura que tenga menos derivaciones. La demostración parte de un árbol T mínimo para una cadena <math>\alpha</math> con <math>|\alpha| \geq n</math>. Usando el lema anterior, puede probarse que <math>a^h \geq | \alpha| \geq n = a^{|V_N|+1}</math>, lo que lleva a que <math>h \geq |V_N|+1</math>.

En otras palabras, si la cadena es lo suficientemente grande, entonces la altura del arbol que la genera sera mayor estricto a la cantidad de simbolos no terminales que tiene la gramatica. Por lo tanto, recorriendo la rama mas larga del arbol, debe haber por lo menos un no terminal repetido (supongamos ''A'').

Se considera entonces que la aparicion mas baja de ''A'' genera la cadena ''y'', mientras que la siguiente genera ''xyz'' (lease ''vwx'' en la figura).

[[Image:PumpingCFL.PNG|300px]]

Esto significa que ''A'' deriva (en uno o mas pasos) tanto en ''y'' como en ''xyz'', y que ''S'' deriva en ''rAs''. Haciendo induccion en la cantidad de apariciones de ''x'' y ''z'' (caso base es cero) es sencillo ver que ''A'' termina derivando en ''xAz'' o ''y'', con lo que <math>r x^i y z^i s</math> es forma sentencial del lenguaje.

Nos falta ver que <math>|xz| > 0</math>. Llamemos <math>A_2</math> a la aparición más baja de A, y <math>A_1</math> a la que le precede. Supongamos que <math>|xz| = 0</math>. Esto quiere decir que podríamos reemplazar el subárbol con raíz en <math>A_1</math> por el árbol con raíz en <math>A_2</math> y tener un árbol T' que genera la misma cadena <math>\alpha</math>. Como <math>A_2</math> ocurre después que <math>A_1</math>, T' tendría menos derivaciones que T. Pero dijimos que T es un árbol mínimo. Absurdo, que vino de suponer que <math>|xz| = 0</math>.

'''NOTA''': Un detalle importante que se toma en el final (y que no queda tan claro en los apuntes) es la justificación de que <math>|xyz| \leq a^{|V_N|+1} </math> (en el dibujo es vwx).
La respuesta es sencilla, recorremos el árbol de abajo hacia arriba buscando la segunda aparición de A, la cantidad  MÁXIMA de no terminales por los que tenemos que pasar hasta encontrar el primer repetido es <math>|V_N|+1 </math>. Esa es la justificación por la que podemos afirmar que ese subárbol tiene esa altura y de ahí acotar la longitud de <math>xyz</math>.

== Decidibilidad ==

Los siguientes problemas sobre lenguajes libres de contexto no son decidibles:
* Dada una gramatica libre de contexto, es ambigua?
* Dado un LIC, existe una gramatica que lo represente que no sea ambigua?
* Es la interseccion de dos LIC vacia?
* Son dos LICs iguales?
* Dado un LIC, es igual a Sigma*, donde Sigma es el alfabeto?

== Equivalencias ==

=== Automata a Gramatica ===

La conversion de automata a gramatica se hace a partir de un automata por pila vacia. Se basa en la construccion de simbolos no terminales de la forma ''[q,A,p]'', tal que cada no terminal asi definido genera las cadenas ''w'' tal que implican que en el automata se haga pop de ''A'' en el stack (y de todos los demas simbolos que genero ''A'') y se pase al estado ''p''. En otras palabras, 
<math>[q,A,p] \Rightarrow ^*_G x \Longleftrightarrow (q,x,A) \vdash ^* _M (p, \lambda, \lambda )</math>.

Las producciones de la gramatica se construyen, entonces, de la siguiente manera:
* <math>S \rightarrow [q_0, Z_0, q]</math>, siendo ''q'' todos los estados posibles. Esto significa generar todas las cadenas que comienzan en en el estado inicial, sacan Z0 de la pila (dejandola vacia) y terminan en cualquier estado. Es decir, todas las cadenas q acepta el automata.

* <math>[q,A,q_{m+1}] \rightarrow a [q_1, B_1, q_2] [q_2, B_2, q_3] \ldots [q_m, B_m, q_{m+1}]</math> sii <math>(q_1, B_1 \ldots B_m) \in \delta (q,a,A)</math>. Los estados ''q2,q3...'' distintos del inicial y final son cualquier combinacion de estados del automata. Esto genera, dada una transicion de un estado a otro cambiando ''A'' por una secuencia de simbolos ''B'', todos los posibles caminos entre estados que permiten hacer pop de cada uno de los ''B''. Es decir, para ir de un estado ''q'' a otro ''p'' haciendo pop de ''A'', se hacen todos los caminos posibles de ''q'' a ''p'' haciendo pop de cada uno de los simbolos que se generaron a partir de ''A''.

Notar que en la segunda regla, ''a'' podria ser lambda, y la secuencia de ''B'' podria ser vacia si la transicion que consume a ''A'' del tope del stack no pushea ningun simbolo. En ese caso se reemplaza la secuencia de no terminales por lambda.

Para demostrar la vuelta de la doble implicacion, es decir, que <math> (q,x,A) \vdash ^i _M (p, \lambda, \lambda ) \Longrightarrow [q,A,p] \Rightarrow ^*_G x</math>, se hace induccion sobre ''i'', o sea, la cantidad de pasos que se dan en el automata para vaciar la pila consumiendo la cadena ''x''.

El caso base (i = 1, es decir, la cadena es un terminal o lambda) es trivial a partir de las reglas para construir las producciones. El paso inductivo separa a ''x'' en ''a + y'', siendo ''a'' un terminal o lambda, y ''y'' el resto de la cadena. En un primer paso, se consume ''A'' del stack y ''a'' de la entrada y se reemplaza ''A'' por una sucesion de simbolos ''B''. Cada uno de estos ''B'' deriva, en menos de ''i'' pasos del automata, en un pedazo de la cadena ''y''. 

Entonces, por hipotesis inductiva, se puede hacer el salto a la gramatica, y se llega a que cada uno de los <math>[q_j,B,q_{j+1}]</math> que conforman la produccion con lado izquierdo ''[q,A,p]'' genera un pedazo de ''y''. Entonces el lado derecho construido para el ''[q,A,p]'' de la tesis deriva efectivamente en ''a + y'', o sea, ''x''.

La ida, <math>[q,A,p] \Rightarrow ^i_G x \Longrightarrow (q,x,A) \vdash ^* _M (p, \lambda, \lambda )</math>, se prueba de manera similar. El caso base, con la cadena ''x'' igual a ''a'', siendo ''a'' un terminal o lambda, se prueba directo a partir de las reglas.

El paso inductivo requiere partir la cadena ''x'' en ''a + x1 + x2 +...+xn'', tal que cada uno de los ''xi'' se deriva a partir de cada simbolo <math>[q_j,B,q_{j+1}]</math> que aparece luego de la primera derivacion. Como estos alcanzan cada ''xi'' en menos de ''i'' pasos, vale la HI, y se puede hacer el salto al automata, en particular, instanciando los ''qj'' en los estados que recorre el automata para vaciar la pila.

=== Gramatica a Automata ===

Para pasar de una gramatica a un AP, se genera un AP por pila vacia de un solo estado, que represente las derivaciones mas a la izquierda generadas por la gramatica. Tener en cuenta que cualquier forma sentencial no terminal generada a partir de derivaciones mas a la izquierda puede representarse como <math>x A \alpha</math>, donde ''x'' es un string de terminales, y <math>A \alpha</math> es la cola (de ahora en mas ''y''), con ''A'' no terminal y <math>\alpha</math> conjunto de terminales y no terminales.

La idea es que el automata comience con el simbolo distinguido ''S'' de la gramatica en la pila, y a cada paso tome una decision basado en el tope de la pila exclusivamente (pues hay un solo estado).

* Si en el tope de la pila hay un no terminal, entonces lo reemplaza no deterministicamente por alguna de sus producciones. Esto es, si <math>A \rightarrow \alpha</math> en la gramatica, entonces <math>(q, \alpha) \in \delta (q, \lambda , A)</math> en el automata.

* Si en el tope de la pila hay un terminal, se matchea con la entrada y se hace pop del stack. Es decir, que para todo terminal, <math>\delta(q,a,a) = \{ (q,\lambda )\}</math>. Así, el automata consume todos los terminales que va apilando (que son parte de ''x'' en la forma sentencial) hasta llegar al primer no terminal ''A'' de la cola y reemplazarlo por alguna de sus producciones.

Para probar que los lenguajes son equivalentes, es decir, que <math>S \Rightarrow ^+ w \Longleftrightarrow (q,w,S) \vdash ^+ (q, \lambda, \lambda)</math>, se prueba como resultado intermedio más general que <math>A \Rightarrow ^m w \Longleftrightarrow (q,w,A) \vdash ^n (q, \lambda, \lambda)</math>.

La ida se prueba por induccion sobre ''m'', es decir, sobre la cantidad de producciones que se aplican para llegar de ''A'' a ''w''. El caso base (1) es trivial a partir de las definiciones, pues la unica derivacion posible es ''A'' en lambda. 

Para el paso inductivo se supone que ''A'' se deriva en <math>X_1 \ldots X_k</math> en un primer paso, y para los ''m-1'' restantes (es decir, cada uno de los X) se puede aplicar hipotesis inductiva y se obtiene el string de terminales correspondientes. El primer paso es el unico que basta probar entonces, y sale directo a partir de la primer regla.

La vuelta, <math>A \Rightarrow ^m w \Longleftarrow (q,w,A) \vdash ^n (q, \lambda, \lambda)</math> tambien se hace por induccion. El caso base (n = 1) nuevamente es trivial, pues implica que ''w'' sea la cadena vacia y la produccion que la genera sea ''A'' en lambda.

El paso inductivo es similar al de la ida. Se observa que ''A'' genera <math>X_1 \ldots X_k</math> en un paso por la regla 1, y los ''X'' entonces generaran los strings correspondientes para formar ''w'' (por hipotesis inductiva). Por lo tanto, ''A'' genera ''w''.

=== Automata por estado final a pila vacia ===

La construccion de un automata por pila vacia (PV) a partir de un automata por estado final (EF) es sencilla. Basta con agregar dos estados nuevos al automata, uno inicial y otro que servira de final para vaciar el stack.

Primero se agrega un nuevo simbolo para el comienzo del stack, llamemoslo X0, y se agrega por debajo de la configuracion inicial original (supongamos Z0) mediante una transicion lambda de un nuevo estado <math>q_0 \prime</math> al original <math>q_0</math>.

Esto impide que el automata original EF pueda vaciar su pila accidentalmente y terminar, caso en el que deberia rechazar la cadena, y un equivalente por PV entonces la aceptaria.

Para simular la aceptacion, se agregan transiciones lambdas de todos los estados finales del automata original a un nuevo estado qf. Este estado no consume simbolos de la entrada y se limita a vaciar la pila. Asi, cuando el automata original llega a un estado final, puede seguir moviendose por el automata o vaciar la pila y aceptar (si no queda mas input).

Para probar que el lenguaje generado por PV incluye al de EF se debe probar que si una cadena ''x'' pertenece a EF, entonces pertenece a PV. Basta usar configuraciones instantaneas y ver que si <math>(q_0,x,Z_0) \vdash ^* _{EF} (q, \lambda, \gamma) (q \in F)</math> entonces en PV vale <math>(q_0,x,Z_0 X_0) \vdash ^* _{PV} (q, \lambda, \gamma X_0)</math>. Esto significa que si en EF se llega a un estado final con cierta configuracion en la pila habiendo consumido toda la entrada, en PV se llega al mismo estado pero con X0 en la base de la pila.

La vuelta se prueba de la misma forma.

=== Automata por pila vacia a estado final ===

La construccion de un automata por EF a partir de uno por PV es similar al caso anterior, en el que se agrega un nuevo estado inicial y un nuevo estado final. Del nuevo estado inicial al inicial del PV se va por una transicion lambda que agrega un nuevo simbolo en la base de la pila (digamos X0) de la misma forma que antes.

Sin embargo, como ahora no hay estados finales (puesto que PV acepta por pila vacia), se generan transiciones lambda desde todos los estados del PV original al nuevo estado final <math>q_f</math>. Estas transiciones requieren que esté el simbolo X0 en el tope de la pila, lo que equivale a decir que el PV original vacio la pila aceptando la cadena de entrada. El X0 entonces se agrega para que la pila no se vacie y sea posible moverse al estado final.

La demostracion es analoga al caso anterior.

== Lenguajes deterministicos ==

Un lenguaje libre de contexto deterministico es aquel que puede reconocerse mediante un automata de pila deterministico. Un automata de pila deterministico debe cumplir que en cualquier estado, dado un terminal a consumir y un tope de la pila determinados, haya una unica transicion posible a realizar. 

Para que se verifique esto, basta con que para cualquier 3-upla (q,a,Z) (estado, terminal, tope de pila) el conjunto determinado por <math>\delta (q,a,Z)</math> sea de cardinal a lo sumo 1. Tambien debe cumplirse que si un estado tiene una transicion lambda dado un tope de pila ''Z'', entonces no puede tener ninguna otra transicion por ese mismo tope de pila, cualquiera sea el terminal.

=== Equivalencias ===

Los lenguajes libres de contexto deterministicos estan incluidos de manera estricta en los libres de contexto. Un ejemplo es el lenguaje <math>ww^r</math> (es decir, una cadena seguida de su reverso). Intuitivamente, no puede parsearse con un APD pues el automata no tiene manera de saber cuando termino ''w'' y cuando comienza su reverso. Como nota de color, esto puede salvarse introduciendo un caracter ''$'' en el momento en que termina ''w'' y comienza el reverso, haciendo el lenguaje deterministico.

Logicamente, los LICD incluyen a los lenguajes regulares, ya que un APD por estado final no es mas que un AFD en el que no se tiene en cuenta el manejo de la pila.

Ademas, si bien en los automatas de pila estandar un automata por pila vacia es equivalente a uno por estado final, en el caso de los deterministicos la equivalencia no se mantiene. Un APD por pila vacia puede representar un lenguaje L solamente si este lenguaje es libre de prefijos.

Notar que un lenguaje sencillo como ser a* es regular, pero no es libre de prefijos, con lo cual el APD por pila vacia no puede reconocerlo. Esto hace que los APD por pila vacia sean menos poderosos que por estado final. Sin embargo, la propiedad del prefijo es lo unico que los diferencia. Vale que si se tiene un lenguaje L reconocible por un APD por estado final, y L es libre de prefijos, entonces L es reconocible por un APD por pila vacia.

Esta limitacion no es tan grave ya que para cualquier lenguaje se puede generar otro similar que sea libre de prefijos simplemente agregando un caracter terminal ''$'' al final.

Los LICD siempre tienen gramaticas no ambiguas que los representan, aunque la vuelta no siempre es cierta. Es decir, puede haber una gramatica no ambigua libre de contexto que no tiene APD que la represente.

=== Consumir cadena de entrada ===

Vale que para cualquier APD M, existe otro APD M' equivalente (por estado final) tal que M' siempre consume la cadena de entrada. Notar que este problema no existía en los lenguajes regulares. Ahora, un autómata puede no consumir por completo la cadena de entrada pues puede bloquearse al llegar a un estado del que ninguna transición es posible, o entrar en un loop infinito de lambdas, o vaciarse su stack.

Esto no sucedía en los finitos pues no había transiciones lambda, y desde cualquier estado siempre había una transición por cualquier terminal hacia otro estado (aunque fuera un estado trampa). Así, un AFD siempre consumía toda la entrada, y aceptaba sii terminaba en un estado final. En un APD puede suceder que la cadena no se consuma enteramente (caso en el cual es rechazada).

Para construir el APD M' se agregan tres nuevos estados. Primero un nuevo estado inicial ''q0' '' con una única transición lambda al original ''q0'', tal que agrega una nueva base ''X0'' en la pila, por debajo de ''Z0''. Esto asegura que en ningún caso el autómata se frena por pila vacía.

El segundo estado que se agrega es un estado trampa ''d''. Dado cualquier estado que para un tope de pila no tenga transiciones lambda, se agrega una transición por cada terminal no contemplado hacia el estado trampa. Esto permite que el autómata no se bloquee por falta de transiciones. La condición de que no haya transiciones lambda es para no romper el determinismo. A su vez, se agregan loops sobre el estado trampa para todos los terminales y símbolos de la pila.

También se agregan transiciones lambda desde todos los estados con tope de pila ''X0'' hacia el estado trampa, para capturar los casos en los que el autómata M hubiera frenado por pila vacía.

Lo último que resta por eliminar son los loops lambda, definidos tal que para todo ''i'' existen estados <math>q_i, \gamma _i</math> tales que <math>(q,\lambda ,Z) \vdash ^i (q_i, \lambda ,\gamma _i)</math>. Si existe algún estado final en el ciclo, entonces se redefine la transición lambda a partir de ''q'' por ''Z'' tal que vaya a un nuevo estado final ''f'' (del cual se construyen transiciones lambda hacia el trampa, por si era necesario consumir más input) haciendo pop del stack. Si ninguno en el ciclo era final, se redefine para que vaya al trampa, también haciendo pop del stack.

=== Complementacion ===

Vale que los LLCD son cerrados respecto de la complementación. Sin embargo, para construir un APD M' que capture el complemento de M, no basta con invertir finales con no finales como sucedía en los regulares. Puede suceder que el autómata M no consuma por completo la cadena de entrada ''w'', por lo tanto ni M ni M' (construido invirtiendo finales y no finales) la reconocerían, pues ambos se bloquearían o entrarían en un loop lambda.

Aún solucionado esto, teniendo un autómata que consuma toda la entrada (lo cual es posible de construir), puede suceder que en M la cadena termine en un estado final ''q'' con una transición lambda hacia un no final ''p''; con lo cual M' también reconocería esa cadena pues al terminar en ''q'' podría pasar a ''p'' y reconocerla.

La construcción de M' se hace entonces a partir de un M que consume toda la entrada, y debe solucionar el problema de quedar en un estado con lambdas hacia estados distintos. 

Cada estado de M' es de la foma [q,k], donde ''q'' es un estado de M y ''k'' es un entero que vale 1, 2 o 3. Los estados finales de M' son todos aquellos con ''k = 3'', y el inicial es [q0,k] con ''k = 1'' si ''q0'' es final o ''k = 2'' si no.

La intuición detrás de ''k'' es que detecta si entre transiciones sin consumo de entrada se ha pasado por un estado final. Si se pasó por un final, vale 1, si no, 2.

La función de transición se define de tal forma que si se hace a través de un lambda desde un estado ''q'' hacia un estado ''p'', entonces se va a [p,1] si ''p'' es final en M o el ''q'' de M' tenía ''k = 1'' (es decir, se encontró con un estado final o venía de un final pasando por lambdas), o a [p,2] si no (no hay finales en el camino).

Si la transición se hace de ''q'' a ''p'' consumiendo un terminal ''a'', entonces primero se permite hacer un salto hacia [q,3] por lambda desde [q,2]. Esto permite finalizar si ya se consume toda la cadena. Luego, desde [q,1] y [q,3] se agregan transiciones a ''p'' por ''a'', yendo a [p,1] si ''p'' es final, o a [p,2] si no lo es.

Resumiendo, la idea es mantener tres ''niveles'' en el autómata, uno de los cuales contiene los estados finales (3), el otro los estados alcanzados a través de una transición lambda que pasaron por un final (2) y el último los no alcanzados por lambda desde un final (1).

= Máquinas de Turing =

Las máquinas de Turing se definen como un autómata con una cinta infinita a derecha (es decir, las celdas van de cero a infinito positivo) con la siguiente aridad:

<math>MT = <Q, \Gamma ,B , \Sigma , \delta ,q_0, F></math>
* <math>Q</math> conjunto de estados
* <math>\Gamma</math> alfabeto de la cinta
* <math>B \in \Gamma</math> símbolo blanco, representa una celda vacía
* <math>\Sigma \subset \Gamma</math> alfabeto de entrada, no incluye al blanco
* <math>\delta : Q \times \Gamma \rightarrow partes(Q \times \Gamma \times \{ L,R\} )</math> acciones
* <math>q_0 \in Q</math> estado inicial
* <math>F \subseteq Q</math> estados finales

Las acciones de la máquina dependen del estado actual y del símbolo que hay bajo la cabeza lectora/escritora, e implican escribir otro símbolo (puede ser el mismo) y moverse a izquierda o derecha.

La configuración instantánea de una máquina de Turing se define como <math>\alpha _1 q \alpha _2</math>, donde <math>\alpha _1</math> es el contenido de la cinta (sucesión de caracteres) a la izquierda del cabezal, ''q'' es el estado actual de la máquina, y <math>\alpha _2</math> es el contenido de la cinta desde el cabezal hasta el último símbolo distinto de blanco. Así, se puede especificar cuál es el estado actual, el contenido de la cinta y la posición del cabezal.

La cinta inicialmente comienza llena de blancos, excepto al comienzo donde tiene escrito el input a reconocer. Notar que el caracter blanco no puede pertenecer al alfabeto de entrada.

La máquina acepta una cadena si en su ejecución llega a un estado final, notar que la máquina no tiene transiciones desde un estado final. Como la cadena está escrita en la cinta, no existe el concepto de consumir la cadena de entrada.

== Máquina de Turing determinística ==

Una máquina de Turing es determinística cuando dado un estado y un símbolo bajo el cabezal existe una única acción. Vale que una máquina determinística puede emular a una no determinística.

Para esto se construye una MTD M' que reconoce la cadena cuando esta pertenece al lenguaje y se cuelga cuando no pertenece. La MTD construida tiene tres cintas (se puede demostrar que una máquina con un número finito de cintas equivale a una de una sola cinta). La idea es guardar en la primer cinta la cadena de entrada, en la segunda un número que simboliza una traza a seguir de la máquina M original, y la tercera usarla para emular las operaciones de M. 

Para simbolizar una traza, se calcula el máximo grado de salida (r) de los nodos de la máquina M, se numera cada transición a partir de cada estado con un número de 1 a r, y se escribe una secuencia de dígitos entre 1 y r. Esto permite recorrer todas las posibles secuencias de configuraciones instantáneas en BFS.

La MTD M', entonces, en cada iteración copia la entrada de la primer cinta a la tercera, incrementa en 1 el valor de la segunda cinta (número expresado en base ''r'' que simboliza la traza) y con esa traza emula a M sobre la tercer cinta. Si termina en estado de aceptación, se acepta la cadena. Si se traba o termina en un estado no final, se itera nuevamente.

== Lenguajes Recursivamente Enumerables ==

Los LRE (lenguajes tipo 0 en la jerarquía de Chomsky) son lenguajes reconocibles por una máquina de Turing. Son aquellos que pueden especificarse sin restricciones sobre sus producciones.

=== Gramática a MTND ===

Para pasar de una gramática tipo 0 a una MTND, se utilizan dos cintas. En la primera se guarda la cadena; en la segunda se van generando formas sentenciales de manera no determinística a partir del símbolo distinguido S. Cuando se encuentra alguna que matchea la entrada, se acepta; si no, la máquina se cuelga.

=== MT a Gramática ===

Para pasar de una MT a una gramática se establece una equivalencia entre los símbolos de la gramática y las configuraciones instantáneas de la máquina de Turing. Los símbolos generados son de la forma [a,b], donde ''a'' representará el caracter original de la cadena de entrada y ''b'' el caracter sobre el que opera la máquina.

Se proveen producciones para generar, incialmente, una cadena arbitraria de símbolos [a,a], siendo ''a'' cualquier terminal. Esto equivale a tener inicialmente en la cinta cualquier cadena. Seguidos a estos se genera una cantidad libre de simbolos [lambda,Blanco], tantos como necesitaría la cinta para operar.

La gramática genera, al principio de todo, un caracter ''q'' que representará el cabezal de la máquina. Las producciones de la gramática permiten "mover" ''q'' entre los símbolos [a,b] (modificando solamente los ''b'') en base a las acciones permitidas por la MT original.

Una vez alcanzado un estado final, se generan producciones que eliminan todos los símbolos [a,b] dejando solamente los ''a'' correspondientes a la cadena original, y finalmente a ''q''. Así, la cadena final de terminales es la cadena a generar.

== Lenguajes Sensitivos al Contexto ==

Los lenguajes dependientes del contexto se expresan con gramáticas tipo 1 en la jerarquía de Chomsky, que tienen la restricción de que la longitud del lado derecho de una producción no puede ser menor a la del lado izquierdo.

=== Autómata Linealmente Acotado ===

Los ALA pueden verse como máquinas de Turing con la cinta acotada. En un ALA el alfabeto de entrada incluye dos símbolos, usados como tope de entrada y tope de salida. El autómata no puede moverse más allá de los topes ni sobreescribirlos.

Notar que un ALA tal que en la cinta tenga una cantidad de blancos lineal a la longitud de la entrada es equivalente a un ALA con cero blancos, que opera exclusivamente sobre la cadena de entrada.

A diferencia de lo que sucedía con las MT, no hay equivalencia entre ALA y ALAD. A primera vista puede observarse que el método anterior no funciona pues el número que simboliza la traza a emular (en la segunda cinta) puede crecer arbitrariamente.

=== Gramática a ALA ===

La equivalencia entre una gramática sensitiva al contexto y un ALA se demuestra exactamente igual que para máquinas de Turing en general, excepto que en este caso puede agregarse la restricción de que si la cadena que se está generando excede el tamaño de la que se ha de reconocer se corta esa rama (pues ninguna cadena de terminales y no terminales puede derivar en una de longitud menor). Así la cantidad de posibilidades a explorar es finita.

== Lenguajes Recursivos ==

Los lenguajes recursivos se encuentran estrictamente entre los sensitivos al contexto y los recursivamente enumerables. Son aquellos reconocibles por una HTM (halting Turing machine). Es decir, existe una máquina de Turing que dada cualquier entrada, siempre para y devuelve si una cadena pertenece o no (no puede colgarse).

=== Inclusión de Sensitivos al Contexto ===

Para demostrar que los LSC están incluidos dentro de los recursivos, se construye una HTM que determine si una cadena pertenece al lenguaje. Dada una gramática GSC y una cadena de entrada w de longitud n, se construye un grafo finito donde cada nodo es un string de terminales y no terminales de longitud menor o igual a n.

Los arcos en este grafo representan si es posible ir de un string a otro mediante derivaciones de la gramática. Notar que este grafo es finito y puede construirse mediante un algoritmo.

Luego, para determinar si una cadena ''w'' pertenece al lenguaje, simplemente se verifica mediante un algoritmo si existe un camino desde ''S'' hasta el nodo que contiene a ''w''. Como lo anterior es un algoritmo (siempre termina) existe una HTM que lo ejecuta, con lo cual el lenguaje LSC es recursivo.

=== Lenguaje Recursivo no LSC ===

Para demostrar que existe un lenguaje recursivo no sensitivo al contexto se utiliza un argumento diagonal. Primero se prueba un lema que indica que dada cualquier enumeración de HTMs, existe un lenguaje recursivo que no es aceptado por ninguna de ellas (el lenguaje que dada la cadena ''i'', la acepta sii no es reconocida por la iesima HTM de la enumeración). 

Eventualmente se llega a una contradicción, pues si existe una HTM de índice ''i'' en la enumeración, la cadena ''i'' debe ser reconocida por dicha HTM sii no lo es. Notar que este lenguaje es recursivo, pues existe un algoritmo (procedimiento que siempre termina) que puede determinar si una cadena ''i'' pertenece al conjunto: simplemente corre la HTM ''i'' con esa cadena y devuelve la negación.

A partir de esto, se construye una enumeración de las HTM que reconocen todos los LSC, lo cual es posible ya que se pueden enumerar las GSCs. Pero por el lema anterior existe un lenguaje que no es reconocido por ninguna de estas HTMs, es decir, por ningún LSC. Y este lenguaje es recursivo.

La demostración parece basarse en que el conjunto de HTMs no es Recursivamente Enumerable, mientras que el de GSCs sí lo es. Por lo tanto debe existir alguna HTM que genere un lenguaje no sensitivo al contexto.

== Lenguaje Diagonal ==

El lenguaje diagonal es un ejemplo de un lenguaje que no es recursivamente enumerable. Requiere enumerar las MT y entradas posibles y llegar a una contradicción similar a la del problema de la parada.

Más formalmente, se basa en construir una tabla infinita de dos entradas. La celda (i,j) entonces vale 1 sii la máquina de Turing de nro ''j'' reconoce la cadena ''i''. La MT se encuentra codificada en binario, y la cadena de entrada es de 0s y 1s.

Entonces, puede construirse el lenguaje de las cadenas ''i'' tal que no pertenecen a la MT de igual número (lenguaje diagonal). Si este lenguaje es recursivamente enumerable, entonces existe una MT ''Mk'' tal que reconce sus cadenas. En otras palabras,

<math>w_k \in L_d \Longleftrightarrow w_k \not \in L(M_k) = L_d</math>

Con lo que se llega a una contradicción. La cadena de igual número que ''M'' es reconocida por la máquina sii no es reconocida.

Otra opción (distinta a la del pdf, revisar) es un lenguaje que acepta una cadena sii esta representa una máquina de Turing con una entrada dada, y dicha máquina para. Si dicha máquina existiera, resolvería el halting problem, lo que no es posible.

== Lenguaje Universal ==

El lenguaje universal es el que se corresponde a la MT que ejecuta cualquier otra MT con cualquier entrada. En otras palabras, toma pares de cadena y MT, y determina si la cadena es reconocida por esa MT.

'''Recursivamente Enumerable'''

Este lenguaje es recursivamente enumerable. Puede construirse una MT con 3 cintas, de las cuales la primera contiene el input (la MT ''M'' más la cadena de entrada ''w''), la segunda (inicializada con la cadena ''w'') emula la cinta de ''M'', y la tercera permite llevar cuenta del estado en el que se encuentra la ''M'' emulada.

'''No Recursivo'''

Para demostrar que este lenguaje no es recursivo, se supone inicialmente que lo es y se intenta llegar al absurdo. Para esto, se construye un algoritmo (es decir, un procedimiento que siempre para, emulable por una HTM) que dada una cadena de entrada, genera su MT con igual número. Luego se determina, usando la HTM del lenguaje universal (supusimos que era recursivo) si <math>(w_i, MT_i)</math> es aceptado, esto es, si la máquina ''i'' acepta la cadena ''i''. 

Notar que este es el complemento del lenguaje diagonal. Como es un algoritmo, siempre termina y devuelve verdadero o falso. Con lo que puede generarse fácilmente una HTM que reconozca el lenguaje diagonal directamente. Lo que es absurdo puesto que no es siquiera recursivamente enumerable.

Intuitivamente, el que el lenguaje universal sea recursivo significaría que es posible tener un método que siempre termina que resuelve (por sí o por no) la pertenencia de cualquier cadena a cualquier MT. Es decir, es capaz de decidir el halting problem.

= Analizadores Sintácticos Descendentes =

== Reescritura ==

=== Simbolos anulables ===

Un símbolo es anulable sii deriva en uno o más pasos en lambda. Una gramática no tiene símbolos anulables sii la única producción con lado derecho lambda es del símbolo distinguido, y éste no aparece en ningún lado derecho.

=== Renombramientos ===

Un renombramiento es una producción de la forma <math>A \rightarrow B</math>.

=== Simbolos inactivos ===

Un símbolo es activo sii deriva en una cadena de terminales.

=== Simbolos inalcanzables ===

Un símbolo es alcanzable sii aparece en alguna derivación a partir del símbolo distinguido, es decir, <math>S \Rightarrow ^+ \alpha A \beta</math>.

=== Orden de aplicación ===

Todos los casos anteriores son salvables mediante un algoritmo, es decir, hay algoritmos para generar una gramática G' a partir de G tal que G' no tenga símbolos anulables, ni renombramientos, ni símbolos inactivos, ni símbolos inalcanzables. El orden de aplicación de los algoritmos es el aquí expuesto.

== Analizador Descendente con Retroceso ==

El analizador descendente con retroceso (o backtracking) comienza a partir del simbolo distinguido generando formas sentenciales más a izquierda e intentando matchear con la entrada, haciendo backtracking si no lo logra. Equivale a pensar en un parser no deterministico.

Tiene el problema de que, como todos los parsers descendentes, no soporta gramáticas recursivas a izquierda, pues entra en una expansión infinita. Además, el backtracking (o no determinismo) hace que el tiempo que requiere para parsear una expresión sea inadmisible.

== Analizador Descendente Predictivo ==

El objetivo de un analizador descendente predictivo es eliminar el no determinismo del anterior sabiendo siempre de alguna manera qué producción expandir para el no terminal más a la izquierda. Para esto se utilizan los símbolos directrices de cada producción.

=== Gramática LL(1) ===

Una gramática es LL(1) sii para toda producción con el mismo lado izquierdo (es decir, para toda expansión de un mismo no terminal) la intersección de los símbolos directrices es vacía. Esto permite decidir siempre, dado un no terminal y un token del input, cuál producción elegir para expandir.

Dada una gramática G, una '''gramática ampliada''' G' es una nueva gramática en la que se le añade a cada cadena un terminal de finalización, mediante una nueva producción <math>S' \rightarrow S \#</math>. Asimismo, una '''gramática reducida''' es aquella en la que todos sus no terminales son alcanzables y activos.

==== Propiedades de LL(1) ====

'''Dada una gramática G ampliada y reducida, vale que siguientes de todo no terminal es un conjunto no vacío.'''

Esto vale pues, como G es reducida, entonces para cualquier no terminal ''U'' vale que <math>\alpha U \beta \#</math> es una forma sentencial. Por lo tanto, el conjunto de siguientes de ''U'' es igual al de primeros de ''beta''. Si este es vacío, entonces siguientes de ''U'' es igual al símbolo ''#''.

'''Dada una gramática G ampliada y reducida, si G es LL(1) entonces no es recursiva a izquierda.'''

La intuición detrás de este teorema viene dada por su contrarreciproco. Ningún parser descendente soporta gramáticas recursivas a izquierda, pues como trabaja con derivaciones más a la izquierda, puede entrar en loop al expandir siempre el mismo no terminal.

Se demuestra por el absurdo. Si es recursiva a izquierda, entonces existe un no terminal ''A'' tal que <math>A \rightarrow ^+ A \alpha</math>, pero como ''A'' debe ser activo, entonces también vale que <math>A \rightarrow ^+ \beta, \beta \in V^t</math>. Por lo tanto, tienen que suceder:

* <math>A_0 \rightarrow A_1 \alpha _1 \rightarrow A_2 \alpha _2 \alpha _1 \rightarrow \ldots \rightarrow A_k \alpha _k \ldots \alpha _1</math>, donde ''A0'' y ''Ak'' son el símbolo ''A''.
* <math>A_0' \rightarrow A_1' \alpha _1' \rightarrow A_2' \alpha _2' \alpha _1' \rightarrow \ldots \rightarrow \beta</math>, donde ''A0' ''es el símbolo ''A''.

En otras palabras, A deriva en dos cadenas distintas de las cuales una comienza nuevamente con A (donde se da la recursividad a izquierda) y otra es una cadena de terminales del lenguaje (pues A debia ser activo). 

Luego, se considera el primer valor ''i'' tal que <math>A_{i-1} = A_{i-1}'</math> pero <math>A_{i} \neq A_{i}'</math>, es decir, el punto en el que las dos derivaciones anteriores se diferencian, al usar las producciones:
* <math>A_{i-1} = A_{i-1}' \rightarrow A_i \alpha _i</math> (1)
* <math>A_{i-1} = A_{i-1}' \rightarrow A_i' \alpha _i'</math> (2)

El objetivo de la demostración será probar que ambas cadenas comparten alguno de sus símbolos directrices, con lo que la gramática no sería LL(1) y esto contradice la hipótesis.

Intuitivamente, esto se logra reemplazando el ''Ak'' de la primer cadena por beta, con lo los símbolos directrices de ambas producciones (1 y 2) serán o bien primeros de beta o bien siguientes de <math>A_{i-1}</math>.

En el caso en que la cadena beta sea no vacía, es posible descomponerla en <math>\beta = a \gamma</math>. Por lo tanto, los símbolos directrices de la cadena '''(2)''', es decir, la que deriva en beta, contienen a ''a''. Pero entonces la cadena recursiva a izquierda puede reescribirse reemplazando el último ''Ak'' por beta: <math>A_0 \rightarrow A_1 \alpha _1 \rightarrow A_2 \alpha _2 \alpha _1 \rightarrow \ldots \rightarrow A_k \alpha _k \ldots \alpha _1 \rightarrow \ldots \rightarrow a \gamma \alpha _k \ldots \alpha _1</math>.

Por lo tanto, los símbolos directrices de la producción '''(1)''' también contienen a ''a'', con lo que la intersección de los directrices de ambas producciones es no vacía, con lo que la gramática no es LL(1), lo que es absurdo.

En el caso de que beta sea vacía, esto es, el símbolo ''A'' es anulable, vale que cada uno de los <math>A_i'</math> y <math>\alpha _i'</math> lo son, con lo que los símbolos directrices de la producción '''(2)''' incluyen a siguientes de <math>A_{i-1}</math>.

Además, vale que puede completarse la primer secuencia de derivaciones de manera similar a como se hizo en el caso anterior, pero este caso cambiando al último ''Ak'' por la cadena vacía: <math>A_0 \rightarrow A_1 \alpha _1 \rightarrow A_2 \alpha _2 \alpha _1 \rightarrow \ldots \rightarrow A_k \alpha _k \ldots \alpha _1 \rightarrow \ldots \rightarrow \alpha _k \ldots \alpha _1</math>.

Suponiendo que la cadena de alfas final sea anulable, eso significa que cada uno de los <math>A_i</math> y <math>\alpha _i</math> también lo son (notar que más arriba habíamos llegado a que también los <math>A_i'</math> y <math>\alpha _i'</math> eran anulables, esto es, los que derivaban en beta). Por lo tanto, los símbolos directrices de la producción '''(1)''' también incluirán a los siguientes de <math>A_{i-1}</math>. Como siguientes de <math>A_{i-1}</math> es un conjunto no vacío por la propiedad anterior, la intersección de los directrices de ambas producciones también será no vacía, con lo que G debe ser no LL(1) (nuevamente absurdo).

La última posibilidad es que la cadena de alfas sea no anulable, es decir, existe algún terminal ''a'' en primeros de dicha cadena. Con lo cual, ese valor ''a'' está presente en los directrices de la producción '''(1)'''. Pero como los <math>\alpha _j'</math>, j < i, son anulables, entonces puedo llegar a que <math>A \alpha _k \rightarrow ^* A_{i-1}' \alpha _{i-1}' \ldots \alpha _1' \alpha _k \ldots \alpha _1 \rightarrow ^* A_{i-1}' \alpha _k \ldots \alpha _1 \rightarrow ^* A_{i-1}' a \gamma</math>.

De eso se deduce que ''a'' queda en siguientes de <math>A_{i-1}</math>, que está incluido en los símbolos directrices de la producción '''(2)'''. Entonces, ''a'' pertenece a los directrices de ambas producciones y se produce el conflicto para que G no sea LL(1).

'''Los lenguajes LL(1) estan contenidos de manera propia en los lenguajes libres de contexto determinísticos.'''

==== Eliminacion de recursividad a izquierda ====

Es posible eliminar la recursividad a izquierda de una gramática mediante un algoritmo. Para eliminar la recursividad a izquierda directa de ''A'', por ejemplo, 

<math>A \rightarrow A \alpha _1 | \ldots | A \alpha _m | \beta _1 | \ldots | \beta _n</math>

Se genera un nuevo símbolo ''A' ''y se redefine ''A'' tal que

<math>A \rightarrow \beta _1 A \prime | \ldots | \beta _n A \prime</math> 
<br/><math>A \prime \rightarrow \alpha _1 A \prime | \ldots | \alpha _m A \prime | \lambda</math>

A su vez, para eliminar recursividad a izquierda en general (es decir, también la indirecta) se usa el siguiente algoritmo:

 Numerar los no terminales de 1 a N
 
 Para i = 1 to N
   Para j = 1 to i-1
      Sustituir cada Ai -> Aj γ por
      Ai -> δ1 γ | δ2 γ | ... | δk γ
      donde Aj -> δ1 | δ2 | ... | δk
 
      Eliminar recursividad a izquierda directa de cada Ai

La idea del algoritmo es recorrer cada una de los no terminales y eliminar todas las producciones que tengan como primer símbolo generado algún no terminal anterior, cambiandolas por una producción equivalente que no depende de ese no terminal. Esto solamente puede generar recursividad a izquierda directa, que se elimina con el método anterior.

Al finalizar, cada no terminal podrá derivar en una cadena que tenga, como primer elemento, solamente un terminal o un no terminal de numeración mayor.

==== Factorizacion ====

Dada una producción de la forma <math>A \rightarrow \alpha \beta _1 | \alpha \beta _2</math>, siendo alfa el prefijo común de mayor longitud entre ambas cadenas, se puede factorizar usando:

<math>A \rightarrow \alpha A'</math>
<br/><math>A' \rightarrow \beta _1 | \beta _2</math>

Notar que a pesar de los algoritmos para eliminar factorización y recursividad a izquierda, puede haber lenguajes para los que no haya una gramática LL(1) que los reconozca (por ejemplo, cualquier lenguaje libre de contexto no determinístico, como ser <math>ww^r</math>).

=== ASDP Recursivo ===

Un analizador sintáctico descendente predictivo puede implementarse de manera recursiva definiendo un procedimiento para cada uno de los símbolos no terminales presentes en la gramática. Cada procedimiento contiene un switch dependiendo en el valor del token actual. Si el token pertenece al conjunto de símbolos directrices de una producción del no terminal del procedimiento, entonces se "ejecuta" la producción actual: los terminales son consumidos de la entrada y para los no terminales se ejecuta su procedimiento correspondiente. Por ejemplo:

 Producciones
 T -> A
 T -> ^A;
 A -> i | c | n

 Proc A()
   if (token in {i,c,n})
      A()
   else if (token in {^})
      match(^)
      A()
      match(;)
   else
      error()

La mayor desventaja es que implica generar código nuevo para cada gramática, además de ser recursivo lo que generalmente es menos performante. La ventaja es que es menos restrictivo: en principio puede capturar cualquier lenguaje libre de contexto no recursivo a izquierda.

=== ASDP con Tabla ===

(Ver definición de la [[Definiciones y teoremas (Teoría de Lenguajes)#Analizador Sintáctico Descendente de Pila (A. S. D. P.) con tabla|práctica]]).

El analizador sintáctico descendente predictivo puede implementarse también usando una tabla. La ventaja es que el código es siempre el mismo, sólo varía la tabla que se usa; además de ser más rapido pues no es recursivo. Se construye a partir de la gramática extendida.

La tabla es una matriz M con tantas columnas como símbolos terminales y tantas filas como no terminales, tal que <math>M(a,A) = 'A \rightarrow \alpha'</math> sii <math>a \in SD(A \rightarrow \alpha)</math>.

El algoritmo, dada la cadena de entrada ''w'', el token actual ''t'' y un stack auxiliar, es el siguiente. Recordar que el lado derecho de la producción <tt>Y1Y2 ... Yk</tt> se apila al revés de manera que el primer símbolo quede como tope.

 Repetir
   Si tope in Vt
       Si tope === t
          extraigo tope de la pila
          avanzo 1 en w
       Si no
          error
   Si no
       Si M(t, tope) === (tope --> Y1Y2 ... Yk)
          extraigo tope de la pila
          apilo YkYk-1 ... Y1 
       Si no
          error
 Hasta que tope === # && t === #

=== Gramática LL(k) ===

Una gramática LL(k) es análoga a una LL(1). La única diferencia radica en que los conjuntos de primeros y siguientes, en lugar de contener terminales, contienen cadenas de terminales de longitud a lo sumo ''k''. Esto reduce las colisiones entre los símbolos directrices de producciones para el mismo no terminal, pero aumenta significativamente el tamaño de la tabla de parseo en memoria.

=== Decidibilidad ===

* ''Dado un k y una gramática G, es G LL(k)?'' Es decidible, se construye el analizador y se evalúa si se producen conflictos.
* ''Dada una gramática G, existe un k tal que G sea LL(k))'' No es decidible.
* ''Dada una gramática G no LL(1), existe una gramática G' LL(1) tal que represente el mismo lenguaje?'' No es decidible.

= Analizadores Sintácticos Ascendentes =

Un estilo de análisis sintáctico de abajo hacia arriba es conocido como "shift-reduce parsing". Shift-Reduce intenta construir un árbol de parseo para una cadena de entrada empezando en las hojas y trabajando hacia arriba en dirección a la raiz. Es como el proceso de reducir un string ''w'' al símbolo distinguido inicial de la gramática. En cada reducción un substring particular de ''w''  que coincide con el lado derecho de una producción se reemplaza por el no terminal de la izq. de la misma, y si el substring se elige correctamente en cada paso, se reconstruye en reversa una derivación más a la derecha.

'''Definicion:''' Pivote: Dada <math>G = <V_N, V_T, P, S></math> y una forma sentencial derecha <math>\alpha \rho \beta</math>:
<math>\rho</math> es pivote si y sólo si <math>\exists \ (N \rightarrow \rho) \wedge \ S \rightarrow_{D}^* \ \alpha N \beta \ \rightarrow_{D} \ \alpha \rho \beta</math>

Informalmente el pivote es una subcadena que matchea con el lado deerecho de una producción y cuya reducción representa un paso "en reversa" de la derivación más a la derecha de la cadena. Es importante notar que en muchos casos el substring <math>\beta</math> más a la derecha que matchea con alguna producción no es un pivote, ya que una reducción de <math>\beta</math> llevaría a una cadena que no se puede seguir reduciendo al símbolo distinguido. Si la gramática no es ambigua, existe un único pivote en una forma sentencial derecha.


'''Algoritmo:''' Shift reduce (algoritmo general)
 Sea w = a1 ... an la cadena de entrada
 pc el símbolo apuntado en w
 La pila inicializada en vacio, tope es el tope de la pila
 
 elFin := F
 error := F
 Repetir hasta elFin
      Según
          tope es pivote
              Desapilar pivote
              Apilar A donde (A->tope) es una prod. de G
          pila == S y fin de w
              aceptar w
              elFin := T
          no es fin de w
              apilar pc
              Si pc != a_n
                  pc++
                  desplazar
          otro caso
              error := T
              elFin := T

== Precedencia Simple ==

'''Definicion:''' Relaciones de precedencia de Wirth-Weber. Permiten definir el pivote dada una forma sentencial derecha; el mismo queda encerrado entre <> al evaluar todas las relaciones de precedencia entre símbolos consecutivos. Notar que no son relaciones de equivalencia u orden.

Sea <math>G = <V_T, V_N, P, S></math>, y <math>\alpha</math> una forma sentencial derecha tal que <math>\alpha = ...X Y...</math>,

* <math>\dot = : V \times V</math>
**<math>X \dot = Y \Leftrightarrow (A \to \alpha X Y \beta) \in P</math>
**Implica que tanto X como Y están en el pivote de <math>\alpha</math>.

*<math>\dot < :V \times V</math> 
**<math>X \dot < Y \Leftrightarrow (A \rightarrow \alpha X B \beta) \in P \ \wedge \ (B \rightarrow^+ Y \gamma)</math>
**Implica que Y está en el pivote de <math>\alpha</math> y X no.

* <math>\dot > :V \times V_T</math>
**<math>X \dot > a \Leftrightarrow (A \to \alpha B Y \beta) \in P \ \wedge \ (B \rightarrow^+ \gamma X) \ \wedge \ (Y \rightarrow^* a \delta) </math>
**Implica que X está en el pivote de <math>\alpha</math> y Y no, notar que Y debe ser un terminal pues alfa es una forma sentencial derecha, esto es, no puede haber no terminales no expandidos a la derecha del pivote.

=== Gramática de Precedencia Simple ===

'''Definicion:''' Gramatica propia
* Si no hay símbolos inútiles (símbolos inalcanzables o  inactivos)
* Si no hay producciones <math>\lambda</math> excepto <math>S \rightarrow \lambda</math> (y S no aparece en la parte derecha de ninguna producción)

'''Definicion:''' Gramaticas de precedencia
*Si es propia y <math>\forall A, B \in V</math> en <math>G</math>, a lo sumo sostienen una relación de precedencia; es decir, no hay conflictos.

'''Definicion:''' Una gramatica es de precedencia simple si:
* Es de precedencia y unívocamente inversible (no hay dos lados derechos iguales) [Si <math>(A \rightarrow \alpha), (B \rightarrow \beta) \in P \Rightarrow ((\alpha = \beta)\rightarrow (A = B))</math>]

=== Algoritmo de Parseo por Precedencia Simple ===

'''Completar tabla de PS'''

Puede hacerse algorítmicamente utilizando las definiciones de P+, U+ y P*, o calculando las relaciones de precedencia entre símbolos consecutivos de la gramática "a ojo".

<math>P^+(X) = \{Y \in V \; / \; X \rightarrow^+ Y \alpha\}</math><br>
<math>U^+(X) = \{Y \in V \; / \; X \rightarrow^+ \alpha Y\}</math><br>
<math>P^*(X) = \{P^+(X) \cup \{X\}\} \cap V_T</math><br>
 
 para cada produccion A -> alfa
    para cada XY in subCadenas(alfa)
       definir X = Y
    IF Y in VN 
       definir X < P+(Y)
    IF X in VN
       definir U+(X) > P*(Y)
 
 para cada X in VN Union VT
    definir # < S Union P+(S)
    definir S Union U+(S) > #

'''Algoritmo de parsing'''

Tabla de precedencia sin conflictos y ''w'' cadena de entrada. (TC es donde apunta en ''w'').

 apilar #
 repetir
    IF TOPE < TC o TOPE = TC
         apilar TC
         avanzar ''w''
    ELSE
         IF TOPE > TC
            OBTENER alfa pivote en la pila
            BUSCAR la produccion A -> alfa
            IF no encuentra produccion A -> alfa 
                 ERROR
            ELSE  
                 reemplazar alfa en la pila por A
         ELSE
            ERROR
 hasta TC = # y en la pila hay #S
 Aceptar ''w''

== Analizador LR ==

=== Definiciones ===

'''Prefijo viable''': Sea <math>\alpha \rho \beta</math> una fsd (forma sentencial derecha) donde <math>\rho</math> es pivote, <math>\gamma</math> es prefijo viable si es prefijo de <math>\alpha \rho</math>. Son los prefijos de una fsd que pueden aparecer en el stack de un parser shift-reduce. Intuitivamente, son los prefijos de cualquier cadena que termine en el pivote. Vale que el conjunto de los prefijos viables de un lenguaje libre de contexto genera un lenguaje regular.

'''Item''': Un item LR(0) de una gramática G es una producción de G con un punto en alguna posición del lado derecho (definición del dragón). Notar que el conjunto de items de una gramática es finito.

'''Item válido''': Dado un prefijo viable <math>\gamma = \delta \alpha</math>, <math>[A \rightarrow \alpha . \beta]</math> es un ítem válido '''para''' <math>\gamma</math> ssi <math>S \rightarrow_{D}^* \ \delta A w \ \rightarrow_{D} \ \delta \alpha \beta w</math>, con <math>(A \rightarrow \alpha \beta) \in P</math>. Notar que acá <math>\alpha \beta</math> es un pivote. 

En general un item puede ser válido para muchos prefijos viables. El hecho de que un item sea válido para <math>\delta \alpha</math> da mucha información acerca de si conviene hacer un shift o un reduce teniendo <math>\delta \alpha</math> en el stack. Si <math>\beta</math> no es vacío, nos dice que todavía no leimos y escribimos todo el pivote en el stack, por lo que hay que hacer shift. Si <math>\beta</math> fuera nulo, nos diría que <math>A \rightarrow \alpha</math> es el pivote y que habría que reducir por esa producción. Lo que es cierto es que dos items válidos puede sugerir acciones distintas, con lo cual surgen conflictos. Algunos de estos conflictos se pueden solucionar mirando a los próximos símbolos en el input, pero no todos se van a poder solucionar para un gramática arbitraria.

'''Item completo''': Es un item que el punto lo tiene al final de la parte derecha de la producción.

=== Construccion del Automata ===

La idea principal es que el conjunto de los prefijos viables de un (¿lenguaje libre de contexto o LR?) es regular.  Entonces existe un AFND-L cuyo lenguaje son ellos. Sea <math>M = <K, (V_N \cup V_T), \delta, q_0, K></math>  con <math>K = \{i \ | \ i \ \textrm{es \ item \ en \ } G \} \cup \{q_0\}</math>. Todos los estados van a ser finales.

Definimos <math>\delta</math> de la siguiente forma:
# <math>\delta(q_0,\lambda) = \{[S \rightarrow . \alpha] \ | \ S \rightarrow \alpha \in P\}</math>
# <math>\delta([A \rightarrow \alpha . B \beta],\lambda) = \{[B \rightarrow . \gamma] \ | \ B \rightarrow \gamma \in P\}</math>, <math>B \in V_N</math>
# <math>\delta([A \rightarrow \alpha . X \beta],X) = \{[A \rightarrow \alpha X . \beta]\}</math>

'''Teorema:''' Dadas <math>G = <V_T, V_N, P, S></math> GLC y  M  el AFND-L construido, se cumple que <math>A \rightarrow \alpha.\beta \in \delta(q_0,\gamma) \Leftrightarrow</math> <math> A  \rightarrow \alpha . \beta</math> es item válido para <math>\gamma</math> prefijo viable. Idea de la demostración:
* '''Ida (=>)''': Se prueba por Inducción en la longitud del camino para consumir <math>\gamma</math>. 
** El caso base es long=1, con lo cual la única transición posible <math>\lambda</math>  (por '''1''') y <math>\gamma</math> tiene que ser la cadena vacía.  Como <math>\delta(q_0,\gamma) = \delta(q_0,\lambda)</math> y  <math>S \rightarrow . \alpha \in \delta(q_0,\lambda)</math> y es además un item válido para el prefijo viable <math>\gamma = \lambda</math>, el caso base se cumple.
** Para el paso inductivo asumimos verdadera la HI para long de camino menores a <math>k</math>. Las reglas para las transiciones 2) y 3) implican dos formas posibles para la última transición en el camino. Nuestra hipótesis es <math>[A \rightarrow \alpha.\beta] \in \delta(q_0,\gamma)</math> en <math>k</math> transiciones:
**# Está etiquetada con <math>X \in V</math>:  Por hipótesis y como además sabemos que en la última transición consumimos <math>X</math>, si tomamos <math>\alpha = \alpha' X</math> y <math>\gamma = \gamma' X</math>, el estado anterior tienen que ser  <math>[A \rightarrow \alpha'.X \beta]</math>, al que se llegó de <math>q_0</math> por <math>\gamma'</math> en <math>k-1</math> pasos, es decir, <math>[A \rightarrow \alpha' . X \beta] \in \delta(q_0,\gamma')</math>. Pero al ser <math>k-1</math> transiciones, vale la hipótesis inductiva, o sea, vale que <math>[A \rightarrow \alpha' . X \beta]</math> es un item válido para el prefijo viable <math>\gamma'</math>. Qué significa esto? Que <math>\alpha' X \beta</math> es un pivote, también que <math>\gamma' = \delta \alpha'</math> y que <math>S \rightarrow_{D}^* \ \delta A w \ \rightarrow_{D} \ \delta \alpha' X \beta w</math> (todo por la definición de prefijo viable e item válido para el mismo). Pero entonces notemos que <math>\delta \alpha' X = \gamma</math> también cumple la definición de prefijo viable (por quién es el pivote) y que <math>[A \rightarrow \alpha' X. \beta]</math> es un item válido para <math>\gamma</math>. Como  <math>[A \rightarrow \alpha' X. \beta] =  [A \rightarrow \alpha . \beta]</math>, llegamos a lo que queríamos: <math>[A \rightarrow \alpha.\beta] \in \delta(q_0,\gamma)</math>  implica <math>[A \rightarrow \alpha . \beta]</math> es un item válido para <math>\gamma</math> prefijo viable.
**# Está etiquetada con <math>\lambda</math>: Como la última transición fue <math>\lambda</math> tiene que haber sido usando la definición '''2''' de <math>\delta</math>. Primero, esto implica que para que el item tenga la forma  <math>[B \rightarrow . \gamma]</math>  debe pasar que <math>\alpha = \lambda</math>. Segundo, el estado previo tiene que haber sido de la forma <math>[B \rightarrow \alpha_1 . A \beta_1]</math>, y a él se tiene que haber llegado del estado inicial por el mismo <math>\gamma</math> (ya que no se consumió entrada), o sea, tiene que pertenecer a <math>\delta(q_0,\gamma)</math>. Nuevamente vale la hipótesis inductiva, entonces podemos deducir que <math>[B \rightarrow \alpha_1 . A \beta_1]</math> es item válido del prefijo viable <math>\gamma</math>. O sea, <math>S \rightarrow_{D}^* \ \delta B w \ \rightarrow_{D} \ \delta \alpha_1 A \beta_1 w \ \rightarrow_{D} \ \delta \alpha_1 \beta \beta_1 w </math> (el último paso por hipótesis y porque concluimos que <math>\alpha = \lambda</math>). Pero entonces <math>\gamma = \delta\alpha_1</math> es también prefijo viable para el pivote <math>\beta</math>, para el cual <math>[A \rightarrow \ .\beta]</math> es un item válido, llegando así a lo que queríamos probar.
* '''Vuelta (<=)'''
** Probamos primero el '''Lema''': Si <math>[A \rightarrow .\alpha]</math> es item válido para <math>\gamma</math> prefijo viable, entonces <math>[A \rightarrow .\alpha] \in \delta(q_0, \gamma)</math>. Demostración por inducción sobre <math>i</math> en <math>S \rightarrow_{D}^i \ \gamma A w \ \rightarrow_{D} \ \gamma \alpha w</math> (esto es aplicar las definiciones de p.v. e i.v. ). 
*** Caso base i = 0: Debe pasar que <math>S \rightarrow \gamma \alpha w = \alpha \ \ (\gamma, w = \lambda)</math>. En este caso el item es en realidad <math>S \rightarrow . \alpha</math> y <math>\gamma = \lambda</math>. Por construcción de <math>\delta</math> sabemos que <math>[S \rightarrow . \alpha] \in \delta(q_0, \lambda)</math>.
*** Paso inductivo: (supongamos HI cierta para <math>i</math>). Por hipotesis del lemma y def. de p.v. e i.v.,  <math>S \rightarrow_{D}^{i+1} \ \gamma A w \ \rightarrow_{D} \ \gamma \alpha w</math> . Como el <math>A</math> tiene que haber surgido en alguna derivación anterior o igual a <math>i+1</math>,  <math>S \rightarrow_{D}^k \ \gamma' A' w'\rightarrow_{D} \ \gamma' \gamma'' A w'' w' \ \rightarrow_{D}^{i-k} \ \gamma A w</math> . Notar que <math>\gamma' \gamma'' = \gamma</math> ya que ningún no terminal a la derecha de <math>A</math> puede expandirse antes que esta (por ser derivación más a la derecha). Ahora, como <math>\gamma' \gamma'' A w'' w'</math> es una f.s.d,  <math>[B \rightarrow .\gamma'' A w'']</math> es un ítem válido para el prefijo viable <math>\gamma'</math>. Por H.I., entonces <math>[B \rightarrow .\gamma'' A w''] \in \delta(q_0, \gamma')</math>. Pero aplicando la definición (3) de <math>\delta</math> por cada símbolo de <math>\gamma'</math> se ve que podemos llegar del estado <math>[B \rightarrow .\gamma'' A w'']</math>  a <math>[B \rightarrow \gamma'' . A w'']</math> consumiendo <math>\gamma''</math>. Entonces, <math>[B \rightarrow \gamma'' . A w''] \in \delta(q_0, \gamma' \gamma'') = \delta(q_0, \gamma)</math> . Para terminar, por la def. (2),  <math>[A \rightarrow .\alpha]  \in \delta(\delta(q_0, \gamma), \lambda) = \delta(q_0, \gamma)</math>, como queríamos probar.
** Ahora, con el lema probado si <math>[A \rightarrow \alpha . \beta]</math> es item válido para <math>\gamma</math>,  entonces debe pasar que <math>[A \rightarrow . \alpha \beta]</math> es item válido para <math>\delta'</math> prefijo viable (con <math>\gamma = \delta' \alpha</math>)- Por el lema anterior , <math>[A \rightarrow . \alpha \beta] \in \delta(q_0, \delta') \Rightarrow</math>  (usando la definición 3 de <math>\delta</math>)  <math> [A \rightarrow \alpha . \beta] \in \delta(q_0, \delta' \alpha) = \delta(q_0, \gamma)</math>

=== Construccion de conjuntos de items ===

==== Funcion Clausura ====

Closure encuentra todos los items en el mismo estado.

closure(I):
#Todo item en I es también un item en closure(I)
#Si <math>[A \rightarrow \alpha . B \beta]</math> está en closure(I) y <math>[B \rightarrow . \gamma]</math> es un item, entonces agregamos <math>[B \rightarrow . \gamma]</math> a closure(I)
#Repetimos hasta que no se pueden agregar más items a closure(I)

==== Funcion Goto ====

Goto encuentra el nuevo estado después de consumir un símbolo de la gramática mientras estamos en el estado actual.

goto(I, X): closure( { <math>A \rightarrow \alpha X . \beta |  A \rightarrow \alpha . X \beta \in I </math> } )

donde I es un conjunto de items y X es un símbolo de la gramática.

==== Procedimiento para conjuntos de items ====

 <math>q_0</math> <- clausura( { <math> s' \rightarrow s$ </math> } )
 K <- {<math>q_0</math>} sin marcar
 mientras hay I <math>\in</math> sin marcar
    marcar I
    para cada x <math>\in</math> V
       j <-- goto[i,x]
       si j <math>\notin</math> K entonces agregar j a K sin marcar

=== Algoritmo de parseo LR ===

Todos los analizadores LR se comportan de la misma forma, lo que cambia es la construcción de la tabla de parsing y/o el autómata, que son específicos a cada clase.

Entrada. Una cadena w y una tabla de parsing LR con funciones acción y goto para una gramática G. 

Salida. Si w pertenece a L(G), un parseo ascendente de w; si no, error.

Método. Inicialmente, el parser tiene <math>s_0</math> en el stack, donde <math>s_0</math> es el estado inicial, y w$ en el buffer the entrada. El parser ejecuta el siguiente algoritmo hasta que acepta la cadena o encuentra en la tabla una entrada de error.

 apuntar ip al primer símbolo de w$
 repetir siempre 
   sea s el estado en el tope de la pila y 
       a el símbolo apuntado por ip
   si action[s, a] = shift s' entonces
       apilar a y luego s'
       avanzar ip
   si no, si action[s, a] = reducir A -> beta
       desapilar 2 * |beta| símbolos
       sea s' el nuevo estado en el tope de la pila
       apilar A y luego goto[s', A]
       imprimir A -> beta
   si no, si action[s, a] = aceptar
       terminar
   si no
       error       

=== Analizador LR(0) ===

Un analizador LR(0) parsea una cadena utilizando el algoritmo anteriormente mencionado y una tabla. Las tablas de parseo tienen las mismas filas y columnas para todos los analizadores, en las filas ponemos todos los estados que obtuvimos del autómata y en las columnas todos los terminales y no terminales.

Algoritmo para crear una tabla de parseo LR(0):

  Para cada estado
      1. Transición a otro estado usando un símbolo terminal
         es un shift a ese estado <math>(shift\;to\;s_n)</math>
      2. Transición a otro estado usando un no-terminal
         es un goto a ese estado <math>(goto\;s_n)</math>
      3. Si hay un ítem <math>[A \rightarrow \alpha .]</math> en el estado
         hacemos una reducción con esa producción para todos los terminales
         (<math>reduce\;k</math>, donde k es la k-ésima producción)

=== Analizador SLR ===

El problema de los analizadores LR(0) es que hay muchos conflictos shift/reduce ya que al reducir lo hacemos sea cual sea el siguiente caracter.
Los analizadores SLR, mejoran este aspecto mirando el siguiente token y reduciendo solo sí el mismo se encuentra dentro de los siguientes del no terminal a la izquierda de la producción del ítem.
El algoritmo para crear la tabla de parseo es idéntico al LR(0) excepto en el tercer paso:

  3. Si hay un ítem <math>[A \rightarrow \alpha .]</math>  en el estado,
     para todos los terminales <math>c \in follow(A)</math> hacer una
     reducción con la producción <math>(reduce\;k)</math>

=== Analizador LR(1) ===

Necesitamos definir nuevas funciones Closure y Goto para crear un analizador LR(1).

  Closure(I):
    repetir
      para todos los ítems <math>[A \rightarrow \alpha . X \beta \;\; c]</math> en I
        para cualquier producción <math>X \to \gamma </math>
          para cualquier <math>d \in first(\beta c)</math> 
            <math>I = I \cup { [X \to . \gamma\;\;d] }</math>
    hasta que I no cambie
  retornar I

  Goto(I, X):
    J = {}
    para todos los ítems <math>[A \rightarrow \alpha . X \beta \;\; c]</math> en I
    <math> J = J \cup {[A \to \alpha X . \beta \;\; c]}</math>

Nuevamente la construcción de la tabla de parseo es idéntica salvo en el último paso:

  3. Si hay un ítem <math>[A \to \alpha . \;\; a]</math>  en el estado, hacemos una
     reducción para el símbolo de entrada "a" con la producción <math>(reduce\;k)</math>


Los parsers LR(1) reducen los conflictos reduce/reduce que eran más frecuentes en los parsers SLR.

=== Analizador LALR ===

Los analizadores LR(1) tienen un gran número de estados, lo que los hace poco eficientes. La idea de los analizadores LALR es: si dos estados son idénticos, excepto por el símbolo de look ahead de los ítems, los colapsamos en uno solo.

Esta forma de colapsar estados no puede producir un conflicto shift/reduce que no estuviera presente en el autómata LR(1), dado que las acciones the shift no dependen del lookahead, si no tan sólo del core del item. Sin embargo, sí puede generar conflictos reduce/reduce, como mostramos en el siguiente ejemplo:

 S' -> S
 S  -> aAd | bBd | aBe | bAe
 A  -> c
 B  -> c

Que genera el lenguaje {acd, ace, bcd, bce}. Esta gramática es LR(1). Si construímos el autómata LR(1), obtenemos el conjunto de items {<math>[A \rightarrow c . , d], [B \rightarrow c . , e]</math>} para el prefijo ''ac'' y {<math>[A \rightarrow c . , e], [B \rightarrow c . , d]</math>} para ''bc''. Si los unimos:

 A -> c., d/e
 B -> c., d/e

Vemos que introdujimos un conflicto reduce/reduce, dado que tanto <math>[A \rightarrow c]</math> como <math>[B \rightarrow c]</math> pueden ser utilizadas para reducir para los caracteres ''d'' y ''e''.

=== Propiedades LR ===

'''Propiedad:''' Si L es LLCD (Lenguaje Libre de Contexto Determinístico) y libre de prefijos, entonces existe una gramatica LR(0) que lo captura.

'''Propiedad:''' Para todo lenguaje LLCD existe una gramatica LR(k) que lo representa.

'''Propiedad:''' Para toda gramatica LR(k) existe una LR(1) equivalente.

'''Propiedad:''' Toda gramática analizable con un parser predictivo descendente es analizable con un LR(1).

= Compiladores =

La parte de compiladores se encuentra fuertemente vinculada con el uso de [[Definiciones y teoremas (Teoría de Lenguajes)#Gramaticas de Atributos|gramáticas de atributos, DDS y TDS]], depende de ésta para realizar los análisis y generación de código.

Los pasos que realiza el compilador son los siguientes, partiendo del programa fuente:
* Análisis lexicografico (genera cadena de tokens)
* Análisis sintáctico (parseo, genera árbol de derivación)
* Análisis estático (genera árbol decorado usando DDS)
* Generación de código intermedio (con DDS, optimizaciones generales)
* Generación de código objeto (con DDS, optimizaciones específicas según arquitectura)

== Análisis estático ==

El análisis estático se realiza sobre el árbol de derivación del programa generado tras el parseo, e incluye los siguientes items:
* Chequeo de tipos
* Chequeo de flujo del programa (break, continue, etc)
* Chequeo de unicidad (ej en switches)
* Apareamiento de etiquetas (linking)

== Chequeo de Tipos ==

El chequeo de tipos se hace manteniendo una tabla global de tipos que relaciona una variable con un tipo de datos. Luego a medida que se va parseando el programa se verifican los tipos correctos de las expresiones usando dicha tabla.

'''Expresión de Tipo:''' Una expresión de tipo es un tipo básico o el resultado de aplicar un constructor de tipo a una expresión de tipo.

'''Tipos básicos:''' Los tipos básicos del lenguaje, deben incluir a los tipos ''vacío'' y ''error_tipo''.

'''Constructores de tipo:''' Arreglos, registros (conjuntos de tuplas nombre:tipo), punteros y funciones.

'''Sistema de tipos:''' Conjunto de reglas que permiten asignar expresiones de tipo a fragmentos del programa.

'''Sistema de tipos seguro:''' Un sistema de tipos es seguro cuando el chequeo de tipos estático (en tiempo de compilacion) asegura que no surjan errores de tipo en runtime.

'''Lenguaje fuertemente tipado:''' Lenguaje que cuenta con un sistema de tipos seguro. Notar que las excepciones de tipo InvalidCast no cuentan como errores de tipo.

'''Equivalencia de tipos:''' La equivalencia de tipos puede definirse por nombre o por estructura. La equivalencia por estructura consiste en verificar si ambos son básicos y matchean sus tipos, o si el último constructor aplicado es el mismo y sus tipos contenidos matchean (ej puntero a int con puntero a int, primero se chequea puntero y luego int). La equivalencia por nombre es por strings.

=== Sobrecarga de operadores ===

La sobrecarga de operadores permite que un mismo operador pueda tomar distintos tipos como operandos y devolver un tipo distinto según estos últimos. Tomemos por ejemplo el operador suma, y los tipos básicos ''int'' y ''float''.

Si se efectúa una suma entre dos enteros, el resultado de esa expresión será también un ''int''. Ahora bien, si se realiza una suma entre dos ''float'', el resultado también será ''float''. Por lo tanto, dada una producción del tipo: 
 E1 -> E2 + E3

el atributo sintetizado ''tipo'' de ''E1'' dependerá de los tipos de ''E2'' y ''E3'':
 E1.tipo <- if (E2.tipo = int && E3.tipo = int) int
            else if (E2.tipo = float && E3.tipo = float) float
            else if (E2.tipo = int && E3.tipo = float) float
            ...
            else error_tipo

Notar que si E2 es de tipo int y E3 de tipo float, se aplica la suma de floats. Para esto se debe ''coercionar'' de manera implítica el tipo de E2 a float. En otras palabras, se hace un casteo implícito.

== Generación de código intermedio ==

La generación de código intermedio involucra el uso de alguna de las siguientes estructuras de representación para las expresiones:
* '''Árboles sintácticos:''' Tienen como nodos intermedios los operadores, y los hijos de cada nodo son las subexpresiones que actúan de operandos. Las hojas son las variables. No confundir con árboles de análisis sintáctico, que son los generados por el parser.
* '''Grafos dirigidos acíclicos:''' Similares a los anteriores, pero pueden tener ciclos no dirigidos (no ciclos dirigidos) para reutilizar subexpresiones y no generarlas más veces que las necesarias.
* '''Notación postfija:''' La notación postfija emula un lenguaje de pila, y es no ambigua y fácil de manejar. Ejemplo, ''a+b*c'' se traduce a ''abc*+''.

=== Código de tres direcciones ===

El código de tres direcciones es un tipo de código intermedio que se puede utilizar donde cada instrucción consiste en una asignación de una operación de dos operandos, así como estructuras de control.

* Expresiones binarias: X = Y op Z
* Expresiones unarias: X = op Z
* Asignaciones: X = Z
* Saltos: goto E (donde E es una etiqueta)
* Saltos condicionales: E Y op Z (si Y op Z entonces goto E)
* Calls: x1 param; x2 param; ... xn param; n call p (call a P con n parametros)
* Indexacion: X = Y[i]
* Referencias: X = &Y

[[Category:Apuntes]]