Wyrażenia regularne kontra parsery

16 minut(y)

Wyrażenia regularne słyną z tego, że są trudne i mało czytelne. Czy są dla nich jakieś alternatywy? Tak, są to parsery.

Rodzaje parserów

Z grubsza najczęściej występujące parsery można podzielić na zstępujące (ang. top-down parsers) i wstępujące (ang. bottom-up parsers). Dla języków programowania głównymi przedstawicielami parserów zstępujących są parsery LL, a parserów wstępujących - parsery LR (które dalej dzielą się na kanoniczne parsery LR, parsery SLR, i parsery LALR). Parsery LL czytają tekst od lewej i analizują także od lewej. Parsery LR czytają tekst od lewej i analizują od prawej.

Historycznie pierwsze były parsery LL. Jednak parsery LR są wydajniejsze niż parsery LL. Dlatego parsery LR wyparły prawie całkowicie parsery LL z zastosowań profesjonalnych, czyli przy tworzeniu języków programowania ogólnego przeznaczenia. Wadą parserów LR jest jednak to, że bardzo trudno jest pisać ręcznie w przeciwieństwie do parserów LL, które wręcz idealnie pisze się ręcznie. Dlatego do implementowania prostych języków DSL lepsze są parsery LL.

Dla Haskella istnieją cztery popularne biblioteki do pisania parserów (plus co najmniej drugie tyle mniej popularnych):

Z mniej popularnych można wymienić:

Happy & Alex

Happy & Alex haskellowe wersje klasycznej pary Yacc i Lex (lub ich darmowych odpowiedników Bison i Flex). Jedyne w tym zestawieniu pozwalają na używanie gramatyk LR. Wadą pary Happy & Alex jest to, że trzeba napisać gramatykę, czyli nauczyć się nowego języka niewiele ładniejszego niż wyrażenia regularne.

Parsec i MegaParsec

Parsec jest to klasyczna haskellowa biblioteka do pisania parserów oraz klasyczny przedstawiciel biblioteki kombinatorów parserów (ang. Parser combinator). Biblioteki kombinatory parserów są dedykowane do ręcznego pisania parserów. Tak utworzone parsery są bardzo podobne do parserów LL i posiadają ich zalety, jednocześnie eliminując wady parserów LL, czyli problem lewostronnej rekurencji. Parsec niestety nie jest już rozwijany. Zamiast tego jest rozwijana jego ulepszona wersja, czyli MegaParsec.

AttoParsec

AttoParsec to biblioteka oryginalnie pomyślana do parsowania logów na bieżąco. Jest szybsza niż MegaParsec czy Parsec oraz jako jedyna umożliwia parsowanie przyrastającego pliku linia po linii. Niestety jest też o wiele uboższa w składni, przez co jest uważana za dobrą do parsowania plików o prostszej strukturze. Ubogość składni przekłada się także na prostszą strukturę samej biblioteki. Dzięki czemu o wiele prościej się jej nauczyć.

Tekst o prostej strukturze

Ponieważ moim marzeniem jest skompilowanie C do BrainFucka. Jako przykład nie będziemy parsować logów, tylko plik z językiem asemblera. Wcześniej jednak zobaczmy rodzaje języków asemblera.

Rodzaje języków assemblera

Składnia języka asemblera jest mocno powiązana z modelem programowym procesora (ang. Instruction set architecture, [ISA]).

Trzy najczęściej spotykane typy modeli programowych procesora to:

  • CISC (ang. Complex Instruction Set Computing)
  • RISC (ang. Reduced Instruction Set Computing)
  • MISC (ang. Minimal Instruction Set Computing)

CISC historycznie był pierwszym modelem. Charakteryzował się skomplikowanymi rozkazami ze skomplikowanymi sposobami adresowania. Miało to ułatwić pisanie kompilatorów. Nie ułatwiło. Żyjącym przedstawicielem tego modelu jest x86. Także mikroprocesor 8051 bywa uważany za przedstawiciela modelu CISC.

RISC został stworzony jako reakcja na to, że model CISC okazał się jednak ślepą uliczką. Skomplikowane rozkazy i sposoby adresowania nie pomagały w pisaniu kompilatorów. W związku z tym postanowiono pójść w drugą skrajność maksymalnie upraszczając listę rozkazów oraz sposoby adresowania. Wynikiem tego była prostsza jednostka arytmetyczno-logiczna. Zaoszczędzone tranzystory przeznaczano na większą ilość rejestrów ogólnego przeznaczenia. Prawdopodobnie najpopularniejszym przedstawicielem tego modelu jest ARM. Także mikroprocesory AVR bywają uważane za przedstawicieli modelu RISC.

MISC był rozwijany niezależnie. Charakteryzuje się bardzo małą ilością rozkazów. Niektóre języki assemblera MISC wyglądają wręcz jak języki ezoteryczne.

