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 , 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 usando esse algoritmo. Na condição inicial, a pilha contém o delimitador $ e o símbolo sentencial ; a lista com a sentença contém os sete símbolos terminais e o delimitador $:
Pilha | Lista |
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 , pois é o primeiro elemento da lista que contém a sentença. Em consulta à tabela sintática, ele verifica que P1, , é essa produção. Assim, os símbolos e são colocados na pilha, enquanto a sentença permanece inalterada:
Produção | Pilha | Lista |
Da mesma forma, as iterações seguintes do algoritmo levam a
Produção | Pilha | Lista |
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 |
-- |
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 |
Novamente a condição de remoção de símbolos acontece, levando a
Produção | Pilha | Lista |
-- |
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.