Análise Sintática Ascendente

Ilustração por um exemplo

Considere a gramática

• D -> T L ; T -> i | r L -> v | L , v

que representa uma declaração de variáveis a la C

Como reconhecer a palavra "u = i v , v ;" como pertencente à linguagem definida pela gramática dada ?

Se u pertence à linguagem definida pela gramática, então D => + u.

Gerando uma derivação á direita tem-se:

• D => T L ; => T L , v => T v , v => T v , v ; => i v , v ;

Tente-se agora fazer a derivação no sentido contrário, isto é, indo de u para D.

Considere a gramática

• D -> T L ; T -> i | r L -> v | L , v

e reduza-se a palavra "u = i v , v ;" ao símbolo inicial D.

Colocando ao contrário, tem-se

• D => T L ; => T L , v => T v , v => i v , v

que corresponde à derivação à direita da palavra "u = i v , v ;".

A tabela seguinte mostra como, na prática, se a realiza esta (retro)derivação.

Pilha	Entrada	Próxima ação
	i v , v ; $	deslocamento
i	v , v ; $	redução por T -> i
T	v , v ; $	deslocamento
T v	, v ; $	redução por L -> v
T L	, v ; $	deslocamento
T L ,	v ; $	deslocamento
T L , v	; $	redução por L -> L . v
T L	; $	deslocamento
T L ;	$	redução por D -> T L ;
D	$	deslocamento / aceitação
D $		aceitação

A palavra à entrada foi reduzida ao símbolo inicial pelo que é aceite como pertencendo à linguagem.

A aceitação pode ser antes de consumir o $ ou depois.

Ilustração de um erro sintático

Veja-se a reação deste procedimento a uma entrada errada, por exemplo a palavra i v v ; .

Pilha	Entrada	Próxima ação
	i v v ; $	deslocamento
i	v v ; $	redução por T -> i
T	v v ; $	deslocamento
T v	v ; $	redução por L -> v
T L	v ; $	deslocamento
T L v	; $	rejeição

Rejeita porque Lv não corresponde ao prefixo de uma produção da gramática.

Na realidade, o erro poderia ter sido detetado dois passos antes, aquando da segunda redução, porque

• v corresponde ao símbolo à entrada.

• L é o símbolo que iria aparecer no topo da pilha se se fizess a redução por L -> v.

Considere a gramática

• S -> i c S | i c S e S | a

e aplique-se o procedimento anterior à palavra i c i c a e a.

Pilha	Entrada	Próxima ação
	i c i c a e a $	deslocamento
i	c i c a e a $	deslocamento
i c	i c a e a $	deslocamento
i c i	c a e a $	deslocamento
i c i c	a e a $	deslocamento
i c i c a	e a $	redução por S -> a

Que gramática representa uma estrutura típica em linguagens de programação. Qual ?

Ilustração de conflito entre reduções

Considere a gramática

• S -> A | B A -> c | A a B -> c | B b

e aplique-se o procedimento anterior à palavra c

Pilha	Entrada	Próxima acção
	c $	deslocamento
c	$	conflito:
		redução usando A -> c
		redução usando B -> c

Ilustração de falso conflito

Considere a gramática

• S -> a | < S > | a P | < S > S P -> < S > | < S > S

e aplique-se o procedimento de reconhecimento à palavra "a < a > a"

Pilha	Entrada	Próxima ação
	a < a > a $	deslocamento
a	< a > a $	falso conflito:
		redução usando S -> a
		deslocamento para tentar S -> a P

Deslocamento, porque se se optasse pela redução no topo da pilha ficaria um S e

Optando pelo deslocamento e continuando...

Pilha	Entrada	Próxima ação
	a < a > a $	deslocamento
a	< a > a $	deslocamento, porque
a <	a > a $	deslocamento
a < a	> a $	redução por S -> a
a < S	> a $	deslocamento
a < S >	a $	deslocamento, porque
a < S > a	$	redução por S -> a
a < S > S	$	redução por P -> < S > S
a P	$	reduções por S -> a P
S	$	deslocamento
S $		aceitação

Eliminação de conflito

Pode ser possível alterar uma gramática de modo a eliminar a fonte de conflito.

Considerando que se pretendia optar pelo deslocamento, a gramática da esquerda gera a mesma linguagem que a da direita e está isenta de conflitos

if ... then ... else sem conflitos

Considere a gramática seguinte e processe-se a palavra "i c i c a e a"

• S -> a | i c S | i c S' e S S´-> a | i c S' e S'