Gramáticas LL(k)

Análise Sintática Descendente Determinista.

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{aligned} S &\to aS \alt cA \cr A &\to bA \alt cB \alt \nil \cr B &\to cB \alt a \alt \nil \end{aligned} $$

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}{l|r|c|l|r} \text{prefixo} & \text{\alert{avanço}resto} & \text{variável} & \text{produção} & \text{derivação} \cr \nil & \alert{a}cbb & S & S \to aS & S \der aS \cr a & \alert{c}bb & S & S \to cA & \der acA \cr ac & \alert{b}b & A & A \to bA & \der acbA \cr acb & \alert{b} & A & A \to bA & \der acbbA \cr acbb & \alert{\nil} & A & A \to \nil & \der 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 = \del{V, \Sigma, P, S}$ com terminador $#$ é LL(1) se dadas duas derivações esquerdas $$ \begin{aligned} S \ider u_1 \alert{A} v_1 \der u_1 \alert{x} v_1 \ider u_1 a w_1 \cr S \ider u_2 \alert{A} v_2 \der u_2 \alert{y} v_2 \ider u_2 a w_2 \end{aligned} $$ em que $u_i, w_i \in \cl{\Sigma},\ a\in\Sigma$ e $A \in V$ então $\alert{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’$ com terminador $#$, de forma que $p \in L(A) \iff p\# \in L(A’)$.

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 = \del{V, \Sigma, P, S}$ 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=\del{V, \Sigma, P, S}$ uma GIC. Supondo que as produções de $A\in V$ são $$ A \to \alert{p}u_1 \alt \alert{p}u_2 \alt \cdots \alt \alert{p}u_n \alt v_1 \alt v_2 \alt \cdots \alt v_m $$

em que $p, u_i, v_j \in \clpar{V \cup \Sigma}$ então a GIC $G’$ obtida de $G$

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

é equivalente a $G$.

Com a fatorização as várias produções de $A$ que começam pelo mesmo prefixo, $A \to pu_1 \alt pu_2 \alt \cdots \alt pu_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} \cr \begin{aligned} L’ & \to bBZB \alt aXBZB \alt aBBZB \alt bZB \alt bBB \alt aXBB \alt aBBB \alt bB \alt b \alt aX \alt aB \alt \nil \cr &\vdots \end{aligned} \cr \text{Fatorizada (duas aplicações)} \cr \begin{aligned} L’ & \to bZ_1 \alt aZ_2 \alt \nil \cr Z_1 &\to BZB \alt ZB \alt BB \alt B \alt \nil \cr Z_2 &\to XBZB \alt BBZB \alt XBB \alt BBB \alt X \alt B \cr &\vdots \end{aligned} \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 = \del{V, \Sigma, P, S}$ uma GIC.

Os primeiros de $u \in \clpar{V \cup \Sigma}$ são os terminais que ocorrem na primeira posição das palavras derivadas de $u$: $$\primeiros\at{u} = \set{a \in \Sigma \st u \ider ax \in \cl{\Sigma}}$$

Os seguintes de $A\in V$ são os terminais que ocorrem imediatamente a seguir a $A$ nalguma derivação de $G$: $$\seguintes\at{A} = \set{a \in \Sigma \st S \ider uAv \land a \in \primeiros\at{v}}$$

Por exemplo, para a GIC $$ \begin{aligned} S &\to aS \alt cA \cr A &\to bA \alt cB \alt \nil \cr B &\to cB \alt a \alt \nil \end{aligned} $$

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 = \del{V, \Sigma, P, S}$ 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 \ldots s_n$:

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

O grafo dos primeiros tem um caminho $A \longrightarrow a \in \Sigma$ se e só se $a \in \primeiros\at{A}$.

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}{c|c} V & \primeiros\at{V} \cr \hline S & \set{a, c} \cr A & \set{b, c} \cr B & \set{a, c} \end{array} $$

ou simplificando a notação: $$ \begin{array}{c|c} & \primeiros \cr \hline S & ac \cr A & bc \cr B & ac \end{array} $$

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

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

• $\primeiros\at{\nil} = \empty$.
• Para $a\in\Sigma, \primeiros\at{a} = \set{a}$.
• Para $A\in V$ usa-se o grafo dos primeiros.
• Para $uv\in\clpar{V \cup \Sigma}$:

$$ \begin{cases}\primeiros\at{u} \cup \primeiros\at{v} & \text{se}\ u \ider \nil \cr \primeiros\at{u} & \text{caso contrário} \end{cases} $$

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

