Gramáticas LL(k)

Análise Sintática Descendente Determinista.

• Gramáticas LL(k)
  • Introdução
  • Conteúdo
    • Exemplos de Aplicação do Teorema dos Diretores
      • Geradores de Vazio
      • Primeiros
      • Seguintes
      • Diretores
      • Analisador Sintático
  • Conclusão

Introdução

A Análise Sintática por pesquisa geral não é eficiente, mesmo após a transformação para a FNG porque continua a ser possível encontrarem-se várias produções para expandir um vértice.

Na situação acima o não determinismo resulta as possíveis múltiplas expansões quando se consideram as variáveis em isolamento. Por exemplo, dada a GIC abaixo, o vértice $aS$ tem dois filhos possíveis: $aaS$ e $acA$.

$$\begin{array}{rl}S& \to aS|cA\\ A& \to bA|cB|\lambda \\ B& \to cB|a|\lambda \end{array}$$

Mas uma observação mais cuidadosa da pesquisa, considerando o primeiro símbolo do sufixo que falta derivar mostra uma situação interessante:

Pesquisa Descendente de $acc$ com Avanço
Em cada vértice podam-se os ramos "incompatíveis".

Neste exemplo, olhando para o próximo terminal durante a pesquisa por $acc$ obtém-se uma pesquisa determinista.

Nesta secção exploram-se pesquisas deterministas com o auxílio dos "símbolos seguintes".

Conteúdo

A apresentação intuitiva acima precisa de uma representação mais formal. Por exemplo, a derivação de $acbb$ pode ser obtida pela seguinte tabela:

$$\begin{array}{lrclr}\text{prefixo}& \text{avanc¸oresto}& \text{variaˊvel}& \text{produc¸a˜o}& \text{derivac¸a˜o}\\ \lambda & acbb& S& S\to aS& S\Rightarrow aS\\ a& cbb& S& S\to cA& \Rightarrow acA\\ ac& bb& A& A\to bA& \Rightarrow acbA\\ acb& b& A& A\to bA& \Rightarrow acbbA\\ acbb& \lambda & A& A\to \lambda & \Rightarrow acbb\end{array}$$

Em cada linha:

• Há uma variável ativa, que inicialmente é $S$.
• É escolhida a única produção cujo primeiro símbolo coincide com o símbolo de avanço.
• O avanço é "transferido" para o prefixo processado e a variável ativa é a primeira que ocorre na produção escolhida na linha anterior.

Interessa formalizar esta exploração com vista a definir métodos rigorosos para:

1. Determinar se uma GIC é adequada, ou não, a este processo.
2. Definir algoritmos eficientes baseados na pesquisa com avanço.

Começando pela definição de gramática "adequada" à pesquisa com avanço:

Gramática LL(1). A GIC $G=\left(V,\Sigma ,P,S\right)$ com terminador $\#$ é LL(1) se dadas duas derivações esquerdas $$\begin{array}{r}S\stackrel{\ast }{\Rightarrow }{u}_{1}A{v}_1\Rightarrow u_{1}x{v}_1\stackrel{\ast }{\Rightarrow }{u}_{1}a{w}_1\\ S\stackrel{\ast }{\Rightarrow }{u}_{2}A{v}_2\Rightarrow u_{2}y{v}_2\stackrel{\ast }{\Rightarrow }{u}_{2}a{w}_2\end{array}$$ em que $u_i,w_i\in {\Sigma }^{\ast },a\in \Sigma$ e $A\in V$ então $x=y$.

N.B. "LL" significa "Left-to-right Leftmost derivation". Em português: "derivação esquerda da esquerda-para-a-direita". Note-se que "derivação esquerda" especifica qual é a variável a tratar enquanto que "da esquerda-para-a-direita" indica que a palavra é processada sequencialmente do primeiro símbolo para o último.

N.B. O terminador ocorre exatamente uma vez nas palavras geradas e é sempre o último símbolo. A sua função é garantir que há sempre um símbolo de avanço na palavra analisada. Fica como exercício encontrar um algoritmo que transforma uma GIC qualquer, $A$, noutra, $A^{\prime }$ com terminador $\#$, de forma que $p\in L(A)⟺p\#\in L(A^{\prime })$.

Intuitivamente a definição de GIC LL(1) diz que não há duas produções distintas de $A$ que produzem sufixos terminais que começam pelo mesmo terminal. Ou seja, os resultados finais da aplicação de duas produções de $A$ distintas difere logo no primeiro símbolo.

As gramáticas LL(1) têm algumas propriedades interessantes:

