GUÍA 18-11-26 Teoría de la Computación

NE111 · miércoles 18/11/2026 · 16:00-17:15 · Sesión 28

Parsers: análisis sintáctico ascendente

POR QUÉ ASCENDENTE

Los parsers LR aceptan una clase de gramáticas estrictamente mayor que los LL, incluida la recursión por la izquierda. No hay que deformar la gramática para que el parser funcione, y por eso son los que se usan en los generadores reales.

DESPLAZAR Y REDUCIR

El parser mantiene una pila y en cada paso elige entre dos acciones, guiado por una tabla.

• Desplazar — meter el siguiente token a la pila.
• Reducir — reconocer que el tope de la pila corresponde al lado derecho de una producción y sustituirlo por el izquierdo.
• Aceptar — cuando se reduce al símbolo inicial y la entrada se agotó.
• Error — cuando ninguna acción aplica.

LA PILA, OTRA VEZ

Un parser LR es un autómata de pila determinista. Todo el bloque anterior se materializa aquí: la pila que estudiamos en abstracto es la pila real del analizador.

LA FAMILIA LR

• LR(0) — sin anticipación; muy limitado.
• SLR(1) — usa SIGUIENTE para decidir reducciones.
• LALR(1) — fusiona estados de LR(1); es el punto de equilibrio y lo que generan yacc y bison.
• LR(1) — el más potente, con tablas mucho más grandes.

CONFLICTOS

• Desplazar o reducir — típicamente precedencia mal especificada o el dangling else.
• Reducir o reducir — dos producciones aplicables; casi siempre indica un error de diseño de la gramática.

Los generadores permiten resolver los conflictos de desplazar o reducir declarando precedencia y asociatividad, que es la forma práctica de manejar la ambigüedad de las expresiones sin reescribir la gramática.

RECUPERACIÓN DE ERRORES

Un compilador real no puede detenerse en el primer error. Se usa recuperación en modo pánico —descartar tokens hasta un símbolo de sincronización, como el punto y coma— para poder reportar varios errores en una sola pasada.

EL PANORAMA DEL ANÁLISIS

Léxico con autómatas finitos y expresiones regulares; sintáctico con gramáticas libres de contexto y autómatas de pila. Los dos primeros niveles de la jerarquía de Chomsky son exactamente las dos primeras fases de un compilador. El análisis semántico ya no es libre de contexto y por eso se hace aparte.

EJERCICIO

Trazar el análisis por desplazamiento y reducción de una expresión aritmética, mostrando el contenido de la pila en cada paso.