Análise Sintática

Pesquisar o Grafo de uma GIC ou uma Árvore das Computações de um AP de forma a encontrar a derivação de uma palavra e construir uma árvore de sintaxe abstrata.

Introdução

A eficiência computacional da análise sintática tem um problema, manifesto no não determinismo dos autómatos de pilha (que, ao contrário dos AFND, deles não se conhece nenhuma simulação determinista, geral e eficiente) e, equivalentemente, nas múltiplas produções das gramáticas independentes do contexto. Ambos estes casos têm representações gráficas: o Grafo da Gramática nas GIC e as Árvores das Computações nos AP.

Nesta situação é necessário fazerem-se pesquisas, abrangendo (no pior cenário) todas as possibilidades. Este é um processo inerentemente (demasiado) demorado pelo que importa encontrar formas de o melhorar.

Conteúdo

Do Problema Principal de ALP — Dada uma linguagem $L \subseteq \cl{\Sigma}$ e uma palavra $p \in \cl{\Sigma}$, determinar se $p \in L$. resta resolver a questão da eficiência computacional, já que a adequação ficou resolvida com as GIC e a computação com os AP.

Intuitivamente, para determinar se $p \in L$ usando um AP, $A$, é necessário explorar a árvore das computações de $A$ com entrada $p$. Especificamente:

O problema de determinar se $p \in L\at{G}$ pode ser resolvido por pesquisa na árvore das computações do AP $A$.

Além disso, como os AP e as GIG são equivalentes, esta observação também sugere que

As derivações de uma GIC podem ser representadas por um grafo orientado.

Mais abaixo vai ser definida rigorosamente a representação das derivações da GIC por um grafo e como é que o problema $p \in L$ pode ser resolvido por pesquisa quer no grafo (das derivações) da GIC quer no grafo (das computações) do AP.

Entretanto, interessa fazer uma breve revisão sobre pesquisa em grafos orientados. O problema pode ser definido como:

Pesquisa em Grafos Orientados. Dado um grafo orientado, descobrir se existe algum caminho $v_0 \to v_1 \to \cdots \to v_n$ desde um vértice inicial, $v_0$, até um vértice final, $v_n$.

A resolução geral deste problema segue o seguinte código:

def pesquisa(grafo, a, b):
  candidatos = [ a ]
  visitados = []
  while len(candidatos) > 0:
    candidato = candidatos.pop(0)
    visitados.append(candidato)
    if candidato == b:
      return True
    else:
      proximos = expande(grafo, candidato)
      proximos_novos = remove(proximos, visitados)
      candidatos = junta(candidatos, proximos_novos)
  return False

N.B. Este código é muito geral e, portanto, não otimizado. Melhorias significativas podem incluir, por exemplo, um resuldado mais descritivo, com o caminho de a até b.

Há quatro variantes da resolução geral deste problema, que correspondem às combinações da seguintes opções para expande e para junta:

• Se expande(G, v) segue a direção das arestas — devolve os filhos de v em G — a pesquisa é descendente, com a = inicial e b = final.
• Se expande(G, v) segue contra a direção das arestas — devolve os pais de v em G — a pesquisa é ascendente, com a = final e b = inicial.
• Se junta(x, y) devolve x + y (x seguido de y) — a pesquisa é em largura.
• Se junta(x, y) devolve y + x (y seguido de x) — a pesquisa é em profundidade.

Resumidamente:

A função remove exclui dos candidatos os vértices já visitados e não depende do tipo de pesquisa.

Grafo de uma Gramática

Todas as possíveis derivações de uma gramática podem ser organizadas num grafo orientado, que começa no símbolo inicial e “percorre” sucessivamente as produções aplicadas durante as derivações. Neste grafo “caminhos” diferentes representam derivações diferentes. Os vértices “são” as palavras intermédias e as arestas as produções aplicadas:

Grafo Esquerdo (resp. Direito) de uma GIC. Seja $G=\del{V, \Sigma, P, S}$ uma GIC. O grafo esquerdo de $G$ (resp. direito) é o digrafo com:

• Vértices: as palavras do conjunto $N = \set{p \in \clpar{V \cup \Sigma} \st S \iderL p}$ (resp. $S \iderR p$).
• Arestas: os elementos de $A = \set{\del{a,b,p} \in N \times N \times P \st a \nderL{p} b}$ (resp. $a \nderR{p} b$).

Por exemplo, para a GIC $S \to aS \alt \nil$ parte do grafo esquerdo é

Grafo Esquerdo de $S \to aS \alt \nil$ (parcial)

