2 Compiladores1 Analise Sintatica

Construo de Compiladores I

Anlise Sinttica

Prof. Odilon [email protected]://odilon.rg3.net

Introduo

A sintaxe de uma Linguagem de Programao pode ser descrita por uma Gramtica Livre de Contexto (GLC)

Introduo

Vantagens:- Especificao sinttica precisa;- A criao do analisador pode ser automatizada por ferramentas especficas, para certas classes de gramticas;- Gramticas bem projetadas facilitam a compilao e a deteco de erros;- Novas construes sintticas so mais facilmente adicionadas.

Analisador Sinttico (AS)

Dada uma gramtica G(S), verificar se uma sentena w pertence ou no L(G) verificar se

S =>+ w

para alguma seqncia de derivao

S => w1 => w2 => ... => wn => w

em outra palavras, obter uma rvore de Derivao Sinttica (ADS) para w.


O AS, portanto, um construtor de ADS.Quando consegue construir uma ADS para uma sentena w (programa), o programa est sintaticamente correto.


Descendente (Top-Down)Ascendente (Bottom-Up)

AS Descendente

Tenta construir a ADS para uma sentena w a partir do smbolo inicial S (raiz), aplicando regras de produo at produzir todos os tokens (folhas) de w.

Exemplo

S aBC

B ab

B b

C c

C a

w1 = aba

w2 = abc

w3 = aabc

e as sentenas:Seja G(S):

ExemploPara w1, temos a sequncia de derivaes:

S


S

a B C


S

a B C

b


S

a B C

b a


S

a B C

b a

As folhas da ADS (smbolos terminais) formam w1

Exerccio

Demonstre a construo da ADS para w2 e w3, usando a tcnica descendente.

AS Ascendente

Tenta construir a ADS para uma sentena w a partir dos tokens (folhas) de w, fazendo redues at obter o smbolo inicial S (raiz).

Exemplo

S aBC

B ab

B b

C c

C a

w1 = aba

w2 = abc

w3 = aabc


ExemploPara w1, temos a sequncia de redues:

a b a


a b a

B


a b a

B C


a b a

B C

S


a b a

B C

S

A raiz foi alcanada

Exerccio

Demonstre a construo da ADS para w2 e w3, usando a tcnica ascendente.

AS Descendente

Pode ser visto como uma tentativa de construir a ADS partindo da raiz e criando os ns em pr-ordem.

AS Descendente

Com Retrocesso (Backup)RecursivoPreditor - LL(k)

AS Descendente com Backup

Tenta derivar a sentena por tentativa e erro, retornando para o passo anterior caso a derivao no tenha sucesso. o mais antigo mtodo para construo de ADS.

Exemplo

S aBC

B ab

B b

C c

C a

w1 = aba

w2 = abc

w3 = aabc



S


S

a B C


S

a B C

a b


S

a B C

a b FALHA


S

a B C


S

a B C

b


S

a B C

b c


S

a B C

b c FALHA


S

a B C

b


S

a B C

b a


S

a B C

b a

As folhas da ADS (smbolos terminais) formam w1

AS Descendente com Backup

O histrico de tentativas de derivao mantido numa pilha;

Requer muita memria/tempo;Por isso, tem sido pouco utilizado

Exerccio

Demonstre a construo da ADS para w2 e w3, usando a tcnica descendente com backup.

AS Descendente Recursivo

implementado na forma de um conjunto de procedimentos recursivos, sendo um procedimento para cada no-terminal.


Vantagem: Aproveita o recurso de recursividade da linguagem escolhida para implementar o analisador;Desvantagem: No pode haver recurses esquerda na gramtica (ex: A A)


Expr Termo + Expr | Termo

Termo Fator * Termo | Fator

Fator num_int | ( Expr )

Seja G(Expr):


(1) Expr Termo (+ Termo)*

(2) Termo Fator (* Fator)*

(3) Fator num_int

(4) Fator ( Expr )

Podemos escrev-la numa forma estendida (EBNF), onde (w)+ significa uma ou mais ocorrncias de w, e (w)* significa zero ou mais ocorrncias de w:


Expr = Termo ouExpr = Termo + Termo ouExpr = Termo + Termo + Termo

A regra 1 interpretada como: "expresso um termo seguido de zero ou mais expresses conectadas pelo operador +", ou seja:


