歡迎光臨
每天分享高質量文章

用 350 行程式碼從零開始,將 Lisp 編譯成 JavaScript | Linux 中國

我們將會在本篇文章中看到從零開始實現的編譯器,將簡單的類 LISP 計算語言編譯成 JavaScript。
— Gil Mizrahi


致謝
編譯自 | 
https://gilmi.me/blog/post/2016/10/14/lisp-to-js
 
 作者 | Gil Mizrahi
 譯者 | 周家未 (BriFuture) ????共計翻譯:27.0 篇 貢獻時間:864 天

我們將會在本篇文章中看到從零開始實現的編譯器,將簡單的類 LISP 計算語言編譯成 JavaScript。完整的原始碼在 這裡[1]

我們將會:

1. 自定義語言,並用它編寫一個簡單的程式
2. 實現一個簡單的解析器組合器
3. 為該語言實現一個解析器
4. 為該語言實現一個美觀的列印器
5. 為我們的用途定義 JavaScript 的一個子集
6. 實現程式碼轉譯器,將程式碼轉譯成我們定義的 JavaScript 子集
7. 把所有東西整合在一起

開始吧!

1、定義語言

Lisp 族語言最迷人的地方在於,它們的語法就是樹狀表示的,這就是這門語言很容易解析的原因。我們很快就能接觸到它。但首先讓我們把自己的語言定義好。關於我們語言的語法的正規化(BNF)描述如下:

  1. program ::= expr

  2. expr ::= <integer> | <name> | ([<expr>])

基本上,我們可以在該語言的最頂層定義運算式並對其進行運算。運算式由一個整數(比如 5)、一個變數(比如 x)或者一個運算式串列(比如 (add x 1))組成。

整數對應它本身的值,變數對應它在當前環境中系結的值,運算式串列對應一個函式呼叫,該串列的第一個引數是相應的函式,剩下的運算式是傳遞給這個函式的引數。

該語言中,我們保留一些內建的特殊形式,這樣我們就能做一些更有意思的事情:

let 運算式使我們可以在它的 body 環境中引入新的變數。語法如下:

  1. let ::= (let ([<letarg>]) <body>)

  2. letargs ::= (<name> <expr>)

  3. body ::= <expr>

lambda 運算式:也就是匿名函式定義。語法如下:

  1. lambda ::= (lambda ([<name>]) <body>)

還有一些內建函式: addmulsubdiv 和 print

讓我們看看用我們這門語言編寫的入門示例程式:

  1. (let

  2.  ((compose

  3.    (lambda (f g)

  4.      (lambda (x) (f (g x)))))

  5.  (square

  6.    (lambda (x) (mul x x)))

  7.  (add1

  8.    (lambda (x) (add x 1))))

  9.  (print ((compose square add1) 5)))

這個程式定義了 3 個函式:composesquare 和 add1。然後將計算結果的值 ((compose square add1) 5) 輸出出來。

我相信瞭解這門語言,這些資訊就足夠了。開始實現它吧。

在 Haskell 中,我們可以這樣定義語言:

  1. type Name = String

  2. data Expr

  3.  = ATOM Atom

  4.  | LIST [Expr]

  5.    deriving (Eq, Read, Show)

  6. data Atom

  7.  = Int Int

  8.  | Symbol Name

  9.    deriving (Eq, Read, Show)

我們可以解析用該語言用 Expr 定義的程式。而且,這裡我們添加了新資料型別 EqRead和 Show 等實體用於測試和除錯。你能夠在 REPL 中使用這些資料型別,驗證它們確實有用。

我們不在語法中定義 lambdalet 或其它的內建函式,原因在於,當前情況下我們沒必要用到這些東西。這些函式僅僅是 LIST (運算式串列)的更加特殊的用例。所以我決定將它放到後面的部分。

一般來說你想要在抽象語法中定義這些特殊用例 —— 用於改進錯誤資訊、禁用靜態分析和最佳化等等,但在這裡我們不會這樣做,對我們來說這些已經足夠了。

另一件你想做的事情可能是在語法中新增一些註釋資訊。比如定位:Expr 是來自哪個檔案的,具體到這個檔案的哪一行哪一列。你可以在後面的階段中使用這一特性,打印出錯誤定位,即使它們不是處於解析階段。

