Lexer Ego w Elixirze

Jarek Pałka i Wiktor Sztajerowski zaczęli z nudów cykl wykładów o tym jak stworzyć język programowania. Na tapetę trafiło Jarkowe Ego, czyli język programowania przeznaczony do ćwiczenia programowania w dziwnych paradygmatach. Pierwszy wykład poświęcili na napisanie prostego leksera^W języka. Całość do obejrzenia poniżej:

A ja postanowiłem, że pobawię się ich zabawką w trochę inny sposób. Napiszę w elixirze lekser, który będzie umiał dokonać analizy leksykalnej Ego z takim samym wynikiem, co oryginalne rozwiązanie. Zaczynamy!

Konfiguracja

By rozpocząć naszą zabawę, należy na początek utworzyć projekt za pomocą mixa. Następnie dla własnej wygody dodałem jedną zależność – bibliotekę assertions, która pozwoli w prosty sposób porównywać listy w testach. W efekcie mój mix.exs wygląda w następujący sposób:

Listing 1. Konfiguracja projektu

defmodule Ego.MixProject do
  use Mix.Project

  def project do
    [
      app: :ego,
      version: "0.1.0",
      elixir: "~> 1.10",
      start_permanent: Mix.env() == :prod,
      deps: deps()
    ]
  end

  def application do
    [extra_applications: [:logger]]
  end

  defp deps do
    [{:assertions, "~> 0.10", only: :test}]
  end
end

Mając taką konfigurację, możemy przystąpić do pisania!

Prosty program – ()

Podobnie jak Jarek i Wiktor rozpocznę od najprostszego programu. W Ego będzie to program złożony z nawiasu otwierającego i zamykającego:

Listing 2. Prosty program w Ego

()

Program ten po przetworzeniu przez lekser powinien wygenerować listę, na której znajdują się trzy tokeny. Pierwszy reprezentuje nawias otwierający, drugi nawias zamykający, a trzeci jest znacznikiem końca pliku. Test, który opisuje to zachowanie, wygląda w następujacy sposób:

Listing 3. Test programu ()

test "()" do
  result = Lexer.tokenize("()")
  assert_lists_equal(result, [:open_bracket, :close_bracket, :eof])
end

Uwaga! Tutaj troszeczkę oszukuję, bo używam elixirowych atomów wprost. Wynika to z chęci utrzymania kodu we w miarę zwięzłej postaci. Oczywiście można ten kod uszczegółowić w podobny sposób jak na filmie, ale ciężko by się go czytało pod postacią blogonotki.

By wypełnić ten test, musimy oczywiście napisać kod. Na początek będzie on bardzo prosty:

Listing 4. Pierwsze elementy leksera

defmodule Ego.Lexer do
  def tokenize(program) when is_binary(program) do
    program
    |> String.split("", trim: true)
    |> token
  end

  defp token(charlist, accumulator \\ [])
  defp token([], accumulator), do: accumulator ++ [:eof]

  defp token(charlist, accumulator) do
    [h | t] = charlist

    case h do
      "(" -> token(t, accumulator ++ [:open_bracket])
      ")" -> token(t, accumulator ++ [:close_bracket])
      _ -> token(t, accumulator)
    end
  end
end

Co my tu mamy? W linii 2 strażnik sprawdza, czy mamy do czynienia z ciągiem znaków. Uroki słabego typowania są urocze… Następnie w liniach 15 i 16 emitujemy odpowiednie tokeny, a w linii 17 ignorujemy inne znaki. Linia 8 jest oczywista, bo jeżeli lista znaków do przetworzenia jest pusta, to znaczy, że osiągnęliśmy koniec pliku i trzeba wyemitować EOF.

Wariacja i kolejny test – `( )`

W tym miejscu pójdę trochę inną drogą nich chłopaki, bo dodam obsługę białych znaków.

Listing 5. Test programu ( )