Nie jest to w zasadzie wymagane, ale zwykle maszyny MISC to maszyny stosowe nie posiadające rejestrów, tylko wszystkie operacje wykonujące na stosie. Rozwiązuje to także problem adresowania, bo większość operacji wykonywanych na stosie to rozkazy 0-adresowe, ewentualnie 1-adresowe.

Co ciekawe rzeczywiste procesory są rzadko budowane jako maszyny stosowe. Prawdopodobnie najbardziej znanym procesorem stosowym był Transputer. Także koprocesor matematyczny był maszyną stosową.

O wiele częściej maszynami stosowymi są maszyny wirtualne jak [JVM], Wirtualna Maszyna Perla czy WebAssembly. Wiele języków ezoterycznych jak ETA, False, Funge, Piet, [WhiteSpace] to języki stosowe. Istnieją też nieezoteryczne wysokopoziomowe języki stosowe (ang. stack-based) jak dc, Joy, Forth, Mouse, PostScript i RPL.

Najprostszy możliwi zestaw instrukcji dla maszyny stosowej został opisany jako A Minimal CISC). Zawiera on tylko 8 instrukcji. Ja jednak zdecydowałem się na inny zestaw instrukcji będący językiem ezoterycznym ETA.

ETA i EAS

Język ETA posiada także prosty assembler, i język asemblerowy o tej samej nazwie, EAS. Jest on co prawda zaimplementowany Perlu, ale przy pomocy wyrażeń regularnych. Oryginalny jest dostępny tutaj, a mirror tutaj.

Struktura asemblera, czyli programu asemblującego (montującego)

Cztery główne moduły asemblera to:

  • Parser asemblera EAS
  • Konsolidator (ang. Linker)
  • Reduktor (ang. Reducer) instrukcji
  • Generator kodu wynikowego, czyli kodu ETA
assemblyIO :: String -> String -> IO (Either String String)
assemblyIO dirName fileName = runExceptT $ assembly dirName fileName

assembly :: String -> String -> ExceptT String IO String
assembly dirName fileName = generateCode . reduce <$> link dirName fileName

Najpierw naprzemiennie następuje faza parsowania i konsolidacji. Następnie następuje redukcja instrukcji i generacja kodu docelowego.

Parser języka asemblera

Pierwszym modułem programu jest parser:

parseAssembler :: T.Text -> Either String InstructionList
parseAssembler = parseOnly instructionListParser

instructionListParser :: Parser InstructionList
instructionListParser = skipManyComment *> skipHorizontalSpace *> many (instructionParser <* skipHorizontalSpace)

Parser pobiera zmienną typu Text i w przypadku powodzenia zwraca listę sparsowanych instrukcji. W przypadku niepowodzenia zwraca mało intuicyjny komunikat o błędzie generowany przez bibliotekę AttoParsec.

Parsowanie pojedynczej instrukcji dzieli się na kilka przypadków:

instructionParser :: Parser Instruction
instructionParser =
  try zeroOperandInstructionParser
  <|> naturalNumberParser
  <|> unescapedStringParser
  <|> labelDefinitionParser
  <|> includeFileParser
  <|> lineBreakParser
  <|> commentParser

Czyli:

  • parsowanie instrukcji bezargumentowej
  • parsowanie liczby naturalnej
  • parsowanie literału stringa
  • parsowanie deklaracji etykiety
  • parsowanie dołączenia pliku
  • parsowanie końca linii
  • parsowanie komentarza

EAS jak to język assemblera dla maszyny stosowej zawiera wiele rozkazów bezargumentowych:

zeroOperandInstructionParser :: Parser Instruction
zeroOperandInstructionParser =
      zeroOperandInstruction E ["E", "dividE"]
  <|> zeroOperandInstruction T ["T", "Transfer"]
  <|> zeroOperandInstruction A ["A", "Address"]
  <|> zeroOperandInstruction O ["O", "Output"]
  <|> zeroOperandInstruction I ["I", "Input"]
  <|> zeroOperandInstruction S ["S", "Subtract"]
  <|> zeroOperandInstruction H ["H", "Halibut"]
    where zeroOperandInstruction i ts = i <$ (asciiCIChoices ts *> endWordParser)

Oryginalnie EAS posiada tylko jeden rozkaz jednoargumentowy. Jest tu umieszczenie liczby naturalnej na stosie. Przy czym liczbą może być wartość podana wprost, wartość literału znakowego lub adres etykiety. Ja rozszerzyłem to jeszcze o możliwość umieszczenie nieescepowanego literału znakowego na stosie. Dodatkowo posiada także możliwość dołączenia (ang. incluDe) pliku oraz zdefiniowania etykiety (ang. Label):

naturalNumberParser :: Parser Instruction
naturalNumberParser = N <$> (
      naturalValueParser
  <|> (asciiCI "N" *> skipHorizontalSpace *> naturalValueParser)
  <|> (asciiCI "Number" *> endWordParser *> skipHorizontalSpace *> naturalValueParser)
  )

unescapedStringParser :: Parser Instruction
unescapedStringParser = U <$> stringParser

labelDefinitionParser :: Parser Instruction
labelDefinitionParser = L <$> (char '>' *> identifierParser <* char ':')