Grafo dos Seguintes. Seja $G = \del{V, \Sigma, P, S}$ 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 \clpar{V \cup \Sigma}$:

1. Acrescenta-se uma aresta $B \longrightarrow a$ para cada $a \in \primeiros\at{v}$.
2. Se $v \ider \nil$, acrescenta-se a aresta $B \longrightarrow A$.

O grafo dos seguintes tem um caminho $A \longrightarrow a \in \Sigma$ se e só se $a \in \seguintes\at{A}$.

Continuando com o mesmo exemplo:

Exemplo de Grafo dos Seguintes

donde resulta $$ \begin{array}{c|c} & \seguintes \cr \hline S & \empty \cr A & \empty \cr B & \empty \end{array} $$

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

Diretores. Seja $G=\del{V, \Sigma, P, S}$ uma GIC e $A \to p \in P$. O conjunto dos diretores de $A \to p$ é: $$\diretores\at{A \to p} = \begin{cases} \primeiros\at{p} \cup \seguintes\at{A} & \text{se}\ p \ider \nil\cr \primeiros\at{p} & \text{caso contrário} \end{cases} $$

Depois de calculados os primeiros e os seguintes, os diretores são facilmente encontrados: $$ \begin{array}{l|cr} & \diretores \cr \hline S \to aS & a \cr S \to cA & c \cr S \to \nil & \empty & \checkmark\cr \hline A \to bA & b \cr A \to cB & c\cr A \to \nil & \empty & \checkmark\cr \hline B \to cB & c \cr B \to a & a\cr B \to \nil & \empty & \checkmark \end{array} $$

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

Teorema dos Diretores. Seja $G = \del{V, \Sigma, P, S}$ uma GIC. Se, para qualquer variável $A \in V$ quaisquer duas produções de $A$ tiverem os respetivos diretores distintos, isto é, se $$\diretores\at{A \to u} \cap \diretores\at{A \to v} = \empty$$ 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 \alt bSb \alt \nil$ não é LL(1):

$$ \begin{array}{c|c|c} & \primeiros & \seguintes \cr \hline S & ab & ab \end{array} $$ e $$ \begin{array}{l|cr} & \diretores \cr \hline S \to aSa & a \cr S \to bSb & b \cr S \to \nil & ab & \text{nok} \end{array} $$ Como $$\diretores\at{S \to \nil} \cap \diretores\at{S \to aSa} = \set{a,b} \cap \set{a} = \set{a} \not= \empty$$ 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{aligned} S &\to E\#\ \cr \alert{E} &\to \alert{E} + T \alt T & \text{recursão direta à esquerda} \cr T &\to (E) \alt a \cr \hline S & \to E\# \cr E &\to \alert{TZ} \alt \alert{T} &\text{prefixos comuns} \cr Z &\to \alert{+T}Z \alt \alert{+T} &\text{prefixos comuns} \cr T &\to (E) \alt a \cr \hline S &\to E\# \cr E &\to TF \cr F &\to \alert{Z \alt \nil} &\text{repetida}\cr Z &\to +TW \cr W &\to \alert{Z \alt \nil} &\text{repetida}\cr T &\to (E) \alt a \cr \hline \hline S &\to E\# \cr E &\to TX \cr Z &\to +TX \cr X &\to Z \alt \nil \cr T &\to (E) \alt a \end{aligned} $$

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

Geradores de Vazio

$$ \Lambda = \set{X}. $$

Primeiros

Grafo dos Primeiros

Seguindo as arestas:

$$ \begin{array}{l|l} &\primeiros \cr \hline S & (\ a \cr E & (\ a \cr Z & + \cr X & + \cr T & (\ a \end{array} $$

Seguintes

Grafo dos Seguintes

Seguindo as arestas:

$$ \begin{array}{l|l} &\seguintes \cr \hline S \cr E & \#\ ) \cr Z & \#\ ) \cr X & \#\ ) \cr T & \#\ )\ + \end{array} $$

Diretores

$$ \begin{array}{rl|lr} &&\diretores \cr \hline S &\to E\# & (\ a\cr \hline E &\to TX & (\ a \cr \hline Z &\to +TX & + \cr \hline X &\to Z & +\cr X &\to \nil & \#\ ) && \checkmark\cr \hline T &\to (E) & (\cr T &\to a & a && \checkmark \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 \ider a+a\#$, que a sua derivação esquerda é $$ S \nder{S \to E\#} E\# \nder{E\to E + T} E + T\# \nder{E\to T} T + T\# \nder{T \to a} a + T\# \nder{T \to a} 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”.