ANTLR - Geração de um parser segundo o algoritmo Top-Down


Written on October 10, 2008 – 1:35 am | by André Gomes

Numa das minhas disciplinas de mestrado, na unidade curricular de Engenharia de Linguagens, o professor colocou-nos uma questão muito simples mas que resolvi pôr aqui com objectivo meramente académico.

A questão foi a seguinte:

“Porque se constata no ANTLRWorks que o parser gerado é Top-Down?”

O ANTLRWorks é um reconhecer de gramáticas Top-Down pois este efectua o parsing de uma frase construindo a árvore de derivação partindo da raiz e terminando nas folhas, criando os nodos da árvore através de uma travessia descendente da esquerda para a direita.

Vejamos a seguinte gramática que pretende representar uma lista de números:

grammar Lista;

lista 	:	'[' nums ']'
	;

nums    :    INT
        |    INT ',' nums
        ;

INT	:	('0'..'9')+

Agora, vamos observar como é que o ANTLR gera a árvore de derivação para a lista exemplo : [ 8, 7, 6 ]

O ANTLR começa por criar a raiz da árvore com lista, à esquerda fica logo o símbolo terminal “[" e em seguida "nums" (isto porque fez match na primeira produção - lista).

Depois disto "nums" fará com que seja a segunda produção a ser analisada e o que sucede é que se criam dois filhos neste nodo, um para o número 8 e outro para a vírgula. Pode ser observado na figura seguinte.



Em seguida, o mesmo se sucede com o número 7 e a vírgula respectiva. Como a segunda produção é recursiva, o ANTLR continua a "apanhar" os números e as vírgulas que vão aparecendo a seguir ao 8.

No caso do último algarismo, o número 6, como já não possui vírgula depois deste e apenas se encontra o símbolo terminal "]” o ANTLR detecta isto e acrescenta mais um filho à raiz lista.

A árvore final gerada é a seguinte:



Como pôde ser observado, a árvore foi construída de cima para baixo e da esquerda para a direita, tal como um analisador Top-Down deve fazer.



Veja também:

Tags: , , ,

Post a Comment