ingeniero

Procesadores de lenguaje

Tema 5
Análisis sintáctico ascendente

Ciencias de la Computación e Inteligencia Artificial

Tema 5. Análisis sintáctico
ascendente

Índice

5.1 Introducción
5.2 Análisis sintáctico por desplazamiento y reducción
5.3 El autómata reconocedor de prefijos viables
5.4 Algoritmos LR(0) y SLR
5.5 Algoritmos LR(1) y LALR
5.6 Gestión de errores
5.7Clasificación de gramáticas

2

Procesadores de lenguaje

1

Tema 5. Análisis sintáctico
ascendente

5.1 Introducción

• El análisis sintáctico ascendente construye la inversa de la
derivación por la derecha
• Construye el árbol de análisis sintáctico de las hojas a la raíz



Gramática

Y id
Y , id


id






id , id

id , id

, id

id , id , id

3

Procesadoresde lenguaje

Tema 5. Análisis sintáctico
ascendente

5.1 Introducción

• El problema fundamental es decidir cuando lo que parece ser la
parte derecha de una regla puede ser sustituida por la parte
izquierda
• No es un problema trivial ya que pueden existir ocasiones en las que
es posible sustituir dos producciones diferentes
• El conjunto de gramáticas que pueden ser analizadas medianteun
análisis ascendente lineal se denomina LR(1)
• El conjunto LR(1) es mucho más amplio que el de las gramáticas
LL(1)

4

Procesadores de lenguaje

2

Tema 5. Análisis sintáctico
ascendente

5.2 Análisis sintáctico por
desplazamiento y reducción

• El análisis ascendente lineal más utilizado es el algoritmo de
desplazamiento-reducción (shift-reduce)
• Este algoritmo se basaen una pila de estados y una tabla de análisis.
• Existen diferentes métodos para generar la tabla de análisis (LR(0),
SLR, LALR, LR(1))
• El método LR(1) genera la tabla para cualquier gramática LR(1),
pero genera tablas muy grandes.
• El método SLR genera tablas muy compactas pero no puede
aplicarse a todas las gramáticas LR(1)
• El método LALR genera tablas compactas y puede aplicarse ala
mayoría de gramáticas LR(1)

5

Procesadores de lenguaje

Tema 5. Análisis sintáctico
ascendente

5.2 Análisis sintáctico por
desplazamiento y reducción

• Utiliza dos acciones básicas:
– Desplazar: consiste en consumir un token de la cadena de
entrada
– Reducir: consiste en sustituir en la pila los símbolos de una parte
derecha de una regla por su parte izquierda

• Elalgoritmo utiliza una pila de estados y una tabla de análisis
con dos partes:
– Acciones: para cada símbolo terminal y $.
– Ir-a: para cada símbolo no terminal
– Las filas corresponden a los estados

6

Procesadores de lenguaje

3

5.2 Análisis sintáctico por
desplazamiento y reducción

Tema 5. Análisis sintáctico
ascendente
• Las acciones pueden ser
– dj : desplazar y apilar elestado j
– rk: reducir por la regla k-ésima.

• Consiste en eliminar tantos estados de la pila como elementos en la
parte derecha de la regla.
• A continuación se analiza el estado de la cima de la pila p.
• Por último se apila el estado Ir_a(p,A) siendo A el símbolo no
terminal que define la regla k-ésima

– aceptar: terminar el análisis aceptando la cadena
– error: producir un error (cuandono se encuentra ninguna
acción)

7

Procesadores de lenguaje

5.2 Análisis sintáctico por
desplazamiento y reducción

Tema 5. Análisis sintáctico
ascendente

1: Y end
2: Y begin
3: Y codigo
4: Y tipo
5: Y id

Estado
0
1
2
3
4
5
6
7
8
9
10

end

begin codigo

tipo
d3

id
d4

$

S
1

A

B
2

C

aceptar
d6
r4

5
d3

d4

7

d8d10

9

r5
r1
r2
r3

8

Procesadores de lenguaje

4

5.2 Análisis sintáctico por
desplazamiento y reducción

Tema 5. Análisis sintáctico
ascendente

PILA

ENTRADA

0
04
043
047
02
026
0 2 6 10
0269
025
0258
01

id tipo begin codigo
tipo begin codigo
begin codigo
begin codigo
begin codigo
codigo

ACCIÓN
end
end
end
end
end
end
end
end
end...