Construção da tabela sintática

A tabela sintática é a estrutura de apoio ao reconhecimento de sentenças pela técnica de construção descendente que tem como chave um par de símbolos. O primeiro componente da chave é um símbolo não-terminal, que corresponde ao símbolo que estará sendo analisado pelo algoritmo de reconhecimento da sentença. O segundo componente da chave é um símbolo da sentença, ou seja, um símbolo terminal ou o delimitador de fim de seqüência $. O valor associado a esse par de símbolos é a produção da gramática a ser aplicada para prosseguir com o reconhecimento da sentença.

Para construir a tabela sintática para uma gramática qualquer $G$, deve-se analisar cada uma das produções $A \rightarrow \alpha$ de $G$. Inicialmente, deve-se obter o conjunto de símbolos terminais que podem iniciar uma cadeia a partir de $\alpha$. Se $\alpha$ for um símbolo terminal, então esse conjunto é composto apenas por esse próprio símbolo. Caso contrário, as possíveis expansões de $\alpha$ devem ser analisadas até que os símbolos terminais ou a string vazia sejam alcançados.

Caso símbolos terminais sejam alcançados, a tabela sintática recebe a entrada com o valor $A \rightarrow \alpha$ para cada chave $A, t$ onde $t$ é cada um dos símbolos terminais que podem ser alcançados desde $\alpha$. Caso a string vazia seja um dos resultados possíveis para a expansão de $\alpha$, é preciso analisar também as possíveis expansões dos símbolos à direita do símbolo corrente na produção.

Dois procedimentos auxiliares são definidos para a construção dessa tabela. O primeiro, STF, computa os símbolos terminais associados ao início das expansões de cada um dos símbolos $X$ da gramática. Esse procedimento é descrito no Algoritmo 3.4.

O cômputo de STF pode também ser aplicado a uma cadeia de símbolos, sendo que neste caso o valor resultante é o primeiro cômputo de STF aplicado a cada símbolo da seqüência tal que o resultado não tenha sido $\varepsilon$. Caso o cômputo de STF para todos os símbolos da cadeia resulte em $\varepsilon$, este também será o resultado final.

O outro procedimento auxiliar deve computar, para cada símbolo não-terminal da gramática $G$, o conjunto de símbolos terminais que podem estar imediatamente à direita do símbolo especificado em alguma forma sentencial. Essa informação é mantida em uma lista $seguinte(\alpha)$, onde $\alpha$ é o símbolo de interesse. Para construir essas listas, as seguintes regras devem ser aplicados até que se esgotem as possibilidades de acrescentar algo às listas:

Regra 1:

O símbolo sentencial da gramática pode ter como próximo símbolo o delimitador de fim de sentença; insira o símbolo $ na lista $seguinte(\Sigma(G))$.

Regra 2:

Se existir uma produção em $G$ da forma $A \rightarrow \alpha B \beta$, então todos os símbolos terminais que podem iniciar a expansão de $\beta$ podem aparecer após $B$; insira em $seguinte(B)$ o conteúdo de STF($\beta$) sem incluir $\varepsilon$, se estiver presente.

Regra 3:

Se existir uma produção em $G$ da forma $A \rightarrow \alpha B$, então $B$ termina a expansão de $A$. O mesmo pode ocorrer para uma produção da forma $A \rightarrow \alpha B \beta$ onde a expansão de $\beta$ pode levar à string vazia $\varepsilon$. Em qualquer um desses casos, tudo que está em $seguinte(A)$ deve ser incluído em $seguinte(B)$.

Com esses procedimentos, a construção da tabela sintática para uma gramática $G$ procede como se segue. Para cada produção $A \rightarrow \chi$ em $G$:

1. Compute STF$(G,\chi)$. Para cada símbolo $x$ dessa lista, acrescente a produção $A \rightarrow \chi$ como o valor da tabela para o par de chaves $[A, x]$.

2. Caso STF$(G,\chi)$ contenha $\varepsilon$, acrescente a produção $A \rightarrow \chi$ à tabela para o par de chaves $[A,y]$ para cada $y$ em $seguinte(A)$.

Como exemplo, considere a construção do analisador sintático preditivo para a gramática da Figura 3.7. Como essa gramática é recursiva à esquerda, o primeiro passo nessa construção é construir a gramática equivalente sem esse tipo de recursão. O resultado da aplicação da técnica para eliminar a recursão à esquerda resulta na seguinte gramática:

$$E \rightarrow T E'$$

$$E' \rightarrow + T E'$$

$$E' \rightarrow \varepsilon$$

$$T \rightarrow F T'$$

$$T' \rightarrow \times F T'$$

$$T' \rightarrow \varepsilon$$

$$F \rightarrow (E)$$

$$F \rightarrow id$$

