1

Análise Sintática LR

Prof. Alexandre Monteiro

Baseado em material cedido pelo Prof. Euclides Arcoverde

Recife

Contatos

Prof. Guilherme Alexandre Monteiro Reinaldo

Apelido: Alexandre Cordel

E-mail/gtalk: alexandrecordel@gmail.com

greinaldo@fbv.edu.br

Site: http://www.alexandrecordel.com.br/fbv

Celular: (81) 9801-1878

3

Análise Sintática LR

É uma técnica de análise sintática bottom-up (ascendente)

Também chamada de shift-reduce

Usada em vários geradores automáticos de parsers

• Exemplo: JavaCC, yacc, CUP

4

Analisador Sintática LR

Existem diversos tipos de analisadores LR(k)

O nome LR(k) indica• Left-to-right – a ordem de leitura dos tokens é

da esquerda para a direita

• Rigthmost derivation – encontra uma derivação mais à direita (porém, de trás para a frente)

• K token são olhados à frente (lookahead)

5

Analisador Sintática LR

O tipo que veremos é chamado LR(0)

Alguns tipos importantes são

• SLR(1) – Simple LR(1)• LALR(1) – Look-Ahead LR(1)

O LALR(1) é usado nos principais geradores de parsers

6

Assuntos

Sobre o parser LR(0) veremos

• Princípios de funcionamento

• Construção do autômato LR(0)

• Construção das tabelas ACTION e GOTO

• Exemplo de execução

Princípios de Funcionamento

8

Funcionamento

Símbolos terminais lidos de uma entrada

• Na prática, são os tokens, obtidos um por vez por meio do lexer

Símbolos terminais (já lidos da entrada) e não-terminais podem ser inseridos em uma pilha

9

Funcionamento

As ações do parser são construídas com base num autômato construído a partir da gramática

Cada símbolo inserido na pilha, levará o autômato a um novo estado

Assim, na pilha, junto com cada símbolo haverá o estado do autômato

O “estado atual” será o estado no topo da pilha

10

Funcionamento

A medida que lê os terminais (tokens), o parser poderá realizar certas ações, de acordo com o estado atual

• SHIFT• REDUCE• ACCEPT• ERROR

11

Ações

Ação SHIFT <estado>

• Pega o próximo terminal da entrada e insere no topo da pilha

• Realizada quando o parser precisa de mais informações sobre a entrada para formar a árvore

• Junto com o terminal, insere o próximo estado

12

Ações

Ação REDUCE X • Realizada quando o parser reconhecer que os

símbolos no topo da pilha formam a cadeia - Na árvore (se for criada), X será pai de toda a cadeia

• O parser remove toda a cadeia da pilha e observa o estado atual (no topo)

• Insere o símbolo X junto com o próximo estado (que dependerá do estado atual)

13

Ações

Ação ACCEPT

• Indica que a entrada terminou e está correta (toda a árvore pode ser criada)

Ação ERROR

• Indica que a entrada está errada

14

Funcionamento

A escolha das ações do parser será dada por uma tabela ACTION

Outra tabela auxiliar usada é a tabela GOTO, usada apenas quando a ação for “reduce”

15

Funcionamento

Tabela ACTION

• Diz qual ação será tomada, de acordo com o estado atual e o próximo token

Tabela GOTO (usada durante um reduce)

• Diz qual o próximo estado, de acordo com o estado atual e o símbolo não-terminal que foi reduzido

16

Autômato e Tabelas

Veremos a seguir como é construído o autômato a partir de uma gramática qualquer dada

Depois, a partir do autômato, veremos como criar as tabelas ACTION e GOTO

Construção do Autômato LR(0)

18

Construção do Autômato

O primeiro passo é estender a gramática com a produção S’S (ou S’S$), onde:

• S é o símbolo inicial original

• $ indica fim de arquivo (EOF)

Essa gramática é chamada de gramática estendida

19

Itens LR(0)

Indicam em que parte de uma produção a análise sintática pode estar, num certo instante• Um ponto é usado para indicar a posição

Para cada produção X YZW , temos os itens• X .YZW• X Y.ZW• X YZ.W• X YZW.

20

Autômato LR(0)

Os itens serão usados para criar um autômato em que

• Cada estado é uma coleção de itens

