Piszemy własny interpreter w Scali – cz. 2: Parser

W tej części cyklu (chyba najobszerniejszej ze wszystkich) będzie więcej kodu, ponieważ weźmiemy na tapetę parser. Do akcji wkroczą: EBNF, ScalaTest oraz Parser Combinators.

W pierwszej kolejności opracujemy publiczny interfejs dla naszego parsera, następnie wyrazimy nasze zamiary w postaci testów jednostkowych, by ostatecznie przygotować diagram EBNF gramatyki naszego mini-języka, na podstawie którego stworzymy implementację.

Interfejs

Nasz parser będzie bezstanowy, więc bez obaw będziemy mogli współdzielić jedną jego instancję na całą aplikację – tutaj Scala wychodzi nam na przeciw z natywną obsługą singletonów, wystarczy użyć słowa kluczowego object:

object SetNotationParser

Dla osób nie znających Scali ciekawostką może być fakt, że nie występuje w niej modyfikator static – zamiast nich definiujemy obiekt o takiej samej nazwie jak klasa (tzw. Companion Object) w którym umieszczamy wszystko to, co chcemy, aby było współdzielone przez instancje.

Wracajac do parsera – potrzebujemy jeszcze definicji metody, która będzie przyjmować łańcuch znaków i zwracać element SetExpression, będący korzeniem drzewa wyrażenia (patrz cz. 1 cyklu):

object SetNotationParser {
  def parse(literalSetExpression: String): SetExpression = SetDef(Set())
}

Na razie metoda będzie zawsze zwracać wyrażenie reprezentujące pusty zbiór. Spokojnie, na implementację przyjdzie jeszcze czas.

Testy jednostkowe

Teraz stworzymy klika testów jednostkowych weryfikujących działanie parsera. Oczywiście nie przejdą one pomyślnie, ponieważ nasz parser to jeszcze wydmuszka.

Ti-Di.. co?

