Análise Sintática
Ascendente
BottomUp
Bottom Up: (empilha-reduz)
-Constrói a árvore de derivação de baixo para cima, das folhas para raíz;
- Produz uma derivação mais à direita para uma cadeia de entrada;
-Processo de redução de uma string X para o símbolo inicial da gramática;
-Em cada passo da redução, uma substring é associada com o corpo de uma produção
e obtém-se a parte principal dessa produção;
-Decisões chave: quando reduzir e quais produções utilizar;
- Por definição, redução é o inverso da derivação.
Obs: bottom up parsing constrói uma derivação em modo reverso.
Operações lícitas:
– empilha (shift): coloca no topo da pilha o símbolo que está sendo lido e avança o
cabeçote de leitura na string;
– reduz (reduce): substitui o handle no topo da pilha pelo não terminal
correspondente;
– aceita: reconhece que a sentença foi gerada pela gramática;
– erro: ocorrendo erro de sintaxe, chama uma subrotina de atendimento a erros;
Poda do Handle
-Handle é uma subcadeia que “casa” com o corpo de uma produção e cuja redução
representa um passo da derivação mais à direita ao inverso;
-Uma derivação mais à direita em ordem reversa pode ser obtida pela “poda do
handle”
1. Iniciar com uma string de terminais “w”. Se “w” é uma sentença da
gramática dada, então w=yn onde “yn” é a n-ésima forma sentencial mais à direita de
alguma derivação mais à direita desconhecida;
2. Para reconstruir a derivação, localizar handle Bn em “yn” e substituir Bn
pelo lado esquerdo da produção An -> Bn para obter a forma sentencial anterior yn-1;
3. Repetimos esse processo até alcançar o símbolo inicial da gramática. Caso
contrário, uma mensagem de erro deve ser gerada.
Analisadores shift-reduce
- Forma de análise ascendente onde uma pilha contém símbolos da gramática e um buffer de
entrada contém o restante da cadeia a ser reconhecida sintaticamente;
- Usa-se o símbolo “$” para marcar o fim da pilha e o último caracter da entrada;
- Durante o parsing (da esquerda para direita), o analisador desloca (shift) zero ou mais símbolos
de entrada na pilha, até que está pronto para reduzir (reduce) uma string B (no topo da pilha)
para a “cabeça” da produção apropriada;
- O analisador sintático repete esse ciclo até encontrar um erro (nenhuma produção é
encontrada) ou até que a pilha contém o símbolo de início e a entrada está vazia;
Exemplos de algoritmos para o parsing Shift-Reduce (empilha-reduz):
– LR(0)
– SLR(1)
– LR(1)
– LALR(1)
Ações em Parsing Empilha-Reduz
Exemplo 1:
Passo 1: “A” recebe “c”
Passo 2: “B” recebe “ca”
Passo 4: “B” recebe “cbB”
Solução: S  AB
- conflito reduce/reduce
Exemplo 2:
Passo 4:
1: “aABe”
2:
3:
“b” recebe
“Abc”
“d”
recebe
recebe
“B”
“A”“A”
“S”
handle = =seqüência
Redução
substituição
de símbolos
do lado direito
do ladodedireito
uma produção
da produção,
pelotais
nãoque
terminal
suas reduções
correspondente
levam, no
(lado ao
final,
esquerdo)
símbolo inicial da gramática
Conflitos durante execução do analisador shiftreduce:
- Quando o analisador não consegue decidir se deve realizar um shift ou um reduce, temos um
conflito shift/reduce;
- Quando o analisador não consegue determinar qual redução fazer, temos um conflito
reduce/reduce;
Referências:
1. http://www.gpec.ucdb.br/ricrs/Courses/CompilerI/Lectures/Lec06.pdf
2. http://www.inf.ufrgs.br/~nmaillard/pdf/Compiladores08-LR0.pdf
3. http://gersonc.anahy.org/repcomp/Compiladores08-Bottom-up.pdf
4. http://osorio.wait4.org/oldsite/compil/aula-botton-up-parsing.pdf