• As transições entre estados acontecem quando um símbolo (terminal ou não) é lido/reconhecido

• Não existe estado final

21

Autômato LR(0)

O estado inicial será o item S’.S Para todo item X.Y , com Y não-

terminal, adicionar ao mesmo estado os itens• Y. , para toda produção de Y

Para todo item X.Y , criar uma transição que:• Lê o símbolo Y (terminal ou não)• Leva ao estado formado por XY.

22

Autômato LR(0)

Depois de concluído o autômato, os estados devem ser numerados, para facilitar

O autômato pode, então, ser usado para criar as tabelas ACTION e GOTO do parser

Construção das Tabelas

24

Relembrando as Tabelas

Tabela ACTION

• Diz qual ação será tomada, de acordo com o estado atual e o próximo token

Tabela GOTO (usada após um reduce)

• Diz qual o próximo estado, de acordo com o estado atual e o símbolo não-terminal que foi reduzido

25

Construção das Tabelas

Para criar ambas as tabelas, é preciso analisar os itens LR(0) de cada estado do autômato

Descreveremos apenas as situações em que as entradas das tabelas são bem definidas

Nos demais casos, subentende-se que a ação é de erro

26

Tabela GOTO

A tabela GOTO é a mais simples de construir

Se o estado tiver um item com um ponto antes de um não-terminal N, assim: X.N

• Quando o não-terminal reduzido for N, ir para o estado do autômato que tem o ponto depois do não-terminal, assim: XN.

27

Tabela ACTION

Se o estado tiver um item com um ponto antes de um terminal t assim: X.t

• Fazer um SHIFT, quando o próximo símbolo for t

• Ir para o estado que tem o ponto depois do terminal, assim: Xt.

28

Tabela ACTION

Se o estado tiver um item com um ponto no final da produção assim: X.

• Fazer um REDUCE para a produção X , qualquer que seja o próximo símbolo

• Observação: Após o parser realizar o reduce, ele consultará a tabela GOTO para decidir o próximo estado

29

Tabela ACTION

Um caso especial será definido quando o estado tiver o item S’S.

• Neste caso, a ação será ACCEPT, apenas se o próximo símbolo for $

Exemplo de Execução

31

Exemplo (quadro)

0) S: stmt $

1) stmt: ID ':=' expr

2) expr: expr '+' ID

3) expr: expr '-' ID

4) expr: ID

32

Exemplo (autômato)

State 0

0)S: . stmt $

1)stmt: . ID ':=' expr

State 1

0)S: stmt . $

State 2

1)stmt: ID . ':=' expr

State 31)stmt: ID ':=' . expr 2)expr: . expr '+' ID 3)expr: . expr '-' ID 4)expr: . ID

33

Exemplo (autômato)

State 0

0) S: . stmt $

1) stmt: . ID ':=' expr

GOTO 2 on stmt

SHIFT 1 on ID

State 1

1) stmt: ID . ':=' expr

SHIFT 3 on ':='

State 2

0) S: stmt . $

SHIFT 4 on $

State 3

1) stmt: ID ':=' . expr

2) expr: . expr '+' ID

3) expr: . expr '-' ID

4) expr: . ID GOTO 6 on expr

SHIFT 5 on ID

State 40) S: stmt $.

State 5 4) expr: ID .

State 6 1) stmt: ID ':=' expr . 2) expr: expr . '+' ID 3) expr: expr . '-' ID SHIFT 7 on '+' SHIFT 8 on '-'

State 7 2) expr: expr '+' . ID SHIFT 9 on ID

State 8 3) expr: expr '-' . ID SHIFT 10 on ID State 9 2) expr: expr '+' ID .

State 10 3) expr: expr '-' ID .

34

Exemplo (Tabelas)

ID ':=' '+' '-' $ stmt expr0 s1 g2 1 s3 2 s4 3 s5 g64 acc acc acc acc acc 5 r4 r4 r4 r4 r4 6 r1 r1 s7 s8 r1 7 s9 8 s10 9 r2 r2 r2 r2 r2

10 r3 r3 r3 r3 r3

Goto TableAction Table

35

Exemplo: a:= b + c - d

Stack Remaining Input Action0/S a:= b + c - d s1

0/S 1/a := b + c - d s30/S 1/a 3/:= b + c - d s5

