Exemplo de Analisador Sintático D dt R i - WWW2

10/16/2008
Analisador Sintático Descendente Recursivo
• Este exemplo descreve um analisador sintático descendente recursivo para a linguagem TINY, definida por Kenneth C. Lounden em “Compiladores: Princípios e Práticas”.
• Este analisador constrói uma árvore sintática e imprime a representação da árvore em um arquivo de listagem.
• O analisador utiliza uma gramática escrita na forma EBNF.
Compiladores –
Exemplo de Analisador Sintático D
Descendente Recursivo
d t R
i
Fabiano Baldo
Fabiano Baldo ‐ UDESC
Gramática TINY em EBNF
2
Analisador TINY
• Segue a estrutura de análise descendente recursiva.
• É composto por dois arquivos de código: parse.h e parse.c
• Parse.h:
– É composto por uma única declaração: – Que define a rotina principal de análise sintática parse, a qual retorna um ponteiro para a árvore sintática construída pelo analisador.
Fabiano Baldo ‐ UDESC
3
Estrutura da Árvore Sintática TINY
4
Estrutura da Árvore Sintática TINY
• Utiliza uma representação de árvore abstrata para minimizar a alocação de memória.
• Cada nó tem informações tais como:
• Cada tipo de nó tem um número definido de filhos:
– Declaração if tem 3 filhos: teste, parte‐then e parte‐else
(sendo que a parte else é opcional);
– Declaração repeat tem 2 filhos: corpo e teste;
– Declaração de atribuição tem 1 filho: expressão;
– Declaração write tem 1 filho: expressão;
– Expressão tem 2 dois filhos: operando à esquerda e operando à direita;
– O que ele representa (tipo de declaração, tipo do token, valor do token, etc.);
– Quais são seus filhos;
– Qual é o seu irmão (formando uma lista encadeada);
Fabiano Baldo ‐ UDESC
Fabiano Baldo ‐ UDESC
5
Fabiano Baldo ‐ UDESC
6
1
10/16/2008
Estrutura da Árvore Sintática TINY
Estrutura da Árvore Sintática TINY
• Ex: Árvore abstrata
• Ex: Código fonte
read
(x)
if
op
( )
(<)
const
(0)
assign
(fact)
id
(x)
repeat
const
(1)
id
(fact)
Fabiano Baldo ‐ UDESC
7
write
assign
(fact)
assign
(x)
op
(*)
op
(‐)
id
(x)
id
(x)
op
(=)
id
(x)
id
(fact)
const
(0)
const
(1)
Fabiano Baldo ‐ UDESC
Espec. do Nós da Árvore Sintática
8
Analisador TINY
• Parse.c:
– É composto pelos procedimentos recursivos que reconhecem os não‐terminais especificados na linguagem
• Ex: decl_seqüência, declaração
– Nem todos os não‐terminais precisam ter um procedimento de reconhecimento especificado.
• Ex: soma, mult
Fabiano Baldo ‐ UDESC
9
Tipos de Tokens da linguagem TINY
• A linguagem TINY reconhece o seguinte conjunto de Tokens:
Fabiano Baldo ‐ UDESC
11
Fabiano Baldo ‐ UDESC
10
Método Principal • O método parse() ativa o reconhecimento de decl_seqüência.
Fabiano Baldo ‐ UDESC
12
2
10/16/2008
Reconhecimento decl_seqüência
Procedimento Match
• Ativa o reconhecimento de declaração
Fabiano Baldo ‐ UDESC
• Faz o casamento entre o token esperado e o lido da entrada através do método getToken() ou gera um erro.
13
Procedimento SyntaxError
• Reconhece os 5 tipos diferentes de declaração.
15
Reconhecimento do if_decl
Fabiano Baldo ‐ UDESC
14
Reconhecimento Declaração
• Imprime uma mensagem de erro no arquivo de listagem.
Fabiano Baldo ‐ UDESC
Fabiano Baldo ‐ UDESC
Fabiano Baldo ‐ UDESC
16
Reconhecimento do atrib_decl
17
Fabiano Baldo ‐ UDESC
18
3
10/16/2008
Procedimentos Auxiliares
Procedimento newStmtNode
• Esta forma de análise sintática recursiva utiliza 3 procedimentos auxiliares (presentes no arq. util.c):
– newStmtNode: Recebe um parâmetro indicado o tipo de declaração e aloca um novo nó de declaração do tipo correspondente, retornando um ponteiro para este nó.
d t
t
d
t i
t ó
– newExpNode: Recebe um parâmetro indicando o tipo de expressão e aloca um novo nó de expressão do tipo correspondente, retornando um ponteiro para este nó.
– copyString: Recebe uma cadeia de caracteres como parâmetro, aloca espaço suficiente e copia a cadeia, retornando um ponteiro para a cópia.
Fabiano Baldo ‐ UDESC
19
Fabiano Baldo ‐ UDESC
Procedimento newExpNode
20
Procedimento copyString
• Necessário porque C não aloca espaço automaticamente para o token.
Fabiano Baldo ‐ UDESC
21
Fabiano Baldo ‐ UDESC
Procedimento printTree
Procedimento printTree
• Serve para visualizar o resultado de uma análise sintática.
• Imprime uma visão linear da árvore sintática abstrata.
Fabiano Baldo ‐ UDESC
22
23
• Ex: Fabiano Baldo ‐ UDESC
24
4