用 350 行代碼從零開始，將 Lisp 編譯成 JavaScript

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

我們將會：

自定義語言，並用它編寫一個簡單的程序
實現一個簡單的解析器組合器
為該語言實現一個解析器
為該語言實現一個美觀的列印器
為我們的用途定義 JavaScript 的一個子集
實現代碼轉譯器，將代碼轉譯成我們定義的 JavaScript 子集
把所有東西整合在一起

開始吧！

1、定義語言

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

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

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

整數對應它本身的值，變數對應它在當前環境中綁定的值，表達式列表對應一個函數調用，該列表的第一個參數是相應的函數，剩下的表達式是傳遞給這個函數的參數。

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

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

let ::= (let ([<letarg>]) <body>)
letargs ::= (<name> <expr>)
body ::= <expr>

lambda 表達式：也就是匿名函數定義。語法如下：

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

還有一些內建函數： add、mul、sub、div 和 print。

讓我們看看用我們這門語言編寫的入門示常式序：

(let
  ((compose
    (lambda (f g)
      (lambda (x) (f (g x)))))
  (square
    (lambda (x) (mul x x)))
  (add1
    (lambda (x) (add x 1))))
  (print ((compose square add1) 5)))

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

我相信了解這門語言，這些信息就足夠了。開始實現它吧。

在 Haskell 中，我們可以這樣定義語言：

type Name = String

data Expr
  = ATOM Atom
  | LIST [Expr]
    deriving (Eq, Read, Show)

data Atom
  = Int Int
  | Symbol Name
    deriving (Eq, Read, Show)

我們可以解析用該語言用 Expr 定義的程序。而且，這裡我們添加了新數據類型 Eq、Read 和 Show 等實例用於測試和調試。你能夠在 REPL 中使用這些數據類型，驗證它們確實有用。

我們不在語法中定義 lambda、let 或其它的內建函數，原因在於，當前情況下我們沒必要用到這些東西。這些函數僅僅是 LIST （表達式列表）的更加特殊的用例。所以我決定將它放到後面的部分。

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

另一件你想做的事情可能是在語法中添加一些注釋信息。比如定位：Expr 是來自哪個文件的，具體到這個文件的哪一行哪一列。你可以在後面的階段中使用這一特性，列印出錯誤定位，即使它們不是處於解析階段。

練習 1：添加一個 Program 數據類型，可以按順序包含多個 Expr
練習 2：向語法樹中添加一個定位註解。

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

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

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

newtype Parser a
  = Parser (ParseString -> Either ParseError (a, ParseString))

data ParseString
  = ParseString Name (Int, Int) String

data ParseError
  = ParseError ParseString Error

type Error = String

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

第一個，Parser a 是之前討論的解析函數。

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

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

第三個，ParseError 包含了解析器的當前狀態和一個錯誤信息。

現在我們想讓這個解析器更靈活，我們將會定義一些常用類型的實例。這些實例讓我們能夠將小巧的解析器和複雜的解析器結合在一起（因此它的名字叫做「解析器組合器」）。

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

instance Functor Parser where
  fmap f (Parser parser) =
    Parser (str -> first f <$> parser str)

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

instance Applicative Parser where
  pure x = Parser (str -> Right (x, str))
  (Parser p1) <*> (Parser p2) =
    Parser $
      str -> do
        (f, rest)  <- p1 str
        (x, rest&apos;) <- p2 rest
        pure (f x, rest&apos;)

（注意：我們還會實現一個 Monad 實例，這樣我們才能使用符號）

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

instance Alternative Parser where
  empty = Parser (`throwErr` "Failed consuming input")
  (Parser p1) <|> (Parser p2) =
    Parser $
      pstr -> case p1 pstr of
        Right result -> Right result
        Left  _      -> p2 pstr

第四個是 Monad 實例。這樣我們就能鏈接解析器。

instance Monad Parser where
  (Parser p1) >>= f =
    Parser $
     str -> case p1 str of
       Left err -> Left err
       Right (rs, rest) ->
         case f rs of
           Parser parser -> parser rest

接下來，讓我們定義一種的方式，用於運行解析器和防止失敗的助手函數：

runParser :: String -> String -> Parser a -> Either ParseError (a, ParseString)
runParser name str (Parser parser) = parser $ ParseString name (0,0) str

throwErr :: ParseString -> String -> Either ParseError a
throwErr ps@(ParseString name (row,col) _) errMsg =
  Left $ ParseError ps $ unlines
    [ "*** " ++ name ++ ": " ++ errMsg
    , "* On row " ++ show row ++ ", column " ++ show col ++ "."
    ]

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

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

