COMPILADORES
ANÁLISE SINTÁTICA
Guilherme Amaral Avelino
gavelino@gmail•com

Analisador sintático (parser) é o responsável por
verificar se as construções utilizados no
programa estão gramaticalmente corretas
Envia token
Programa
fonte
Analisador
sintático
Analisador
léxico
Solicita novo token
Tabela de
símbolos
Árvore de
derivação
RECONHECIMENTO DE UMA LINGUAGEM



Toda linguagem tem de ter regras que descrevem sua estrutura
sintática (ou sintaxe)
A sintaxe pode ser descrita através de uma gramática ou pela
notação BNF
Vantagens de se utilizar uma gramática:
 Fornece uma especificação sintática precisa e fácil de
entender
 Para certas classes de gramáticas, podemos construir
automaticamente um analisador sintático e o gerador
automático pode certas ambigüidades sintáticas da LP,
difíceis de serem identificadas diretamente pelo projeto do
compilador
 Novas construções que surgem com a evolução da linguagem
podem facilmente ser incorporadas a um compilador se este
tem sua implementação baseada em descrições gramaticais
DESCRIÇÃO DE UMA LINGUAGEM ATRAVÉS
DE UMA GRAMÁTICA

Linguagens regulares não são capazes de
identificar recursões centrais

E = x | “(“ E “)”
Solução: Uso de gramáticas livres de contextos
 Uma Gramática Livre de Contexto é construída
utilizando símbolos terminais e não-terminais,
um símbolo de partida e regras de produções,
onde:


Os terminais são os símbolos básicos a partir dos
quais as cadeias são formadas• Na fase de análise
gramatical os tokens da linguagem representam os
símbolos terminais• Ex: if, then, else, num, id, etc•
GRAMÁTICA LIVRE DE CONTEXTO
Os não-terminais as variáveis sintáticas que denotam
cadeias de caracteres• Impõem uma estrutura
hierárquica que auxilia na análise sintática e
influencia a tradução• Ex: cmd, expr•
 Numa gramática um não terminal é distinguido como
símbolo de partida, e o conjunto que o mesmo denota
é a linguagem definida pela linguagem• Ex: program
 As produções de uma gramática especificam como os
terminais e não-terminais podem se combinar para
formas as cadeias da linguagem• Cada produção
consiste em um não terminal seguido por uma seta
(ou ::=), serguido por uma cadeia de não terminais e
terminais

GRAMÁTICA LIVRE DE CONTEXTO



Ex:
expr ::= expr op expr
expr ::= (expr)
expr ::= - expr
expr ::= id
op ::= +
op ::= op ::= *
op ::= /
Simbolos terminais
 id + - * / ( )
Símbolos não-terminais
 expr e op , sendo expr o símbolo de partida
CONVENÇÕES NOTACIONAIS


Símbolos Terminais
 Letras minúsculas do inicio do alfabeto, tais como a, b c
 Símbolos de operadores, tais como +, -, etc
 Símbolos de pontuação, tais como parênteses e vírgulas
 Dígitos 0, 1, •••, 9
 Cadeias em negritos como id ou if
Símbolos não-terminais
 Letras maiúsculas do início do alfabeto, tais como A, B, C
A letra S, quando aparecer é usualmente símbolo de
partida
 Nomes em itálico formados por letras minúsculas, como
expr ou cmd
A menos que seja explicitamente estabelecido, o lado
esquerdo da primeira produção é o símbolo de partida


GRAMÁTICAS


Produções para o mesmo símbolo não terminal a esquerda
podem ser agrupadas utilizando “|”• Ex: A::= +|-|•••
Exemplo:
expr ::= expr op expr
expr ::= (expr)
expr ::= - expr
expr ::= id
op ::= +
op ::= op ::= *
op ::= /
E ::= E A E|(E)|-E| id
A ::= +|-|*|/
GRAFOS DE SINTAXE

Grafo direcionado contendo dois tipos de vértices
Vértices em elipse para representar os símbolos
terminais
 Vértices retangulares para não terminais

ÁRVORES GRAMATICAIS
Representação gráfica de uma derivação
 Dá forma explícita a estrutura hierárquica que
originou a sentença
A
 Dada uma GLC, a árvore de derivação é obtida:

A raiz da árvore é o símbolo inicial da gramática
X1 X2 ••• Xn
 Os vértices interiores são obrigatoriamente nãoterminais• Ex: Se A ::= X1X2•••Xn é uma produção