Podemos, agora, escrever um algoritmo que faa a anlise de sentenas geradas a partir dessa gramtica.


void analisar() {/* chama o lxico */lexico.proximoToken(); Expr();}


void Expr() {Termo();while (tokenAtual == '+') {lexico.proximoToken();Termo();}}


void Termo() {Fator();while (tokenAtual == '*') {lexico.proximoToken();Fator();}}

AS Descendente Recursivovoid Fator() {if (tokenAtual == num_int) {/* tratar nmero inteiro... */lexico.proximoToken();}else if (tokenAtual == '(') {Expr();if (tokenAtual != ')'){erroSintaxe();}}}

Problema da Recursividade

Para que se possa construir um analisador sinttico descendente, uma gramtica no pode ter regras recursivas esquerda (diretas ou indiretas). Uma gramtica recursiva esquerda se tem produes da forma

A ANesse caso, um algoritmo que implemente um analisador descendente vai entrar em ciclo (loop) infinito


Este problema pode ser resolvido com uma transformao na gramtica. Produes do tipo

A A | Cujo cujo objetivo produzir cadeias da forma, , , ...devem ser transformadas para

A A'

A' A'|


Em outras palavras, a soluo consiste em transferir a recursividade para a direita.

Exemplo

Expr Expr + Termo | Termo

Termo Termo * Fator | Fator

Fator id | num_int | ( E )

Exemplo

Expr Termo Expr'

Expr' + Termo Expr' |

Termo Fator Termo'

Termo' * Fator Termo' |

Fator id | num_int | ( E )

Problema do Indeterminismo

Outro problema relacionado aos analisadores descendentes o de produes da forma

(1) A

(2) A a partir do ponto A na ADS de uma sentena, pode-se derivar pela regra (1) ou pela regra (2)para chegar mesma cadeia ; ou seja, pode-se aplicar mais de uma regra para chegar ao mesmo resultado.

Problema do Indeterminismo

Uma nova transformao necessria. Produes do tipo

A

A so fatoradas pelo prefixo comum, gerando

A Aresto

Aresto |

Exemplo

Expr Termo Expr'


Termo Fator Termo'


Fator id | id [ num_int ]| num_int | ( E )

Exemplo

Expr Termo Expr'


Termo Fator Termo'


Fator id FatorR | num_int | ( E )

FatorR [ num_int ] |

Gramtica LL(1)

A uma gramtica transformada de modo a eliminar recursividades esquerda e indeterminismos, chamamos gramtica LL(k) ("Left-to-right, Left-most-derivation with Lookahead k").

Gramtica LL(1)

A ideia de anlise LL(k) a de que basta olharmos no mximo k smbolos frente na sentena, a partir do ponto em que estamos na ADS, para que possamos decidir que regra de produo aplicar.A constante k deve ser to pequena quanto possvel ( idealmente, k=1; da o nome: gramtica LL(1) ).

Exemplo

S a S

S b S

S c

G(S) LL(1). Testar a anlise paraw1 = abc

w2 = bac

Exemplo

S a b S

S a c S

S ad

G(S) LL(2). Testar a anlise paraw1 = abad

w2 = acad

AS Descendente Tabular

Utiliza uma tabela de anlise, com uma estrutura auxiliar (pilha); implementado atravs de um autmato de pilha (Push-Down Automaton);A exemplo do analisador descendente recursivo, este tambm utiliza gramticas LL(1)


Este mtodo de anlise utilizado quando a linguagem usada para implementar o analisador no dispe de recursividade, ou quando no se deseja usar recursividade, por exemplo, para evitar estouros de pilha.


Por utilizar uma pilha explcita (ao invs da pilha implcita em ativaes recursivas), facilita a visualizao do funcionamento do analisador, conforme regras de produo so aplicadas.

Funcionamento do AS Tabular

Tabela de Anlise Sinttica (TAS)Pilha de Anlise

Modelo do AS Tabular

TAS

Analisador Sinttico

pilha

X

Y

a b c aentrada

1 4 8sada


A partir de X, smbolo do topo da pilha, e de tokenAtual, o atual smbolo de entrada, o analisador determina sua ao que pode ser uma das quatro possibilidades a seguir:


1) Se X um terminal = tokenAtual = , o analisador encerra sua atividade e comunica fim da anlise sinttica com sucesso;


2) Se X um terminal = tokenAtual , o analisador elimina X do topo da pilha e avana para o prximo smbolo de entrada;