oneOf :: [Char] -> Parser Char
oneOf chars =
  Parser $ case
    ps@(ParseString name (row, col) str) ->
      case str of
        []     -> throwErr ps "Cannot read character of empty string"
        (c:cs) ->
          if c `elem` chars
          then Right (c, ParseString name (row, col+1) cs)
          else throwErr ps $ unlines ["Unexpected character " ++ [c], "Expecting one of: " ++ show chars]

optional 將會拋出異常，停止解析器。失敗時它僅僅會返回 Nothing。

optional :: Parser a -> Parser (Maybe a)
optional (Parser parser) =
  Parser $
    pstr -> case parser pstr of
      Left _ -> Right (Nothing, pstr)
      Right (x, rest) -> Right (Just x, rest)

many 將會試著重複運行解析器，直到失敗。當它完成的時候，會返回成功運行的解析器列表。many1 做的事情是一樣的，但解析失敗時它至少會拋出一次異常。

many :: Parser a -> Parser [a]
many parser = go []
  where go cs = (parser >>= c -> go (c:cs)) <|> pure (reverse cs)

many1 :: Parser a -> Parser [a]
many1 parser =
  (:) <$> parser <*> many parser

下面的這些解析器通過我們定義的組合器來實現一些特殊的解析器：

char :: Char -> Parser Char
char c = oneOf [c]

string :: String -> Parser String
string = traverse char

space :: Parser Char
space = oneOf " n"

spaces :: Parser String
spaces = many space

spaces1 :: Parser String
spaces1 = many1 space

withSpaces :: Parser a -> Parser a
withSpaces parser =
  spaces *> parser <* spaces

parens :: Parser a -> Parser a
parens parser =
     (withSpaces $ char &apos;(&apos;)
  *> withSpaces parser
  <* (spaces *> char &apos;)&apos;)

sepBy :: Parser a -> Parser b -> Parser [b]
sepBy sep parser = do
  frst <- optional parser
  rest <- many (sep *> parser)
  pure $ maybe rest (:rest) frst

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

練習：實現一個 EOF（end of file/input，即文件或輸入終止符）解析器組合器。

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

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

parseExpr :: Parser Expr
parseExpr = fmap ATOM parseAtom <|> fmap LIST parseList

parseList :: Parser [Expr]
parseList = parens $ sepBy spaces1 parseExpr

parseAtom :: Parser Atom
parseAtom = parseSymbol <|> parseInt

parseSymbol :: Parser Atom
parseSymbol = fmap Symbol parseName

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

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

parseName :: Parser Name
parseName = do
  c  <- oneOf [&apos;a&apos;..&apos;z&apos;]
  cs <- many $ oneOf $ [&apos;a&apos;..&apos;z&apos;] ++ "0123456789" ++ "_"
  pure (c:cs)

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

parseInt :: Parser Atom
parseInt = do
  sign <- optional $ char &apos;-&apos;
  num  <- many1 $ oneOf "0123456789"
  let result = read $ maybe num (:num) sign of
  pure $ Int result

最後，我們會定義用來運行解析器的函數，返回值可能是一個 Expr 或者是一條錯誤信息。

runExprParser :: Name -> String -> Either String Expr
runExprParser name str =
  case runParser name str (withSpaces parseExpr) of
    Left (ParseError _ errMsg) -> Left errMsg
    Right (result, _) -> Right result

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

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

我們還想做一件事，將我們的程序以源代碼的形式列印出來。這對完善錯誤信息很有用。

printExpr :: Expr -> String
printExpr = printExpr&apos; False 0

printAtom :: Atom -> String
printAtom = case
  Symbol s -> s
  Int i -> show i

printExpr&apos; :: Bool -> Int -> Expr -> String
printExpr&apos; doindent level = case
  ATOM a -> indent (bool 0 level doindent) (printAtom a)
  LIST (e:es) ->
    indent (bool 0 level doindent) $
      concat
        [ "("
        , printExpr&apos; False (level + 1) e
        , bool "n" "" (null es)
        , intercalate "n" $ map (printExpr&apos; True (level + 1)) es
        , ")"
        ]

indent :: Int -> String -> String
indent tabs e = concat (replicate tabs "  ") ++ e

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

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

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

首先，我們要定義將要使用的 JavaScript 的子集：