da gramática, então A será um vétice interior e X1,
X2, •••, Xn serão os filhos (da esquerda para a
direita)
 Símbolos terminais e a palavra vazia são as folhas

ÁRVORES DE DERIVAÇÃO

Exemplo: -(id + id)
E
-
E::=-E
E
(
E
)
E::=(E)
E
+
E
E::=E+E
id
E::=id
Id
E::=id
DERIVAÇÕES
Processo através do qual as regras de produções
da gramática são aplicadas para formar uma
palavra ou verificar se esta pertence a linguagem
 Símbolo não terminal é substituído pelo lado
direito da produção correspondete
 Ex: -( id + id )


E => -E => -(E) => -(E+E) => -(id + E) => -(id + id)
Dois passos:

Qual terminal será escolhido para derivar



Derivação mais a esquerda
Derivação mais a direita
Qual regra utilizar
AMBIGÜIDADE



Se uma gramática possui mais de uma árvore gramatical
para uma mesma sentença é dita ambígua
Parte do significado dos comandos de uma linguagem
podem estar especificado em sua estrutura sintática
Ex: id + id * id possui duas derivações mais a esquerda
E
id
E
+
E
E
id
*
E
E
id
id
E
+
*
E
id
id
AMBIGÜIDADE
Regras de precedência
 Reescrita da gramática

expr ::= expr op expr
expr ::= id
op ::= +
op ::= op ::= *
op ::= /
expr ::= term | term op1 term
term ::= fator | fator op2 fator
fator ::= id | (expr)
op1 ::= +
op1 ::= op2 ::= *
op2 ::= /
cmd ::= if expr then cmd
|if expr then cmd else cmd
|outro
if E1 then S1 else if E2 then S2 else S3
cmd
if
expr
E1
then
cmd
else
cmd
S1
if
expr
E2
then
cmd
S2
else
cmd
S3
cmd ::= if expr then cmd
|if expr then cmd else cmd
|outro
cmd
if E1 then if E2 then S1 else S2
if
expr
then
cmd
E1
if
expr
then
E2
cmd
S1
else
cmd
S2
cmd
if
expr
then
cmd
else
cmd
S2
E1
if
expr
E2
then
cmd
S1
Regra geral: associar cada
else ao then anterior mais
próximo
REESCREVENDO A GRAMÁTICA


Todo enunciado entre um then e um else precisa ser
“associado”, isto é não pode terminar com um then
ainda não “associado”
Um enunciado associado ou é um enunciado if-thenelse contendo somente enunciados associados ou é
qualquer outro tipo de enunciado incondicional
cmd ::= cmd_associado
|cmd_não_associado
cmd_associado ::= if expr then cmd_associado else cmd_associado
|outro
cmd_não_associado ::= if expr then cmd
| if expr then cmd_associado else
cmd_não_associado
ELIMINAÇÃO DE RECURSÃO A ESQUERDA



Uma gramática é recursiva a esquerda se possui um nãoterminal A, tal que, exista uma derivação A => Aα para
alguma cadeia α
É importante para permitir o processamento top-down
Método:
 Agrupamos os produções recursivas
1.
2.

A ::= Aα1|Aα2|••• |Aαn |β1|β2|•••|βn
 Onde nenhum β começa com um A
Substituímos as produções-A por

A ::= β1A’| β2A’| •••|βnA’

A’ ::= α1A’| α2A’|•••| αnA’|ε
Ex:
E ::= E + T|T
T ::= T * F|F
F ::= (E)|id
E ::= TE’
E’ ::= +TE’ | ε
T ::= FT’
T’ ::= *FT’ | ε
F ::= (E) | id
ELIMINAÇÃO DE RECURSÃO A ESQUERDA

Recursão não-imediata
S ::= Aa | b
A ::= Ac | Sd | ε
A ::= Ac | Aad | bd | ε
S ::= Aa | b
A ::= bdA’ | A’
A’ ::= cA’ | adA’ | ε
S ::= Sda | b
A ::= Ac | Sd | ε
S ::= bS’
S’ ::= daS’| ε
A ::= SdA‘
A’ ::= cA’ | ε
S ::= bS’
S’ ::= daS’| ε
A ::= SdA‘
A’ ::= cA’ | ε
FATORAÇÃO À ESQUERDA
Transformação que facilita a análise sintática
 Deve ser realizada quando a escolha entre duas
opções começa com uma cadeia comum
 Neste caso deve se adiar a escolha
 Regra geral:

Se A ::= αβ1 | αβ2 forem duas produções e a entrada
começar com uma cadeia não vazia derivada de α, não
sabemos se A deve ser expandida para αβ1 ou αβ2
 Devemos, então, adiar a decisão expandido A para αA’ e após
ler a entrada derivada de α, expandir A’ para β1 ou β2•
 A ::= αA’
A’ ::= β1 | β2

cmd ::= if expr then cmd else cmd
|if expr then cmd
|outro α
cmd ::= if expr then cmd cmd’| outro
cmd' ::= else cmd | ε
ANÁLISE GRAMATICAL

S ::= aS|c
Processo através do qual
é verificado se uma
w = aac
cadeia pode ser gerado
pela gramática

Análise Top-Down ou Descendente
Inicia-se na raiz da árvore gramatical e segue em direção as
folhas
S
 Em cada passo um lado esquerdo de uma regra de produção
S os símbolos
S
S até
::= aS|c
é substituído pelo direito
produzir todos
w = aac
folha da palavra
a a c
a a c
a a c
a


Análise Botton-Up
S
S
S
a
c
S em direçãoSa raiz
S
A análise é feita a partirSdas folhas
 Em cada passo um lado direito de uma regra de produção é
a
S
a
S
a
S
substituído por um símbolo não-terminal (redução) até obter
o símbolo inicial S (raiz)
a S
a
S

c
ANALISADOR SINTÁTICO TOP-DOWN
(DESCENDENTE)
Produz uma derivação mais a esquerda para uma
cadeia de entrada
 Tem como principal problema determinar, a cada
passo, qual produção deve ser aplicada para
substituir um o símbolo não-terminal
 Quando uma produção é escolhida, o restante do
processo de análise consiste em casar os símbolos
terminais da produção com o a cadeia de entrada

ANÁLISE SINTÁTICA DE DESCIDA
RECURSIVA

Consiste em um conjunto de procedimentos, um
para cada não terminal da gramática
1. void A(){
2.
escolheProdução-A(); // A:: X1X2•••Xk
3.
for (i=1 até k){
4.
if (Xi é um não terminal)
5.
executa Xi();
6.
else if (Xi igual a símbolo de entrada a)
7.
avança na entrada para o próximo símbolo;
8.
else /*ocorre um erro*/
9.
}
10. }
ANÁLISE SINTÁTICA DE DESCIDA
RECURSIVA

Pode exigir retrocesso, resultando em repetidas leituras
sobre a entrada (Tentativa e erro)
Deve-se permitir a escolha de mais de uma produção
 Um erro em uma tentativa de reconhecimento não deve gerar
um erro, mas sim a tentativa de uma nova produção
 Um erro só deve ocorrer quando não houver mais nenhuma
produção a ser testada e ainda houver símbolos na cadeia de
entrada
 Para tentar uma nova produção é necessário colocar o
apontador de entrada na posição que estava no inicio do
processo

S ::= cAd
A ::= ab | a
S
c
A
d
a a b
*Obs: Uma gramática recursiva
à esquerda pode fazer com que
um analisador recursivo à
esquerda entre em loop infinito
FUNÇÕES FIRST E FOLLOW
Funções que auxiliam a construção de S
analisadores sintáticos
α
A
a
 Permitem escolher qual produção deve ser
aplicada baseada no próximo símbolo de entrada
c
γ
 First

Define o conjunto de símbolos que iniciam derivações
a partir de uma seqüência de símbolos terminais e
não-terminais
 c está em First(A)


Follow
Define o conjunto de símbolos terminais que podem
aparecer imediatamente à direita de um dado símbolo
não terminal
 a está em Follow(A) •••

β
FUNÇÃO FIRST - REGRAS

Para calcular FIRST(X) de todos os símbolos X da
gramática, as seguintes regras devem ser
aplicadas até que não haja mais terminais ou ε:
1.
2.
Se X é um símbolo terminal, então FIRST(X)={X}
Se X é um símbolo não-terminal e X::= Y1Y2•••Yk é
uma produção p/ algum k≥1, então:

acrescente a a First(X) se, para algum i, a estiver em
FIRST(Yi), e ε estiver em todos os FIRST(Y1),••• FIRST(Yi1)•


3.
adicione ε se ε está em FIRST(Yj) para todo j = 1,2,•••k
Se Y1 não derivar ε, nada mais deve ser acrescentado a
FIRST(X)
Se X::= ε é uma produção, então acrescente ε a FIRST(X)
FUNÇÃO FIRST - EXEMPLO