0/S 1/a 3/:= 5/b + c - d r40/S 1/a 3/:= + c - d g6 on expr

0/S 1/a 3/:= 6/expr + c - d s70/S 1/a 3/:= 6/expr 7/+ c - d s9

0/S 1/a 3/:= 6/expr 7/+ 9/c - d r20/S 1/a 3/:= - d g6 on expr

0/S 1/a 3/:= 6/expr - d s80/S 1/a 3/:= 6/expr 8/- d s10

0/S 1/a 3/:= 6/expr 8/- 10/d $ r30/S 1/a 3/:= $ g6 on expr

0/S 1/a 3/:= 6/expr $ r10/S $ g2 on stmt

0/S 2/stmt $ s40/S 2/stmt 4/$ accept

36

Exemplo

O que acontece ao tentar criar as tabelas de parsing LR(0) para a gramática abaixo?

E → 1 E | 1

Conflitos na Criação de Parsers LR

38

Conflitos

Um mesmo estado do autômato pode ter itens que permitam mais de uma ação, gerando conflitos na criação das tabelas

Conflitos possíveis:• SHIFT/REDUCE: em um mesmo estado, o

parser não consegue decidir se faz um shift ou um reduce

• REDUCE/REDUCE: em um mesmo estado, o parser pode fazer reduce para duas produções diferentes e ele não consegue decidir qual escolher

39

Conflitos em Parsers LR(0)

Os tipos de conflitos citados podem aparecer com qualquer técnica de construção de parser LR

Para ilustrar, veremos como esses conflitos acontecem na construção de parsers LR(0)

40

Conflitos em Parsers LR(0)

Se o estado tiver um item X.t e outro X.

• O primeiro item indica que se deve fazer um shift de t, enquanto o segundo indica para fazer um reduce para a produção X

• Conflito SHIFT/REDUCE !

• É o que aconteceria na gramáticaE → 1 E | 1

41

Conflitos em Parsers LR(0)

Se o estado tiver um item X. e outro Y.

• Neste caso, o parser poderia fazer o reduce para duas produções diferentes

• Conflito REDUCE/REDUCE !

42

Tratamento de Conflitos

Dependendo do caso, os conflitos podem ser tratados das seguintes maneiras

• Alterando a gramática, ou

• Definindo precedências para as produções, ou

• Usando outra técnica LR (SLR, LALR, etc.)- Veremos a SLR...

Parser SLR

44

Parser SLR

É um caso simples de parser LR(1)

• “Simple LR(1)”

Vamos comparar a técnica LR(0) vista antes com o princípio dos parsers LR(1)

45

LR(0) x LR(1)

O parser LR(0) visto antes tem o número 0 no nome porque a ação a ser tomada (shift ou reduce) independe do próximo token• Ele poderia simplesmente fazer a ação

olhando só para os símbolos que já estão na pilha

• Olha “zero” tokens adiante

Já um parser LR(1) confere 1 token à frente para escolher a ação• Pode ter uma ação específica para cada token

46

Parser SLR

Não veremos como construir um parser LR(1) canônico, mas veremos o SLR(1), que é mais simples

O LR(1) canônico usa um autômato especial chamado autômato LR(1)• Não veremos...

Mas a técnica SLR(1) usa o mesmo autômato LR(0) que vimos até agora

47

Parser SLR

O parser SLR(1)

• Funciona de maneira muito parecida com o LR(0)

• É baseado no mesmo autômato LR(0)

• Na prática, a diferença para o LR(0) será apenas na construção da tabela

48

Parser SLR

Na construção da tabela ACTION para o parser SLR(1), uma ação só será escolhida se o próximo símbolo (1 à frente) estiver “correto”

• O critério para escolha da ação “SHIFT” não mudará em relação ao parser LR(0), porque essa ação já considera o próximo símbolo

• Já o “REDUCE X” só será a ação válida para os tokens que podem aparecer após o não-terminal X

49

Parser SLR

Os símbolos que podem vir após o não-terminal X são exatamente o conjunto FOLLOW(X) visto em aulas passadas

50

Conjunto FOLLOW

FOLLOW (N)

• Aplicado a não-terminais N quaisquer

É o conjunto de terminais que podem aparecer à direita do não-terminal N, em alguma cadeia derivada pela gramática