includeFileParser :: Parser Instruction
includeFileParser = D <$> (char '*' *> fileNameParser <* char '\n')

Ponieważ w EAS znaki końca linii są znaczące to trzeba je parsować w sposób świadomy:

lineBreakParser :: Parser Instruction
lineBreakParser = R <$ (skipMany1EndLine *> skipManyComment)

commentParser :: Parser Instruction
commentParser = skipComment *> lineBreakParser

skipManyComment :: Parser [()]
skipManyComment = many (skipComment <* skipMany1EndLine)

skipComment :: Parser ()
skipComment = char commentChar *> skipAllToEndOfLine

skipMany1EndLine :: Parser String
skipMany1EndLine = many1 (char '\n')

Problem końca wyrazu (identyfikatora) to coś, co zajęło mi jeden wieczór. W wyrażeniach regularnych byłoby to proste \b. Tutaj jednak trzeba było napisać ręcznie funkcję wykrywania końca wyrazu oraz funkcję pobierającą wszystko przed końcem wyrazu. Ostatecznie stwierdziłem, że koniec wyrazu to albo biały znak, albo początek komentarza:

endWordParser :: Parser T.Text
endWordParser = takeTill isEndWord

isEndWord :: Char -> Bool
isEndWord c = isSpace c || (c == commentChar)

commentChar :: Char
commentChar = '#'

Konsolidator

Konsolidator (ang. linker) to program łączący pliki. Dołącza on plik biblioteczny w miejsce wystąpienia *nazwa_biblioteki.wsa:

link :: String -> String -> ExceptT String IO InstructionList
link dirName fileName = includeFiles $ ExceptT $ parseAssembler <$> T.readFile (dirName ++ "/" ++ fileName) where

  includeFiles :: ExceptT String IO InstructionList -> ExceptT String IO InstructionList
  includeFiles expect = loadFiles =<< expect

  loadFiles :: InstructionList -> ExceptT String IO InstructionList
  loadFiles il = concat <$> mapM loadFile il

  loadFile :: Instruction -> ExceptT String IO InstructionList
  loadFile (D libName) = link dirName libName
  loadFile i = pure [i]

Ponieważ dołączana biblioteka może zawierać inne biblioteki to funkcja link jest funkcją rekurencyjną.

Reduktor instrukcji

Redukcja siły operatorów (ang. Strength reduction) jest częścią optymalizacji. W naszym przypadku mamy redukcję skomplikowanych instrukcji na instrukcje proste. Reduktor instrukcji jest to w zasadzie uproszczony selektor instrukcji, który normalnie jest częścią generatora kodu docelowego.

Redukcja etykiet, czyli wyliczanie adresów skoków:

replaceLabels ::  LabelAddresses -> InstructionList -> InstructionList
replaceLabels addresses il = replaceLabel addresses <$> il

replaceLabel :: LabelAddresses -> Instruction -> Instruction
replaceLabel addresses (N (Variable l)) = N $ Literal $ findOrError l addresses
replaceLabel _          i               = i

Redukcja literałów stringów, czyli zamiana na literały znaków:

replaceStrings :: InstructionList -> InstructionList
replaceStrings il = replaceString =<< il

replaceString :: Instruction -> InstructionList
replaceString (U s) = charToInstruction <$> reverse s 
replaceString  i    = [i]

charToInstruction :: Char -> Instruction
charToInstruction c = N $ Literal $ fromIntegral $ ord c

Właściwy generator kodu docelowego

Ponieważ wszystkie potrzebne operacje zostały już wykonane, to właściwy generator kodu docelowego zamienia naszą zredukowaną listę instrukcji na język ETA:

generateCode :: InstructionList -> String
generateCode il = show . WhiteInstruction =<< il

newtype WhiteInstruction = WhiteInstruction Instruction

instance Show WhiteInstruction where
  show (WhiteInstruction (N (Literal  n))) = "N" ++ showValue n ++ "e"
  show (WhiteInstruction (N (Variable i))) = error $ show i
  show (WhiteInstruction (D i))            = error $ show i
  show (WhiteInstruction (U i))            = error $ show i
  show (WhiteInstruction (L _))            = ""
  show (WhiteInstruction R)                = "\n"
  show (WhiteInstruction i)                = show i

showValue :: Natural -> String
showValue value = naturalToChar <$> naturalToDigits7 value

naturalToChar :: Natural -> Char
naturalToChar index = ['h', 't', 'a', 'o', 'i', 'n', 's'] `genericIndex` index

Podsumowanie

AttoParsec jest prostą biblioteką. Czy tak samo prostą jak wyrażenia regularne? Tego nie wiem, ale na pewno jest dużo czytelniejszy. Jednocześnie AttoParsec posiada o wiele większe możliwości. Szkoda, że nie jest przeportowany do innych języków programowania niż Haskell.

Kod assemblera EAS jest dostępny na GitHubie. Kod interpretera ETA też jest dostępny na GitHubie.

Zostaw komentarz