Analisis LR

ANÁLISIS SINTÁCTICO ASCENDENTE

1

Análisis sintáctico ascendete
•
•

El análisis sintáctico ascendente crea el
inverso de una derivación derecha
Los pasos para realizar la inversa de una
derivación derecha son:
• Comenzar con la cadena de caracteres
(las hojas del árbol)
•

Intentar reducir al símbolo de inicio
encontrado en el mango actual.

2

Ejemplo
Dada la gramática:
N → D|ND
D →0|1|2|3|4|5|6|7|8|9
Realizar el análisis sintácto ascendente sobre la
cadena 35
35 ← D5 ← N5 ← ND ← N

3

Desplazamiento y reducción








El método de análisis ascendente revisado anteriormente
es llamado de desplazamiento y reducción
El análisis sintáctico por desplazamiento y reducción
intenta construir un árbol de análisis sintáctico para una
cadena de entrada que comienza por las hojas (elfondo) y
avanza hacia la raíz (la cima)
Se puede considerar este proceso como de “reducir” una
cadena w al símbolo inicial de la gramática
En cada paso de reducción se sustituye una subcadena
determinada que concuerde con el lado derecho de una
producción por el símbolo del lado izquierdo de dicha
producción
4

Ejercicio
Dada la gramática:
S → aABe
A → Abc | b
B → d
Reducir al no terminal inicial lacadena abbcde

5

Mangos




Un mango de una cadena es una subcadena
que concuerda con el lado derecho de una
producción y cuya reducción al no terminal
del lado izquierdo de la producción representa
un paso a lo largo de la inversa de una
derivación por la derecha
Si una gramática no es ambigua, entonces toda
forma de frase derecha de la gramática tiene
exactamente un mango
6

Mangos


En el ejercicio anterior la cadena abbcde es
una forma de frase derecha cuyo mango es A
→ b en la posición 2
Del mismo modo, aAbcde es una forma de
frase derecha cuyo mango es A → Abc en la
posición 2

7

Ejemplo de reducción y
desplazamiento
1. E→E + E
2. E→E * E
3. E→id

8

Ejercicio
E→E+T|T
T→T*F|F
F → (E) | id
id * (id + id)

9

Conflictos durante el análisis
sintáctico por desplazamiento yreducción




Existen gramáticas independientes del contexto para
las cuales no se pueden utilizar analizadores
sintácticos por desplazamiento y reducción
Estos analizadores pueden alcanzar una
configuración en la cual conociendo el contenido total
de la pila y el siguiente símbolo de la entrada se
presenten dos conflictos:




Desplazamiento/reducción: no puede decidir si
desplazar o reducirReducción/reducción: no puede decidir que tipo de
reducción realizar
10

Ejemplo
prop → if expr then prop
|

if expr then prop else

|

otro

prop

PILA

ENTRADA

...if expr then prop else...$
No se puede saber si if expr then prop es
el mango
11

Ejemplo
prop → id(lista_params)
prop → expr := expr
lista_params → lista_params, parametro
lista_params → parametro
parametro → id
expr →id(lista_expr)
expr → id
lista_expr → lista_expr, expr
lista_expr → expr
PILA

ENTRADA

...id(id

, id)...

No se puede saber por cual producción reducir
12

Conflictos durante el análisis
sintáctico por desplazamiento y
reducción




Las gramáticas en las cuales se presentan los
conflictos anteriores no están dentro de la clase
LR(k)
En general ninguna gramática ambigua puede
ser LR(k) para ninguna k

13Análisis sintáctico LR




Una técnica eficiente de análisis sintáctico
ascendente es denominda LR (left-to-right,
rightmost derivation)
Como su nombre lo indica, en este análisis se
intentará construir una derivación por la derecha

14

Análisis sintáctico LR


Este análisis es util por las siguientes razones:






Se pueden construir analizadores sintácticos
LR para reconocerpracticamente todas las
construcciones de los lenguajes de
programación
Un analizador sintáctico LR puede detectar un
error sintáctico tan pronto como sea posible
hacerlo en un examen de izquierda a derecha
de la entrada
Se puede construir una tabla que dirija todo el
proceso de análisis
15

Técnicas de análisis sintáctico LR


Existen tres técnicas para la construcción de una tabla de
análisis...