Työkaluja

Kääntäjän rakentaminen on työläs ohjelmointiprojekti. Sopivilla työkaluilla ja ohjelmointimalleilla saa projektia helpotettua kuitenkin melkoisesti, mikä on erityisesti lyhyellä kurssilla hyväksi. Tässä muutamia välineitä eri kielille.

Luennoilla ja ohjauksissa ei toki ehditä käsittelemään näitä kaikkia, joten harkitse itse mitkä seuraavista opettelet vai teetkö kaiken käsin.

Tällä sivulla "minä" on VT vaikka molemmat sitä muokkaavat.

Haskell

Front end

Käytetään esimerkkinä seuraavaa minimaalista AST:tä:

Megaparsec

Megaparsec on jäsenninkombinaattorikirjasto, jota kehitetään parhaillaan Daan Leijenin alkuperäisen Parsec kirjaston korvaajaksi. Vaikkakin megaparsec vaatii alkuun hieman enemmän koodia kuin muut, lopputulos on helpompi ylläpitää (VT).

Megaparsec tukee myös sisennyspohjaisia kieliä (kuten python).

Tässä lyhyt tutoriaali

Trifecta

Trifecta on toinen jäsennyskombinaattorikirjasto. Trifektalle ei ole kunnollista tutoriaalia, mutta se tuottaa siinä määrin hyviä virheilmoituksia, että opettelu saattaa kannattaa.

Käyttöä aloitellessa tointaa huomata, että varsinaiset jäsenninkombinaattorit pitää asentaa erillisestä parsers -paketista.

Attoparsec

Attoparsec ei tuota kovin hyviä virheilmoituksia, mutta se on hyvin, hyvin nopea.

Tutoriaaleja:

Happy

LALR-jäsenningeneraattori vähän Yaccin tyyliin. AJK:n suosikki (joskaan ei ole käyttänyt sitä vuosiin). Linkitettyä sivustoa uudempi versio näyttäisi löytyvän ainakin GitHubista ja Hackagesta.

Middle end

Generics

Kääntäjää tehdessä AST:tä joutuu läpikäymään ja tarkastelemaan useampaan otteeseen, mikä suoraan tehtynä vaatii käsinkirjoitettuja rekursioita. Tässä kohtaa on hyvä turvautua johonkin monista generics kirjastoista, jolloin läpikäyntiä ei tarvitse kirjoittaa itse, tahi edes muuttaa AST:n kasvaessa.

Suosittelen käyttämään joko uniplatea tai, mikäli olet aiemmin käyttänyt Control.Lens pakettia, niin Control.Lens.Platedia.

Lyhyt esimerkki käyttäen uniplatea:

Ensin tietotyyppi:

{-#LANGUAGE DeriveDataTypeable#-}
module Expression where
import Data.Generics.Uniplate.Data
import Data.Data(Data)
import Data.Typeable


data AST = Var String
         | Const Integer
         | Parens AST
         | Negate AST
         | BinOp Op AST AST deriving (Eq, Show,Data,Typeable)
         
data Op = Add | Sub | Mul | Div deriving (Eq,Show,Data,Typeable)
*Main> -- Tehdään jonkinlainen lauseke
*Main> let expr = BinOp Sub (BinOp Add (Const 1) (BinOp Div (Const 4) (Const 6))) (Var "x")
*Main> -- Mitä muuttujia lausekkeessa on?
*Main> [v | Var v <- universe expr] 
["x"]
*Main> -- Entäpä vakioita?
*Main> [v | Const v <- universe expr]
[1,4,6]
*Main> -- Käännösvaiheessa olisi varmasti hyvä laskea auki vakiolaskutoimitukset,
       -- jotenka sievennetään kokeeksi yhteenlaskut:
*Main> :set -XLambdaCase
*Main> transform (\case {BinOp Add (Const n) (Const m) -> Const (n+m); x -> x}) expr
BinOp Sub (BinOp Add (Const 1) (BinOp Div (Const 4) (Const 6))) (Var "x")

Kuten voit huomata, tämä on hieman kätevämpää uniplatella kuin käsin:

findVars ast = case ast of
    Parens a₁ -> findVars a₁
    Negate a₁ -> findVars a₁
    BinOp op a₁ a₂ -> findVars a₁ ++ findVars a₁
    Var x -> [x]
    constant -> []

findConst ast = case ast of
    Parens a₁ -> findConst a₁
    Negate a₁ -> findConst a₁
    BinOp op a₁ a₂ -> findConst a₁ ++ findConst a₁
    Const x -> [x]
    var -> []

constantSum ast = case ast of
    Parens a₁ -> Parens (constantSum a₁)
    Negate a₁ -> Parens (constantSum a₁)
    BinOp Add (Const n) (Const m) -> Const (n+m)
    BinOp op a₁ a₂ -> BinOp op (constantSum a₁) (constantSum a₂)

Back end

LLVM-general ja LLVM-general-pure

LLVM, eli Low Level Virtual Machine, on kääntäjänrakennuskirjasto, joka toteuttaa työläimmät osat back endin luomisesta. LLVM on alunperin C++ kirjasto mutta sen Haskell käyttöliittymä on jopa siistimpi kuin alkuperäinen.

HUOM Koska LLVM oletuksena segfaulttaa (for speed!!) lähes kaikista virheistä, kuten esimerkiksi tyyppivirheellisen AST:n generoimisesta, niin LLVM-general on melkolailla hyödytön, ellei LLVM:ää ole käännetty vivulla --enable-assertions'. TL:DR: Jos saat segfaultteja, käännä LLVM uudestaan vivulla-enable-assertions`.

LLVM-general sisältää työkalut LLVM tavukoodin ja assemblerin ajamiseen, optimointiin ja kääntämiseen. LLVM-general-pure puolestaan on sivuvaikutukseton esitys LLVM:n sisäisestä esityksestä. Käytännössä kääntäjän back end syntyy näillä kirjastoilla tuottamalla ensin sopiva LLVM-general-pure modulin Module tietue ja syöttämällä se LLVM-general:n käännösfunktioille.

Siinä missä LLVM-general-pure:n käyttö on mukavaa tietuiden täyttelyä (melkein kuin veroilmoitusta täyttelisi!), niin LLVM-general on melko työläs käytettävä. Enemmittä selityksittä, näin ajetaan funktio, joka on määritelty LLVM-general-pure:n avulla:

sampleModule =
  Module "SampleModule" Nothing Nothing ..määritelmät..
  
withModule :: Context -> LLVM.General.AST.Module -> (LLVM.General.Module.Module -> IO ()) -> IO ()
withModule ctx mod fun = fin (withModuleFromAST ctx mod fun)
    where
     fin eop = runExceptT eop>>= either print return  

foreign import ccall "dynamic" 
  haskFun :: FunPtr (CDouble -> IO CDouble) -> (CDouble ->IO CDouble)  
  
executeLLVM :: IO ()
executeLLVM = do
      withContext $
        \ctx -> withMCJIT ctx optLevel model ptrelim fastins $
          \executionEngine -> withModule ctx sampleModule $
            \llvmModule -> withModuleInEngine executionEngine llvmModule $
              \ee -> do
                Just mainFun <- getFunction ee (Name ..mainin nimi..)
                
                -- Muunnetaan llvm:n luoma funktio-osoitin haskell funktioksi
                -- Tässä oletetaan, että funktio on tyyppiä CDouble -> IO CDouble
                let compiled = haskFun (castFunPtr mainFun :: FunPtr (CDouble -> IO CDouble)) 42
                
                -- Ajetaan ohjelma. 
                res <- compiled 42
                print res

Java

Etupää

JFlex

Flex-tyylinen selaingeneraattori. Toimii mukavasti ja on helposti yhdistettävissä CUP-jäsentimeen.

CUP

AJK:n suosikki Javan LALR-jäsenningeneraattoreista. Yacc-mainen siinä mielessä, että produktioihin voi liittää varsin vapaasti Java-koodia, jossa voi tehdä melkein mitä haluaa, esim. rakentaa AST:n.

SableCC

Selain- ja jäsenningeneraattori (LALR), jonka tuotos johtaa syötteestä valmiin AST:n. Näyttää olevan aika kuollut projekti nykyään, mutta tutustumisen arvoinen vaihtoehto silti.

ANTLR

\(LL(*)\)-jäsenningeneraattori, varsin uniikki vekotin. Kykenee tuottamaan myös selaimen, ja oletuksena sen tuottama jäsennin johtaa syötteestä konkreetin jäsennyspuun. ANTLR:ssä on myös työkaluja jäsennyspuun tutkimiseen ja läpikäyntiin. \(LL\)-jäsennystekniikasta huolimatta myös vasenrekursiiviset produktiot toimivat. AJK ei ole ANTLRia koskaan käyttänyt, mutta sillä on laaja ja aktiivinen käyttäjäkunta.

ANTLR on kirjoitettu Javalla, ja se kykenee tuottamaan jäsentimiä seuraaville isäntäkielille: Java, C#, Python ja JavaScript.

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.