◈ 練習 1:新增一個 Program 資料型別,可以按順序包含多個 Expr
◈ 練習 2:向語法樹中新增一個定位註解。

2、實現一個簡單的解析器組合庫

我們要做的第一件事情是定義一個嵌入式領域專用語言Embedded Domain Specific Language(EDSL),我們會用它來定義我們的語言解析器。這常常被稱為解析器組合庫。我們做這件事完全是出於學習的目的,Haskell 裡有很好的解析庫,在實際構建軟體或者進行實驗時,你應該使用它們。megaparsec[2] 就是這樣的一個庫。

首先我們來談談解析庫的實現的思路。本質上,我們的解析器就是一個函式,接受一些輸入,可能會讀取輸入的一些或全部內容,然後傳回解析出來的值和無法解析的輸入部分,或者在解析失敗時丟擲異常。我們把它寫出來。

  1. newtype Parser a

  2.  = Parser (ParseString -> Either ParseError (a, ParseString))

  3. data ParseString

  4.  = ParseString Name (Int, Int) String

  5. data ParseError

  6.  = ParseError ParseString Error

  7. type Error = String

這裡我們定義了三個主要的新型別。

第一個,Parser a 是之前討論的解析函式。

第二個,ParseString 是我們的輸入或攜帶的狀態。它有三個重要的部分:

◈ Name: 這是源的名字
◈ (Int, Int): 這是源的當前位置
◈ String: 這是等待解析的字串

第三個,ParseError 包含瞭解析器的當前狀態和一個錯誤資訊。

現在我們想讓這個解析器更靈活,我們將會定義一些常用型別的實體。這些實體讓我們能夠將小巧的解析器和複雜的解析器結合在一起(因此它的名字叫做 “解析器組合器”)。

第一個是 Functor 實體。我們需要 Functor 實體,因為我們要能夠對解析值應用函式從而使用不同的解析器。當我們定義自己語言的解析器時,我們將會看到關於它的示例。

  1. instance Functor Parser where

  2.  fmap f (Parser parser) =

  3.    Parser (\str -> first f <$> parser str)

