Introdução

• Introdução
  • Representação de Programas e/ou Expressões

Procura-se ilustrar uma das principais aplicações da análise sintática: A implementação de linguagens de programação.

Antes de se definir a própria linguagem de programação e considerar os aspetos da implementação do respetivo analisador sintático e do interpretador faz-se uma revisão dos termos e processos envolvidos.

Alguns termos relevantes, alguns já familiares, são:

• Símbolos: "entidades" indivisíveis e distintas entre si. Um conjunto de símbolos é um alfabeto.
• Palavra: sequência finita de símbolos.
• Linguagem: conjunto de palavras.
• Gramática: regras que permitem especificar certas linguagens.
• Representação: descrição da estrutura duma palavra, de acordo com uma gramática.

Também é importante recapitular alguns processos:

• A análise sintática consiste em decidir de uma palavra $p$ está, ou não, numa linguagem $L$: "$p\in L$?". No caso da linguagem ser gerada por uma certa gramática $G$, isto é, se $L=L(G)$, a questão da análise sintática passa a ser "$S\stackrel{\ast }{\Rightarrow }p$?" em que $S$ é o símbolo inicial de $G$.
• Para o processamento de programas, em particular para a interpretação e/ou compilação, não basta saber que $S\stackrel{\ast }{\Rightarrow }p$; É mais importante representar a estrutura de $p$ de acordo com as regras de $G$. Essa representação pode ser, por exemplo, a árvore da derivação de $p$ ou a sua própria derivação, isto é a sequência de regras aplicadas passo-a-passo em $S\stackrel{\ast }{\Rightarrow }p$.
• A representação do programa é processada pelo interpretador, que mantém uma configuração interna, atualizada conforme a computação avança nas instruções.
• A evolução da computação depende, por um lado, dos tipos das instruções e, por outro, dos valores das expressões.

Representação de Programas e/ou Expressões

É necessária uma estrutura de dados adequada à representação e ao processamento de programas.

Começando pelas expressões algébricas:

Árvore de Derivação	Árvore Simplificada	Valoração da Expressão

• A palavra 2 + (3 * 4) representa a expressão algébrica $2+(3\times 4)$ mas, como "simples" sequência de símbolos, perde-se a estrutura da expressão que representa.

• As sequências (isto é, listas) não são adequadas para processar expressões ou programas. Por exemplo, para calcular o valor de $2+(3\times 4)$ primeiro avalia-se a parte $3\times 4$ e depois esse resultado é somado a $2$.

• A estrutura da expressão algébrica resulta de uma certa gramática, implícita na respetiva definição formal.

• A linguagem das expressões algébricas resulta, por exemplo, da seguinte GIC:

  E → E + T | E - T | T
  T → T * U | T / U | U
  U → N | V | ( E )
  

  em que N define números (-1, 2.45E-5, 42.021, etc) e V variáveis (a, Largura, etc).

• De acordo com esta GIC a palavra 2 + (3 * 4) tem a Árvore de Derivação acima.

• Na Árvore Simplificada a representação em árvore permite calcular o valor da expressão, propagando os valores das folhas para a raíz e, em cada nó, aplicando a operação adequada conforme o tipo do nó.

• A implementação de árvores por uma estrutura de dados é assunto doutras disciplinas. Aqui estamos interessados numa representação simples de árvores, de preferência sem a introdução de novos tipos, operações, etc

• A árvore simplificada fica representada (em Python) pelo tuplo ('+', 2, ('*', 3, 4)).

• Em geral, cada nó tem um conteúdo X e descendentes D1, ..., Dn. Este nó é representado pelo tuplo (X, D1, ..., Dn) com a convenção de que as folhas (Z) são representadas apenas por Z.

• Subindo a árvore de 2 + (3 * 4) temos:

  1. Folhas 2, 3 e 4 (e não (2) por exemplo).
  2. A multiplicação é o tuplo ('*', 3, 4) porque o respetivo conteúdo é '*' (uma string Python) e tem dois descendentes, 3 e 4.
  3. O nó da soma tem conteúdo '+' e dois descendentes, a folha 2 e a sub-árvore ('*', 3, 4). Fica representado por ('+', 2, ('*', 3, 4)).

Esta forma de representar as (estruturas das) expressões vai ser aplicada à representação (das estruturas) dos programas.

Também o exemplo do cálculo do valor da expressão algébrica orienta a implementação do interpretador.