compiladores 2a prova

Embed Size (px)

Citation preview

CompiladoresFACID Sistemas de Informao

Prof. Leonardo Saraiva

Anlise Sinttica Conceitos Verifica se o programa est de acordo com a gramtica da linguagem Seja G uma GLC e s uma palavra, ento a anlise sinttica tem a funo de responder s L(G) ? Para cada palavra gerada uma rvore de derivao rvore explcita: representada atravs de estrutura de dados rvore implcita: chamada de rotinas e recurso

Estratgias para anlise Top-down (descendente) Constroi a rvore de derivao a partir do smbolo inicial de G

Bottom-up (redutiva) Inverso da top-down: a partir das folhas (tokens) a rvore gerada2FACID - Sistemas de Informao

1

Anlise Sinttica Exemplos AaB | aa Bba | baB A aB abaB ababa (TOP-DOWN) ababa abaB aB A (BOTTOM-UP) numero num num num digito | digito digito 0|1|2|3|4|5|6|7|8|9

numero num num digito 4 digito 5FACID - Sistemas de Informao

3

Anlise Sinttica Anlise Top-down Recursiva com retrocesso (backtracking) Expande o no terminal mais esquerda da produo A aBC Aps a identificao do terminal a, o no terminal B escolhido, caso B falhe ento ERRO, caso contrrio, escolhe C, caso C falhe ento ERRO if (token == TOKEN_a) { B; C; } else { out.println(ERRO); }4FACID - Sistemas de Informao

2

Anlise SintticaScAd Aab | a w=cad

5

FACID - Sistemas de Informao

Anlise Sinttica Problemas da anlise recursiva com retrocesso Repetio da leitura de partes da palavra a ser reconhecida Possibilidade de desfazer aes semnticas, como atualizaes na tabela de smbolos Dificuldades na identificao de onde o erro ocorreu, devido a tentativa de aplicaes de produes Recurso infinita em GLC com recurso a esquerda !

6

FACID - Sistemas de Informao

3

Anlise Sinttica Anlise recursiva preditiva o analisador recursivo sem backtracking O terminal na cabea de leitura determina qual produo ser aplicada Dado um smbolo de entrada a, e um no terminal A, necessrio saber com exatido qual a nica alternativa de A1| 2| ... |n que deriva o string com prefixo a.

Exigncias A gramtica no tenha recursividade esquerda A gramtica seja fatorada esquerda No terminais com mais de uma produo, os terminais identifiquem unicamente a produo a ser FACID - Sistemas de Informao aplicada.

7

