05 Analise Sintatica.pdf

INF25 – Compiladores

Análise Sintática

2

Etapas da Compilação

Front-End(Análise)

Back-End(Síntese)

Análise Léxica

Análise Sintática

Analise Semântica

Geração de CódigoIntermediário

Geração de CódigoFinal

3

Análise Sintática Alguns autores consideram que a

análise sintática envolve tudo que diz respeito à verificação do formato do código fonte

Inclui a análise léxica como subfase

Visão mais coerente, porém o livro texto que usamos tem outra visão...

4

Análise Sintática Entenderemos análise sintática como sendo

apenas a segunda fase dessa verificação de formato:

“É a fase que analisa os tokens para descobrir a estrutura gramatical do código fonte”

Também chamada “Reconhecimento” (Parsing)

Porém, um nome melhor seria “Análise Gramatical”

Gramáticas Livres de Contexto

6

Gramáticas São usadas para organizar os tokens

em “frases” de sentido lógico

Definem regras de formação recursivas

expressão → CTE_INT| ID| expressão + expressão

7

Gramáticas As gramáticas livres de contexto

possuem quatro elementos:

Símbolos terminais Símbolos não-terminais Símbolo inicial Produções !

8

Gramáticas Elementos das gramáticas livres de

contexto:

Símbolos terminais: Símbolos assumidos como atômicos, indivisíveis Em compiladores, são os tokens

Símbolos não-terminais: Usados para organizar os tokens em “frases” Representam elementos abstratos do programa

9

Gramáticas Elementos das gramáticas livres de

contexto:

Símbolo inicial: Não-terminal a partir do qual são derivadas “cadeias” de

símbolos terminais Geralmente é um não-terminal chamado programa

Produções: São as regras de formação Definem as “frases” de terminais válidas na linguagem

10

Notações Notação formal típica

Símbolo não-terminal: letras maiúscula Símbolo terminal: letras minúsculas, sinais,

etc.

E → T| T + E

T → x| i

11

Notações Notação BNF

Símbolo não-terminal delimitado por “<“ e “>”

<expressao> ::= <termo>| <termo> "+" <expressao>

<termo> ::= "x"| "i"

12

Notações Notações EBNF (existem várias versões)

Não-terminais sem delimitadores BNF + operadores de expressões regulares

expressao = termo {"+" termo}*

termo = "x"| "i"

13

Notações Notações que usaremos

Formal: para mostrar conceitos mais teóricos

BNF e EBNF: para os exemplos práticos

14

Gramáticas A partir do símbolo inicial, podemos

derivar (gerar) as cadeias (palavras) de terminais que são válidas na linguagem

15

Derivação Seja a gramática BNF anterior

Derivar a cadeia “i+i+x”

Esta é uma derivação mais à esquerda

<expressao> <termo> + <expressao> i + <expressao> i + <termo> + <expressao> i + i + <expressao> i + i + <termo> i + i + x

16

Derivação Seja a gramática BNF mostrada antes

Derivação mais à direita da cadeia “i+i+x”

<expressao> <termo> + <expressao> <termo> + <termo> + <expressao> <termo> + <termo> + <termo> <termo> + <termo> + x

<termo> + i + x

i + i + x

17

Derivação O processo de derivação consiste em

substituir cada ocorrência de um não-terminal pelo lado direito (corpo) de alguma de suas produções Derivação mais à esquerda: substituir sempre o

não-terminal mais à esquerda Derivação mais à direita: análogo

A derivação pára quando sobrarem apenas terminais e o resultado é a cadeia

18

Árvore de Derivação

A árvore dos exemplos anterioresexpressao

expressao

i

+

i

+

x

termo

termo expressao

a cadeia gerada pode ser percebida nas folhas, analisando-

as da esquerda para a direita

termo

19

Árvore de Derivação

A mesma árvore reorganizada

expressao

expressao

i + i + x

termo

termo expressao

a seqüência de terminais (cadeia) gerada

termo

20

Árvore de Derivação Mostra de maneira estática as produções

aplicadas Não diferencia se foi uma derivação mais à

esquerda ou mais à direita que gerou a cadeia

Forma Tem o símbolo inicial como raiz Não-terminais formam nós intermediários As folhas são os terminais (tokens) da cadeia

