COMPILADORES
ANÁLISE SINTÁTICA
Guilherme Amaral Avelino
[email protected]

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:: X1,X2,...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 no 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
 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 que se pode seguir a
derivar após 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 ε:
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(Yi-1).


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 {ε} U FIRST(ba) U FISRT(c)
{a} U {ε} U {b} U {c}
{a,b,c, ε}
FUNÇÃO FOLLOW - REGRA

Para calcular FOLLOW(A) de todos os nãoterminais A, as seguintes regras devem ser
aplicadas até que nada mais possa ser
acrescentado a nenhum dos conjuntos FOLLOW:
Coloque $ em FOLLOW(S), onde $ é o marcador de
fim da entrada
 Se houver uma produção A::αBβ, então tudo em
FIRST(β) exceto ε está em FOLLOW(B)
 Se houver uma produção A::αB, ou uma produção A::=
αBβ, onde o FIRST(β) contém ε, então inclua o FOLLOW(A)
em FOLLOW(B)

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) =
FOLLOW()) 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}
CENAS DO PRÓXIMO CAPÍTULO
Gramáticas LL(1)
 Construção de tabela preditiva
