Ciências da computação dia 228

Dpbm
2 min readMay 12, 2024

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 |

--

--

Dpbm

I'm just a guy engaged with computer science and technology in general.