Kompilator lub interpreter przetwarza kod źródłowy w formie tekstu, aby wyprodukować kod wynikowy. Ponieważ program nie rozumie “po polsku” to język programowania musi mieć odpowiednią formę, która następnie posłuży do wygenerowania algorytmu, który ten plik tekstowy przekształci na inną formę, łatwo rozumialną przez maszynę, czyli zazwyczaj abstrakcyjne drzewo składni. Ten process przetwarszania tekstu nazywamy parsowaniem.

Język opisany jest przez jego gramatykę. Najczęściej będzie to w formie produkcji. Poniżej przykład w notacji BNF

Num  ::= 1 | 2 | 3 | ...
Term ::= Num | '(' Exp ')'
Exp  ::= Exp '+' Mult | Mult
Mult ::= Mult '*' Term | Term

Powyższa to gramatyka konkretna (jednoznaczna) dla wyrażeń dodawania i mnożenia liczb, z zachowaniem kolejności wykonywania działań.

W przypadku mojego języka opis gramatyki (w formie Labeled BNF) ma 170 linii, a moduł parsujący niecałe 650. Nie będę więc przytaczał całości, ale zaprezentuję kilka ciekawszych elementów.

Lexer

Podstawowe pytanie jakie chcemy sobie zadać to czy nasz parser będzie pracować na tokenach, czy na znakach. Podejście tokenowe jest generalnie prostsze, a odpowiednie użycie biblioteki parsującej może pozwolić na mieszanie tych dwóch.

Token opisuje pojedyńczy element. Np. słowo kluczowe, operator, identyfikator, liczba, etc. Nasz parser będzie zjadać tokeny na koniec wypluwając struktury AST (abstract syntax tree) zgodnie z zaimplementowaną logiką.

Używanie tokenów powoduje, że nie musimy się martwić o białe znaki (whitespace), czyli spacje, taby, entery i komentarze. Jednocześnie powoduje, że użytkownik może pisać brzydki kod, nie wymuszając odstępów. Żeby to właściwie osiągnąć trzeba by było napisać bardziej zaawansowany lexer.

Ja będę korzystał z Haskellowej biblioteki Parsec

import Text.Parsec
import Text.Parsec.String
import qualified Text.Parsec.Token as Tok
import Text.Parsec.Language

A następnie utworzę definicję języka, który posłuży do stworzenia lexera

lexer :: Stream s m Char => Tok.GenTokenParser s u m
lexer = Tok.makeTokenParser $ emptyDef{
            Tok.commentStart = "(*",
            Tok.commentEnd = "*)",
            Tok.commentLine = "//",
            Tok.nestedComments = True,
            Tok.identStart = letter <|> char '_',
            Tok.identLetter = alphaNum <|> char '_',
            Tok.opStart = oneOf ":!#$%&*+/<=>?\\^|-~",
            Tok.opLetter = oneOf ":!#$%&*+./<=>?@\\^|-~",
            Tok.reservedNames = [
                "let", "with", "in", "match", "type",
                "data", "if", "then", "else", "do"
            ],
            Tok.reservedOpNames = [
                "(", ")", "_", "=", "@", "::", ",", "{",
                "}", ";", "|", "->", "[", "]", "()",
                ".", "..", "\\", "<-", "..."
            ]
        }

Następnie mogę używać funkcji lexera wymienionych tutaj do parsowania i lexowaniu treści pliku z kodem źródłowym.

Parsowanie literałów i identyfikatorów

Parser Parseca jest monadą. Haskellowe monady są nieco bardziej zaawansowane niż monady w F#, ponieważ Haskell pozwala na klasy typów i uogólnienie pewnych zachowań. Tak czy siak polecam przeczytać moje wprowadzenie do monad (tu >>= to bind).

Poniżej przykład parsera literałów. Robimy sparsuj wartość >>= opakuj w obiekt AST i zwróć. Dodatkowo korzystam z operatora <|>, który w przypadku niepowodzenia lewej strony wykonuje prawą stronę. I jest jeszcze funkcja try, która w przypadku błędów cofa parser, żeby wypluł znaki, które zjadł przed wystąpieniem błędu.

pLiteral :: Stream s m Char => ParsecT s u m Literal
pLiteral =
    (stringLiteral >>= return . AST.String)
    <|> (charLiteral >>= return . AST.Char)
    <|> try (float >>= return . AST.Float)
    <|> try (integer >>= return . AST.Integer)
    <|> try (reservedOp "()" >> return UnitValue)

Jeszcze pokażę mój parser identyfikatorów, który korzysta z monadycznej notacji do. Oprócz stringa id zgodnego z regułą języka lexera, zapisuję też pozycję jego występowania.

pIdentifier :: Stream s m Char => ParsecT s u m Identifier
pIdentifier = do
    pos <- getPosition
    id <- identifier
    return $ Identifier id pos

Notacja do działa tak, że do x <- m; b x <=> m >>= b. A $ to taki lewostronny pipe <|.

Parsowanie wyrażeń operatorów

Parsując wyrażenia z operatorami, należy pamiętać o dwóch rzeczach: priorytet i lewo/prawo-stronność. Mnożenie wiąże mocniej niż dodawanie, a potęgowanie mocniej niż mnożenie.

Mój parser operatorów jest generowany na podstawie listy list operatorów o tym samym priorytecie. Najpierw parsujemy wyrażenie z operatorami o wyższych priorytetach i wyrażenia bez operatorów, potem operator, drugie wyrażenie i być może znowu operator i kolejne wyrażenie, rekurencyjnie. Kilka operatorów jest lewo-stronnych, reszta jest prawo-stronna, a wpływa to na ten moment rekurencyjności. Albo od razu tworzymy wyrażenie z operatorem i przekazujemy je jako lewa strona do wywołania rekurencyjnego, albo prawą stronę przekazujemy do wywołania rekurencyjnego, a jego rezultat używamy jako prawa strona naszego operatora.

Parsowanie typów funkcji i tupli

Podobnie jak w przypadku wyrażeń i operatorów, podzieliłem moje typy na dwie kategorie: jednoznaczne i operatorowe. Najpierw wczytujemy typ jednoznaczny (bo jest on składową typu operatorowego), potem patrzymy czy jest operator -> lub * i jak tak to parsujemy kolejny typ, a jak nie to zwracamy to co już sparsowaliśmy.

Parsowanie list i krotek

Tu wykorzystałem wbudowaną funkcję sepBy oraz nawiasy i przecinek z lexera i uzyskałem coś takiego

pTupleExpr :: Stream s m Char => ParsecT s u m Expression
pTupleExpr = do
    pos <- getPosition
    parens (sepBy2 pExpression comma) >>= return . (ETuple pos)

pListExpr :: Stream s m Char => ParsecT s u m Expression
pListExpr = do
    pos <- getPosition
    brackets (sepBy pExpression comma) >>= return . (EList pos)

Gdzie krotka jest postaci (a,b,c), a lista [a,b,c]. (sepBy2 to mój wariant wymuszający conajmniej dwa elementy)

Uruchamianie parsera

Jak już skończymy pisać nasz parser to będziemy chceli dostać od użytkownika kod w postaci stringa (najczęsciej przez wczytanie pliku) i nasz parser na nim zapuścić.

parse mójParser nazwaPlikuDoŁadnychBłędów zawartośćPliku

To zwraca nam Either ParseError a, gdzie a jest typem obiektu zwracanego przez nasz parser. Either to albo Left error albo Right value.