data JSExpr
  = JSInt Int
  | JSSymbol Name
  | JSBinOp JSBinOp JSExpr JSExpr
  | JSLambda [Name] JSExpr
  | JSFunCall JSExpr [JSExpr]
  | JSReturn JSExpr
    deriving (Eq, Show, Read)

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 中做的基本上是一樣的。我們還會追蹤元素的作用域，這樣我們才可以用合適的方式縮進生成的代碼。

printJSOp :: JSBinOp -> String
printJSOp op = op

printJSExpr :: Bool -> Int -> JSExpr -> String
printJSExpr doindent tabs = case
  JSInt    i     -> show i
  JSSymbol name  -> name
  JSLambda vars expr -> (if doindent then indent tabs else id) $ unlines
    ["function(" ++ intercalate ", " vars ++ ") {"
    ,indent (tabs+1) $ printJSExpr False (tabs+1) expr
    ] ++ indent tabs "}"
  JSBinOp  op e1 e2  -> "(" ++ printJSExpr False tabs e1 ++ " " ++ printJSOp op ++ " " ++ printJSExpr False tabs e2 ++ ")"
  JSFunCall f exprs  -> "(" ++ printJSExpr False tabs f ++ ")(" ++ intercalate ", " (fmap (printJSExpr False tabs) exprs) ++ ")"
  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 轉譯成一個函數調用或者轉譯的特例。

type TransError = String

translateToJS :: Expr -> Either TransError JSExpr
translateToJS = case
  ATOM (Symbol s) -> pure $ JSSymbol s
  ATOM (Int i)    -> pure $ JSInt i
  LIST xs -> translateList xs

translateList :: [Expr] -> Either TransError JSExpr
translateList = case
  []     -> Left "translating empty list"
  ATOM (Symbol s):xs
    | Just f <- lookup s builtins ->
      f xs
  f:xs ->
    JSFunCall <$> translateToJS f <*> traverse translateToJS xs

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

type Builtin  = [Expr] -> Either TransError JSExpr
type Builtins = [(Name, Builtin)]

builtins :: Builtins
builtins =
  [("lambda", transLambda)
  ,("let", transLet)
  ,("add", transBinOp "add" "+")
  ,("mul", transBinOp "mul" "*")
  ,("sub", transBinOp "sub" "-")
  ,("div", transBinOp "div" "/")
  ,("print", transPrint)
  ]

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

我們會把 Lambda 表達式轉譯成一個匿名函數：

transLambda :: [Expr] -> Either TransError JSExpr
transLambda = case
  [LIST vars, body] -> do
    vars&apos; <- traverse fromSymbol vars
    JSLambda vars&apos; <$> (JSReturn <$> translateToJS body)

  vars ->
    Left $ unlines
      ["Syntax error: unexpected arguments for lambda."
      ,"expecting 2 arguments, the first is the list of vars and the second is the body of the lambda."
      ,"In expression: " ++ show (LIST $ ATOM (Symbol "lambda") : vars)
      ]

fromSymbol :: Expr -> Either String Name
fromSymbol (ATOM (Symbol s)) = Right s
fromSymbol e = Left $ "cannot bind value to non symbol type: " ++ show e

我們會將 let 轉譯成帶有相關名字參數的函數定義，然後帶上參數調用函數，因此會在這一作用域中引入變數：

transLet :: [Expr] -> Either TransError JSExpr
transLet = case
  [LIST binds, body] -> do
    (vars, vals) <- letParams binds
    vars&apos; <- traverse fromSymbol vars
    JSFunCall . JSLambda vars&apos; <$> (JSReturn <$> translateToJS body) <*> traverse translateToJS vals
   where
    letParams :: [Expr] -> Either Error ([Expr],[Expr])
    letParams = case
      [] -> pure ([],[])
      LIST [x,y] : rest -> ((x:) *** (y:)) <$> letParams rest
      x : _ -> Left ("Unexpected argument in let list in expression:n" ++ printExpr x)

  vars ->
    Left $ unlines
      ["Syntax error: unexpected arguments for let."
      ,"expecting 2 arguments, the first is the list of var/val pairs and the second is the let body."
      ,"In expression:n" ++ printExpr (LIST $ ATOM (Symbol "let") : vars)
      ]

我們會將可以在多個參數之間執行的操作符轉譯成一系列二元操作符。比如：(add 1 2 3) 將會變成 1 + (2 + 3)。

transBinOp :: Name -> Name -> [Expr] -> Either TransError JSExpr
transBinOp f _ []   = Left $ "Syntax error: &apos;" ++ f ++ "&apos; expected at least 1 argument, got: 0"
transBinOp _ _ [x]  = translateToJS x
transBinOp _ f list = foldl1 (JSBinOp f) <$> traverse translateToJS list

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