test "( )" do
  result = Lexer.tokenize("( )")
  assert_lists_equal(result, [:open_bracket, :close_bracket, :eof])
end

Inaczej mówiąc, jeżeli trafię na spację, to mogę ją olać. Ten test już przejdzie, bo warunek z 17 linijki nie jest po nic. Jednak delikatnie zmienię kod:

Listing 6. Małe zmiany – uwzględniamy spację

defmodule Ego.Lexer do
  def tokenize(program) when is_binary(program) do
    program
    |> String.split("", trim: true)
    |> token
  end

  defp token(charlist, accumulator \\ [])
  defp token([], accumulator), do: accumulator ++ [:eof]

  defp token(charlist, accumulator) do
    [h | t] = charlist

    case h do
      "(" -> token(t, accumulator ++ [:open_bracket])
      ")" -> token(t, accumulator ++ [:close_bracket])
      " " -> token(t, accumulator)
      _ -> token(t, accumulator)
    end
  end
end

Nic się praktycznie nie zmieniło, ale to tylko pozory. W ten sposób mamy już obsługiwane (prawie) wszystkie symbole jednoznakowe.

Symbole wieloznakowe

Kolejnym krokiem jest obsługa symboli wieloznakowych. Zaczniemy tradycyjnie od napisania testu:

Listing 7. Test programu (Print Hello)

test "(Print Hello)" do
  result = Lexer.tokenize("(Print Hello)")
  assert_lists_equal(result, [:open_bracket, :Print, :Hello, :close_bracket, :eof])
end

Sprawa wydaje się być bardzo prosta. Musimy dodać do naszego leksera bufor, w którym będziemy zbierać kolejne znaki i w momencie gdy trafimy na znak z pierwszej grupy, to wyemitujemy odpowiedni token.

Listing 8. Obsługa symboli wieloznakowych

defmodule Ego.Lexer do
  def tokenize(program) when is_binary(program) do
    program
    |> String.split("", trim: true)
    |> token
  end

  defp token(charlist, accumulator \\ [], buffer \\ [])
  defp token([], accumulator, buffer), do: accumulator ++ [:eof]

  defp token(charlist, accumulator, buffer) do
    [h | t] = charlist

    case h do
      "(" -> token(t, accumulator ++ read_buffer(buffer) ++ [:open_bracket], [])
      ")" -> token(t, accumulator ++ read_buffer(buffer) ++ [:close_bracket], [])
      " " -> token(t, accumulator ++ read_buffer(buffer), [])
      _ -> token(t, accumulator, buffer ++ [h])
    end
  end

  defp read_buffer([]), do: []

  defp read_buffer(buffer) do
    [buffer |> Enum.join("") |> String.to_atom()]
  end
end

Tu się robi ciekawie. Po pierwsze przyjmujemy, że trafiając na któryś ze znaków „specjalnych”, opróżniamy bufor i emitujemy token. Po drugie bufor może być pusty, a zatem nie możemy emitować pustego tokenu. W Elixirze :”” jest poprawnym atomem, więc trzeba tu trochę pohakować. W ten sposób mamy już prosty lekser, który możemy zacząć komplikować. Wzorem Jarka i Wiktora dodajmy obsługę ciągów znaków.

Ciągi znaków

Wspomniałem, że mamy już obsługę prawie wszystkich symboli jednoznakowych. Pozostał nam jeszcze jeden symbol – cudzysłów. Jego obsługa skomplikuje nam lekser, ale też pozwoli na opisanie całej klasy problemów. Zacznijmy jednak od napisania testów:

Listing 9. Test programu (Print Hello)

test "(Print \"Hello World\")" do
  result = Lexer.tokenize("(Print \"Hello World\")")
  assert_lists_equal(result, [:open_bracket, :Print, :"Hello World", :close_bracket, :eof])
end