Anlise Sinttica Exemplos Sif E then S else S | while E do S | begin S_list endswitch (TOKEN) { case TOKEN_IF:{ E(); if (TOKEN == TOKEN_THEN) { S(); if (TOKEN == TOKEN_ELSE) { S(); } } break(); } case TOKEN_WHILE:{ E(); if (TOKEN == TOKEN_DO) { S(); } break(); } case TOKEN_BEGIN:{ S_LIST(); if (TOKEN != TOKEN_END){ erro(); } }

8

FACID - Sistemas de Informao

4

Anlise SintticaSC | I | A Cif E then C I repeat L until E | while E do C A id := E Quais terminais iniciam as sentenas dos no terminais C, I eA? O conjunto FIRST(), onde um no terminal (devem ser disjuntos). FIRST() o conjunto de todos os terminais que podem iniciar qualquer sentena derivada de . Exemplo: FIRST(I) = {repeat, while}9FACID - Sistemas de Informao

Anlise SintticaSE$ EE+T EET ET TT*F TT/F TF F id F num F (E)void S() { E(); eat(EOF); } void E() {switch (tok) case ?: E(); case ?: E(); case ?: T(); }} { eat(PLUS); T(); break; eat(MINUS); T(); break; break; default: error();

void T() {switch (tok) { case ?: T(); eat(TIMES); F(); break; case ?: T(); eat(DIV); F(); break; case ?: F(); break; default: error(); }}

Como resolver o caso E() ? Qual case utilizar ? Usar o conjunto FIRST e verificar as exigncias para a G10FACID - Sistemas de Informao

5

Anlise Sinttica Analisador Preditivo Tabular (sem recurso!)

11

FACID - Sistemas de Informao

Anlise Sinttica Caractersticas Usa uma pilha explcita que implementa a recursividade So utlizadas tabelas auxiliares: tabela de anlise (parse) e uma pilha O problema chave determinar qual produo usar cujo o lado direito da produo ir substituir um no terminal que est no topo da pilha A pilha inicia-se com o smbolo $ e em seguida os smbolos da gramtica (comeando o smbolo inicial) A tabela de anlise uma matriz M[N,n+1], onde N a quantidade de no terminais e n a quantidade de terminais12FACID - Sistemas de Informao

6

Anlise Sinttica Funcionamento do parser preditivo Considerando X o topo da pilha e a o smbolo de entrada:repita Se X terminal ou $ ento Se X = a ento Desempilha X e avana o ponteiro de leitura seno ERRO ! seno Se M[X,a] for um produo (XUVW) ento desempilha X topo da pilha = produo (com U no topo) seno Se M[X,a] for vazio ento ERRO ! At X = $13FACID - Sistemas de Informao

14

FACID - Sistemas de Informao

7

Anlise Sinttica Construo da tabela de anlise FIRST Se uma sentena ento FIRST() conjunto de terminais que iniciam as formas sentenciais derivadas a partir de O vazio pertence a FIRST() se * Exemplos: slide 9 !

FOLLOW Para um no terminal A, FOLLOW(A) o conjunto de terminais a que podem aparecer imediatamente do lado direito de A em alguma forma sentencial. Isto , o conjunto de terminais a tal que exista uma derivao da forma S *Aa, para algum e .

15

FACID - Sistemas de Informao

Anlise Sinttica ALGORITMO - FIRST(X)1. Se X terminal ento FIRST(X) {X} 2. Se X ento adicione em FIRST(X) 3. Se X no terminal e Xa ento coloque a em FIRST(X) 4 Se XY1Y2...Yk, ento para todo i, adicione FIRST(Y1Y2...Yk) a FIRST(X), FIRST(Y1Y2...Yk) como abaixo: a. FIRST(Y1) se FIRST(Y1) no contm b. OU Se FIRST(Y1) contm ento FIRST(Y1Y2...Yk) est contido em FIRST (Y1) - {} bem como tudo em FIRST(Y2...Yk) c. Finalmente, se para todo i (de 1 a k) FIRST(Yi) contm , ento adicione em FIRST(X). FACID - Sistemas de Informao

16

8

Anlise SintticaExemploE TE E +TE| T FT T *FT| F (E)|id FIRST(E) = {+, } FIRST(T) = {*, } FIRST(F) = {(, id} FIRST(T) = FIRST(F) = {(, id} FIRST(E) = FIRST(T) = {(, id}17FACID - Sistemas de Informao

Exerccio: S Baa A BcA| B b|

Anlise Sinttica ALGORITMO FOLLOW(A) (A no terminal) 1. Coloque $ (a marca de final de sentena) em FOLLOW(S), onde S o Smbolo Inicial da gramtica em questo; 2. Se A B P e , ento ( qualquer sentena), FOLLOW(B) = FIRST() {}; 3.Se A B (ou A B, onde FIRST() ) P, ento adicione FOLLOW(A) em FOLLOW(B).

18

FACID - Sistemas de Informao

9

Anlise SintticaExemploE TE E +TE| T FT T *FT| F (E)|id FOLLOW(E) = {$,)} FOLLOW(E) = FOLLOW(E) = {$,)} FOLLOW(T) = FOLLOW(T) = {+,),$} FOLLOW(F) = {+,*,),$}

Exerccio: S BAa A BcA| B b|

19

FACID - Sistemas de Informao

Anlise Sinttica Construo da Tabela de AnlisePara cada A execute Para cada terminal a de FIRST(), adicione A a M[A,a] Se FIRST() ento adicione A a M[A,b] para cada b FOLLOW(A) . Se FIRST() E $ FOLLOW(A), adicione A a M[A,$]

20

FACID - Sistemas de Informao

10

