Algoritmo de reconhecimento de sentença

O Algoritmo 3.5 descreve o analisador sintático preditivo não-recursivo que reconhece sentenças para a gramática especificada. Durante o processamento, o programa utiliza uma estrutura de pilha para acomodar os símbolos sob análise.

O programa utiliza dois procedimentos auxiliares. O primeiro, SELECT, recebe como argumentos a descrição da gramática, um símbolo não-terminal (que está sob análise para expansão) e o próximo símbolo da sentença, retornando uma lista com os símbolos do lado direito da produção que deve ser aplicada para expandir o símbolo analisado, ou o valor nulo no caso de erro. Internamente, esse procedimento faz uso da informação contida na tabela sintática.

O outro procedimento auxiliar é TERMINAL, que recebe como argumentos a descrição da gramática e um de seus símbolos, retornando verdadeiro se este for um símbolo terminal ou falso, se for não-terminal.

A seqüência de produções usadas para reconhecer a sentença é registrada em uma lista $\ell$, que é retornada ao final do algoritmo. Um valor de retorno nulo indica que a sentença não foi reconhecida para a gramática indicada.

Considere o reconhecimento da sentença $(id+id)\times id$ usando esse algoritmo. Na condição inicial, a pilha contém o delimitador $ e o símbolo sentencial $E$; a lista com a sentença contém os sete símbolos terminais e o delimitador $:

Pilha	Lista
$\$ \; E$	$( \; id \; + \; id \; ) \; \times \; id \; \$$

O analisador, verificando que o topo da pilha (na representação, o símbolo mais à direita) é um símbolo não-terminal, busca uma produção apropriada para a entrada $[E,(]$, pois $($ é o primeiro elemento da lista que contém a sentença. Em consulta à tabela sintática, ele verifica que P1, $E \rightarrow T E'$, é essa produção. Assim, os símbolos $E'$ e $T$ são colocados na pilha, enquanto a sentença permanece inalterada:

Produção	Pilha	Lista
$E \rightarrow T E'$	$\$ \; E' \; T$	$( \; id \; + \; id \; ) \; \times \; id \; \$$

Da mesma forma, as iterações seguintes do algoritmo levam a

Produção	Pilha	Lista
$T \rightarrow F T'$	$\$ \; E' \; T'\; F$	$( \; id \; + \; id \; ) \; \times \; id \; \$$
$F \rightarrow ( \; E \; )$	$\$ \; E' \; T'\; ) \; E \; ($	$( \; id \; + \; id \; ) \; \times \; id \; \$$

Na iteração seguinte, o programa encontra no topo da pilha um símbolo terminal. Como esse símbolo é idêntico ao primeiro símbolo da sentença, essa não é uma condição de erro; os dois símbolos são simplesmente retirados de suas respectivas estruturas:

Produção	Pilha	Lista
--	$\$ \; E' \; T'\; ) \; E$	$id \; + \; id \; ) \; \times \; id \; \$$

Para as iterações seguintes, o topo da pilha contém símbolos não terminais e a expansão continua com a utilização das produções P1, P4 e P8:

Produção	Pilha	Lista
$E \rightarrow T E'$	$\$ \; E' \; T'\; ) \; E'\; T$	$id \; + \; id \; ) \; \times \; id \; \$$
$T \rightarrow F T'$	$\$ \; E' \; T'\; ) \; E'\; T'\; F$	$id \; + \; id \; ) \; \times \; id \; \$$
$F \rightarrow id$	$\$ \; E' \; T'\; ) \; E'\; T'\; id$	$id \; + \; id \; ) \; \times \; id \; \$$

Novamente a condição de remoção de símbolos acontece, levando a

Produção	Pilha	Lista
--	$\$ \; E' \; T'\; ) \; E'\; T'$	$+ \; id \; ) \; \times \; id \; \$$

O resultado das iterações seguintes é apresentado na Tabela 3.2, até a condição final de aceitação quando resta apenas o símbolo delimitador no topo da pilha e na sentença.

Tabela: Final da seqüência de reconhecimento da sentença.

Produção	Pilha	Lista
$T'\rightarrow \varepsilon$	$\$ \; E' \; T'\; ) \; E'$	$+ \; id \; ) \; \times \; id \; \$$
$E'\rightarrow + \; T \; E'$	$\$ \; E' \; T'\; ) \; E' \; T \; +$	$+ \; id \; ) \; \times \; id \; \$$
--	$\$ \; E' \; T'\; ) \; E'\; T$	$id \; ) \; \times \; id \; \$$
$T \rightarrow F \; T'$	$\$ \; E' \; T'\; ) \; E'\; T'\; F$	$id \; ) \; \times \; id \; \$$
$F \rightarrow id$	$\$ \; E' \; T'\; ) \; E'\; T'\; id$	$id \; ) \; \times \; id \; \$$
--	$\$ \; E' \; T'\; ) \; E'\; T'$	$) \; \times \; id \; \$$
$T'\rightarrow \varepsilon$	$\$ \; E' \; T'\; ) \; E'$	$) \; \times \; id \; \$$
$E' \rightarrow \varepsilon$	$\$ \; E' \; T'\; )$	$) \; \times \; id \; \$$
--	$\$ \; E' \; T'$	$\times \; id \; \$$
$T'\rightarrow \times \; F \; T'$	$\$ \; E' \; T' \; F \; \times$	$\times \; id \; \$$
--	$\$ \; E' \; T'\; F$	$id \; \$$
$F \rightarrow id$	$\$ \; E' \; T' \; id$	$id \; \$$
--	$\$ \; E' \; T'$	$\$$
$T'\rightarrow \varepsilon$	$\$ \; E'$	$\$$
$E' \rightarrow \varepsilon$	$\$$	$\$$