W moim ostatnim artykule omówiliśmy proces budowania kompilatora języka programowania, który może się sam skompilować . Część tego procesu obejmuje najpierw zbudowanie kompilatora lub silnika wykonawczego w innym języku.

Tak więc, aby zrozumieć, jak zbudować kompilator dla graficznego języka programowania (G), który jest w stanie sam się skompilować, może działać (jeśli to w ogóle możliwe), pomoże nam to trochę zrozumieć działanie kompilatorów dla tradycyjnych tekstowe języki programowania.

Wszystkie różne elementarne części tekstowego języka programowania mogą być reprezentowane w oprogramowaniu i obejmują kroki pokazane na poniższym rysunku:

Krok 1. Analiza leksykalna: Analiza tekstu kodu źródłowego

Pierwszym krokiem w tym procesie jest przeanalizowanie tekstu kodu i zidentyfikowanie rzeczy (inaczej „tokenów”), takich jak nazwy zmiennych, liczby, wywołania funkcji, argumenty funkcji, pętle i inne struktury. Ten proces nazywa się „parsowaniem” i „leksowaniem”.

Krok 2. Analiza składni: generowanie reprezentacji struktury danych programu

Składnia języka programowania to zasady określające, w jaki sposób poszczególne części mogą być ze sobą połączone, oraz znaczenie, jakie mają one w oparciu o sposób ich połączenia. Etap analizy składni zinterpretuje wszystkie tokeny zgodnie ze składnią języka i zbuduje strukturę danych (zwaną abstrakcyjnym drzewem składni lub „AST”), która reprezentuje kod źródłowy w formacie bardziej „obiektowym” i możliwym do manipulowane przez inne oprogramowanie.

Krok 3. Zyski! (er… Generowanie kodu)

Dzięki AST dla tekstowego kodu źródłowego możesz teraz generować bity, które opłacają rachunki!

Przykład abstrakcyjnego drzewa składni (AST) (w pseudokodzie Pythona)

Przyjrzyjmy się AST prostego języka tekstowego, który używa „wyrażeń” jako podstawowego składnika (klasy bazowej) struktury języka.

Oto prosta struktura klas Pythona dla AST (która może zawierać pewne błędy, a jeśli tak, daj mi znać):

@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()

Oto trochę „kodu źródłowego”

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

# -> 4
# -> -16

Przeanalizujmy to ręcznie (ręcznie), ponieważ te wyrażenia matematyczne można dość łatwo przedstawić jako AST w naszym modelu Pythona przy użyciu pseudokodu. Rezultatem jest struktura danych, która może wyglądać mniej więcej tak:

# 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

Teraz, gdy omówiliśmy trochę sposób działania kompilatorów i sposób, w jaki abstrakcyjne struktury drzewa składni pomagają nam wykonywać nasz kod, możemy przyjrzeć się, jak można stworzyć kompilator dla graficznego języka programowania przepływu danych.

Wkrótce porozmawiamy o tym więcej…