Exemplo de Analisador Sintático D dt R i - WWW2
Transcrição
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