Construção da tabela SR

A base para a operação de reconhecimento neste tipo de analisador é a Tabela de Deslocamento e Redução ou Tabela SR (shift-reduce), as duas ações básicas desempenhadas pelo analisador durante a análise de uma sentença. Essa tabela determina, a partir do último símbolo resultante das ações efetuadas sobre os símbolos já lidos (que pode ser tanto um símbolo terminal como um não-terminal) e do próximo símbolo terminal presente na sentença, se o próximo passo da análise é ler o próximo símbolo, reduzir os símbolos já lidos ou se não há ação a ser tomada.

Para construir essa tabela, as produções da gramática são analisadas para obter as relações de precedência simples entre os símbolos gramaticais, acrescidos do delimitador de sentenças $. Para dois símbolos $X$ e $Y$, as relações de precedência definidas são $X \preceq Y$ ($X$ confere precedência a $Y$) e $X \succ Y$ ($X$ tem precedência sobre $Y$).

Para obter as relações ``confere precedência'' entre os símbolos de uma gramática $G$, as seguintes regras são aplicadas:

Regra 1:

$\$ \preceq \Sigma(G)$, ou seja, o símbolo delimitador de sentença confere precedência ao símbolo sentencial da gramática.

Regra 2:

$X \preceq Y$ se existe alguma produção de $G$ na forma $\alpha \rightarrow \beta X Y \mu$, ou seja, onde $X$ aparece à esquerda de $Y$ no lado direito da produção.

Regra 3:

$X \preceq Y$ se $X \preceq \alpha$, onde $\alpha$ é um símbolo não-terminal, e existe alguma produção para $\alpha$ em $G$ onde $Y$ é o primeiro símbolo do lado direito, $\alpha \rightarrow Y \mu$.

As relações ``tem precedência sobre'' entre os símbolos de $G$ são obtidas pela aplicação das seguintes regras:

Regra 1:

$\Sigma(G) \succ \$, ou seja, o símbolo sentencial da gramática tem precedência sobre o delimitador de sentença.

Regra 2:

$X \succ Y$ se, para algum símbolo não-terminal $\alpha$, $\alpha \preceq Y$ e existe uma produção para $\alpha$ em $G$ cujo último símbolo é $X$, $\alpha \rightarrow \beta X$.

Regra 3:

$X \succ Y$ se, para algum símbolo não-terminal $\alpha$, $\alpha \succ Y$ e existe uma produção para $\alpha$ em $G$ cujo último símbolo é $X$, $\alpha \rightarrow \beta X$.

Regra 4:

$X \succ Y$ se, para algum símbolo não-terminal $\alpha$, $X \succ \alpha$ e existe uma produção para $\alpha$ em $G$ cujo primeiro símbolo é $Y$, $\alpha \rightarrow Y \mu$.

Deve-se observar que $X \preceq Y$ não implica que $Y \succ X$. Também pode ser verdade para alguma gramática que $X \preceq Y$ ao mesmo tempo que $Y \preceq X$ ou $X \succ Y$. Assim, não se deve confundir as propriedades dessas relações, apesar da semelhança de notação, com aquelas das bem conhecidas relações de ordem ``menor ou igual'' e ``maior''.

Uma vez determinado o conjunto completo das relações de precedência simples, é possível construir diretamente a tabela de deslocamento e redução. Nessa tabela, a chave é composta por dois símbolos $[X,a]$ da gramática estendida com o delimitador de sentença. O primeiro estará associado ao estado corrente da análise da sentença, podendo portanto ser um símbolo qualquer. O segundo símbolo da chave é um símbolo terminal, que estará associado ao próximo símbolo da sentença. Se $X \preceq a$, então o valor na tabela para a chave $[X,a]$ conterá a indicação de que a próxima ação deve ser a leitura do próximo símbolo da sentença. Se $X \succ a$, então o valor da chave indicará que a próxima ação do analisador deve ser a redução dos últimos símbolos lidos pela aplicação de uma produção da gramática.

Considere como exemplo a construção da tabela de deslocamento e redução para a gramática da Figura 3.7. Pela Regra 1, obtém-se a primeira relação de precedência,

$$\$ \preceq E$$

A Regra 2 estabelece que há a mesma relação de precedência entre símbolos contíguos no lado direito das produções da gramática. A aplicação dessa regra deriva as relações