Dada a Gramática G=({+,*,(,),id}, {E,T,F,T’,E’}, E,
{E::=TE’; E’::=+TE’|ε; T::=FT’; T’=*FT’|ε;
F::=(E)|id}), determine:

FIRST(T) =
FIRST(F)
FIRST(() U FIRST(id)
{(,id}

FIRST(E’) =
FIRST(+) U FIRST(ε)
{+, ε}

FIRST(T’) =
FIRST(*) U FIRST(ε)
{*, ε}
FUNÇÃO FIRST - EXEMPLO

Dada a Gramática G=({a,b,c}, {I,A,B}, I,
{I::=aBa|BAc|ABc; A::=aA|ε; B::=ba|c}),
determine:
FIRST(aBa) = {a}
 FIRST(BAc) = FIRST(ba) U FIRST(c)
{b} U {c}
{b,c}


FIRST(ABc) = FIRST(aA) U FIRST(ε) U FIRST(Bc)
{a,ε} U FIRST(ba) U FISRT(c)
{a,ε} U {b} U {c}
{a,b,c}
FUNÇÃO FOLLOW - REGRA

Para calcular FOLLOW(X) de todos os nãoterminais A, as seguintes regras devem ser
aplicadas até que nada mais possa ser
acrescentado a nenhum dos conjuntos FOLLOW:
1.
2.
3.
Se X é o símbolo inicial da gramática coloque $ em
FOLLOW(X), onde $ é o marcador de fim da entrada
Se houver uma produção A::αXβ, então tudo em
FIRST(β) exceto ε está em FOLLOW(X)
Se houver uma produção A::αX, ou uma produção A::=
αXβ, onde o FIRST(β) contém ε, então inclua o
FOLLOW(A) em FOLLOW(X)
FUNÇÃO FOLLOW - EXEMPLO

G=({+,*,(,),id}, {E,T,F,T’,E’}, E, {E::=TE’;
E’::=+TE’|ε; T::=FT’; T’=*FT’|ε; F::=(E)|id})

FOLLOW(E) =
FIRST()) U {$}
{),$}

FOLLOW(T) =
FIRST(E’) U FOLLOW(E)
{+} U {),$}
{+,),$}

FOLLOW(F) =
FIRST(T’) U FOLLOW(T)
{*} U {+,),$}
{*,+,),$}
FUNÇÃO FOLLOW - EXEMPLO