21

Gramáticas Ambíguas Uma gramática é dita ambígua se ela

puder gerar duas árvores de derivação distintas para uma mesma cadeia

Veremos uma gramática equivalente à anterior, porém ambígua...

22

Gramáticas Ambíguas Exemplo

Mostrar duas árvores de derivação para “i+i+x”

<expressao> ::= <expressao> "+" <expressao>| "x"| "i"

23

Gramáticas Ambíguas Gramáticas ambíguas são, em geral,

inadequadas para uso em compiladores Dificultam a construção do analisador

sintático

Em alguns casos, são usadas gramáticas ambíguas junto com restrições adicionais Exemplo: precedência e associatividade

24

Análise Sintática Vimos que gramáticas são formalismos

que geram cadeias

Em compiladores, não vamos gerar uma cadeia, mas já temos a cadeia de terminais (ou seja, de tokens) pronta...

Diante disso, qual seria a função do analisador sintático?

Introdução à Análise Sintática

26

Análise Sintática O objetivo

Descobrir como uma sequência de tokens pode ser gerada pela gramática da linguagem

Em outras palavras Entrada: sequência de tokens Saída: árvore

27

Análise Sintática O módulo de software responsável por

essa etapa pode ser chamado de Analisador sintático ou parser

(reconhecedor)

Existem duas estratégias algorítmicas que podem ser adotadas Bottom-up / ascendente Top-down / descendente

28

Análise Sintática Usaremos a seguinte gramática não-

ambígua para ilustrar, a seguir, as duas estratégias de análise sintática

<expressao> ::= <termo>| <termo> "+" <expressao>

<termo> ::= "x"| "i"

29

Análise Top-down Parte da raiz (símbolo inicial) e tenta criar a

árvore de cima para baixo

Recursivamente testa se a cadeia de tokens (lida da esquerda para a direita) pode ser gerada pelas produções de cada não-terminal

O processo de construção da árvore lembra uma derivação mais à esquerda da cadeia

30

Análise Top-down O parser vai ter que escolher uma produção

adequada para o símbolo inicial <expressao>

expressao

i + i + x

?

31

Análise Top-down Sabe-se que ambas as produções iniciam com

<termo>, variando o restante

i + i + x

expressao

termo ?

?

32

Análise Top-down Ao ler o token “i”, o parser identifica que é

gerado por <termo>, mas falta decidir o resto...

i + i + x

expressao

termo ?

33

Análise Top-down A descoberta do “+” faz o parser decidir a

produção adequada

expressao

expressao

i + i + x

termo

?

34

Análise Top-down Processo similar acontece após a leitura dos

dois tokens seguintes

expressao

expressao

i + i + x

termo

termo expressao

?

35

Análise Top-down Porém, no último token, <expressão> vai ter

apenas <termo> e o parser encerra no EOF (fim de arquivo)

expressao

expressao

i + i + x

termo

termo expressao

termo

EOF

36

Análise Bottom-up Parte das folhas (tokens) e tenta crescer a

árvore até a raiz (símbolo inicial)

Para isso, compara a sequência de símbolos o lado direito (ou corpo) das produções para tentar criar um ramo da árvore

Diz-se que a sequência é “reduzida” ao não-terminal do lado esquerdo da produção

37

Análise Bottom-up Tenta crescer a árvore usando o corpo das

produções, até chegar ao símbolo inicial

expressao

i + i + x

38

Análise Bottom-up O token “i” é reduzido ao não-terminal

<termo>, devido à produção <termo> ::= “i”

expressao

i + i + x

termo

39

Análise Bottom-up O parser lê o token “+”, mas ainda não pode

fazer uma redução

expressao

i + i + x

termo

40

Análise Bottom-up Mais uma redução ao não-terminal <termo>

expressao

i + i + x

termo termo

41

Análise Bottom-up Apenas continua a leitura

expressao

i + i + x

termo termo

42

Análise Bottom-up Nova redução ao não-terminal <termo>

expressao

i + i + x

termo termo termo

43

Análise Bottom-up Como acabaram-se os tokens, o último <termo>

só pode ser gerado diretamente por <expressao>, então reduz