transPrint :: [Expr] -> Either TransError JSExpr
transPrint [expr] = JSFunCall (JSSymbol "console.log") . (:[]) <$> translateToJS expr
transPrint xs     = Left $ "Syntax error. print expected 1 arguments, got: " ++ show (length xs)

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

練習 1 ：將 Program 轉譯成 JSProgram
練習 2 ：為 if Expr Expr Expr 添加一個特例，並將它轉譯成你在上一次練習中實現的 JSIf 條件語句。

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

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

讀取文件
將文件解析成 Expr
將文件轉譯成 JSExpr
將 JavaScript 代碼發送到標準輸出流

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

--e 將進行解析並列印出表達式的抽象表示（Expr）
--pp 將進行解析，美化輸出
--jse 將進行解析、轉譯、並列印出生成的 JS 表達式（JSExpr）的抽象表示
--ppc 將進行解析，美化輸出並進行編譯

main :: IO ()
main = getArgs >>= case
  [file] ->
    printCompile =<< readFile file
  ["--e",file] ->
    either putStrLn print . runExprParser "--e" =<< readFile file
  ["--pp",file] ->
    either putStrLn (putStrLn . printExpr) . runExprParser "--pp" =<< readFile file
  ["--jse",file] ->
    either print (either putStrLn print . translateToJS) . runExprParser "--jse" =<< readFile file
  ["--ppc",file] ->
    either putStrLn (either putStrLn putStrLn) . fmap (compile . printExpr) . runExprParser "--ppc" =<< readFile file
  _ ->
    putStrLn $ unlines
      ["Usage: runghc Main.hs [ --e, --pp, --jse, --ppc ] <filename>"
      ,"--e     print the Expr"
      ,"--pp    pretty print Expr"
      ,"--jse   print the JSExpr"
      ,"--ppc   pretty print Expr and then compile"
      ]

printCompile :: String -> IO ()
printCompile = either putStrLn putStrLn . compile

compile :: String -> Either Error String
compile str = printJSExpr False 0 <$> (translateToJS =<< runExprParser "compile" str)

大功告成。將自己的語言編譯到 JS 子集的編譯器已經完成了。再說一次，你可以在這裡看到完整的源文件。

用我們的編譯器運行第一節的示例，產生的 JavaScript 代碼如下：

$ runhaskell Lisp.hs example.lsp
(function(compose, square, add1) {
  return (console.log)(((compose)(square, add1))(5));
})(function(f, g) {
  return function(x) {
    return (f)((g)(x));
  };
}, function(x) {
  return (x * x);
}, function(x) {
  return (x + 1);
})

如果你在自己電腦上安裝了 node.js，你可以用以下命令運行這段代碼：

$ runhaskell Lisp.hs example.lsp | node -p
36
undefined

最終練習 : 編譯有多個表達式的程序而非僅編譯一個表達式。

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

作者：Gil Mizrahi 選題：oska874 譯者：BriFuture 校對：wxy

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

本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive

對這篇文章感覺如何？

太棒了

不錯

愛死了

不太好

感覺很糟

Rain

雨落清風。心向陽

用 350 行代碼從零開始，將 Lisp 編譯成 JavaScript

1、定義語言

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

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

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

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

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

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

對這篇文章感覺如何？

MidnightBSD 發布 1.0！

重啟和關閉 Linux 系統的 6 個終端命令

Leave a reply 取消回復

More in:Linux中國

如何通過 VLC 使用字幕

Unix 桌面：在 Linux 問世之前

Valve 對於 Ubuntu 的 Snap 版本的 Steam 並不滿意：原因何在

Wine 9.0 發布，實驗性地加入了 Wayland 驅動

中文操作系統論壇

關注 LinuxStory

開源學村

編程類開放書籍薈萃

如何殺死 Linux 中的殭屍進程

2022年，從學習Rust開始

Makefile 簡介

5本學習 TeX 的最佳免費書籍

Linux 內核補丁提交初體驗

使用 Linux 命令行解決Wordle 問題

Linux 的前世今生 – 1

特別關注

NetBSD 10.0 正式發布

「Linux 中國」開源社區，停止運營

人工智慧教程（七）：Scikit-learn 和訓練第一個模型

LinuxStory

加入 LinuxStory 交流群組

投票調查

最熱標籤

1、定義語言

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

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

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

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

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

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

分享

對這篇文章感覺如何？

You may also like

Leave a reply 取消回復

More in:Linux中國

中文操作系統論壇

關注 LinuxStory

開源學村

特別關注

最新文章

最熱標籤