bottom1

Bottom-up Parsing

Objetivo® Redução da cadeia ao símbolo inicial da Gramática

Passo: reduzir uma sub-cadeia a um não-terminal - aquele que a tem como lado direito de uma regra

Þ constróem uma derivação mais à direita (ordem reversa) - dmd

EX1:

S ® aAcBe

A ® Ab/b

B ® d

sent: abbcde

Reduções:

b por A ou d por B?

Ab por A ou b por A?

Derivação mais à direita:

S ® aAcBe ® aAcde ® aAbcde ® abbcde

Handle - (a) lado direito de uma regra, (b) cuja redução representa um passo em direção à construção de uma dmd (no Ex1, passo 2, 'b' não é handle)

Definição: Um handle de uma forma sentencial à direita, g , consiste de:

uma produção A ® b e
uma posição de g onde b pode ser encontrada e substituída por A, para produzir a forma sentencial anterior, numa derivação mais à direita de g .

Isto é, se S ® a Aw ® a b w, então

A ® b , na posição que segue a , é um handle de a b w [w Î V_T*]

OBS: Se G é ambígua, uma forma sentencial pode Ter mais de um handle.

No Ex1:

abbcde tem como handle A ® b - (posição 2)

aAbcde tem como handle A ® Ab - (posição 2)

aAcde tem como handle B ® d - (posição 4)

aAcBe tem como handle S ® aAcBe - (posição 1)

Ex2: E ® E + E |E * E| (E) | id Ambígua

2 handles para E + E * id: id * E + E

IMPLEMENTAÇÃO DO SHIFT-REDUCE

Dois problemas:

Uso de uma Pilha:

EMPILHAR (SHIFT) símbolos da cadeia até detectar o símbolo mais à direita de um handle;
DESEMPILHA o handle (REDUCE) e empilha o lado esquerdo da respectiva regra.

Repetir o ciclo até (a) uma situação de erro ou (b) terminar entrada e pilha = S.

No Ex2:

OBS: dmd Þ handle sempre no topo.

4 operações:

SHIFT: próximo símbolo entrada é empilhado;
REDUCE: símbolo mais à direita de um handle no topo; deve localizar extremidade esquerda do handle e decidir sobre regra.
ACEITAÇÃO: término da cadeia e pilha com S.
ERRO: descobre erro sintático e chama rotina de recuperação.

Como decidir sobre SHIFT ou REDUCE?

Þ 2 Técnicas: Precedência de Operadores e L.R.

- conflito shift/reduce: o que fazer com o símbolo do topo da pilha?

- conflito reduce/reduce: qual regra aplicar?

Þ Gramáticas "não-LR"

Exemplo de conflito shif/reduce:

Cmd ® if Expr then Cmd |

If Expr then Cmd else Cmd |

Outros - Cmd