$E \preceq +$		$+ \preceq T$		$T \preceq \times$
$\times \preceq F$		$( \; \preceq E$		$E \preceq \; )$

Para a aplicação da Regra 3, é preciso analisar todas as relações, obtidas pela aplicação das Regras 1 e 2 e da própria Regra 3, onde o símbolo do lado direito é um símbolo não-terminal, até que novas relações não possam mais ser estabelecidas. Por exemplo, como $\$ \preceq E \wedge E \rightarrow T$, então $\$ \preceq T$; como esta relação tem do lado direito um símbolo não-terminal, deve-se analisar quais símbolos iniciam o lado direito das produções para $T$, o que leva à obtenção da relação $\$ \preceq F$.

A aplicação da Regra 3 gera as seguintes relações de precedência:

$\$ \preceq E$		$\$ \preceq T$		$+ \preceq T$		$+ \preceq F$
$\times \preceq \; ($		$\times \preceq id$		$( \; \preceq E )$		$( \; \preceq T$
$\$ \preceq F$		$+ \preceq \; ($		$+ \preceq id$		$( \; \preceq F$
$\$ \preceq \; ($		$\$ \preceq id$		$( \; \preceq \; ($		$( \; \preceq id$

Destas relações, três já haviam sido anteriormente derivadas pelas outras regras.

As regras seguintes permitem estabelecer as relações ``tem precedência sobre'', que estarão associadas a reduções durante a análise. A primeira dessas regras, Regra 4, deriva a relação

$$E \succ \$$$

Para a aplicação da Regra 5, é preciso analisar as relações ``confere precedência a'' que tenham símbolos não-terminais do lado esquerdo, que são $E \preceq +$, $T \preceq \times$ e $E \preceq \; )$, e quais símbolos terminam as produções para esses símbolos não-terminais. Essa análise permite derivar as relações

$T \succ +$

$F \succ \times$

$T \succ \; )$

A aplicação da Regra 6 requer a análise das relações ``tem precedência sobre'' derivadas da aplicação das regras 4 e 5 e da própria Regra 6. As relações de interesse são aquelas que têm do lado esquerdo um símbolo não-terminal. A aplicação da regra deriva as relações

$T \succ \$$		$F \succ +$		$) \; \succ \times$		$id \succ \times$
$F \succ \; )$		$F \succ \$$		$) \; \succ +$		$id \; \succ +$
$) \; \succ \; )$		$id \succ \; )$		$) \; \succ \$$		$id \; \succ \$$

A última regra, Regra 7, deriva novas relações de ``tem precedência sobre'' a partir dessas relações onde há um símbolo não-terminal no lado direito. Particularmente para esse exemplo não há nenhuma relação dessa forma e portanto nenhuma nova relação pode ser derivada.

Concluída a análise das relações de precedência para a gramática, é possível construir a sua tabela de deslocamento e redução (Tabela 3.3) usando as relações $X \preceq Y$ ou $X \succ Y$ onde $Y$ é um símbolo terminal. Nessa tabela, a entrada ``S'' (shift) indica que a ação deve ser de leitura do próximo símbolo da sentença, enquanto que a entrada ``R'' determina a redução dos símbolos já lidos. Para as entradas em branco não há uma ação que possa ser tomada que leve ao reconhecimento da sentença.

Tabela: Tabela de deslocamento e redução.

	$id$	$+$	$\times$	$($	$)$	$
$	S			S
$E$		S		S	S	R$^*$
$T$		R	S		R	R
$F$		R	R		R	R
$id$		R	R		R	R
$+$	S			S
$\times$	S			S
$($	S			S
$)$		R	R		R	R

Observe na Tabela 3.3 que a entrada para $[E,\$]$ recebeu uma marcação especial, pois essa situação -- os símbolos já analisados resultaram no símbolo sentencial e a sentença chegou ao fim -- determina a condição de reconhecimento da sentença.

Para algumas gramáticas, a construção da tabela de deslocamento e redução pode levar a situações onde mais de uma ação poderia ser tomada para um dado estado e próximo símbolo da sentença. Essa tabela não terá entrada duplicadas se a gramática for uma gramática de operadores, para a qual nenhuma produção tem do lado direito dois símbolos não-terminais adjacentes, e se nenhuma produção tiver $\varepsilon$ do lado direito.