Software Básico

Silvio Fernandes2009.1

Universidade Federal Rural do Semi-ÁridoDepartamento de Ciências Exatas e Naturais

Ciência da Computação

Aula 19: Introdução aos compiladores II

1

Análise Sintática

• Durante a análise sintática, as instruções originais escritas pelo programador são reconhecidas como construtores da linguagem segundo a gramática que está sendo utilizada

• As técnicas podem ser: – Bottom-up– Top-down

2

Análise Sintática

• Bottom-up– Partem dos nós finais (instruções que estão sendo

analisadas) e tentam combiná-las em nós cada vez mais altos, até chegar à raiz

• Top-down – partem da regra da gramática específica a meta

da análise e tentam construir a árvore de modo que os nós finais correspondam às instruções que estão sendo analisadas

3

Análise Sintática

• Bottom-up (baixo para cima)– A técnica que estudaremos é chamada de método

de precedência dos operadores– Baseia-se no exame de pares de operadores

consecutivos do programa-fonte, e na tomada de decisões sobre a operação que deve ser realizada em 1º lugar

– Ex: A + B * C - D

4

Análise Sintática

• Bottom-up (baixo para cima)– A multiplicação e a divisão devem ter uma

precedência maior que a soma e a subtração– Desse modo

• + < *• * > -

– Assim• A + B * C – D

< >

– Isso significa que B * C tem que ser calculada antes da outras 2 operações da expressão

5

Análise Sintática

• Bottom-up (baixo para cima)– Em termos de árvore sintática, isso significa que a

operação * aparece em um nível inferior a + ou –– O 1º passo na construção de um parser com

precedência dos operadores é determinar as relações de precedência entre os operadores da gramática

– Nesse contexto, operador significa qualquer símbolo terminal de modo que teremos também relações de precedência envolvendo tokens

6

Análise Sintática

• Bottom-up (baixo para cima)– Matriz de precedência para a gramática exemplo

7

Análise Sintática

• Bottom-up (baixo para cima)– Vemos na matriz que

• PROGRAM = VAR• BEGIN < FOR

– A relação indica que os 2 tokens têm a mesma precedência e devem ser reconhecidos pelo parser como parte do mesmo construto da linguagem

8

Análise Sintática

• Bottom-up (baixo para cima)– Observe que não há relação de precedência entre

os mesmos tokens– Significa que os 2 tokens não podem aparecer

juntos numa instrução válida– Se uma combinação destas aparecer na análise

sintática, ela deverá ser considerada um erro de sintaxe

9

Análise Sintática

• Bottom-up (baixo para cima)– A fig. a seguir mostra a aplicação do método de

análise sintática baseado na precedência dos operadores

– Na fig. (a) examinamos a instrução READ da linha 9 do programa exemplo

– A instrução é lida da esquerda para a direita, um token de cada vez, determinando-se a relação de precedência entre cada par de operadores

10

Análise Sintática

• Bottom-up (baixo para cima)

11

Análise Sintática

• Bottom-up (baixo para cima)– O parser identificou a seção da instrução formada

pelo token simples id– Esse identificador é reconhecido como um fator,

<factor>, segundo a Regra 12– Na realidade ele poderia ser também um nome de

programa <prog-name> (Regra 2) ou uma lista de identificadores <id-list> (Regra 6)

12

Análise Sintática

• Bottom-up (baixo para cima)– Numa análise baseada na precedência dos

operadores, não é preciso que o parser se preocupe com o significado dos símbolos não terminais que são reconhecidos;

– Basta que id seja interpretado como um símbolo não terminal <N1>

– Em geral, os parsers baseados na precedência dos operadores usam uma pilha para guardar os tokens lidos mas ainda não analisados, de modo que possam ser reexaminados

13

Análise Sintática

• Top-down– Conhecido como descida recursiva– Têm uma procedure para cada símbolo não

terminal da gramática– Quando uma procedure é chamada, ela tenta