expressao

i + i + x

termo termo

expressao

termo

EOF

44

Análise Bottom-up Agora, a subcadeia “<termo>+<expressao>”

pode ser reduzida para <expressao>

expressao

i + i + x

termo

expressão

termo

expressão

termo

45

Análise Bottom-up Outra redução, usando a mesma produção

expressao

i + i + x

termo

expressao

expressao

termotermo

46

Exercício Realizar a análise bottom-up da

seguinte gramatica para a cadeia “a + a * a”:E -> E + TE -> TT -> T * FT -> FF -> EE -> a

47

Resposta

48

Top-down x Bottom-up A análise sintática top-down é mais fácil de

entender e de implementar, porém a bottom-up é mais poderosa (aplicável em mais linguagens)

Uso principal das duas estratégias Bottom-up: usada pelos melhores geradores

semi-atomáticos de parsers Top-down: melhor técnica para implementar

manualmente

49

Análise Sintática Além de construir a árvore, outras

atribuições importantes do analisador sintático são:

Reportar erros, o que deve ser feito de maneira clara para permitir ao usuário corrigir o problema

Recuperar-se de erros automaticamente (pouco uso em compiladores comerciais)

50

Análise Sintática Na verdade, a análise sintática não precisa

construir a árvore durante o reconhecimento

Só é necessário construir a árvore se a análise sintática for separada das etapas seguintes

Em todo caso, o parser vai funcionar como se estivesse descobrindo a árvore que seriagerada pela gramática para os tokens dados

Conceitos

52

Conceitos Veremos alguns conceitos adicionais ligados à

fase de análise sintática

Árvore sintática

Sintaxe abstrata

Precedência e associatividade

Sintaxe concreta

53

Árvore Sintática É quase igual à árvore de derivação, porém é

organizada de maneira mais “racional”

Cada nó interior é uma construção da linguagem ou um operador

Cada nó filho é uma parte significativa da construção ou um operando São descartados: pontuação, parênteses, etc.

54

Árvore Sintática Gramática para os exemplos a seguir

expressao ::= expressao + expressao| expressao - expressao| expressao * expressao| expressao / expressao| ( expressao )| IDENTIFICADOR| INTEIRO_LITERAL

55

Árvore de Derivação Árvore de derivação de “x*(i+i)”

expressao

expressao

x

*

i

+

i

expressao

expressao expressao

( )expressao

56

Árvore Sintática Árvore sintática de “x*(i+i)”

produto

x

i i

var

soma

var

var

57

Sintaxe Abstrata É comum uma linguagem ser

especificada por meio de uma gramática de sintaxe abstrata Em geral, é ambígua Porém, mais simples de entender

Para resolver as ambiguidades, a especificação precisa definir restrições adicionais

58

Sintaxe Abstrata Um exemplo seria a gramática

mostrada antes

É comum assumir associatividade à esquerda e precedência maior para a multiplicação

expressao ::= expressao + expressao| expressao * expressao| ( expressao )| INTEIRO_LITERAL

59

Associatividade Associatividade diz como será aplicada uma

mesma operação binária quando há vários operandos

Exemplo: como interpretar a + b + c + d + e ?

Se o operador for associativo à esquerda: ((((a + b) + c) + d) + e)

Se o operador for associativo à direita: (a + (b + (c + (d + e))))

60

Precedência Precedência diz qual operação binária será

aplicada primeiro houver operadores diferentes

Exemplo: como interpretar a + b * c + d * e ?

Se o operador * tiver maior precedência: ((a + (b * c)) + (d * e))

Se o operador + tiver maior precedência: (((a + b) * (c + d)) * e)

61

Sintaxe Concreta Por outro lado, a gramática tal como ela

foi usada para implementar o parser é chamada de sintaxe concreta Geralmente não tem ambigüidades Mais fácil de implementar

Específica da implementação Cada compilador (de uma mesma

linguagem) pode criar uma implementação diferente

62

Sintaxe Concreta Exemplo de sintaxe concreta

correspondente à gramática de expressões anteriorexpressao ::= termo + expressao

| termo

termo ::= fator * termo| fator

fator ::= ( expressao )| INTEIRO_LITERAL

63

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)