Construção de um reconhecedor ascendente
Abordagem
Como determinar de forma sistemática a ação a realizar (deslocamento, redução, aceitação, rejeição) ?
i v v ; $
deslocamento
i
v v ; $
redução por T ->i
T
v v ; $
deslocamento
T v
v ; $
rejeição
A ação a realizar em cada passo do procediemnto de reconhecimento - delocamento, redução, aceitação ou rejeição - depende da configuração em cada momento.
Uma configuração é formada pelo conteúdo da pilha mais apertada da entrada ainda não processada.
A pilha é conhecida - na realidade, é preenchida pelo procedimento de reconhecimento.
Da entrada, em cada momento, apenas se conhece o lookahead.
Quantos símbolos da pilha usar ?
Poder-se-á usar apenas um ?
Se se quiser e puder construir um reconhecedor que apenas use o símbolo no topo, uma pilha onde se guardam os símbolos terminais e não terminains tem pouco interesse.
Mas pode definir-se um alfabeto adequado para a pilha.
Os símbolos a colocar na pilha devem representar estados no processo de deslocamento/redução/aceitação.
Por exemplo, um dado símbolo pode significar que, na produção "D -> T L ;", já se processou algum que corresponde ao "T L", faltando o ";"
Itens de uma gramática
O alfabeto da pilha representa assim o conjunto de possíveis estados nesse processo de reconhecimento.
Cada estado representa um conjunto de itens.
Cada item representa o quanto de uma produção já foi processado e o quanto ainda falta processar.
Usa-se um ponto (•) ao longo dos símbolos de uma produção para o representar.
A produção A -> B1 B2 B3 produz 4 itens:
A -> • B1 B2 B3 A -> B1 • B2 B3 A -> B1 B2 • B3 A -> B1 B2 B3 •
A produção de A -> end produz um único item:
A -> •
Exemplo
Considere a gramática
S -> E E -> a | ( E )
Reconhecer a palavra u = u1 u2 ... un, significa reduzir u$ a u$, então, o estado inicial no processo de reconhecimento pode ser definido por:
O facto de o ponto (•) se encontrar imediatamente à esquerda de um símbolo significa que para se avançar no processo de reconhecimento é preciso obter esse símbolo.
Se o símbolo é terminal, isso corresponde a uma ação de deslocamento.
Se o símbolo é não terminal, é preciso dar-se a redução de uma produção que o produza.
Isso é considerado juntando ao conjunto os itens iniciais das produções cuja cabeça é o símbolo pretendido:
Se aparecerem novos símbolos não terminais imediatamente à direita de um ponto (•), repete-se o processo. Faz-se o fecho (closure).
Evolução de Z0:
O estado Z0 pode evoluir por ocorrência de um E, um a ou um (, que correspondem aos símbolos que aparecem imediatamente à direita do (•).
Z3 tem de ser estendido pela função de fecho, uma vez que o ponto (•) ficou imediatamente à esquerda de um símbolo não terminal (E).
Z2, apenas possui um item terminal (com o ponto (•) à direita), que representa uma situação passível de redução, neste caso pela produção E -> a.
Evolução de Z1:
Apenas evolui por ocorrência de um $
Se o símbolo inicial da gramática não aparecer no corpo de qualquer produção (como acontece aqui), pode-se considerar Z1 como uma situação de aceitação se o lookahead de $.
Evoluação de Z3:
Pode evoluir por ocorrência de um E, um a ou um (
Evolução de Z4
Apenas evolui por ocorrência de )
Z5
Z5 apenas possui um item terminal, que representa uma situação passível de redução pela regra E -> ( E ).
Pode acontecer que um dado elemento (conjunto de itens) possua itens terminais (associados a reduções ) e não terminais.
Pondo tudo junto
Representado na forma de um autómato, tem-se
Neste autómato, os estados representam o alfabeto da pilha.
As transições represenam operações de push.
As transições etiquetadas com símbolos terminais representam adicionalmente ações de deslocamento (shift).
As ações de redução provocam operações de pop, em número igual ao número de elementos do corpo da produção.
As transições etiquetadas com símbolos não terminais ocorrem após as ações de redução.
Tudo isto representa o funcionamento de um autómato de pilha que permite fazer o reconhecimento da linguagem.
Last updated