Na takim działaniu (a raczej kolejności ich podejmowania) polega Test-Driven Development (http://en.wikipedia.org/wiki/Test-driven_development) – testy są definicją tego co chcemy osiągnąć, a nie weryfikacją już stworzonego kodu. TDD warto stosować nie tylko w przypadku nowych funkcjonalności ale także bug-fixów.
Po pierwsze, wymusza to na nas stworzenie przypadku testowego pokrywającego bug (dzięki czemu unikniemy niespodzianek w postaci regresji przy okazji przyszłych modyfikacji kodu).
Po drugie, pozwala nam bardzo szybko zweryfikować poprawkę, bez wykonywania manualnych testów developerskich (których pokrycie także może zostawiać wiele do życzenia, bo przeprowadzając ten sam test po raz N-ty z kolei wkrada się pośpiech, rutyna, albo oba).

Sięgamy po ScalaTest

Stworzyłem klasę testową SetNotationParserTest (dziedziczącą po FunSuite, dla innych rodzajów testów, np. behawioralnych (BDD) możemy wykorzystać SpecSuite – więcej informacji wraz z przykładami można znaleźć w dokumentacji ScalaTest -> http://www.scalatest.org/quick_start) w której umieściłem testy parsera:

package pl.mkubala.sets.parser
import org.scalatest.FunSuite
class SetNotationParserTest extends FunSuite {
  // ..
}

Poniżej opis wybranych przypadków testowych:

  • Jeśli do parsera przekażemy pusty ciąg powinniśmy otrzymać pusty zbiór:
    test("should return empty set definition for empty input string") {
      // given
      val input = ""
      // when
      val result = SetNotationParser.parse(input)
      // then
      assert(result === SetDef(Set()))
    }
  • Jeśli zabraknie zamknięcia nawiasu klamrowego w definicji zbioru to powinien zostać wyrzucony IllegalArgumentException:
    test("should throw exception for '{1,2,3'") {
      // given
      val input = "{1,2,3"
      // when & then
      intercept[IllegalArgumentException] {
        SetNotationParser.parse(input)
      }
    }
  • Definicja zbioru powinna zwrócić nam pojedynczy element drzewa definiujący zbiór skłądający się ze wskazanych elementów:
    test("should parse '{1,2,3}'") {
      // given
      val input = "{1,2,3}"
      // when
      val result = SetNotationParser.parse(input)
      // then
      assert(result === SetDef(Set(1, 2, 3)))
    }
  • Wyrażenie zawierające definicję 2 zbiorów oraz operację na nich powinno zwrócić nam element SetBinaryOp, którego lewa gałąź (odnoga) odpowiada definicji pierwszego zbioru, a prawa – drugiego:
    test("should parse '{1,2,3} ^ {3,4,5}'") {
      // given
      val input = "{1,2,3} ^ {3,4,5}"
      // when
      val result = SetNotationParser.parse(input)
      // then
      assert(result === SetBinOp("^", SetDef(Set(1, 2, 3)), SetDef(Set(3, 4, 5))))
    }
  • I jeszcze test weryfikujący poprawność działania nawiasów:
    test("should parse '{1,2,3} opA ({3,4,5} opB ({5,6,7} opC {7,8,9}))'") {
      // given
      val input = "{1,2,3} opA ({3,4,5} opB ({5,6,7} opC {7,8,9}))"
      // when
      val result = SetNotationParser.parse(input)
      // then
      assert(result === SetBinOp("opA", SetDef(Set(1, 2, 3)), SetBinOp("opB", SetDef(Set(3, 4, 5)), SetBinOp("opC", SetDef(Set(5, 6, 7)), SetDef(Set(7, 8, 9))))))
    }

    Dlaczego taka a nie inna wartość oczekiwana? Zamiast pisać pokażę na diagramie poniżej (kliknij aby zobaczyć powiększenie)

Pozostałe testy można znaleźć w repozytorium (https://github.com/mkubala/sets-notation-interpreter/blob/master/src/test/scala/pl/mkubala/sets/parser/SetNotationParserTest.scala).

Diagram oraz opis w notacji EBNF

Kolejny krok to przygotowanie diagramu EBNF (http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form) dla gramatyki naszego mini-języka.

Sam diagram miał tu na celu gł. pomóc w stworzeniu zapisu słownego oraz jego weryfikacji. Jeśli będziesz tworzył składnie dla własnego mini-języka możesz pominąć ten krok.

Zadanie to zrealizowałem rozpisując jak największą ilość wspieranych wyrażeń i poddawałem je wszystkie analizie uzyskując (kliknij na obrazek aby powiększyć):

Na podstawie powyższego diagramu (by oszczędzić sobie czasu pominąłem w nim diagram dla elementu op jako mało interesujący, wręcz oczywisty) możemy łatwo sporządzić taki oto zapis:

expr = (set | subExpr), [ { op, (set | subExpr) } ];
subExpr = "(", expr, ")";
op = { "[" | "!" | "#" | "$" | "%" | "&" | "'" | "*" | "+" | .. }; 
set = setMultiElem | setSingleElem;
setSingleElem = integerNumber;
setMultiElem = "{", [ { integerNumber, "," } ], integerNumber, "}";
integerNumber = [ "-" | "+" ], { "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0" };

Krótkie wyjaśnienie odnośnie pierwszej linii, tj. wyrażenia expr: Mogłeś zwrócić uwagę, że zapis jest nieco rozdmuchany i można by go uzwięźlić do postaci:

expr = (set | subExpr), [ op, expr ];

Jednak takie rozwiązanie niosło by ze sobą konieczność przetwarzania ciągu operacji od prawej do lewej, a nie od lewej do prawej jak w przypadku wyrażeń arytmetycznych (co było jednnym z naszych założeń, patrz test jednostkowy “should results of ‘{1,2,3} opA {3,4,5} opB {5,6,7}’ be equals to ‘({1,2,3} opA {3,4,5}) opB {5,6,7}'”https://github.com/mkubala/sets-notation-interpreter/blob/master/src/test/scala/pl/mkubala/sets/parser/SetNotationParserTest.scala#L135-146).

Właściwa implementacja

Na podstawie zapisu uzyskanego w poprzednej sekcji możemy od razu stworzyć parser.

Szczypta DSL

Jeśli czytasz tę notkę, to zapewne masz przynajmniej minimalną wiedzę na temat Scali i wiesz, że poniższe 2 linijki wyrażają dokładnie to samo:

1 + 2
1.+(2)

Tak jest – każdy operator jest metodą. Do tego dochodzi jeszcze Currying (http://www.scala-lang.org/node/135), Implicit Conversions (http://tomjefferys.blogspot.com/2011/11/implicit-conversions-in-scala.html) i mamy idealne środowisko do tworzenia wewnętrznych języków domenowych (Inner Domain-Specific Language, http://martinfowler.com/books/dsl.html).

Przykładem takiego Wewnętrznego DSL’a mogą być właśnie Parser Combinators, oferujące składnię bardzo podobną do EBNF – wystarczy tylko kilka zmian by z zapisu z poprzedniej sekcji utworzyć działający parser.

Tłumaczymy EBNF na kod wykorzystujący Parser Combinators

Weźmy na tapetę setMultiElem:

setMultiElem = "{", [ { integerNumber, "," } ], integerNumber, "}";
  1. W pierwszej kolejności dokonamy konwersji 1:1 zamieniając w tym celu:
    • przecinki na tyldę (~)
    • opcjonalne wystąpienia ([ .. ]) na opt( .. )
    • powtórzenia ({ .. }) na rep( .. )

    Dodatkowo przed nazwą wstawiamy def (odwzorowując tym samym element na metodę) oraz usuwamy średnik na końcu (dla spójności – scala zezwala na stawianie średników na końcu linii, zatem nic by się nie stało gdyby tam został):

    def setMultiElem = "{" ~ opt( rep( integerNumber ~ "," ) ) ~ integerNumber ~ "}"
  2. Teraz szukamy możliwych uproszczeń.
    rep( .. ) oznacza zero lub więcej powtórzeń, zatem możemy usunąć niepotrzebny, otaczający eleemnt opt( .. ):

    def setMultiElem = "{" ~ rep( integerNumber ~ "," ) ~ integerNumber ~ "}"

    Możemy jeszcze zastąpić wyrażenie rep( integerNumber ~ “,” ) ~ integerNumber przez repsep( integerNumber, “,” ), czyli powtórzenia integerNumber z “,” w roli separatora. RepSep działa na tyle sprytnie, że mogliśmy rówież wyciąć fragment ~ integerNumber za powtórzeniem:

    def setMultiElem = "{" ~ repsep( integerNumber, "," ) ~ "}"
  3. Jeśli element składa się z literału, który służy tylko przypasowaniu wzorca i nie będzie nam więcej potrzebny, możemy symbol ~ zamienić na ~> lub <~. Wtedy wszystko co znajduje się po przeciwnej stronie względem grota takiej strzałki (~> / <~) zostanie zignorowane w dalszym przetwarzaniu:
    def setMultiElem = "{" ~> repsep( integerNumber, "," ) <~ "}"

Czynność powtarzamy dla wszystkich elementów, w wyniku otrzymując:

def expr = (set | subExpr) ~ rep(op ~ (set | subExpr))
def subExpr = "(" ~ expr ~ ")"
def op = "[" | "!" | '"' | "#" | "$" | .. | "y" | "z"
def set = setMultiElem | setSingleElem
def setSingleElem = integerNumber
def setMultiElem = "{" ~ repsep(integerNumber, ',') ~ "}"
def integerNumber = opt( "+" | "-" ) ~ rep( "1" | "2" | "3" | .. | "8" | "9" | "0" )

Powyższy kod umieścimy w obiekcie SetNotationParser.

Metody rep, opt czy repsep zdefiniowane są w traicie Parsers (http://www.scala-lang.org/api/current/index.html#scala.util.parsing.combinator.Parsers), który powinniśmy ‘domieszać‘ do naszego obiektu.
Ja nie będę dziedziczył po Parser, tylko jego pośrednim potomku – JavaTokenParsers (http://www.scala-lang.org/api/current/index.html#scala.util.parsing.combinator.JavaTokenParsers), dzięki czemu będę mógł wykorzystać istniejącą metodę ‘wholeNumber‘ zamiast definiować własną ‘integerNumber‘.
Dodatkowo w ‘op‘ użyję wyrażenia regularnego.

Tak wygląda kod obiektu SetNotationParser w tym momencie:

package pl.mkubala.sets.parser

import scala.util.parsing.combinator.JavaTokenParsers
import pl.mkubala.sets.SetExpression
import pl.mkubala.sets.SetBinOp
import pl.mkubala.sets.SetDef

object SetNotationParser extends JavaTokenParsers {

  def expr = (set | subExpr) ~ rep(op ~ (set | subExpr))

  def subExpr = "(" ~ expr ~ ")"

  def op = """[!"#$%&'*+./:;<=>?@\^_`|~\-\\A-Za-z]+""".r

  def set = setMultiElem | setSingleElem

  def setSingleElem = wholeNumber

  def setMultiElem = "{" ~ repsep(wholeNumber, ',') ~ "}"

  def parse(literalSetExpression: String): SetExpression = SetDef(Set())

}

Nasze metody w tym momencie zwracają obiekty Parser[Any], a my chcemy aby zwracały Parser[SetExpression]. Próba zadeklarowania zwracanego typu dla większości metod zakończy się następującym błędem:

type mismatch; 
found : 
  pl.mkubala.sets.parser.SetNotationParser.Parser[String] 
required: 
  pl.mkubala.sets.parser.SetNotationParser.Parser[pl.mkubala.sets.SetExpression]
Konwertujemy wynik dopasowania na elementy drzewa wyrażenia

Przytoczony wyżej błąd wskazuje nam, że wynik działania metody musimy jeszcze przetworzyć. Wykorzystamy w tym celu składnię:

def elemParser = jakis ~ wzorzec ^^ funkcja_przetwarzająca_wynik

Zacznijmy od najprostszego elementu:

def setSingleElem: Parser[SetExpression] = wholeNumber ^^ { num => SetDef(Set(num.toInt)) }

W argumencie funkcji dostajemy sparsowany string zawierający liczbę całkowitą. Tworzymy instancję SetDef opakowującą jednoelementowy zbiór zawierający tę liczbę.

Teraz przykład przetwarzania wyniku repsep:

def setMultiElem: Parser[SetExpression] = "{" ~> repsep(wholeNumber, ',') <~ "}" ^^
    { setElements => SetDef(Set() ++ setElements map (_.toInt)) }

repsep( .. ) zwraca nam sekwencję (konkretnie to listę) elementów rozdzielonych zadanym separatorem. Podobnie jak w poprzednim przykładzie tworzymy instancję SetDef i przekazujemy do niej zbiór liczb, który otrzymaliśmy przez wstawienie listy (otrzymanej poprzez transformację oryginalnej listy łańcuchów znaków na listę liczb całkowitych z pomocą funkcji _.toInt (oznaczającej to samo co elem => elem.toInt)) do pustego zbioru.

Ponieważ zarówno setSingleElem jak i setMultiElem zwracają nam obiekt SetExpression, to nie jest wymagane żadne przetwarzanie wyniku set:

def set: Parser[SetExpression] = setMultiElem | setSingleElem

Podobnie jest w przypadku subExpr (wiemy, że expr zwróci nam SetExpression):

def subExpr: Parser[SetExpression] = "(" ~> expr <~ ")"

Pamiętasz definicję klasy SetBinOp? Jako drugi argument przyjmowała ona String reprezentujący symbol operacji:

case class SetBinOp(leftBranch: SetExpression, opSymbol: String, rightBranch: SetExpression) extends SetExpression

Zatem metoda “op” powinna zwracać Parser[String], co oznacza, że przetwarzanie wyniku nie będzie konieczne:

def op: Parser[String] = """[!"#$%&'*+./:;<=>?@\^_`|~\-\\A-Za-z]+""".r

Na koniec expr – wyrażenie “(set | subExpr) ~ rep(op ~ (set | subExpr))” może nam zwrócić:

  1. SetExpression ~ Nil (Nil oznacza pustą listę i jest tożsamy z List()) w przypadku gdy w wyrażeniu nie występuje żadne powtórzenie op ~ (set | subExpr), np. “{1, 2, 3}
  2. SetExpression ~ List(SetExpression, ..) w przeciwnym wypadku, np.: “{1, 2, 3} ^ {3, 4, 5}“, “{1, 2, 3} ^ {3, 4, 5} ^ {3, 7, 5, 8}“, czy “{3, 5, 8} ^ ({3, 4, 5} v {6, 7, 8})

W pierwszym przypadku powinniśmy po prostu zwrócić pierwsze wyrażenie SetExpression.
Natomiast w drugim będziemy musieli zmapować kolejne operacje na instancje SetBinOp:

def expr: Parser[SetExpression] = (set | subExpr) ~ rep(op ~ (set | subExpr)) ^^ {
  case first ~ Nil => first
  case first ~ rest => (rest foldLeft (first))((left, right) =>
    right match {
      case op ~ next => SetBinOp(left, op, next)
    })
}

Dla drugiego przypadku użyłem metody foldLeft w celu ‘zwinięcia‘ kolekcji. Nie będę się rozpisywał na jej temat, bardzo dobre jej omówienie (po polsku) można znaleźć w artykuje na Polskim Portalu Scala (http://scala.net.pl/ukryta-potega-foldleft/)

Cały kod wygląda następująco:

package pl.mkubala.sets.parser

import scala.util.parsing.combinator.JavaTokenParsers
import pl.mkubala.sets.SetExpression
import pl.mkubala.sets.SetBinOp
import pl.mkubala.sets.SetDef

object SetNotationParser extends JavaTokenParsers {

  def expr: Parser[SetExpression] = (set | subExpr) ~ rep(op ~ (set | subExpr)) ^^ {
    case first ~ Nil => first
    case first ~ rest => (rest foldLeft (first))((left, right) =>
      right match {
        case op ~ next => SetBinOp(left, op, next)
      })
  }

  def subExpr: Parser[SetExpression] = "(" ~> expr <~ ")"

  def op: Parser[String] = """[!"#$%&'*+./:;<=>?@\^_`|~\-\\A-Za-z]+""".r

  def set: Parser[SetExpression] = setMultiElem | setSingleElem

  def setSingleElem: Parser[SetExpression] = wholeNumber ^^ { num => SetDef(Set(num.toInt)) }

  def setMultiElem: Parser[SetExpression] = "{" ~> repsep(wholeNumber, ',') <~ "}" ^^
    { setElements => SetDef(Set() ++ setElements map (_.toInt)) }

  def parse(literalSetExpression: String): SetExpression = SetDef(Set())

}

Nasze testy wciąż nie działają, ponieważ niezależnie od tego co podamy w argumencie metody parse zawsze otrzymamy drzewo, którego jedynym elementem będzie definicja pustego zbioru.
Zabierzmy się zatem za implementację tej metody.

Implementujemy SetNotationParser.parse(String)

Wykorzystamy metodę parseAll, której definicja zawarta jest w traicie Parsers.
Przyjmuje ona 2 argumenty – pierwszy z nich to funkcja (metoda to także rodzaj funkcji) zwracająca Parser[T], a druga to wejście (w naszym wypadku String, implementujący interfejs java.lang.CharSequence) i zwraca obiekt ParseResult (http://www.scala-lang.org/api/current/index.html#scala.util.parsing.combinator.Parsers$ParseResult).
W chwili pisania tej notki standardowo dostępne są następujące jego implementacje:

  • Error(msg: String, next: Input) – wystąpił krytyczny błąd. Nie użyto backtrackingu (http://en.wikibooks.org/wiki/Algorithms/Backtracking)
  • Failure(msg: String, next: Input) – j.w. z tym, że wykorzystano backtracking
  • NoSuccess(msg: String, next: Input) – abstrakcyjna klasa, reprezentująca niepowodzenie. Dziedzczą po niej Error oraz Failure.
  • Success[+T](result: T, next: Input) – parsowanie zakończyło się pomyślnie, pierwszym argumentem jest wynik zwrócony przez funkcję parsującą.

Nie mam powodu aby rozdrabniać się na Error i Failure, dlatego będę rozpatrywał bardziej generalny przypadek – NoSuccess. W przypadku jego wystąpienia będę wyrzucał IllegalArgumentException zawierający komunikat błędu parsera w atrybucie message.
W przypadku sukcesu po prostu zwrócę wynik (SetExpression będący korzeniem drzewa wyrażenia):

def parse(literalSetExpression: String): SetExpression = 
  parseAll(expr, literalSetExpression) match {
    case Success(res, _) => res
    case NoSuccess(msg, _) => throw new IllegalArgumentException(msg)
  }

Dodatkowo powinienem sprawdzać czy wejściowy ciąg znaków w ogóle zawiera jakiekolwiek wyrażenie – w przypadku jego braku mogę automatycznie zwrócić element reprezentujący definicję pustego zbioru:

def parse(literalSetExpression: String): SetExpression =
  if (literalSetExpression == null || (literalSetExpression.trim isEmpty)) {
    SetDef(Set())
  } else {
    parseAll(expr, literalSetExpression) match {
      case Success(res, _) => res
      case NoSuccess(msg, _) => throw new IllegalArgumentException(msg)
    }
  }

Ostateczny kod obiektu SetNotationParser wygląda następująco:

package pl.mkubala.sets.parser

import scala.util.parsing.combinator.JavaTokenParsers
import pl.mkubala.sets.SetExpression
import pl.mkubala.sets.SetBinOp
import pl.mkubala.sets.SetDef

object SetNotationParser extends JavaTokenParsers {

  def expr: Parser[SetExpression] = (set | subExpr) ~ rep(op ~ (set | subExpr)) ^^ {
    case first ~ Nil => first
    case first ~ rest => (rest foldLeft (first))((left, right) =>
      right match {
        case op ~ next => SetBinOp(left, op, next)
      })
  }

  def subExpr: Parser[SetExpression] = "(" ~> expr <~ ")"

  def op: Parser[String] = """[!"#$%&'*+./:;<=>?@\^_`|~\-\\A-Za-z]+""".r

  def set: Parser[SetExpression] = setMultiElem | setSingleElem

  def setSingleElem: Parser[SetExpression] = wholeNumber ^^ { num => SetDef(Set(num.toInt)) }

  def setMultiElem: Parser[SetExpression] = "{" ~> repsep(wholeNumber, ',') <~ "}" ^^
    { setElements => SetDef(Set() ++ setElements map (_.toInt)) }

  def parse(literalSetExpression: String): SetExpression =
    if (literalSetExpression == null || (literalSetExpression.trim isEmpty)) {
      SetDef(Set())
    } else {
      parseAll(expr, literalSetExpression) match {
        case Success(res, _) => res
        case NoSuccess(msg, _) => throw new IllegalArgumentException(msg)
      }
    }

}

I to byłby cały parser 🙂

Jeszcze tylko uruchomimy testy jednostkowe aby upewnić się czy wszystkie założenia zostały spełnione:

marcin@maku-pc:~/scala/sets-notation-interpreter$ sbt test
[info] Loading project definition from /home/marcin/scala/sets-notation-interpreter/project
[info] Set current project to SetsNotationInterpreter (in build file:/home/marcin/scala/sets-notation-interpreter/)
[info] Compiling 1 Scala source to /home/marcin/scala/sets-notation-interpreter/target/scala-2.10/classes...
[info] SetNotationParserTest:
[info] - should return empty set definition for null input string
[info] - should return empty set definition for empty input string
[info] - should return empty set definition for blank input string
[info] - should parse '{3}'
[info] - should parse '3'
[info] - should parse '{1,2,3}'
[info] - should parse '{1,2,3} ^ {3,4,5}'
[info] - should parse '{1,2,3}       ^     {3,4,5}'
[info] - should parse '{1,2,3} anyOperator#!? {3,4,5}'
[info] - should parse '{1,2,3} opA {3,4,5} opB {5,6,7}'
[info] - should results of '{1,2,3} opA {3,4,5} opB {5,6,7}' be equals to '({1,2,3} opA {3,4,5}) opB {5,6,7}'
[info] - should parse '{1,2,3} opA ({3,4,5} opB {5,6,7})'
[info] - should parse '{1,2,3} opA ({3,4,5} opB ({5,6,7} opC {7,8,9}))'
[info] - should parse '({1,2,3} opA {3,4,5}) opB ({5,6,7} opC {7,8,9})'
[info] - should throw exception for '{1,2,3'
[info] - should throw exception for '({1,2,3} op1 {3,4,5}))'
[info] Passed: : Total 16, Failed 0, Errors 0, Passed 16, Skipped 0
[success] Total time: 7 s, completed 2013-01-27 14:14:17

Sukces, pierwszy element układanki zwanej interpreterem jest już gotowy!

Podsumowanie

Nie wiem czy zwróciłeś uwagę, ale całą implementację parsera udało się zmieścić w około 30 linijkach (licząc także puste odstępy).
Również na uznanie zasługuje intuicyjność i prostota (podobieństwo do EBNF) samej składni Parser Combinators.
Nie był także wymagany żaden overhead w postaci konieczności poznania np. ANTLR i jego integracji – wszystko czego potrzebujemy to zapoznać się z dokumentacją biblioteki.

Kod źródłowy dostępny jest na guthubie pod adresem https://github.com/mkubala/sets-notation-interpreter

W kolejnej (i nieco krótszej) części cyklu zajmiemy się przetwarzaniem wynikowego drzewka na konkretny wynik.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s