3) Se X um terminal tokenAtual, o analisador acusa um erro de sintaxe (ativa rotina de tratamento de erros);


4) Se X um no-terminal, o analisador consulta TAS[X, tokenAtual]. Se a resposta for uma regra X 1..n, o analisador desempilha X e empilha n..1(com 1 no topo da pilha). Para a sada enviada a regra de produo usada.

Se TAS[X, tokenAtual] = ERRO, o analisador acusa um erro de sintaxe (ativa rotina de tratamento de erros).

Algoritmo do AS Tabular

/* seja X o smbolo do topo da pilha etokenAtual o smbolo atual da entrada */

Algoritmo do AS Tabularwhile (X != ) {if (X.isTerminal) {if (X == tokenAtual) {pop(X); lexico.proximoToken();} else ERRO();}elseif (TAS[X, tokenAtual] == "X1..n") {

pop(X); push(n..1);

} else ERRO();} if (tokenAtual != ) ERRO();

Obteno da TAS

Como visto, a Tabela de Anlise Sinttica o componente central do analisador tabular.Para constru-la, precisamos introduzir dois novos conceitos (ou relaes) em gramticas. So os conjuntos Primeiro ("First") e Seguidor ("Follow")

Obteno da TAS - FIRST

O conjunto dos Primeiros (FIRST) contm todos os smbolos que podem iniciar uma produo para um determinado no-terminal. Para obt-lo, utiliza-se o seguinte algoritmo ( No algoritmo a seguir, um no-terminal qualquer):

Obteno da TAS - FIRST

Obteno de FIRST(), para y1y2...yn FIRST() := FIRST(y1) {} i := 1 Enquanto (i < n) e ( FIRST(yi)) Faa {FIRST() := FIRST() (FIRST(yi+1) {}) i := i + 1 }Se (i = n) e ( FIRST(yn)) Ento FIRST() := FIRST() {}

Obteno da TAS - FOLLOW

O conjunto dos Seguidores (FOLLOW) contm os smbolos terminais que podem aparecer aps um dado smbolo no-terminal, em alguma forma sentencial. O algoritmo de obteno dos seguidores o seguinte:

Observao

No algoritmo a seguir, e so cadeias de smbolos (terminais ou no-terminais), S o smbolo inicial e N o conjunto dos no-terminais

Obteno da TAS - FOLLOWObteno de FOLLOW, para todos os A Vn

FOLLOW(A) := , A N ; FOLLOW(S) := {}

Para toda produo A B Faa

FOLLOW(B) := (FIRST() {}) FOLLOW (B) Repita

Para toda produo (A B) ou (A B, com FIRST()) Faa

FOLLOW(B) := FOLLOW(A) FOLLOW(B) At no adicionar mais smbolos a qualquer FOLLOW

Obteno da TAS

Uma vez obtidos estes dois conjuntos, pode-se construir a TAS, conforme o algoritmo a seguir:

Obteno da TASpara cada produo A , faa { para cada terminal a FIRST(), faa adicione A em TAS[A, a]; se FIRST(), adicione A em TAS[A, b], para cada b FOLLOW(A); se FIRST() e FOLLOW(A), adicione A em TAS[A, ] } indique situao de ERRO para todas as posies indefinidas de TAS[A, a];

Exemplo1. Expr Termo Expr'

2. Expr' + Termo Expr'

3. Expr'

4. Termo Fator Termo'

5. Termo' * Fator Termo'

6. Termo'

7. Fator id

8. Fator ( E )

Exemplo - FIRST

FIRST(Expr) = {(,id}FIRST(Expr') = {+,}FIRST(Termo) = {(,id}FIRST(Termo') = {*,}FIRST(Fator) = {(,id}

Exemplo - FOLLOW

FOLLOW(Expr) = {),}FOLLOW(Expr') = {),}FOLLOW(Termo) = {+,),}FOLLOW(Termo') = {+,),}FOLLOW(Fator) = {+,*,),}

Exemplo - TAS

ExemploAnalisar a entrada:

a + b * c

Atravs do algoritmo LL(1), demonstrando-o visualmente, passo a passo.

ExemploEntrada: a + b * c

Pilha de Anlise

Expr

Derivaes:


Pilha de Anlise

TermoExpr'

Derivaes: Expr Termo Expr'


Pilha de Anlise

FatorTermo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo'