第二個是 Applicative 實體。該實體的常見用例是在多個解析器中實現一個純函式。

  1. instance Applicative Parser where

  2.  pure x = Parser (\str -> Right (x, str))

  3.  (Parser p1) (Parser p2) =

  4.    Parser $

  5.      \str -> do

  6.        (f, rest)   p1 str

  7.        (x, rest')

  8.        pure (f x, rest')

(註意:我們還會實現一個 Monad 實體,這樣我們才能使用符號

第三個是 Alternative 實體。萬一前面的解析器解析失敗了,我們要能夠提供一個備用的解析器。

  1. instance Alternative Parser where

  2.  empty = Parser (`throwErr` "Failed consuming input")

  3.  (Parser p1) (Parser p2) =

  4.    Parser $

  5.      \pstr -> case p1 pstr of

  6.        Right result -> Right result

  7.        Left  _      -> p2 pstr

第四個是 Monad 實體。這樣我們就能連結解析器。

  1. instance Monad Parser where

  2.  (Parser p1) >>= f =

  3.    Parser $

  4.     \str -> case p1 str of

  5.       Left err -> Left err

  6.       Right (rs, rest) ->

  7.         case f rs of

  8.           Parser parser -> parser rest

接下來,讓我們定義一種的方式,用於執行解析器和防止失敗的助手函式:

  1. runParser :: String -> String -> Parser a -> Either ParseError (a, ParseString)

  2. runParser name str (Parser parser) = parser $ ParseString name (0,0) str

  3. throwErr :: ParseString -> String -> Either ParseError a

  4. throwErr ps@(ParseString name (row,col) _) errMsg =

  5.  Left $ ParseError ps $ unlines

  6.    [ "*** " ++ name ++ ": " ++ errMsg

  7.    , "* On row " ++ show row ++ ", column " ++ show col ++ "."

  8.    ]

現在我們將會開始實現組合器,這是 EDSL 的 API,也是它的核心。

首先,我們會定義 oneOf。如果輸入串列中的字元後面還有字元的話,oneOf 將會成功,否則就會失敗。

  1. oneOf :: [Char] -> Parser Char

  2. oneOf chars =

  3.  Parser $ \case

  4.    ps@(ParseString name (row, col) str) ->

  5.      case str of

  6.        []     -> throwErr ps "Cannot read character of empty string"

  7.        (c:cs) ->

  8.          if c `elem` chars

  9.          then Right (c, ParseString name (row, col+1) cs)

  10.          else throwErr ps $ unlines ["Unexpected character " ++ [c], "Expecting one of: " ++ show chars]

optional 將會丟擲異常,停止解析器。失敗時它僅僅會傳回 Nothing

  1. optional :: Parser a -> Parser (Maybe a)

  2. optional (Parser parser) =

  3.  Parser $

  4.    \pstr -> case parser pstr of

  5.      Left _ -> Right (Nothing, pstr)

  6.      Right (x, rest) -> Right (Just x, rest)

many 將會試著重覆執行解析器,直到失敗。當它完成的時候,會傳回成功執行的解析器串列。many1 做的事情是一樣的,但解析失敗時它至少會丟擲一次異常。

  1. many :: Parser a -> Parser [a]

  2. many parser = go []

  3.  where go cs = (parser >>= \c -> go (c:cs)) pure (reverse cs)

  4. many1 :: Parser a -> Parser [a]

  5. many1 parser =

  6.  (:) <$> parser many parser

下麵的這些解析器透過我們定義的組合器來實現一些特殊的解析器:

  1. char :: Char -> Parser Char

  2. char c = oneOf [c]

  3. string :: String -> Parser String

  4. string = traverse char

  5. space :: Parser Char

  6. space = oneOf " \n"

  7. spaces :: Parser String

  8. spaces = many space

  9. spaces1 :: Parser String

  10. spaces1 = many1 space

  11. withSpaces :: Parser a -> Parser a

  12. withSpaces parser =

  13.  spaces *> parser spaces

  14. parens :: Parser a -> Parser a

  15. parens parser =

  16.     (withSpaces $ char '(')

  17.  *> withSpaces parser

  18.   (spaces *> char ')')

  19. sepBy :: Parser a -> Parser b -> Parser [b]

  20. sepBy sep parser = do

  21.  frst optional parser

  22.  rest many (sep *> parser)

  23.  pure $ maybe rest (:rest) frst

現在為該門語言定義解析器所需要的所有東西都有了。

◈ 練習 :實現一個 EOF(end of file/input,即檔案或輸入終止符)解析器組合器。

3、為我們的語言實現解析器

我們會用自頂而下的方法定義解析器。

  1. parseExpr :: Parser Expr

  2. parseExpr = fmap ATOM parseAtom fmap LIST parseList

  3. parseList :: Parser [Expr]

  4. parseList = parens $ sepBy spaces1 parseExpr

  5. parseAtom :: Parser Atom

  6. parseAtom = parseSymbol parseInt

  7. parseSymbol :: Parser Atom

  8. parseSymbol = fmap Symbol parseName

註意到這四個函式是在我們這門語言中屬於高階描述。這解釋了為什麼 Haskell 執行解析工作這麼棒。在定義完高階部分後,我們還需要定義低階別的 parseName 和 parseInt

我們能在這門語言中用什麼字元作為名字呢?用小寫的字母、數字和下劃線吧,而且名字的第一個字元必須是字母。

  1. parseName :: Parser Name

  2. parseName = do

  3.  c   oneOf ['a'..'z']

  4.  cs many $ oneOf $ ['a'..'z'] ++ "0123456789" ++ "_"

  5.  pure (c:cs)

整數是一系列數字,數字前面可能有負號 -

  1. parseInt :: Parser Atom

  2. parseInt = do

  3.  sign optional $ char '-'

  4.  num   many1 $ oneOf "0123456789"

  5.  let result = read $ maybe num (:num) sign of

  6.  pure $ Int result

最後,我們會定義用來執行解析器的函式,傳回值可能是一個 Expr 或者是一條錯誤資訊。

  1. runExprParser :: Name -> String -> Either String Expr

  2. runExprParser name str =

  3.  case runParser name str (withSpaces parseExpr) of

  4.    Left (ParseError _ errMsg) -> Left errMsg

  5.    Right (result, _) -> Right result

◈ 練習 1 :為第一節中定義的 Program 型別編寫一個解析器
◈ 練習 2 :用 Applicative 的形式重寫 parseName
◈ 練習 3 :parseInt 可能出現上限溢位情況,找到處理它的方法,不要用 read

4、為這門語言實現一個更好看的輸出器

我們還想做一件事,將我們的程式以原始碼的形式打印出來。這對完善錯誤資訊很有用。

  1. printExpr :: Expr -> String

  2. printExpr = printExpr' False 0

  3. printAtom :: Atom -> String

  4. printAtom = \case

  5.  Symbol s -> s

  6.  Int i -> show i

  7. printExpr' :: Bool -> Int -> Expr -> String

  8. printExpr' doindent level = \case

  9.  ATOM a -> indent (bool 0 level doindent) (printAtom a)

  10.  LIST (e:es) ->

  11.    indent (bool 0 level doindent) $

  12.      concat

  13.        [ "("

  14.        , printExpr' False (level + 1) e

  15.        , bool "\n" "" (null es)

  16.        , intercalate "\n" $ map (printExpr' True (level + 1)) es

  17.        , ")"

  18.        ]

  19. indent :: Int -> String -> String

  20. indent tabs e = concat (replicate tabs "  ") ++ e

◈ 練習 :為第一節中定義的 Program 型別編寫一個美觀的輸出器

好,目前為止我們寫了近 200 行程式碼,這些程式碼一般叫做編譯器的前端。我們還要寫大概 150 行程式碼,用來執行三個額外的任務:我們需要根據需求定義一個 JS 的子集,定義一個將我們的語言轉譯成這個子集的轉譯器,最後把所有東西整合在一起。開始吧。

5、根據需求定義 JavaScript 的子集

首先,我們要定義將要使用的 JavaScript 的子集:

  1. data JSExpr

  2.  = JSInt Int

  3.  | JSSymbol Name

  4.  | JSBinOp JSBinOp JSExpr JSExpr

  5.  | JSLambda [Name] JSExpr

  6.  | JSFunCall JSExpr [JSExpr]

  7.  | JSReturn JSExpr

  8.    deriving (Eq, Show, Read)

  9. type JSBinOp = String

這個資料型別表示 JavaScript 運算式。我們有兩個原子型別 JSInt 和 JSSymbol,它們是由我們這個語言中的 Atom 轉譯來的,我們用 JSBinOp 來表示二元操作,比如 + 或 *,用 JSLambda 來表示匿名函式,和我們語言中的 lambda expression(lambda 運算式) 一樣,我們將會用 JSFunCall 來呼叫函式,用 let 來引入新名字,用 JSReturn 從函式中傳回值,在 JavaScript 中是需要傳回值的。

JSExpr 型別是對 JavaScript 運算式的 抽象表示。我們會把自己語言中運算式的抽象表示 Expr 轉譯成 JavaScript 運算式的抽象表示 JSExpr。但為了實現這個功能,我們需要實現 JSExpr ,並從這個抽象表示中生成 JavaScript 程式碼。我們將透過遞迴匹配 JSExpr 實現,將 JS 程式碼當作 String 來輸出。這和我們在 printExpr 中做的基本上是一樣的。我們還會追蹤元素的作用域,這樣我們才可以用合適的方式縮排生成的程式碼。

  1. printJSOp :: JSBinOp -> String

  2. printJSOp op = op

  3. printJSExpr :: Bool -> Int -> JSExpr -> String

  4. printJSExpr doindent tabs = \case

  5.  JSInt    i     -> show i

  6.  JSSymbol name  -> name

  7.  JSLambda vars expr -> (if doindent then indent tabs else id) $ unlines

  8.    ["function(" ++ intercalate ", " vars ++ ") {"

  9.    ,indent (tabs+1) $ printJSExpr False (tabs+1) expr

  10.    ] ++ indent tabs "}"

  11.  JSBinOp  op e1 e2  -> "(" ++ printJSExpr False tabs e1 ++ " " ++ printJSOp op ++ " " ++ printJSExpr False tabs e2 ++ ")"

  12.  JSFunCall f exprs  -> "(" ++ printJSExpr False tabs f ++ ")(" ++ intercalate ", " (fmap (printJSExpr False tabs) exprs) ++ ")"

  13.  JSReturn expr      -> (if doindent then indent tabs else id) $ "return " ++ printJSExpr False tabs expr ++ ";"

◈ 練習 1 :新增 JSProgram 型別,它可以包含多個 JSExpr ,然後建立一個叫做 printJSExprProgram 的函式來生成程式碼。
◈ 練習 2 :新增 JSExpr 的新型別:JSIf,併為其生成程式碼。

6、實現到我們定義的 JavaScript 子集的程式碼轉譯器

我們快做完了。這一節將會建立函式,將 Expr 轉譯成 JSExpr

基本思想很簡單,我們會將 ATOM 轉譯成 JSSymbol 或者 JSInt,然後會將 LIST 轉譯成一個函式呼叫或者轉譯的特例。

  1. type TransError = String

  2. translateToJS :: Expr -> Either TransError JSExpr

  3. translateToJS = \case

  4.  ATOM (Symbol s) -> pure $ JSSymbol s

  5.  ATOM (Int i)    -> pure $ JSInt i

  6.  LIST xs -> translateList xs

  7. translateList :: [Expr] -> Either TransError JSExpr

  8. translateList = \case

  9.  []     -> Left "translating empty list"

  10.  ATOM (Symbol s):xs

  11.    | Just f lookup s builtins ->

  12.      f xs

  13.  f:xs ->

  14.    JSFunCall <$> translateToJS f traverse translateToJS xs

builtins 是一系列要轉譯的特例,就像 lambada 和 let。每一種情況都可以獲得一系列引數,驗證它是否合乎語法規範,然後將其轉譯成等效的 JSExpr

  1. type Builtin  = [Expr] -> Either TransError JSExpr

  2. type Builtins = [(Name, Builtin)]

  3. builtins :: Builtins

  4. builtins =

  5.  [("lambda", transLambda)

  6.  ,("let", transLet)

  7.  ,("add", transBinOp "add" "+")

  8.  ,("mul", transBinOp "mul" "*")

  9.  ,("sub", transBinOp "sub" "-")

  10.  ,("div", transBinOp "div" "/")

  11.  ,("print", transPrint)

  12.  ]

我們這種情況,會將內建的特殊形式當作特殊的、非第一類的進行對待,因此不可能將它們當作第一類函式。

我們會把 Lambda 運算式轉譯成一個匿名函式:

  1. transLambda :: [Expr] -> Either TransError JSExpr

  2. transLambda = \case

  3.  [LIST vars, body] -> do

  4.    vars'

  5.    JSLambda vars' <$> (JSReturn <$> translateToJS body)

  6.  vars ->

  7.    Left $ unlines

  8.      ["Syntax error: unexpected arguments for lambda."

  9.      ,"expecting 2 arguments, the first is the list of vars and the second is the body of the lambda."

  10.      ,"In expression: " ++ show (LIST $ ATOM (Symbol "lambda") : vars)

  11.      ]

  12. fromSymbol :: Expr -> Either String Name

  13. fromSymbol (ATOM (Symbol s)) = Right s

  14. fromSymbol e = Left $ "cannot bind value to non symbol type: " ++ show e

我們會將 let 轉譯成帶有相關名字引數的函式定義,然後帶上引數呼叫函式,因此會在這一作用域中引入變數:

  1. transLet :: [Expr] -> Either TransError JSExpr

  2. transLet = \case

  3.  [LIST binds, body] -> do

  4.    (vars, vals) letParams binds

  5.    vars'

  6.    JSFunCall . JSLambda vars' <$> (JSReturn <$> translateToJS body) traverse translateToJS vals

  7.   where

  8.    letParams :: [Expr] -> Either Error ([Expr],[Expr])

  9.    letParams = \case

  10.      [] -> pure ([],[])

  11.      LIST [x,y] : rest -> ((x🙂 *** (y:)) <$> letParams rest

  12.      x : _ -> Left ("Unexpected argument in let list in expression:\n" ++ printExpr x)

  13.  vars ->

  14.    Left $ unlines

  15.      ["Syntax error: unexpected arguments for let."

  16.      ,"expecting 2 arguments, the first is the list of var/val pairs and the second is the let body."

  17.      ,"In expression:\n" ++ printExpr (LIST $ ATOM (Symbol "let") : vars)

  18.      ]

我們會將可以在多個引數之間執行的運運算元轉譯成一系列二元運運算元。比如:(add 1 2 3) 將會變成 1 + (2 + 3)

  1. transBinOp :: Name -> Name -> [Expr] -> Either TransError JSExpr

  2. transBinOp f _ []   = Left $ "Syntax error: '" ++ f ++ "' expected at least 1 argument, got: 0"

  3. transBinOp _ _ [x]  = translateToJS x

  4. transBinOp _ f list = foldl1 (JSBinOp f) <$> traverse translateToJS list

然後我們會將 print 轉換成對 console.log 的呼叫。

  1. transPrint :: [Expr] -> Either TransError JSExpr

  2. transPrint [expr] = JSFunCall (JSSymbol "console.log") . (:[]) <$> translateToJS expr

  3. transPrint xs     = Left $ "Syntax error. print expected 1 arguments, got: " ++ show (length xs)

註意,如果我們將這些程式碼當作 Expr 的特例進行解析,那我們就可能會跳過語法驗證。

◈ 練習 1 :將 Program 轉譯成 JSProgram
◈ 練習 2 :為 if Expr Expr Expr 新增一個特例,並將它轉譯成你在上一次練習中實現的 JSIf 條件陳述句。

7、把所有東西整合到一起

最終,我們將會把所有東西整合到一起。我們會:

1. 讀取檔案
2. 將檔案解析成 Expr
3. 將檔案轉譯成 JSExpr
4. 將 JavaScript 程式碼傳送到標準輸出流

我們還會啟用一些用於測試的標誌位:

◈ --e 將進行解析並打印出運算式的抽象表示(Expr
◈ --pp 將進行解析,美化輸出
◈ --jse 將進行解析、轉譯、並打印出生成的 JS 運算式(JSExpr)的抽象表示
◈ --ppc 將進行解析,美化輸出併進行編譯
  1. main :: IO ()

  2. main = getArgs >>= \case

  3.  [file] ->

  4.    printCompile =<< readFile file

  5.  ["--e",file] ->

  6.    either putStrLn print . runExprParser "--e" =<< readFile file

  7.  ["--pp",file] ->

  8.    either putStrLn (putStrLn . printExpr) . runExprParser "--pp" =<< readFile file

  9.  ["--jse",file] ->

  10.    either print (either putStrLn print . translateToJS) . runExprParser "--jse" =<< readFile file

  11.  ["--ppc",file] ->

  12.    either putStrLn (either putStrLn putStrLn) . fmap (compile . printExpr) . runExprParser "--ppc" =<< readFile file

  13.  _ ->

  14.    putStrLn $ unlines

  15.      ["Usage: runghc Main.hs [ --e, --pp, --jse, --ppc ] "

  16.      ,"--e     print the Expr"

  17.      ,"--pp    pretty print Expr"

  18.      ,"--jse   print the JSExpr"

  19.      ,"--ppc   pretty print Expr and then compile"

  20.      ]

  21. printCompile :: String -> IO ()

  22. printCompile = either putStrLn putStrLn . compile

  23. compile :: String -> Either Error String

  24. compile str = printJSExpr False 0 <$> (translateToJS =<< runExprParser "compile" str)

大功告成。將自己的語言編譯到 JS 子集的編譯器已經完成了。再說一次,你可以在 這裡[1] 看到完整的源檔案。

用我們的編譯器執行第一節的示例,產生的 JavaScript 程式碼如下:

  1. $ runhaskell Lisp.hs example.lsp

  2. (function(compose, square, add1) {

  3.  return (console.log)(((compose)(square, add1))(5));

  4. })(function(f, g) {

  5.  return function(x) {

  6.    return (f)((g)(x));

  7.  };

  8. }, function(x) {

  9.  return (x * x);

  10. }, function(x) {

  11.  return (x + 1);

  12. })

如果你在自己電腦上安裝了 node.js,你可以用以下命令執行這段程式碼:

  1. $ runhaskell Lisp.hs example.lsp | node -p

  2. 36

  3. undefined

◈ 最終練習 : 編譯有多個運算式的程式而非僅編譯一個運算式。

via: https://gilmi.me/blog/post/2016/10/14/lisp-to-js

作者:Gil Mizrahi[4] 選題:oska874 譯者:BriFuture 校對:wxy

本文由 LCTT 原創編譯,Linux中國 榮譽推出

贊(0)

分享創造快樂

© 2024 知識星球   網站地圖