test "(Print \"Hello ( ) World\")" do
  result = Lexer.tokenize("(Print \"Hello ( ) World\")")
  assert_lists_equal(result, [:open_bracket, :Print, :"Hello ( ) World", :close_bracket, :eof])
end

test "(Print \"Hello (\n) World\")" do
  result = Lexer.tokenize("""
rint \"Hello (
  ) World\")
  """)
  assert_lists_equal(result, [:open_bracket, :Print, :"Hello (\n) World", :close_bracket, :eof])
end

Te trzy małe testy pokrywają użycie znaków (,), spacji i znaku nowej linii w ciągu znaków. Jednocześnie wymuszają na nas duże zmiany w implementacji leksera. Od tego momentu lekser będzie musiał działać w dwóch trybach. Pierwszy zwykły tryb, to wszystko co dotychczas napisaliśmy. W momencie, gdy trafi na znak „, lekser przejdzie w tryb procesowania tekstu, którego nie opuści do momentu, gdy po raz kolejny trafi na znak „. Proste, prawda?

Listing 10. Obsługa ciągów znaków

defmodule Ego.Lexer do
  def tokenize(program) when is_binary(program) do
    program
    |> String.split("", trim: true)
    |> token
  end

  defp token(charlist, accumulator \\ [], buffer \\ [], mode \\ :common)
  defp token([], accumulator, buffer, _), do: accumulator ++ [:eof]

  defp token(charlist, accumulator, buffer, :common) do
    [h | t] = charlist

    case h do
      "(" -> token(t, accumulator ++ read_buffer(buffer) ++ [:open_bracket], [])
      ")" -> token(t, accumulator ++ read_buffer(buffer) ++ [:close_bracket], [])
      " " -> token(t, accumulator ++ read_buffer(buffer), [])
      "\"" -> token(t, accumulator ++ read_buffer(buffer), [], :text)
      _ -> token(t, accumulator, buffer ++ [h])
    end
  end

  defp token(charlist, accumulator, buffer, :text) do
    [h | t] = charlist

    case h do
      "\"" -> token(t, accumulator ++ read_buffer(buffer), [], :common)
      _ -> token(t, accumulator, buffer ++ [h], :text)
    end
  end

  defp read_buffer([]), do: []

  defp read_buffer(buffer) do
    [buffer |> Enum.join("") |> String.to_atom()]
  end
end

Jest prawie dobrze. Czwarty parametr funkcji steruje nam trybem pracy. W podobny sposób możemy implementować kolejne tryby np. tryb komentarza. To, co jest jednak nie do końca dobre, to wzrost liczby parametrów. Z drugiej strony możemy wprowadzić jakąś strukturę, która będzie opisywać aktualny tryb pracy i na jej podstawie uruchamiać różne strategie obsługi znaków.

Podsumowanie

Na koniec kilka słów podsumowania. Po pierwsze kod jest w miarę zwięzły. Po drugie trochę inaczej obsługuję błędy, ale to już jest kwestia języka i tego w jaki sposób chcemy informować użytkownika, że napisał coś głupiego. Po trzecie cała ta zabawa zapoczątkowana przez Jarka i Wiktora jest tylko zabawą i nie ma na celu stworzenia jakieŋ poważnego produktu.
Dla mnie osobiście jest to ciekawe doświadczenie. Nigdy nie miałem okazji napisania kompilatora, a ten cykl pozwoli mi na podjęcie wyzwania. Kolejne wersje kodu będą dostępne w repozytorium

Koziołekweb

Sięgam tam gdzie wzrok nie sięga, a tam NullPointerException

Lexer Ego w Elixirze

Konfiguracja

Prosty program – ()

Wariacja i kolejny test – `( )`

Symbole wieloznakowe

Ciągi znaków

Podsumowanie

Konfiguracja

Prosty program – ()

Wariacja i kolejny test – ( )

Symbole wieloznakowe

Ciągi znaków

Podsumowanie

Wariacja i kolejny test – `( )`