Em meu último artigo, discutimos o processo de construção de um compilador de linguagem de programação que pode compilar a si mesmo . Parte desse processo envolve a construção de um compilador ou mecanismo de execução em alguma outra linguagem, primeiro.

Então, para entender como construir um compilador para uma linguagem de programação gráfica (G) que seja capaz de compilar a si mesma pode funcionar (se é que é possível), isso nos ajudará a entender um pouco sobre o funcionamento de compiladores para sistemas tradicionais linguagens de programação baseadas em texto.

Todas as várias partes elementares de uma linguagem de programação baseada em texto podem ser representadas em software e envolvem as etapas mostradas na figura abaixo:

Etapa 1. Análise léxica: analisando o texto do código-fonte

A primeira etapa desse processo é analisar o texto do código e identificar coisas (também conhecidas como “tokens”) como nomes de variáveis, números, chamadas de função, argumentos de função, loops e outras estruturas. Esse processo é chamado de “análise” e “lexificação”.

Passo 2. Análise de Sintaxe: Gerando uma Representação da Estrutura de Dados do Programa

A sintaxe de uma linguagem de programação são as regras sobre como as partes individuais podem ser reunidas e o significado que elas têm com base em como são reunidas. A etapa de análise de sintaxe interpretará todos os tokens de acordo com a sintaxe da linguagem e construirá uma estrutura de dados (chamada Abstract Syntax Tree ou “AST”) que representa o código-fonte em um formato mais “orientado a objetos” e capaz de ser manipulado por outro software.

Passo 3. Lucros! (er… Geração de Código)

Com o AST instalado para seu código-fonte baseado em texto, agora você pode gerar os bits que pagam as contas!

Exemplo de Árvore de Sintaxe Abstrata (AST) (em Pseudocódigo Python)

Vejamos um AST de uma linguagem baseada em texto simples que usa “expressões” como componente fundamental (classe base) para a estrutura da linguagem.

Aqui está uma estrutura de classe python simples para um AST (que pode ter alguns bugs e, em caso afirmativo, sinta-se à vontade para me avisar):

@dataclass
class AST:
  """Our AST is a list/array of expressions to evaluate in order."""
  lines: List[Expression]= []

@dataclass
class Expression:
  """An Expression is evaluated and returns a value"""
def evaluate(self) -> Any:
    ...
@dataclass
class LiteralExpression:
  """An Literal Expression has and returns a value"""
  value: int | float | str | bool
__init__(self, value):
    self.value = value
def evaluate(self):
    return value

@dataclass
class UnaryExpression(Expression):
  """An Unary Expression has a single expression"""
  expression: Expression

@dataclass
class Negate(UnaryExpression):
  """Evaluate the expression, negates it, and return the result"""
def evaluate(self):
    return -self.expression.evaluate()

@dataclass
class BinaryExpression(Expression):
  """An Binary Expression has two expressions: left and right."""
  left_expression: Expression
  right_expression: Expression

@dataclass
class Add(BinaryExpression):
  """e.g. Add(1, 2) -> 3"""
def evaluate(self):
    return left_expression.evaluate() + right_expression.evaluate()

Aqui está um "código-fonte"

01: 1 + 3
02: -( 7 + 9 )

# -> 4
# -> -16

Vamos analisar isso manualmente (à mão), pois essas expressões matemáticas são bastante simples de representar como AST em nosso modelo python usando pseudocódigo. O resultado é uma estrutura de dados que pode se parecer com isto:

# Here is an AST instance (object)representing our two-line "Program" above.
my_ast = AST([

# line 01:                              1 + 3
  Add(
      LiteralExpression(1), # evaluate() ->   1
      LiteralExpression(3), # evaluate() ->   3
                            # -----------------
    ),                      # evaluate() ->   4
  # line 02:                         -( 7 + 9 )
  Negate(
    Add(
      LiteralExpression(7), # evaluate() ->   7
      LiteralExpression(9), # evaluate() ->   9
                            # -----------------
    )                       # evaluate() ->  16
                            # -----------------
  )                         # evaluate() -> -16
])

def run(program: AST):
  """Print the result of evaluating each expression in the AST"""
    for expression in ast.lines:
      print(expression.evaluate())

>>> run(my_ast)
4
-16

Agora que abordamos um pouco sobre como os compiladores funcionam e como as estruturas de árvore de sintaxe abstrata nos ajudam a executar nosso código, podemos ver como alguém pode criar um compilador para uma linguagem de programação gráfica de fluxo de dados.

Falaremos mais sobre isso em breve…