Linguagens formais — Análise sintática ascendente
Análise sintática ascendente (shift-reduce)
- de baixo para cima (folha para a raiz)
- reduz(reduce) ao invés de derivar
- vai do terminal reduzindo a cadeia para um não terminal (chegando no símbolo não terminal inicial da cadeia, se a entrada for válida)
- gramática LR(K)
- por utilizar gramáticas LR(K), podemos verificar qualquer quantidade de simbolos a frente K, sendo 0 ou 1 os mais comuns e o suficiente para a maioria dos casos
- São eficientes
- podem ser usadas com uma grande variedade de gramáticas
- aceita recursão à esquerda e ambiguidade
- Por aceitar ambiguidade há várias maneiras de reduzir uma unica expressão, mas o resultando sempre deve ser o mesmo
- usado por diversas linguagens
- vai empilhando(shift) os símbolos e a partir da tabela sintática (dos produtos da expansão), o conjunto de símbolos(handle) é convertido para um único não terminal
S -> [L] | a
L -> L;S | S
entrada = [a;a]
| Pilha | Entrada | Ação |
|--------|----------|---------|
| $ | [a;a]$ | shift [ |
| $[ | a;a]$ | shift a |
| $[a | ;a]$ | reduce a to S |
| $[S | ;a]$ | reduce S to L |
| $[L | ;a]$ | shift ; |
| $[L; | a]$ | shift a |
| $[L;a | ]$ | reduce a to S |
| $[L;S | ]$ | reduce L;S to S |
| $[L | ]$ | shift ] |
| $[L] | $ | reduce [L] to S |
| $S | $ | reduce S to L |
| $L | $ | ACCEPT |