• Se o símbolo inicial deriva uma cadeia “... N t ...” então t faz parte de FOLLOW(A)

51

Parser SLR

Assim, na construção da tabela ACTION de um parser SLR, se tiver um item X. em um estado do autômato...

• A ação naquele estado será REDUCE X, apenas para os símbolos que estão em FOLLOW(X)

O restante é idêntico ao LR(0)...

52

Parser SLR

Com essa simples alteração no critério de escolha para a ação REDUCE, essa técnica consegue tratar mais gramáticas do que a LR(0)

Ela evita que aconteça alguns casos de conflitos SHIFT / REDUCE como o que vimos no início da aula

53

Exemplo

Dada a gramática abaixo

• Construir as tabelas de parsing SLR

(0) S → E(1) E → 1 E(2) E → 1

54

Exemplo

Estado 0S → • EE → • 1 EE → • 1

Estado 1E → 1 • EE → 1 •E → • 1 EE → • 1

Estado 2S → E •

Estado 3E → 1 E •

Estados

55

Exemplo

Tabelas de parsing SLR

FOLLOW(E) = {$}, então REDUCE só é valido para $

gotostate 1 $ E

0 s1 21 s1/r2 r2 32 acc3 r1 r1

action

gotostate 1 $ E

0 s1 21 s1 r2 32 acc3 r1

action

56

Parser SLR A análise sintática SLR é uma extensão simples e

eficaz da análise LR(0) • Ela é capaz de tratar quase todas as estruturas práticas

de linguagens de programação

No entanto, existem algumas poucas situações que a análise SLR é incapaz de tratar

Para esses casos, é comum usar um método LR(1) mais avançado (que não veremos) que é o chamado LALR(1)

• Usado no CUP, yacc e diversos outros geradores de parsers

57

Exercício SLR

Dada a gramática abaixo

• Construir as tabelas de parsing SLR• Fazer o reconhecimento de “n+n+n”

E → n + E | n

58

Exemplo

Estado 0S → • EE → • n + EE → • n

Estado 1E → n • + EE → n •

Estado 2S → E •

Estado 3E → n + • EE → • n + EE → • n

Estado 4E → n + E •

Estados

59

Exercício

Tabelas de parsing SLR

gotostate n + $ E

0 s11 s3 r2 g22 acc3 s1 g44 r1

action

60

Exercício

Reconhecimento de “n+n+n”

Stack Remaining Input Action0/S n + n + n s1

0/S 1/n + n + n s30/S 1/n 3/+ n + n s1

0/S 1/n 3/+ 1/n + n s30/S 1/n 3/+ 1/n 3/+ n s1

0/S 1/n 3/+ 1/n 3/+ 1/n $ r20/S 1/n 3/+ 1/n 3/+ 4/E $ g4

0/S 1/n 3/+ 4/E $... r1...0/S 1/E $ g2

0/S 1/E 2/$ acc

61

Exercício LR(0)

Dada a gramática abaixo

• Construir as tabelas de parsing LR(0)• Fazer o reconhecimento de “1+1”

(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1

62

Exercício

state * + 0 1 $ E B0 s1 s2 3 41 r4 r4 r4 r4 r4 2 r5 r5 r5 r5 r5 3 s5 s6 acc 4 r3 r3 r3 r3 r3 5 s1 s2 76 s1 s2 87 r1 r1 r1 r1 r1 8 r2 r2 r2 r2 r2

ACTION GOTO

Tabelas de parsing LR(0)

63

Exercício

Reconhecimento de “1+1”

Estado Entrada de dados Saída de dados Pilha Próxima ação0 1+1$ [0] shift 22 +1$ [0,2] reduce 54 +1$ 5 [0,4] reduce 33 +1$ 5,3 [0,3] shift 66 1$ 5,3 [0,3,6] shift 22 $ 5,3 [0,3,6,2] reduce 58 $ 5,3,5 [0,3,6,8] reduce 23 $ 5,3,5,2 [0 3] aceita

64

Bibliografia

AHO, A., LAM, M. S., SETHI, R., ULLMAN, J. D., Compiladores: princípios, técnicas e ferramentas. Ed. Addison Wesley. 2a Edição, 2008 (Capítulo 4)