Pilha de Anlise

idTermo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id

ExemploEntrada: + b * c

Pilha de Anlise

Termo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id


Pilha de Anlise

Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo'


Pilha de Anlise

+Termo

Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr'

ExemploEntrada: b * c

Pilha de Anlise

TermoExpr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr'


Pilha de Anlise

FatorTermo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo'


Pilha de Anlise

idTermo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id

ExemploEntrada: * c

Pilha de Anlise

Termo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id

ExemploEntrada: * c

Pilha de Anlise

*Fator

Termo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id,Termo' * Fator Termo'

ExemploEntrada: c

Pilha de Anlise

FatorTermo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id,Termo' * Fator Termo'

ExemploEntrada: c

Pilha de Anlise

idTermo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id,Termo' * Fator Termo', Fator id

ExemploEntrada:

Pilha de Anlise

Termo'Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id,Termo' * Fator Termo', Fator id

ExemploEntrada:

Pilha de Anlise

Expr'

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id,Termo' * Fator Termo', Fator id,Termo'

ExemploEntrada:

Pilha de Anlise

Derivaes: Expr Termo Expr',Termo Fator Termo', Fator id,Termo' , Expr' + Termo Expr',Termo Fator Termo', Fator id,Termo' * Fator Termo', Fator id,Termo' , Expr'

Sucesso!

Exerccio

a) Montar a Tabela de Anlise Sinttica para a gramtica da mini-linguagem descrita a seguir (note que os passos necessrios so:[1] Reescrever a gramtica na forma LL(1);[2] Encontrar os conjuntos FIRST e FOLLOW;[3] Construir a TAS);

Exercciob) Demonstrar o algoritmo de anlise tabular para o seguinte programa:

integer x; x := 0;integer y; y := 1 + x;write y*2end

Terceira Condio LL(1)

Como visto anteriormente, o algoritmo do Analisador Preditor s funciona para gramticas LL(1); no entanto, ainda que a gramtica tenha sido modificada para eliminar as recursividades esquerda e os indetermenismos, a mesma pode ainda no ser LL(1).


Ao se montar a TAS para uma gramtica (supostamente LL(1)), caso alguma entrada da tabela contenha referncia a mais de uma produo, ento a gramtica no LL(1). Dizxemos, neste caso, que h um conflito LL(1)


Consideremos apenas as produes correspondentes ao if-else, numerando-as:

1. Cmd CmdIf2. CmdIf if Cond then Cmd ParteElse3. ParteElse else Cmd4. ParteElse


Podemos simplificar (isolar) nossas produes, representando Cond como o terminal id:

1. Cmd CmdIf2. CmdIf if Cond then Cmd ParteElse3. ParteElse else Cmd4. ParteElse 5. Cond id(Isso possibilita construir uma TAS apenas para as produes dadas, a fim de ilustrar o problema)


FIRST(Cmd) = { if }FIRST(CmdIf) = { if }FIRST(ParteElse) = { else, }FIRST(Cond) = { id }


FOLLOW(Cmd) = { else, }FOLLOW(CmdIf) = { else, }FOLLOW(ParteElse) = { else, }FOLLOW(Cond) = { then }

Terceira Condio LL(1) - Soluo

Em casos de conflitos LL(1) como os descritos anteriormente, uma possvel soluo adicionar uma heurstica ao algoritmo do analisador, para indicar qual das produes possui precedncia. A forma mais simples de implementar tal heurstica editar a TAS, removendo a produo extra indesejada.

Terceira Condio LL(1) - Soluo

A alterao (heurstica) feita na TAS indica ao analisador que, ao encontrar ParteElse no topo da pilha e else na entrada, a produo 3 deve ser escolhida (ParteElse else Cmd), ignorando-se a produo 4 (ParteElse ). Isso efetivamente resolve o conflito LL(1).

Bibliografia RecomendadaAHO, A., SETHI, R. e ULLMAN, J. D. Compiladores: Princpios, Tcnicas e Ferramentas, LTC, 1995

LOUDEN, KENNETH C. Compiladores: Princpios e Prctica Thomson, 2004

MONGIOVI, GIUSEPPE. Construo de Compiladores, Notas de Aula. Joo Pessoa: 2002

NICOLLETTI, PEDRO S. Compiladores, Notas de Aula. Campina Grande, 2003

Documents

2 Compiladores1 Analise Sintatica