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.

• Análise Sintática
  • Introdução
  • Conteúdo
    • Grafo de uma Gramática
      • Exemplos com Expressões Algébricas Simplificadas
    • Análise Sintática Descendente em Largura no Grafo da GIC
    • Análise Sintática Descendente em Profundidade no Grafo da GIC
    • Análise Sintática Ascendente e as Computações do AP
    • Análise Sintática Ascendente em Largura
    • Análise Sintática Ascendente em Profundidade
  • Conclusão

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 {\Sigma }^{\ast }$ e uma palavra $p\in {\Sigma }^{\ast }$, 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\left(G\right)$ 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=\left(V,\Sigma ,P,S\right)$ uma GIC. O grafo esquerdo de $G$ (resp. direito) é o digrafo com:

• Vértices: as palavras do conjunto $N=\left\{p\in {\left(V\cup \Sigma \right)}^{\ast }:S\stackrel{\ast }{{\Rightarrow }_L}p\right\}$ (resp. $S\stackrel{\ast }{{\Rightarrow }_R}p$).
• Arestas: os elementos de $A=\left\{\left(a,b,p\right)\in N\times N\times P:a\stackrel{p}{{\Rightarrow }_L}b\right\}$ (resp. $a\stackrel{p}{{\Rightarrow }_R}b$).

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

Grafo Esquerdo de $S\to aS|\lambda$ (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|Sa|\lambda$.

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\stackrel{\ast }{\Rightarrow }p\in {\Sigma }^{\ast }$ 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=\left(V,\Sigma ,P,S\right)$ e uma palavra $p\in {\Sigma }^{\ast }$, existe algum caminho $S⟶p$ no grafo (esquerdo) de $G$? Nesse caso $p\in L\left(G\right)$; caso contrário $p\notin L\left(G\right)$.

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}:\{\begin{array}{rl}S& \to U|S+U\\ U& \to a|b\end{array}$$

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{array}{rlr}S& & \\ U& ,& S+U\\ S+U& ,& a,b\\ a& ,& b,U+U,S+U+U\\ b& ,& U+U,S+U+U\\ U+U& ,& S+U+U\\ S+U+U& ,& a+U,b+U\\ a+U& ,& b+U,U+U+U,S+U+U+U\\ b+U& ,& U+U+U,S+U+U+U,a+a,a+b\\ U+U+U& ,& S+U+U+U,a+a,a+b,b+a,b+b\\ ⋮& & \\ b+a& ,& \cdots \end{array}$$

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{array}{rlr}S& & \\ U& ,& S+U\\ a& ,& b,S+U\\ b& ,& S+U\\ S+U& & \\ U+U& ,& S+U+U\\ a+U& ,& b+U,S+U+U\\ b+U& ,& S+U+U\\ b+a& ,& b+b,S+U+U\end{array}$$

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\stackrel{A\to cBc}{\Rightarrow }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}{lrcl}\text{pilha}& \text{entrada}& \text{operac¸a˜o}& \text{produc¸a˜o}\\ \lambda & b+a& Tr& \\ b& +a& Red& U\to b\\ U& +a& Red& S\to U\\ S& +a& Tr& \\ S+& a& Tr& \\ S+a& \lambda & Red& U\to a\\ S+U& \lambda & Red& S\to S+U\\ S& \lambda & & \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\stackrel{S\to S+U}{\Rightarrow }S+U\stackrel{U\to a}{\Rightarrow }S+a\stackrel{S\to U}{\Rightarrow }U+a\stackrel{U\to b}{\Rightarrow }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|bB,A\to a,B\to aa|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{array}{rlr}b+a& & \\ U+a& ,& b+U\\ b+U& ,& S+a,U+U\\ S+a& ,& U+U,b+S,(U+U)\\ U+U& ,& b+S,S+U\\ b+S& ,& S+U,U+S,(S+U)\\ S+U& ,& U+S,(U+S)\\ U+S& ,& S,S+S\\ S& ,& S+S,(S+S)\end{array}$$

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{array}{rlr}b+a& & \\ U+a& ,& b+U\\ S+a& ,& U+U,b+U\\ S+U& ,& U+U,b+U\\ S& ,& U+U,b+U\end{array}$$

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.