O grafo (esquerdo/direito) de uma GIC representa todas as possíveis derivações (esquerdas/direitas) dessa GIC. Este grafo não tem de ser uma árvore porque no grafo de uma gramática ambígua há vários “caminhos” para o mesmo vértice.

Exemplo/Exercício: Desenhe o grafo de $S \to aS \alt Sa \alt \nil $.

As árvores e as gramáticas não ambíguas estão relacionadas:

O grafo esquerdo (resp. direito) de uma GIC não ambígua é uma árvore. Recíprocamente, se o grafo esquerdo (resp. direito) de uma GIC for uma árvore, então a GIC é não ambígua.

O grafo da GIC não deve ser confundido com as árvores de derivação, que ilustram uma possível derivação de uma palavra.

Qualquer palavra de terminais gerada pela GIC é um vértice sem filhos. Isto é, $G \ider p \in \cl{\Sigma}$ se, e só se, $p$ é um vértice sem filhos no grafo de $G$.

Isto é a reformulação do Problema Principal de ALP como um problema de pesquisa em grafos: Dada uma GIC $G = \del{V, \Sigma, P, S}$ e uma palavra $p \in \cl{\Sigma}$, existe algum caminho $S \longrightarrow p$ no grafo (esquerdo) de $G$? Nesse caso $p \in L\at{G}$; caso contrário $p \not\in L\at{G}$.

Exemplos com Expressões Algébricas Simplificadas

Para ilustrar melhor os grafos esquerdos e direitos, assim como os algoritmos de pesquisa, considere-se a seguinte gramática, para expressões algébricas simplificadas (EAS):

$$ \mathrm{EAS}: \left\lbrace \begin{aligned} S &\to U \alt S + U \cr U &\to a \alt b \end{aligned} \right. $$

Os inícios dos grafos (esquerdo e direito) são

Grafo Esquerdo de EAS	Grafo Direito de EAS

Portanto, para já, a análise sintática pode ser feita em oito tipos de pesquisa:

Análise Sintática Descendente em Largura no Grafo da GIC

Intuitivamente, mantém-se uma lista de candidatos, iniciada com $S$ e aplicam-se sucessivamente produções, sempre ao primeiro elemento dessa lista, o “candidato”. Há três hipóteses:

1. O candidato é o alvo ou não há candidatos. A pesquisa termina.
2. O candidato é incompatível com o alvo. Passa-se ao próximo candidato.
3. O candidato é compatível com o alvo, mas diferente. Os filhos do candidato atual são acrescentados ao fim da lista.

Compatível significa que o prefixo terminal do candidato é um prefixo do alvo.

Por exemplo, nas EAS, a pesquisa DL de $b+a$ é:

$$ \begin{aligned} S \cr U &,& S + U \cr S + U &,& a, b \cr a &,& b, U + U, S + U + U \cr b &,& U + U, S + U + U \cr U + U &,& S + U + U \cr S + U + U &,& a + U, b + U \cr a + U &,& b + U, U + U + U, S + U + U + U \cr b + U &,& U + U + U, S + U + U + U, a + a, a + b \cr U + U + U &,& S + U + U + U, a + a, a + b, b + a, b + b \cr \vdots \cr b + a &,& \cdots \end{aligned} $$

Análise Sintática Descendente em Profundidade no Grafo da GIC

Intuitivamente, mantém-se uma lista de candidatos, iniciada com $S$ e aplicam-se sucessivamente produções, sempre ao primeiro elemento dessa lista, o “candidato”. Há três hipóteses:

1. O candidato é o alvo ou não há candidatos. A pesquisa termina.
2. O candidato é incompatível com o alvo. Passa-se ao próximo candidato.
3. O candidato é compatível com o alvo, mas diferente. Os filhos do candidato atual são acrescentados ao início da lista.

Por exemplo, nas EAS, a pesquisa DP de $b+a$ é:

$$ \begin{aligned} S \cr U &,& S + U \cr a&,& b, S + U\cr b &,& S + U \cr S + U\cr U + U &,& S + U + U \cr a + U &,& b + U, S + U + U \cr b + U &,& S + U + U \cr b + a &,& b + b, S + U + U \end{aligned} $$

Análise Sintática Ascendente e as Computações do AP

As pesquisas anteriores percorrem o grafo da gramática, gerado pelas suas produções. Por outro lado, os autómatos de pilha, sendo equivalentes às GIC, também podem ser usados para a análise sintática.

No caso dos AP o não determinismo ocorre sempre que uma configuração tem dois ou mais sucessores. Por outro lado a própria palavra proporciona informação que pode ser usada para guiar a pesquisa.

As computações nos AP “consomem” a palavra na entrada e este processo é semelhante às pesquisas ascendentes, que começam no “alvo” e “andam para trás” até chegarem a um vértice “inicial”.

