Analisador sintático LL

Um analisador sintático LL é um algoritmo de análise sintática para um sub-conjunto de gramáticas livre de contexto. Ele é dito um analisador sintático descendente (top-down) pois tenta deduzir as produções da gramática a partir do nó raíz. Ele lê a entrada de texto da esquerda para a direita, e produz uma derivação mais à esquerda (por isso LL, do termo em inglês left-left, diferente do analisador sintático LR). As gramáticas que podem ser analisadas sintaticamente usando esse tipo de analisador são chamadas gramáticas LL. Outro termo usado é analisador sintático LL(x), no qual $x$ refere-se à quantidade de tokens posteriores ao símbolo atual (ainda não consumidos da entrada) que são usados para tomar decisões na análise. Se tal analisador sintático existe para uma dada gramática, e ele pode analisar sentenças nessa gramática sem o uso de backtracking, então essa gramática é chamada gramática LL(x). Dessas gramáticas com análise posterior, as gramáticas LL(1) são as mais populares, pela necessidade de verificar somente o token posterior para a análise. Linguagens mal desenvolvidas tipicamente possuem gramáticas com um valor alto de $x$, e necessitam de bastante esforço computacional para serem analisadas.

Arquitetura

Caso geral

O analisador sintático trabalha em cadeias de texto de uma determinada gramática formal, e consiste de:

• um buffer de entrada;
• uma pilha na qual são armazenados os símbolos da gramática ainda não analisados;
• uma tabela análise que indica se qual regra gramatical a ser aplicada dados os símbolos no topo da pilha e o próximo token de entrada.

Quando o analisador é iniciado, a pilha já contém dois símbolos:

[ S, $ ]

no qual $ é um terminador especial para indicar o fim da pilha e o fim da entrada de dados, e S é o símbolo de entrada da gramática. O analisador sintático irá tentar reescrever o conteúdo da pilha para o que ele interpreta da entrada de texto. Entretanto, ele somente mantém na pilha o que ainda deve ser reescrito.

Exemplo

A gramática abaixo será usada para o exemplo a seguir. Ela trata expressões matemáticas, no qual são aceitas somas entre uns:

(1) S → F

(2) S → ( S + F )

(3) F → 1

deve-se analisar sintaticamente a seguinte entrada:

( 1 + 1 )

Tabela de análise

	(	)	1	+	$
S	2	-	1	-	-
F	-	-	3	-	-

Procedimento de análise

O analisador sintático primeiro lê o terminal ( da entrada de texto, e o S da pilha. Da tabela é indicado que deve-se aplicar a regra 2, isto é, reescrever S para ( S + F ) na pilha e escrever o número dessa regra na saída de dados. No próximo passo é removido o ( da entrada de dados e da pilha. Agora o analisador verifica o terminal 1 na entrada de texto então aplica a regra 1 e então a regra 3 da gramática, e escreve seus números na saída de dados.

Nos próximos dois passos o analisador sintático lê o 1 e o + da entrada de dados e os compara aos valores da pilha. Como são iguais, eles são removidos da pilha. Nos próximos três passos o F será substituído da pilha por 1, e o número 3 (a regra gramatical) será escrita na saída de dados. Então o 1 e o ) são removidos da pilha e da entrada de dados. Por fim, o analisador termina com $ tanto na pilha quanto na entrada de dados. Nesse caso será retornado que a cadeia de caracteres de entrada foi aceita, e na saída de dados está a lista de regras usadas na análise.

Como pode ser visto no exemplo, o analisador sintático LL realiza três tipos de passos dependendo do conteúdo do topo da pilha, seja não-terminal, terminal ou $:

• Se o topo é não terminal então ele verifica a tabela de análise, com base do valor não terminal e o símbolo na entrada de dados, qual regra da gramática deve ser usada. O número da regra é escrito na saída de dados. Se a tabela de análise indica que não há regra programada, é retornado um erro.
• Se o topo é terminal então ele compara o símbolo na entrada com o símbolo do topo da pilha, e se são iguais ambos são removidos. Se eles não são iguais é retornado um erro de sintaxe.
• Se o topo é $ e na entrada de dados também existe um $ então ele retorna sucesso de análise, senão erro de sintaxe. Parecido com o tratamento para um topo terminal, note que nesse caso o algoritmo é terminado em ambos os casos.

Esses três passos são repetidos até o algoritmo parar, seja com sucesso ou com erro.