Análisis sintáctico: Análisis ascendente LR
Introducción
¡Hola!
¡Vaya qué momento más grato el poder saludarte! Es un orgullo que continúes como estudiante de este curso. Espero que sigas perseverando hasta el final, por lo pronto te invito a revisar esta onceava sesión.
En esta sesión aprenderemos sobre
Iniciemos nuestra aventura del conocimiento ahondando un poco más en el conocimiento del tema.
¡Mucho éxito!
Desarrollo del tema
Análisis Ascendente (BU):
- Es un tipo de análisis que construye el árbol sintáctico desde las hojas (la parte inferior) hasta la raíz (la parte superior).
- Aplica reducciones (pasos de la derivación en reversa) y desplazamientos (lecturas de tokens de entrada).
- Las hojas del árbol sintáctico son los símbolos terminales de entrada (tokens) y el nodo raíz es el símbolo inicial.
- Es uno de los métodos más poderosos y generales.
- Funciona para muchos tipos de gramáticas CFG aunque tengan recursividad izquierda.
- Explora la secuencia de tokens de izquierda a derecha.
- Se puede construir el árbol sintáctico usando reducción aleatoria
Se tiene el problema de cómo determinar las reducciones correctas
Se pueden hacer retrocesos
Analizador LR:
- Es una forma especial de analizador BU inventada por Knuth en 1969.
- La L significa exploración de izquierda a derecha.
- La R significa construir la derivación derecha en reversa.
- Su diseño es más laborioso y complicado que para el analizador descendente.
- Forma parte de los analizadores más poderosos y generales.
- También puede usar búsqueda hacia delante.
- LR(1), LR(2), etc.
- La tabla de análisis puede indicar el tipo de gramática.
- Variantes:
- LR canónico: es el más poderoso y costoso.
- SLR (Simple LR): funciona para menos gramáticas pero es fácil de implementar.
- LALR (LookAhead LR): funciona con la mayoría de las gramáticas de los lenguajes de programación pero con un poco de esfuerzo.
GLR (Generalized LR): es una extensión de LR para manejar gramáticas ambiguas y no determinísticas.
Los analizadores sintácticos ascendentes LR son más poderosos que los analizadores descendentes LL.
Análisis LR:
- Construir árbol de análisis desde las hojas hacia la raíz, explorando de izquierda a derecha (resultando en derivación más a la derecha en reversa).
G:
S → a A B e entrada: abbcde
A → A b c | b
B → d
- Sea G =
S → aABe
A → Abc|b
B → d
La cadena abbcde puede ser reducida a S según los pasos siguientes:
abbcde
aAbcde
aAde
aABe
S
- Las reducciones anteriores dan la siguiente derivación más a la derecha en reversa:
- Análisis LR ≠ Reducción Izquierda
- La primera subcadena reducible no siempre resulta en un análisis exitoso.
- Handle(s): los que conducen a
- S exitosamente.
- Análisis Descendente:
- Expansión.
- Concordancia.
- Análisis Ascendente: Desplazar/Reducir
- Localizar siguiente “handle” para reducir
Podado de Handles
Handles o Asideros:
- Handle de una cadena o forma sentencial derecha.
Es una subcadena que concuerda con una parte derecha de una producción, y cuya reducción al no terminal de la izquierda representa un paso para su reducción al símbolo inicial.- Un handle de una forma sentencial derecha es:
Una producción Aβ y una posición donde la cadena β puede ser reemplazada por A para producir la forma sentencial derecha previa en una derivación derecha de
- Un handle de una forma sentencial derecha es:
- Si S⇒αAω⇒αβω, entonces
Aβ en la posición que sigue a es un handle de αβω
La cadena contiene sólo símbolos terminales.
Si la gramática no es ambigua, entonces cada forma sentencial derecha tiene exactamente un handle.
- Sea la gramática:
SaABe
A Abc | b
B d
La cadena de tokens abbcde puede ser reducida a S como:
abbcde tiene como handle A b en posición 2
aAbcde tiene como handle A Abc en posición 2
aAde tiene como handle B d en posición 3
aABe tiene como handle S aABe en posición 1
S
Las reducciones anteriores dan la siguiente derivación derecha en reversa:
- Gramática:
S → E
E → E+T | E-T | T
T → T*F | T/F | F
F → number | id
Handles para id1*id2
Una colección de ítems es un estado del analizador LR
El analizador sintáctico ascendente LR utiliza tabla y stack.
Una ventaja de los analizadores sintácticos LR es que existen herramientas en línea para calcular las tablas de análisis.
Tipo de analizador sintáctico que generan las herramientas Yacc y Bison: LALR(1).
Conclusión
Para recordar:
Hemos llegado al final de la sesión. ¡Mis felicitaciones por tu gran logro! Espero que el tema sea de mucha ayuda en tus aprendizajes. Acude con tu asesor para despejar las dudas que hayan surgido. Resuelve la consigna en tiempo y forma.
Nos encontraremos en la siguiente sesión.