O processo de pesquisa nas computações é essencialmente descrito pelas operações de transferência e de redução de um certo AP derivado da GIC.

N.B. que este AP não foi ainda formalmente definido.

Intuitivamente, a palavra da entrada é passada para a pilha, transferindo um símbolo de cada vez. Também a palavra que está na pilha pode ser reduzida, isto é, “desfeito” o resultado de aplicar uma produção. No fim, a entrada deve ficar vazia e a pilha só com o símbolo inicial.

Redução é o inverso da aplicação de uma produção. Por exemplo, se $A \to cBc$ for uma produção então uma possível redução da palavra $bbcBcab$ será $bbAab$ porque $bb\underline{A}ab\nder{A \to cBc} bb\underline{cBc}ab$.

Por exemplo, escolhendo convenientemente as operações “transferência”, $Tr$, da entrada para a pilha e “redução”, $Red$, duma subpalavra na pilha, uma computação possível de $b+a$ é

$$ \begin{array}{lr|cl} \text{pilha} & \text{entrada} & \text{operação} & \text{produção} \cr \hline \nil & b + a & Tr\cr b & + a & Red& U \to b \cr U & + a & Red & S \to U \cr S & + a & Tr \cr S + & a & Tr \cr S + a &\nil& Red & U \to a \cr S + U &\nil& Red & S \to S + U \cr S & \nil \end{array} $$

Um resultado interessante deste método é que as reduções aplicadas mostram uma derivação direita da palavra, lida “de baixo para cima” na coluna “Produção”:

$$S \nder{S \to S + U} S + U \nder{U \to a} S + a \nder{S \to U} U + a \nder{U \to b} b + a$$

Este esquema não só determina se a palavra é gerada pela gramática como, nesse caso, encontra uma derivação da palavra.

No entanto, tem algumas fontes de não determinismo:

• Quando fazer uma redução ou uma transferência?
• Numa redução podem ser escolhidos várias subpalavras da pilha e várias produções da gramática.

Por exemplo, dada a GIC $S \to aA \alt bB, A \to a, B \to aa \alt a$ como reduzir $baa$ na pilha? Pode escolher-se:

Análise Sintática Ascendente em Largura

Intuitivamente, mantém-se uma lista de candidatos, iniciada com $p$ e aplicam-se todas as reduções possíveis, sempre ao primeiro elemento dessa lista, o “candidato”. Há duas hipóteses:

1. O candidato é a produção inicial ou não há candidatos. A pesquisa termina.
2. O candidato admite reduções. Os pais desse candidato são acrescentados ao fim da lista.

Por exemplo, nas EAS, a pesquisa AL de $b+a$ é:

$$ \begin{aligned} b + a \cr U + a &,& b + U \cr b + U &,& S + a, U + U \cr S + a &,& U + U, b + S, (U + U) \cr U + U &,& b + S, S + U \cr b + S &,& S + U, U + S, (S + U) \cr S + U &,& U + S, (U + S) \cr U + S &,& S, S + S \cr S &,& S + S, (S + S) \end{aligned} $$

Análise Sintática Ascendente em Profundidade

Intuitivamente, mantém-se uma lista de candidatos, iniciada com $p$ e aplicam-se todas as reduções possíveis, sempre ao primeiro elemento dessa lista, o “candidato”. Há duas hipóteses:

1. O candidato é a produção inicial ou não há candidatos. A pesquisa termina.
2. O candidato admite reduções. Os pais do candidato atual são acrescentados ao início da lista.

Por exemplo, nas EAS, a pesquisa AP de $b+a$ é:

$$ \begin{aligned} b + a \cr U + a &,& b + U \cr S + a&,& U + U, b + U\cr S + U&,& U + U, b + U\cr S&,& U + U, b + U\cr \end{aligned} $$

Conclusão

Depois de resolvidas as questões da adequação e da computação, está-se a tratar da eficiência no Problema Principal de ALP/Análise Sintática.

A análise sintática é representada como um problema de pesquisa em grafos orientados que, em geral, pode ser resolvido por quatro estratégias diferentes: (ascendente ou descendente) x (largura ou profundidade). Por outro lado a pesquisa tanto pode ser feita no grafo da gramática como na árvore das computações do autómato de pilha.

Nenhuma destas estratégias gerais é eficiente. Para melhorar este problema e guiar as pesquisas na análise sintática colocam-se duas possibilidades: ou se condiciona a gramática, de forma reduzir as produções aplicáveis em cada passo ou, então, consultam-se os símbolos por processar para guiar as transições dos autómatos de pilha.