G=({a,b,c}, {I,A,B}, I, {I::=aBa|BAc|ABc;
A::=aA|ε; B::=ba|c}
FOLLOW(I) =
 FOLLOW(A) =


FOLLOW(B) =
{$}
FIRST(c) U FIRST(Bc) U FOLLOW(A)
{c} U {b,c} U ({c} U {b,c} U •••)
{b,c}
FIRST(a) U FIRST(Ac) U FIRST(c)
{a} U {a,c} U {c}
{a,c}
ANALISADORES SINTÁTICOS PREDITIVOS
Não necessitam de retrocesso
 O símbolo da cadeia de entrada, em análise, é
suficiente para determinar qual regra de
produção deve ser escolhida
 São construídos utilizando gramáticas LL(1)

Cadeia de entrada analisada da esquerda para a
direita (left-to-right)
 A derivação das produções é feita mais a esquerda
(leftmost)
 A cada passo é observado um símbolo a frente para
determinação de que ação deve ser tomada

GRAMÁTICAS LL(1)

Uma gramática G é LL(1) se, e somente se:
A gramática não tiver recursividade a esquerda
 For fatorada a esquerda
 Para os terminais com mais de uma regra de produção, os
primeiros terminais devem ser capazes de identificar,
univocamente, a produção que deve ser aplicada a cada
instante da análise

Ex:
cmd ::= if ( expr ) cmd else cmd
|while ( expr ) cmd
|{ cmd_list }

CONSTRUÇÃO DA TABELA

Para cada produção A ::= α da gramática faça:
1.
2.
Para cada terminal a em FIRST(A), inclua A::=α em
M[A,a]
Se FIRST(α) inclui a palavra vazia, então adicione A::= α
a M[A,b] para cada b em FOLLOW(A)
Não
Terminal
Símbolo de Entrada
Id
E
E::=TE’
E’
T
*
(
)
T::=FT’
E’::=ε
T::=FT’
T’::= ε
F::=id
$
E::=TE’
E’::=+TE’
T’
F
+
T’::= ε
T’::=*FT’
F::=(E)
T’::= ε
ANÁLISE ASCENDENTE

Corresponde a construção de uma árvore de
derivação para uma cadeia de entrada a partir
das folhas (parte de baixo) em direção à raiz
(topo)
id * id
F * id
T * id
id
F
id
T*F
T*F
T*F
ANALISADORES LR(K)
Analisadores redutores eficientes que lêem a
sentença em análise da esquerda para a direita
(left-to-right) e produzem uma derivação mais à
direita (rightmost) ao reverso, considerando k
símbolos em cada leitura
 São capazes de reconhecer, praticamente todas as
estruturas sintáticas definidas por gramáticas
livres de contexto
 Tem como desvantagem a dificuldade da
implementação do mesmo, sendo necessário, em
muitos casos, a utilização de ferramentas
automatizadas para construção da tabela de
análise

ANALISADORES LR(K)

Os analisadores LR são classificados quanto ao
tipo de tabela de análise que utilizam em:
SLR (Simple LR), fáceis de implementar, porém
aplicáveis a uma classe restrita de gramáticas
 LR Canônicos, mais poderosos, podendo ser
aplicados a um grande número de linguagens livres
de contexto
 LALR (Look Ahead LR), nível intermediário de
complexidade e implementação eficiente que funciona
para a maioria das linguagens de programação• É
utilizado pelo gerador de analisadores sintáticos yacc

Estado
0
Ação
id
+
*
Transição
(
)
$
E
T
F
ANALISADORES
LR(K)
- FUNCIONAMENTO
e5
e4
1
2
3
1
e6
Xi - símbolo da gramática
2
r2
e7
Ei - estado
3
r4
r4
4
e5
ac
r2 a1 •••
r2ai •••• an$
r4
r4
e4
5
r6
6
8
e5 Em
Xm
e5 •••
X1 e6
9
E0 r1
e7
r1
r1
10
r3
r3
r3
r3
11
r5
r5
r5
r5
7
(1) E ::= E + T
(4) T ::= F
r6
8
r6
3
9
3
r6
Analisador
LR
e4
Tabela de análise
e4
e11
(2) E ::= T
(5) F ::= (E)
2
(3) T ::= T * F
(6) F ::= id
10
ANALISADORES LR(K) - FUNCIONAMENTO

Seja Em o estado no topo da pilha e ai o token sob
o cabeçote de leitura• O analisador consulta a
tabela AÇÃO[Em, ai], que pode assumir um dos
valores
empilha Ex: causa o empilhamento de "aiEx"
 reduz n (onde n é o número da produção A::=β): causa
o desempilhamento de 2r símbolos, onde r = |β | e o
empilhamento de "AEy" onde Ey resulta da consulta à tabela
de TRANSIÇÃO [Em-r*, A];
 aceita: o analisador reconhece a sentença como válida
 erro: o analisador para a execução, identificando um
erro sintático

* Em-r é o estado do topo da pilha após a operação de redução
ANALISADORES LR(K) - FUNCIONAMENTO
Pilha
0
0 id 5
0F3
Entrada
Ação/Transição
id * id + id $ e5: empillha id 5
* id + id $ r6: reduz F::=id
TRANSIÇÃO[0,F]
CONSTRUÇÃO DA TABELA PARA
ANALISADORES SLR



A construção da tabela de controle para analisadores
SLR, baseia-se no Conjunto Canônico de Itens LR(0) o
qual serve de base para a construção de um AFD p/ o
reconhecimento
Um item LR(0), para uma gramática G, é uma
produção com um ponto em alguma posição do lado
direito
A ::= •XYZ Inicio da busca por uma cadeia derivável de XYZ
A ::= X•YZ X já foi encontrada, continua a busca por YZ
A ::= XY•Z XY já foi encontrada, continua a busca por Z
A ::= XYZ• Fim da busca• XYZ foi encontrada, podendo ser reduzida p/ A
O ponto é a indicação de até onde uma produção já foi
analisado no processo de reconhecimento
FUNÇÕES CLOSURE E GOTO


Fechamento de conjuntos de itens (CLOSURE)
 Se I é um conjunto de itens para a gramática G, então
CLOSURE(I) é construído a partir das duas regras:
1. Inicialmente, acrescente todo item de I no
CLOSURE(I)
2. Se A→α•Bβ está em CLOSURE(I) e B → γ é uma produção,
então adicione o item B →•γ em CLOSURE(I), se ele ainda
não estiver lá• Aplique esta regra até que nenhum outro item
possa ser incluído no CLOSURE(I)
E’ → E
E→E+T|T
Exemplo: sendo I = {E´ → •E}, calcule CLOSURE(I)
T→T*F|F
F → (E) | id
CLOSURE(I) = { E´ → •E, E → •E+T, E → •T, T → •T*F, T → •F, F → •(E), F → •id}
Aplica regra 1 a I
Aplica regra 2
FUNÇÕES CLOSURE E GOTO
Função de Transição (GOTO)
 É definida como GOTO(I,X), onde I é um conjunto de
itens e X é um símbolo da gramática
 Formalmente, GOTO(I,X) é a função CLOSURE do
conjunto dos itens A→αX•β, tais que A→α•Xβ pertence a I
 Informalmente, consiste em coletar as produções com
o ponto no lado esquerdo de X, passar o ponto para a
direita de X, e obter a função CLOSURE desse conjunto
 Exemplo: sendo I={E’ →E•, E →E•+T}, calcule GOTO(I,+)
GOTO(I,+) = { E→ E+•T,
E’ → E
E→E+T|T
T→ •T*F,
T→T*F|F
T→ •F,
F → (E) | id
F→•(E),
F→ •id } Calcula
PassaCLOSURE(E→
o ponto para o lado
E+•T)
Adiciona
a novo produção
direito do símbolo X

CONJUNTO CANÔNICO DE ITENS
void itens(G’){
C = CLOSURE({S’→•S});
repeat
for (cada conjunto de itens I em C)
for (cada X símbolo da gramática)
if (GOTO(I,X) não vazio em não está em C)
adicione GOTO(I,X) em C;
until nenhum novo conjunto de itens seja adicionado em uma rodada
}
I0
E’→•E
E→•E+T
E→•T
T→•T*F
T→•F
F→•(E)
F→•id
I1
E’→E•
E→E•+T
E
T
I2
E→T•
T→T•*F
id
+
*
I5
F→id•
I9
E→E+T•
T→T•*F
T
I6
E→E+•T
T→•T*F
T→•F
F→•(E)
F→•id
I7
T→T*•F
F→•(E)
F→•id
id
*
F
I10
T→T*F•
id
+
(
T
id
I4
F→(•E)
E→•E+T
E→•T
T→•T*F
T→•F
F→•(E)
F→•id
E
I8
(
E→E•+T
F→(E•)
(
(
(
F
F
I3
T→F•
I11
F→(E)•
F
(1) E → E + T (4) T → F
(2) E → T
(5) F → (E)
(3) T → T * F (6)F → id
CONSTRUÇÃO DA TABELA SLR

Seja C={I0, I1, ..., In}. Os estados doa analisador
são 0, 1, ..., n. A linha i da tabela é construída a
partir do conjunto Ii, como segue:

As ações do analisador para o estado i são
determinadas:
1.
2.
3.

Se GOTO(Ii,a) = Ij, então faça AÇÃO[i,a] = empilha j;
Se A→α• está em Ii, então para todo FOLLOW(A), faça
AÇÃO[i,a] = reduz n, sendo n o número da produção A→α
Se S’→S• está em Ii, então faça AÇÃO[i,$] = aceita
As transições para o estado i são construídas:
1.
Se GOTO(Ii,A) = Ij, então TRANSIÇÂO(i,A) = j
Obs: se ocorrer algum conflito resultante da aplicação das
regras descritas, podemos afirmar que a gramática não é
SLR(1)
Estado
0
Ação
id
+
*
e5
Transição
(
)
$
e4
1
e6
2
r2
e7
r2
r2
3
r4
r4
r4
r4
4
e4
r6
r6
r6
6
e5
e4
7
e5
e4
F
1
2
3
8
2
3
9
3
r6
10
8
e6
9
r1
e7
r1
r1
10
r3
r3
r3
r3
11
r5
r5
r5
r5
(1) E ::= E + T
(4) T ::= F
T
ac
e5
5
E
e11
(2) E ::= T
(5) F ::= (E)
(3) T ::= T * F
(6) F ::= id
TABELA SLR

Representação eficiente do autômato de pilha que
reconhece a linguagem. Onde:
O topo da pilha contém sempre o estado atual do
autômato
 Dado o estado atual e o token de entrada, a tabela
indica a ação a ser executada
 No caso da ação ser uma redução a tabela Transição
indica o próximo estado a ser assumido pelo autômato
 As entradas em branco correspondem a situações de
erro