Para esta gramática, o cômputo de STF() para cada um dos símbolos não-terminais resulta em:

$$\textsc{stf}(E) = \textsc{stf}(T) = \textsc{stf}(F) = ( , id$$

$$\textsc{stf}(E') = +, \varepsilon$$

$$\textsc{stf}(T') = \$ , \varepsilon$$

Como STF() para um símbolo terminal é o próprio símbolo, esses valores não são aqui apresentados.

A aplicação das regras para a construção das listas $seguinte()$ resulta, para cada símbolo não-terminal:

$$seguinte(E) = seguinte(E') = \$, )$$

$$seguinte(T) = seguinte(T') = +, \$, )$$

$$seguinte(F) = \times, +, \$, )$$

A construção da tabela sintática para essa gramática analisa cada uma das suas produções:

P1.

$E \rightarrow T \; E'$
Para essa produção, $\textsc{stf}(T E') = \textsc{stf}(T)$, que resulta na lista com os símbolos $($ e $id$. Portanto, na tabela sintática as entradas $[E,(]$ e $[E,id]$ farão referência à produção P1.

P2.

$E'\rightarrow + \; T \; E'$
O cômputo de $\textsc{stf}(+ T E')$ resulta em $+$, ou seja, haverá uma referência para P2 na entrada $[E',+]$ da tabela sintática.

P3.

$E' \rightarrow \varepsilon$
$\textsc{stf}(\varepsilon) = \varepsilon$; portanto, a segunda regra para a construção da tabela deve ser aplicada. Como $seguinte(E') = \$ , )$, as entradas correspondentes à $[E',\$]$ e $[E', )]$ farão referência à produção P3.

P4.

$T \rightarrow F \; T'$
Como $\textsc{stf}(F T') = \textsc{stf}(F) = (, id$, as entradas para $[T , (]$ e $[T , id]$ farão referência à P4.

P5.

$T'\rightarrow \times \; F \; T'$
Neste caso, $\textsc{stf}( \times F T') = \times$. Portanto, a entrada $[ T' , \times ]$ terá a referência para P5.

P6.

$T'\rightarrow \varepsilon$
Novamente a segunda regra deve ser aplicada. Como $seguinte(T') = +, \$, )$, as entradas com referência à P6 na tabela serão $[T', +]$, $[T', \$]$ e $[T', )]$.

P7.

$F \rightarrow ( \; E \; )$
Apenas a entrada $[F , (]$ fará referência a esta produção, pois $\textsc{stf}((E)) = ($.

P8.

$F \rightarrow id$
Apenas a entrada $[F , id]$ fará referência a esta produção, pois $\textsc{stf}(id) = id$.

A Tabela 3.1 apresenta esses resultados na forma de um arranjo bidimensional, resumindo os resultados encontrados. Nessa tabela, a primeira coluna contém os símbolos não-terminais da gramática, que corresponderão aos símbolos que estarão no topo da pilha do analisador sintático. A primeira linha contém os símbolos que podem ser encontrados na sentença, ou seja, os símbolos terminais da gramática e o símbolo indicador de fim de sentença.

Tabela: Tabela sintática para o analisador preditivo.

	$+$	$\times$	$($	$)$	$id$	$
$E$			P1		P1
$E'$	P2			P3		P3
$T$			P4		P4
$T'$	P6	P5		P6		P6
$F$			P7		P8

Para algumas gramáticas, pode ser que a tabela sintática apresente mais que uma produção por chave, o que reduz a aplicabilidade desse tipo de analisador -- seria necessário manter um registro do estado do analisador em pontos de múltipla escolha para eventualmente retornar a esse estado e tentar a outra alternativa, em caso de insucesso na escolha anterior. Gramáticas ambíguas e gramáticas recursivas à esquerda são exemplos de gramáticas que produziriam tabelas sintáticas com múltiplas produções para uma chave de par de símbolos.

Gramáticas com tabelas sintáticas sem múltiplas definições são denominadas gramáticas LL(1), indicando que a varredura da sentença ocorre da esquerda para a direita (Left-to-right) e que é utilizada a derivação canônica mais à esquerda (Leftmost derivation). O número entre parênteses indica quantos símbolos da sentença precisam ser analisados (lookahead) para a tomada de decisão no processo de reconhecimento.

Uma gramática com duas produções $A \rightarrow \alpha$ e $A \rightarrow \beta$ é LL(1) se apresentar as seguintes propriedades:

1. $\alpha$ e $\beta$ não podem derivar ao mesmo tempo seqüências que tenham início pelo mesmo símbolo terminal;
2. Apenas um dos dois, $\alpha$ ou $\beta$, podem derivar $\varepsilon$; e
3. Se uma das produções deriva $\varepsilon$, a outra não pode derivar qualquer seqüência de símbolos que tenha início com um símbolo presente em $seguinte(A)$.