encontrar uma substring da entrada que se inicie pelo token atual e que possa ser interpretado como o símbolo não terminal ao qual a procedure está associada

14

Análise Sintática

• Top-down– Nesse processo, ela pode chamar outras

procedures ou até, chamar a si mesma recursivamente na procura de outros símbolos não terminais

– Quando uma procedure encontra o símbolo não terminal que está procurando, ela informa à rotina anterior que a pesquisa foi bem-sucedida e faz avançar o ponteiro de token para além da substring que acabou de ser reconhecida

15

Análise Sintática

• Top-down– Se a procedure não conseguir encontrar uma

substring que possa ser interpretada como o símbolo não terminal que estava procurando, ela informa que a pesquisa foi malsucedida ou chamará uma rotina de diagnóstico e recuperação

16

Análise Sintática

• Top-down– Quando a gramática oferece diversas

possibilidades para um símbolo não terminal, a procedure precisa decidir qual delas será examinada

– A decisão pode ser tomada com base no exame do próximo token

– Ex: na procedure <stmt> se o próximo token for READ, ela chamará a proc. <read>; se for id, ela chamará <assign>

17

Análise Sintática

• Top-down– Se tentássemos escrever um conjunto completo de

procedures para a gramática apresentada, descobriríamos um problema

– A <id-list> (regra 6) não conseguiria decidir entre suas 2 alternativas pois tanto id quanto <id-list> podem começar por id

– Ela pode levar a uma recursividade indefinada– O motivo está em que uma das alternativas de <id-

list> se inicia por <id-list>18

Análise Sintática

• Top-down– Os analisadores sintáticos top-down não podem

ser utilizados com uma gramática que contenha este tipo de recursão imediata à esquerda

– O mesmo problema aconteceria com relação às regras 3, 7, 10 e 11

– A figura a seguir mostra a gramática sem recursão à esquerda

19

Análise Sintática

20

Análise Sintática

• Top-down– A regra 6a <id-list> ::= id {, id}– É uma extensão comum da BNF, define <id-list> como

sendo composta por um id seguido de zero ou mais ocorrências de “, id”

– Nessa definição é procurado um id, e continua lendo a entrada enquanto os 2 tokens forem uma vírgula e um id

– Assim se elimina o problema da recursão à esquerda e também a dificuldade de decisão entre as alternativas de <id-list>

21

Análise Sintática

• Top-down– Modificações semelhantes foram feitas nas regras

3a, 7a, 10a, 11a – Repare que a gramática continua sendo recursiva– Isto significa que as chamada recursivas entre as

procedures do parser continuam sendo possíveis– Entretanto, a recursão direta à esquerda

desapareceu

22

Análise Sintática• Top-down

– Na figura a seguir temos a representação gráfica do método de descida recursiva para a instrução que está sendo analisada

– Na parte (i), a procedure READ foi chamada e examinou os tokens READ e (

– Na parte (ii), READ chamou IDLIST, que examinou o token id

– Na parte (iii), IDLIST voltou a READ com a indicação que foi bem-sucedida; em seguida, READ examinou o token )

– Com isso, termina a análise da instrução

23

Análise Sintática

24

Análise Sintática

• Top-down– O exemplo visto utiliza apenas instruções isoladas– Entretanto, a mesma técnica poderia ser aplicada

a programas completos– A análise sintática consistiria apenas na chamada

da procedure referente a <prog>– As chamadas feitas por <prog> criariam a árvore

sintática do programa

25

Análise Sintática

• Nenhuma característica inerente às linguagens de programação nos obriga a utilizar uma ou outra técnica de análise sintática

• Usamos um método bottom-up e um top-down para analisar o mesmo programa, usando praticamente a mesma gramática

• Seria possível, inclusive, combinar as 2 técnicas

26

Referências

• Leland L Beck. “Desenvolvimento de software básico”. 2ª ed. Rio de Janeiro: Campus, 1993. 525p.

27