Ostatnio wspomniałem o moim planie na stworzenie nowego języka programowania, który będzie “lepszym” C#/F#. Great# będzie językiem, w którym wcięcia są częścią gramatyki. Wobec tego potrzebuję narzędzia, aby taką gramatykę opisać i sparsować.

Zacząłem od przeszukiwania internetu, czy ktoś już czegoś nie zrobił, czego mógłbym użyć. Trafiłem na pracę Michela D. Adamsa z Portland State University o tytule Principled Parsing for Indentation-Sensitive Languages. W tej pracy opisany jest koncept gramatyki bezkontekstowej czułej na wcięcia oraz schemat algorytmu parsera dla takich gramatyk typu LALR. Moim zdaniem niektóre fragmenty tej pracy są nazbyt zawiłe i nie jestem w stanie zrozumieć w 100% podanych tam do wyjaśnień przykładów. Jednakże duża część jest jasna i postaram się ją poniżej skrócić.

IS-CFG

Bezkontekstowa gramatyka czuła na wcięcia (IS-CFG od Indentation Sensitive Contex Free Grammar) opisywana jest za pomocą czwórki (N, T, P, S), gdzie

• N to zbiór nieterminali (innymi słowy etykiet)
• T to zbiór terminali (znaków)
• P to zbiór produkcji
• S to nieterminal startowy (plus jego wcięcie)

P to pewna relacja ze zbioru N x ((N + T) x I)*, dla I będącego zbiorem relacji na wcięciach, w postaci

A -> X_1^(r_1) X_2^(r_2) ... X_n^(r_n)

W zasadzie chodzi o to, że jesli będąc na wcięciu k chcemy sparsować A to X_i musi być na pozycji j_i, takiej że (j_i, k) in r_i.

To wygląda bardzo skomplikowanie ale zaraz na przykładzie zobaczymy, że jest proste.

Weźmy język nawiasów

A -> '('(=)  A(>)  ')'(>=)
A ->

Będzie do niego należeć słowa:

1.
    ((()))
2.
    (
     (
      (
      )
     )
    )
3.
    (((        
      )
     )
    )

Zaczynając na pozycji 1 parsujemy A. Na tej samej pozycji musi być nawias otwierający. Następnie parsujemy kolejne A, którego pozycja jest większa od 1. To znaczy, że kolejny nawias otwierający będzie najwcześniej zaczynał się na pozycji 2. Po sparsowaniu A oczekujemy nawiasu zamykającego na pozycji 1 lub większej, a dla wewnętrznego A na pozycji 2 lub większej, itd.

Jeśli w tej gramatyce zamiast ')'(>=) zrobić ')'(=) to pierwsze słowo przestałoby być akceptowane.

Parsowanie

W pracy Adamsa oparto się na budowie parsera LALR opartego o stos. Potrzebny mi jest parser takich gramatyk w środowisku .NET, a przykładowa implementacja opierała się o Haskell (happy), co nie bardzo pozwala mi na jej wykorzystanie.

Wobec tego zacząłem przyglądać się jak wzbogacić FParsec - bibliotekę do tworzenia parserów kombinatorycznych w F# - tak, abym mógł napisać w nim generator parserów dla danej gramatyki albo chociaż usprawnić ręczne pisanie takich parserów, które respektują wcięcia.

Dwa dni kombinowania i coś mi się udało osiągnąć. Stworzyłem mini bibliotekę IndentFParsec, którą pewnie jeszcze ciut rozbuduję w trakcie prac nad Great#.

Testowałem ją na gramatyce

Stmts  ->    Stmt(=)  Stmts'(=)
Stmts' ->   Stmts(=)
Stmts' ->
Stmt   ->   Print(=)
Stmt   ->    Loop(=)
Print  -> "print"(=)  Ident(>)
Loop   ->  "loop"(=)  Ident(>) Int(>) Int(>) Stmts(>)

Przykładem dobrego programu jest

loop i 1 10
  print i
  loop j 1 5
    loop k 5 10 print j
                print k
print f

Używając tej mojej mini biblioteki tworzymy parser w taki sposób

loop = parse {
    let! pos = getPosition
    do! exact pos (keyword "loop")
    let! id = greater pos identifier
    let! min = greater pos integer
    let! max = greater pos integer
    let! stmts = greater pos statements
    return Loop(id, min, max, stmts)
}

Na początku bierzemy pozycję, a następnie dla każdego elementu prawej strony produkcji parsujemy go aplikując odpowiednią funkcję określającą relację w stosunku do pozycji z początku.

Ponieważ sporo jest tego pisania modyfikatorów pozycji, to widać miejsce na usprawnienia. Ale jeśli ten kod byłby generowany, no to w sumie nie boli.

Powyższy przykład został rozszerzony o wymuszanie nowej linii po loop id n m.

Pełny kod znajdziesz tu: manio143/IndentFParsec