Anlise Sinttica ExemplosPara E TE tem-se FIRST(TE)={(, id}, adiciona a produo em M[E,(] e M[E,id] Para E +TE tem-se FIRST(+TE)={+, }, adiciona a produo em M[E,+], M[E,$], M[E,)] (pois FIRST(+TE) possui o vazio e FOLLOW(E)={$,)} Para E adiciona-se a produo em M[E,$] e M[E,)] (pois FOLLOW(E) = {$,)} Para T FT tem-se FIRST(FT)={(,id}, adiciona a produo em M[T,(] e M[T,id] Para T *FT tem-se FIRST(*FT)={+, }, adiciona a produo em M[T,+], M[T,)], M[T,$] (pois FIRST(+TE) possui o vazio e FOLLOW(T)={+,$,)} ) Para T adiciona-se a produo em M[T,+], M[T,)] e M[T,$] Para F (E) tem-se FIRST((E))={(}, adiciona a produo em M[F,(] Para F id adiciona-se a produo em M[F,id]21FACID - Sistemas de Informao

Anlise SintticaProduoE TE E +TE E T FT T *FT T F (E) F id {(} {id} {(,id} {*, } {+,$,)} {+,),$}

FIRST{(, id} {+, }

FOLLOW

MM[E,(] e M[E,id]

{$,)} {S,)}

M[E,+] M[E,$] e M[E,)] M[T,(] e M[T,id] M[T,*] M[T,+], M[T,)] e M[T,$] M[F,(] M[F,id]

22

FACID - Sistemas de Informao

11

Anlise SintticaTabela de Anlise Preditivaid E E T T F Fid TFT T T*FT F(E) ETE E+TE TFT T T + * ( ETE E E ) $

A gramtica LL(1): no possui mais de uma derivao para M[A,a]23FACID - Sistemas de Informao

Anlise Sinttica Anlise Redutiva (Bottom-up) o processo inverso de derivao, onde h uma substituio do terminal esquerda por um no terminal do lado esquerdo da produo; Exemplo: SaABe AAbc | b BdSentena: abbcde abbcde aAbcde aAde aABe S24FACID - Sistemas de Informao

12

Anlise SintticaPilha $ $a $ab $aA $aAb $aAbc $aA $aAd $aAB $aABe $S25

Entrada abbcde$ abbcde$ abbcde$ aAbcde$ aAbcde$ aAbcde$ aAde$ aAde$ aABe$ aABe$ $

Ao Empilha a Empilha b Reduz Ab Empilha b Empilha c Reduz AAbc Empilha d Reduz Bd Empilha e Reduz SaABe Aceita !

SaABe AAbc | b Bd

FACID - Sistemas de Informao

Anlise Sinttica Processo Consiste em transferir smbolos da fita de entrada (sentena) para a pilha at que se tenha na pilha um lado direito da produo; Quando na pilha h o lado direito de uma produo, este lado substitudo pelo smbolo do lado esquerdo da produo, at que a sentea seja completamente lida e a pilha fique reduzida ao smbolo inicial da gramtica. Mas por que na linha destacada no foi escolhido b ?

Handle uma substring que se iguala ao lado direito de uma produo e cuja reduo para um no terminal do lado esquerdo da produo representa uma reduo reversa na derivao mais a direita da sentena; Na reduo aAbcde no foi tratado o b como um handle, pois nopodemos reduzir para o smbolo inicial da gramtica Definio formal de handle;26FACID - Sistemas de Informao

13

Anlise Sinttica Tipos de Analisadores Redutivos Analisadores de Precedncia de Operadores Operam sobre gramticas de operadores (sempre possuem um terminal entre no terminais do lado direito da produo e no h produes vazias) So utilizadas nos reconhecimentos de expresses aritmticas com precedncia de operadores; Os handles so identificados pelas precedncias

Analisadores LR(k) (left to right with rightmost derivation) So analisadores redutores que lem a sentena da esquerda para a direita (L) e produzem uma derivao mais esquerda ao reverso, considerando k smbolos sob o cabeote de leitura Reconhecem as Linguagens geradas por GLC o mais mtodo mais genrico para analisadores sem recurso com pilha e ainda pode ser implementado com a mesma eficincia Descobrem erros sintticos na leitura da sentena em anlise27FACID - Sistemas de Informao

Anlise Sinttica Dificuldade na implementao da tabela de anlise

Tipos de analisadores LR SLR (Short LR): so aplicados a uma classe restrita de gramticas LR Cannico: cobre um nmero de gramticas maior que SLR LARL (look-ahead LR): funciona para as maiorias das linguagens de programao. de nvel inermedirio

Earley: trata de gramticas que implementam linguagens naturais (Charts parsers)

28

FACID - Sistemas de Informao

14

Anlise Sinttica Recuperao de Erros uma tentativa do compilador em continuar o processo de anlise sinttica na busca de mais erros A qualidade do recuperador de erros inversamente proporcional a quantidade de erros falsos gerados. Ao identificar erros deve-se desativar a gerao do cdigo

a := b c + d

Comentrios: 1. Inserir ; aps o identificador b 2. Outro erro gerado em c + d;

Erro !29FACID - Sistemas de Informao

Anlise Sinttica Quando ocorrem os erros: Tempo mais cedo No ato da leitura da sentena, quando o token lido no o esperado (LL, LR e de precedncia)

Tempo mais tarde Em operaes sobre a pilha quando, numa reduo, o handle no se encontra na pilha (precedncia de operadores)

Tipos de recuperao Modo pnico O analisador l e descarta smbolos de entrada at encontrar um token de sincronizao (delimitador ou palavra reservada); Eventualmente, so removidos os smbolos da pilha at o ponto a partir do qual consiga reestabelecer o processo de anlise.30FACID - Sistemas de Informao

15

Anlise Sinttica Recuperao baseada em expresses O analisador realiza um correo, substitundo a substring errada por outra que permita com que o analisador prossiga o processamento. A substituio pode ser: um ponto por um ponto e vrgula Pode gerar loops infinitos (erros infinitos) se a substituio no for bem escolhida

Produo de erros Pode-se prever os erros mais comuns aumentando-se a gramtica com as produes que gerem construes errneas

Correo global So utilizados algoritmos que permitem mnimas modificaes na gramtica para que o erro seja recuperado uma composio da produo de erros e recuperao baseada em expresses.31FACID - Sistemas de Informao

Anlise Sinttica Recuperao de erros em anlise LL So identificados atravs de posies M[A,a] que no posuem produes e quando o no terminal do topo da pilha no corresponde ao token lido. utilizada a tabela de anlise para realizar sincronismos, atravs de dois modos: Modo pnico: Despreza os smbolos da entrada at encontrar um token de sincronizao

Recuperao local: H a tentativa de recuperar o erro, fazendo alteraes sobre um smbolo apenas: desprezando o token de entrada, ou substitundo por outro, ou inserindo um novo token ou removendo o smbolo da pilha.

32

FACID - Sistemas de Informao

16

Anlise Sinttica Modo pnico Construir o conjunto de terminais ao qual o analisador pode sincronizar: SYNC(A) Quando ocorrer um erro e o topo da pilha for A, ento leia a sentena at que um terminal de SYNC(A) seja encontrado, ento desempilhe A e prossiga anlise. O conjunto SYNC(A) Todo FOLLOW(A) est em SYNC(A) Se a gramtica for hierquica adicione o FIRST(A) em SYNC(A)

33

FACID - Sistemas de Informao

Anlise SintticaFOLLOW(E) = {$,)} FOLLOW(E) = FOLLOW(E) = {$,)} FOLLOW(T) = FOLLOW(T) = {+,),$} FOLLOW(F) = {+,*,),$}

E E T T F

id ETE TFT Fid

+ E+TE sinc T sinc

*

( ETE TFT

) sinc E sinc T sinc

$ sinc E sinc T sinc

T*FT sinc

F(E)

34

FACID - Sistemas de Informao

17

Anlise Sintticaid E E T T F Fid TFT ETE E+TE sinc T sinc T*FT sinc + * ( ETE TFT F(E) ) sinc E sinc T sinc $ sinc E sinc T sinc

)id*+id$

)id* +* id F T T E E $35

pop * pop id F pop T pop E

Observaes1. Passa ) (skip) 2. Erro! M[F,+]=sinc (pop F)

FACID - Sistemas de Informao

Bibliografia Aho, A. V., Sethi, R. e Ullman, J. D. Compiladores: Princpios, Tcnicas e Ferramentas. Editora LTC Cap 4

Price, Ana Maria; Toscani, Simo Sirineo. Implementao de Linguagens de Programao : Compiladores. Ed Sagra Luzzatto Cap 3

36

FACID - Sistemas de Informao

18