Propriedades das Gramáticas LL(1). Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC:

1. Se $G$ é LL(1) então não é ambígua,
2. Se alguma variável de $G$ for recursiva à esquerda então $L$ não é LL(1).

A generalização de LL(1) para mais do que um símbolo de avanço é representada por $LL(k)$. Este caso é pouco interessante em termos teóricos porque torna a notação mais críptica sem progredir na resolução da análise sintática.

Note-se que uma gramática na FNG quase que é LL(1). O problema está na possibilidade de várias produções começarem pelo mesmo terminal. Para ajudar a ultrapassar esta situação é preciso "arrumar" as produções que começam pelo mesmo símbolo.

Fatorização à Esquerda. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC. Supondo que as produções de $A\in V$ são $$A\to p{u}_1|p{u}_2|\cdots |p{u}_n|v_1|v_2|\cdots |v_m$$

em que $p,u_i,v_j\in {\left(V\cup \Sigma \right)}^{\ast }$ então a GIC $G^{\prime }$ obtida de $G$

1. Acrescentando uma nova variável, $Z$.
2. Substituindo as produções de $A$ por $A\to pZ|v_1|v_2|\cdots |v_m$.
3. Acrescentado as produções $Z\to u_1|u_2|\cdots |u_n$.

é equivalente a $G$.

Com a fatorização as várias produções de $A$ que começam pelo mesmo prefixo, $A\to p{u}_1|p{u}_2|\cdots |p{u}_n$ ficam agrupadas numa só produção, $A\to pZ$ e a nova variável, $Z$, gera os restantes sufixos.

Por exemplo, recuperando a gramática $G^6$ que ilustrou da construção da FNG:

$$\begin{array}{c}\text{Forma Normal de Greibach}\\ \begin{array}{rl}{L}^{\prime }& \to bBZB|aXBZB|aBBZB|bZB|bBB|aXBB|aBBB|bB|b|aX|aB|\lambda \\ & ⋮\end{array}\\ \text{Fatorizada (duas aplicac¸o˜es)}\\ \begin{array}{rl}{L}^{\prime }& \to b{Z}_1|a{Z}_2|\lambda \\ Z_1& \to BZB|ZB|BB|B|\lambda \\ Z_2& \to XBZB|BBZB|XBB|BBB|X|B\\ & ⋮\end{array}\end{array}$$

A fatorização pode ser aplicada repetidas vezes até que o resultado seja adequado, por exemplo uma GIC LL(1).

Para determinar se uma GIC é LL(1) a partir da definição pode ser confuso. Para ajudar neste problema mas também para definir um algoritmo determinista de análise sintática para gramáticas LL(1) usam-se os primeiros, seguintes e os diretores.

Primeiros. Seguintes. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC.

Os primeiros de $u\in {\left(V\cup \Sigma \right)}^{\ast }$ são os terminais que ocorrem na primeira posição das palavras derivadas de $u$: $$\text{primeiros}\left(u\right)=\left\{a\in \Sigma :u\stackrel{\ast }{\Rightarrow }ax\in {\Sigma }^{\ast }\right\}$$

Os seguintes de $A\in V$ são os terminais que ocorrem imediatamente a seguir a $A$ nalguma derivação de $G$: $$\text{seguintes}\left(A\right)=\left\{a\in \Sigma :S\stackrel{\ast }{\Rightarrow }uAv\wedge a\in \text{primeiros}\left(v\right)\right\}$$

Por exemplo, para a GIC $$\begin{array}{rl}S& \to aS|cA\\ A& \to bA|cB|\lambda \\ B& \to cB|a|\lambda \end{array}$$

A partir da definição não é simples calcular os conjuntos dos primeiros e dos seguintes. Para esse cálculo há dois algoritmos gráficos:

Grafo dos Primeiros. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC. O grafo dos primeiros é um grafo em que os vértices são os símbolos de $V\cup \Sigma$ e para cada produção $A\to s_1{s}_2\dots s_n$:

1. Acrescenta-se a aresta $A⟶s_1$.
2. Se $s_1\in \Lambda$, acrescenta-se a aresta $A⟶s_2$.
3. Assim sucessivamente até se esgotarem os $s_i$ ou $s_i\notin \Lambda$.

O grafo dos primeiros tem um caminho $A⟶a\in \Sigma$ se e só se $a\in \text{primeiros}\left(A\right)$.

Continuando com a GIC anterior, obtém-se

Exemplo de Grafo dos Primeiros
N.B. Os "cantos" das arestas são arredondados.

e, portanto, os primeiros de cada variável são:

$$\begin{array}{cc}V& \text{primeiros}\left(V\right)\\ S& \left\{a,c\right\}\\ A& \left\{b,c\right\}\\ B& \left\{a,c\right\}\end{array}$$

ou simplificando a notação: $$\begin{array}{cc}& \text{primeiros}\\ S& ac\\ A& bc\\ B& ac\end{array}$$

Este método mostra apenas os primeiros das variáveis. Para as restantes palavras:

Em geral, calculam-se recursivamente os $\text{primeiros}$:

• $\text{primeiros}\left(\lambda \right)=\varnothing$.
• Para $a\in \Sigma ,\text{primeiros}\left(a\right)=\left\{a\right\}$.
• Para $A\in V$ usa-se o grafo dos primeiros.
• Para $uv\in {\left(V\cup \Sigma \right)}^{\ast }$:

$$\{\begin{array}{ll}\text{primeiros}\left(u\right)\cup \text{primeiros}\left(v\right)& \text{se}u\stackrel{\ast }{\Rightarrow }\lambda \\ \text{primeiros}\left(u\right)& \text{caso contraˊrio}\end{array}$$

Depois dos primeiros (das variáveis) podem calcular-se os seguintes.

Grafo dos Seguintes. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC. O grafo dos seguintes é um grafo em que os vértices são os símbolos de $V\cup \Sigma$ e para cada produção $A\to uBv$ com $B\in V,u,v\in {\left(V\cup \Sigma \right)}^{\ast }$:

1. Acrescenta-se uma aresta $B⟶a$ para cada $a\in \text{primeiros}\left(v\right)$.
2. Se $v\stackrel{\ast }{\Rightarrow }\lambda$, acrescenta-se a aresta $B⟶A$.

O grafo dos seguintes tem um caminho $A⟶a\in \Sigma$ se e só se $a\in \text{seguintes}\left(A\right)$.

Continuando com o mesmo exemplo:

Exemplo de Grafo dos Seguintes

donde resulta $$\begin{array}{cc}& \text{seguintes}\\ S& \varnothing \\ A& \varnothing \\ B& \varnothing \end{array}$$

O próximo passo consiste em determinar os primeiros símbolos que cada produção gera.

Diretores. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC e $A\to p\in P$. O conjunto dos diretores de $A\to p$ é: $$\text{diretores}\left(A\to p\right)=\{\begin{array}{ll}\text{primeiros}\left(p\right)\cup \text{seguintes}\left(A\right)& \text{se}p\stackrel{\ast }{\Rightarrow }\lambda \\ \text{primeiros}\left(p\right)& \text{caso contraˊrio}\end{array}$$

Depois de calculados os primeiros e os seguintes, os diretores são facilmente encontrados: $$\begin{array}{lcr}& \text{diretores}& \\ S\to aS& a& \\ S\to cA& c& \\ S\to \lambda & \varnothing & ✓\\ A\to bA& b& \\ A\to cB& c& \\ A\to \lambda & \varnothing & ✓\\ B\to cB& c& \\ B\to a& a& \\ B\to \lambda & \varnothing & ✓\end{array}$$

Os diretores permitem facilmente verificar se uma GIC é LL(1):

Teorema dos Diretores. Seja $G=\left(V,\Sigma ,P,S\right)$ uma GIC. Se, para qualquer variável $A\in V$ quaisquer duas produções de $A$ tiverem os respetivos diretores distintos, isto é, se $$\text{diretores}\left(A\to u\right)\cap \text{diretores}\left(A\to v\right)=\varnothing$$ para quaisquer duas produções de $A$, então $G$ é LL(1)

Exemplos de Aplicação do Teorema dos Diretores

A GIC definida por $S\to aSa|bSb|\lambda$ não é LL(1):

$$\begin{array}{ccc}& \text{primeiros}& \text{seguintes}\\ S& ab& ab\end{array}$$ e $$\begin{array}{lcr}& \text{diretores}& \\ S\to aSa& a& \\ S\to bSb& b& \\ S\to \lambda & ab& \text{nok}\end{array}$$ Como $$\text{diretores}\left(S\to \lambda \right)\cap \text{diretores}\left(S\to aSa\right)=\left\{a,b\right\}\cap \left\{a\right\}=\left\{a\right\}\ne \varnothing$$ conclui-se que esta gramática não é LL(1).

Um caso mais interessante é a seguinte variante das expressões algébricas, que ilustra a aplicação de algumas transformações:

$$\begin{array}{rlr}S& \to E\#& \\ E& \to E+T|T& \text{recursa˜o direta aˋ esquerda}\\ T& \to (E)|a& \\ S& \to E\#& \\ E& \to TZ|T& \text{prefixos comuns}\\ Z& \to +TZ|+T& \text{prefixos comuns}\\ T& \to (E)|a& \\ S& \to E\#& \\ E& \to TF& \\ F& \to Z|\lambda & \text{repetida}\\ Z& \to +TW& \\ W& \to Z|\lambda & \text{repetida}\\ T& \to (E)|a& \\ S& \to E\#& \\ E& \to TX& \\ Z& \to +TX& \\ X& \to Z|\lambda & \\ T& \to (E)|a& \end{array}$$

Para verificar se esta última gramática é LL(1), passo a passo:

Geradores de Vazio

$$\Lambda =\left\{X\right\}.$$

Primeiros

Grafo dos Primeiros

Seguindo as arestas:

$$\begin{array}{ll}& \text{primeiros}\\ S& (a\\ E& (a\\ Z& +\\ X& +\\ T& (a\end{array}$$

Seguintes

Grafo dos Seguintes

Seguindo as arestas:

$$\begin{array}{ll}& \text{seguintes}\\ S& \\ E& \#)\\ Z& \#)\\ X& \#)\\ T& \#)+\end{array}$$

Diretores

$$\begin{array}{rllrc}& & \text{diretores}& & \\ S& \to E\#& (a& & \\ E& \to TX& (a& & \\ Z& \to +TX& +& & \\ X& \to Z& +& & \\ X& \to \lambda & \#)& & ✓\\ T& \to (E)& (& & \\ T& \to a& a& & ✓\end{array}$$

Analisador Sintático

Com os diretores de cada produção calculados, se a gramática for LL(1), é simples implementar manualmente um Analisador Sintático para essa gramática:

def S():
    if seguinte in "(a":
        E()
        consome("#")
    else:
        erro()

def E():
    if seguinte in "(a":
        T()
        X()
    else:
        erro()

def Z():
    if seguinte in "+":
        consome("+")
        T()
        X()
    else:
        erro()

def X():
    if seguinte in "+":
        Z()
    elif seguinte in "#)":
        return
    else:
        erro()

def T():
    if seguinte in "(":
        consome("(")
        E()
        consome("(")
    elif seguinte in "a":
        consome("a")
    else:
        return erro()

def consome(terminal):
    if terminal == seguinte:
        # AVANÇA
        seguinte = ...
    else:
        erro()

def erro():
    # Para o processamento
    ...

Um exemplo deste programa a correr, para analisar a palavra a+a#, é:

O resultado deste analisador sintático é "verdade" ou "falso" conforme a palavra dada é, ou não, gerada pela gramática. Este é o resultado esperado mas insatisfatório pois nada diz sobre a derivação, isto é a estrutura, da palavra.

Por exemplo, dada a palavra a+a# é desejável saber, além de que $G\stackrel{\ast }{\Rightarrow }a+a\#$, que a sua derivação esquerda é $$S\stackrel{S\to E\#}{\Rightarrow }E\#\stackrel{E\to E+T}{\Rightarrow }E+T\#\stackrel{E\to T}{\Rightarrow }T+T\#\stackrel{T\to a}{\Rightarrow }a+T\#\stackrel{T\to a}{\Rightarrow }a+a\#$$ na gramática inicial.

Conclusão

Este último exemplo mostra que a Análise Sintática está quase resolvida:

As GIC LL(1) são adequadas para representar as linguagens de programação. Além disso, é possível definir algoritmos eficientes para determinar computacionalmente se uma palavra é, ou não, gerada por essa gramática.

No entanto... ainda há por onde melhorar esta situação:

1. A transformação de uma GIC noutra que seja LL(1) é um passo Ad hoc, que depende de muitas escolhas específicas.
2. Nessa transformação perde-se a ligação à gramática inicial. Em concreto, olhando para a computação de a+a# não se percebe como a palavra é gerada pelas produções da gramática inicial.
3. Este processo implica a implementação "manual" das "produções" (human in the middle) mas seria muito melhor que fosse totalmente automático. Isto é, pretende-se definir um programa "geral" Super que aceita como entrada uma gramática G e devolve um certo programa P que, por sua vez, aceita como entrada uma palavra p e calcula se esta é, ou não, gerada por G:
   1. P = Super(G).
   2. P(p) é equivalente a "p é gerada por G".