日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

我們將會(huì)在本篇文章中看到從零開始實(shí)現(xiàn)的編譯器，將簡單的類 LISP 計(jì)算語言編譯成 JavaScript。完整的源代碼在 這里。

我們將會(huì)：

1. 自定義語言，并用它編寫一個(gè)簡單的程序
2. 實(shí)現(xiàn)一個(gè)簡單的解析器組合器
3. 為該語言實(shí)現(xiàn)一個(gè)解析器
4. 為該語言實(shí)現(xiàn)一個(gè)美觀的打印器
5. 為我們的用途定義 JavaScript 的一個(gè)子集
6. 實(shí)現(xiàn)代碼轉(zhuǎn)譯器，將代碼轉(zhuǎn)譯成我們定義的 JavaScript 子集
7. 把所有東西整合在一起

開始吧！

1、定義語言

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

 
 
 
  
  
  
program ::= expr
  
  
  
expr ::=  |  | ([])
 
 

基本上，我們可以在該語言的最頂層定義表達(dá)式并對其進(jìn)行運(yùn)算。表達(dá)式由一個(gè)整數(shù)（比如 5）、一個(gè)變量（比如 x）或者一個(gè)表達(dá)式列表（比如 (add x 1)）組成。

整數(shù)對應(yīng)它本身的值，變量對應(yīng)它在當(dāng)前環(huán)境中綁定的值，表達(dá)式列表對應(yīng)一個(gè)函數(shù)調(diào)用，該列表的第一個(gè)參數(shù)是相應(yīng)的函數(shù)，剩下的表達(dá)式是傳遞給這個(gè)函數(shù)的參數(shù)。

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

• let 表達(dá)式使我們可以在它的 body 環(huán)境中引入新的變量。語法如下：

     
     
     
      
      
      
  let ::= (let ([]) )
      
      
      
  letargs ::= ( )
      
      
      
  body ::= 
     
     
   

• lambda 表達(dá)式：也就是匿名函數(shù)定義。語法如下：

     
     
     
      
      
      
  lambda ::= (lambda ([]) )
     
     
   

還有一些內(nèi)建函數(shù)： 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)))
 
 

這個(gè)程序定義了 3 個(gè)函數(shù)：compose、square 和 add1。然后將計(jì)算結(jié)果的值 ((compose square add1) 5) 輸出出來。

我相信了解這門語言，這些信息就足夠了。開始實(shí)現(xiàn)它吧。

在 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 定義的程序。而且，這里我們添加了新數(shù)據(jù)類型 Eq、Read 和 Show 等實(shí)例用于測試和調(diào)試。你能夠在 REPL 中使用這些數(shù)據(jù)類型，驗(yàn)證它們確實(shí)有用。

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

一般來說你想要在抽象語法中定義這些特殊用例 —— 用于改進(jìn)錯(cuò)誤信息、禁用靜態(tài)分析和優(yōu)化等等，但在這里我們不會(huì)這樣做，對我們來說這些已經(jīng)足夠了。

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

• 練習(xí) 1：添加一個(gè) Program 數(shù)據(jù)類型，可以按順序包含多個(gè) Expr
• 練習(xí) 2：向語法樹中添加一個(gè)定位注解。

2、實(shí)現(xiàn)一個(gè)簡單的解析器組合庫

我們要做的第一件事情是定義一個(gè)嵌入式領(lǐng)域?qū)Ｓ谜Z言Embedded Domain Specific Language（EDSL），我們會(huì)用它來定義我們的語言解析器。這常常被稱為解析器組合庫。我們做這件事完全是出于學(xué)習(xí)的目的，Haskell 里有很好的解析庫，在實(shí)際構(gòu)建軟件或者進(jìn)行實(shí)驗(yàn)時(shí)，你應(yīng)該使用它們。megaparsec 就是這樣的一個(gè)庫。

首先我們來談?wù)劷馕鰩斓膶?shí)現(xiàn)的思路。本質(zhì)上，我們的解析器就是一個(gè)函數(shù)，接受一些輸入，可能會(huì)讀取輸入的一些或全部內(nèi)容，然后返回解析出來的值和無法解析的輸入部分，或者在解析失敗時(shí)拋出異常。我們把它寫出來。

 
 
 
  
  
  
newtype Parser a
  
  
  
 = Parser (ParseString -> Either ParseError (a, ParseString))
  
  
  
 
  
  
  
data ParseString
  
  
  
 = ParseString Name (Int, Int) String
  
  
  
 
  
  
  
data ParseError
  
  
  
 = ParseError ParseString Error
  
  
  
 
  
  
  
type Error = String
 
 

這里我們定義了三個(gè)主要的新類型。

第一個(gè)，Parser a 是之前討論的解析函數(shù)。

第二個(gè)，ParseString 是我們的輸入或攜帶的狀態(tài)。它有三個(gè)重要的部分：

• Name: 這是源的名字
• (Int, Int): 這是源的當(dāng)前位置
• String: 這是等待解析的字符串

第三個(gè)，ParseError 包含了解析器的當(dāng)前狀態(tài)和一個(gè)錯(cuò)誤信息。

現(xiàn)在我們想讓這個(gè)解析器更靈活，我們將會(huì)定義一些常用類型的實(shí)例。這些實(shí)例讓我們能夠?qū)⑿∏傻慕馕銎骱蛷?fù)雜的解析器結(jié)合在一起（因此它的名字叫做 “解析器組合器”）。

第一個(gè)是 Functor 實(shí)例。我們需要 Functor 實(shí)例，因?yàn)槲覀円軌驅(qū)馕鲋祽?yīng)用函數(shù)從而使用不同的解析器。當(dāng)我們定義自己語言的解析器時(shí)，我們將會(huì)看到關(guān)于它的示例。

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

第二個(gè)是 Applicative 實(shí)例。該實(shí)例的常見用例是在多個(gè)解析器中實(shí)現(xiàn)一個(gè)純函數(shù)。

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

（注意：我們還會(huì)實(shí)現(xiàn)一個(gè) Monad 實(shí)例，這樣我們才能使用符號）

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

 
 
 
  
  
  
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
 
 

第四個(gè)是 Monad 實(shí)例。這樣我們就能鏈接解析器。

 
 
 
  
  
  
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
 
 

接下來，讓我們定義一種的方式，用于運(yùn)行解析器和防止失敗的助手函數(shù)：

 
 
 
  
  
  
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 ++ "."
  
  
  
 ]
 
 

現(xiàn)在我們將會(huì)開始實(shí)現(xiàn)組合器，這是 EDSL 的 API，也是它的核心。

首先，我們會(huì)定義 oneOf。如果輸入列表中的字符后面還有字符的話，oneOf 將會(huì)成功，否則就會(huì)失敗。

 
 
 
  
  
  
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 將會(huì)拋出異常，停止解析器。失敗時(shí)它僅僅會(huì)返回 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 將會(huì)試著重復(fù)運(yùn)行解析器，直到失敗。當(dāng)它完成的時(shí)候，會(huì)返回成功運(yùn)行的解析器列表。many1 做的事情是一樣的，但解析失敗時(shí)它至少會(huì)拋出一次異常。

 
 
 
  
  
  
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
 
 

下面的這些解析器通過我們定義的組合器來實(shí)現(xiàn)一些特殊的解析器：

 
 
 
  
  
  
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 '(')
  
  
  
 *> withSpaces parser
  
  
  
 <* (spaces *> char ')')
  
  
  
 
  
  
  
sepBy :: Parser a -> Parser b -> Parser [b]
  
  
  
sepBy sep parser = do
  
  
  
 frst <- optional parser
  
  
  
 rest <- many (sep *> parser)
  
  
  
 pure $ maybe rest (:rest) frst
 
 

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

• 練習(xí) ：實(shí)現(xiàn)一個(gè) EOF（end of file/input，即文件或輸入終止符）解析器組合器。

3、為我們的語言實(shí)現(xiàn)解析器

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

 
 
 
  
  
  
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
 
 

注意到這四個(gè)函數(shù)是在我們這門語言中屬于高階描述。這解釋了為什么 Haskell 執(zhí)行解析工作這么棒。在定義完高級部分后，我們還需要定義低級別的 parseName 和 parseInt。

我們能在這門語言中用什么字符作為名字呢？用小寫的字母、數(shù)字和下劃線吧，而且名字的第一個(gè)字符必須是字母。

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

整數(shù)是一系列數(shù)字，數(shù)字前面可能有負(fù)號 -：

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

最后，我們會(huì)定義用來運(yùn)行解析器的函數(shù)，返回值可能是一個(gè) Expr 或者是一條錯(cuò)誤信息。

 
 
 
  
  
  
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
 
 

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

4、為這門語言實(shí)現(xiàn)一個(gè)更好看的輸出器

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

 
 
 
  
  
  
printExpr :: Expr -> String
  
  
  
printExpr = printExpr' False 0
  
  
  
 
  
  
  
printAtom :: Atom -> String
  
  
  
printAtom = \case
  
  
  
 Symbol s -> s
  
  
  
 Int i -> show i
  
  
  
 
  
  
  
printExpr' :: Bool -> Int -> Expr -> String
  
  
  
printExpr' doindent level = \case
  
  
  
 ATOM a -> indent (bool 0 level doindent) (printAtom a)
  
  
  
 LIST (e:es) ->
  
  
  
 indent (bool 0 level doindent) $
  
  
  
 concat
  
  
  
 [ "("
  
  
  
 , printExpr' False (level + 1) e
  
  
  
 , bool "\n" "" (null es)
  
  
  
 , intercalate "\n" $ map (printExpr' True (level + 1)) es
  
  
  
 , ")"
  
  
  
 ]
  
  
  
 
  
  
  
indent :: Int -> String -> String
  
  
  
indent tabs e = concat (replicate tabs " ") ++ e
 
 

• 練習(xí) ：為第一節(jié)中定義的 Program 類型編寫一個(gè)美觀的輸出器

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

5、根據(jù)需求定義 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
 
 

這個(gè)數(shù)據(jù)類型表示 JavaScript 表達(dá)式。我們有兩個(gè)原子類型 JSInt 和 JSSymbol，它們是由我們這個(gè)語言中的 Atom 轉(zhuǎn)譯來的，我們用 JSBinOp 來表示二元操作，比如 + 或 *，用 JSLambda 來表示匿名函數(shù)，和我們語言中的 lambda expression（lambda 表達(dá)式） 一樣，我們將會(huì)用 JSFunCall 來調(diào)用函數(shù)，用 let 來引入新名字，用 JSReturn 從函數(shù)中返回值，在 JavaScript 中是需要返回值的。

JSExpr 類型是對 JavaScript 表達(dá)式的 抽象表示。我們會(huì)把自己語言中表達(dá)式的抽象表示 Expr 轉(zhuǎn)譯成 JavaScript 表達(dá)式的抽象表示 JSExpr。但為了實(shí)現(xiàn)這個(gè)功能，我們需要實(shí)現(xiàn) JSExpr ，并從這個(gè)抽象表示中生成 JavaScript 代碼。我們將通過遞歸匹配 JSExpr 實(shí)現(xiàn)，將 JS 代碼當(dāng)作 String 來輸出。這和我們在 printExpr 中做的基本上是一樣的。我們還會(huì)追蹤元素的作用域，這樣我們才可以用合適的方式縮進(jìn)生成的代碼。

 
 
 
  
  
  
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 ++ ";"
 
 

• 練習(xí) 1 ：添加 JSProgram 類型，它可以包含多個(gè) JSExpr ，然后創(chuàng)建一個(gè)叫做 printJSExprProgram 的函數(shù)來生成代碼。
• 練習(xí) 2 ：添加 JSExpr 的新類型：JSIf，并為其生成代碼。

6、實(shí)現(xiàn)到我們定義的 JavaScript 子集的代碼轉(zhuǎn)譯器

我們快做完了。這一節(jié)將會(huì)創(chuàng)建函數(shù)，將 Expr 轉(zhuǎn)譯成 JSExpr。

基本思想很簡單，我們會(huì)將 ATOM 轉(zhuǎn)譯成 JSSymbol 或者 JSInt，然后會(huì)將 LIST 轉(zhuǎn)譯成一個(gè)函數(shù)調(diào)用或者轉(zhuǎn)譯的特例。

 
 
 
  
  
  
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 是一系列要轉(zhuǎn)譯的特例，就像 lambada 和 let。每一種情況都可以獲得一系列參數(shù)，驗(yàn)證它是否合乎語法規(guī)范，然后將其轉(zhuǎn)譯成等效的 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)
  
  
  
 ]
 
 

我們這種情況，會(huì)將內(nèi)建的特殊形式當(dāng)作特殊的、非第一類的進(jìn)行對待，因此不可能將它們當(dāng)作第一類函數(shù)。

我們會(huì)把 Lambda 表達(dá)式轉(zhuǎn)譯成一個(gè)匿名函數(shù)：

 
 
 
  
  
  
transLambda :: [Expr] -> Either TransError JSExpr
  
  
  
transLambda = \case
  
  
  
 [LIST vars, body] -> do
  
  
  
 vars' <- traverse fromSymbol vars
  
  
  
 JSLambda vars' <$> (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
 
 

我們會(huì)將 let 轉(zhuǎn)譯成帶有相關(guān)名字參數(shù)的函數(shù)定義，然后帶上參數(shù)調(diào)用函數(shù)，因此會(huì)在這一作用域中引入變量：

 
 
 
  
  
  
transLet :: [Expr] -> Either TransError JSExpr
  
  
  
transLet = \case
  
  
  
 [LIST binds, body] -> do
  
  
  
 (vars, vals) <- letParams binds
  
  
  
 vars' <- traverse fromSymbol vars
  
  
  
 JSFunCall . JSLambda vars' <$> (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)
  
  
  
 ]
 
 

我們會(huì)將可以在多個(gè)參數(shù)之間執(zhí)行的操作符轉(zhuǎn)譯成一系列二元操作符。比如：(add 1 2 3) 將會(huì)變成 1 + (2 + 3)。

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

然后我們會(huì)將 print 轉(zhuǎn)換成對 console.log 的調(diào)用。

 
 
 
  
  
  
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)
 
 

注意，如果我們將這些代碼當(dāng)作 Expr 的特例進(jìn)行解析，那我們就可能會(huì)跳過語法驗(yàn)證。

• 練習(xí) 1 ：將 Program 轉(zhuǎn)譯成 JSProgram
• 練習(xí) 2 ：為 if Expr Expr Expr 添加一個(gè)特例，并將它轉(zhuǎn)譯成你在上一次練習(xí)中實(shí)現(xiàn)的 JSIf 條件語句。

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

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

1. 讀取文件
2. 將文件解析成 Expr
3. 將文件轉(zhuǎn)譯成 JSExpr
4. 將 JavaScript 代碼發(fā)送到標(biāo)準(zhǔn)輸出流

我們還會(huì)啟用一些用于測試的標(biāo)志位：

• --e 將進(jìn)行解析并打印出表達(dá)式的抽象表示（Expr）
• --pp 將進(jìn)行解析，美化輸出
• --jse 將進(jìn)行解析、轉(zhuǎn)譯、并打印出生成的 JS 表達(dá)式（JSExpr）的抽象表示
• --ppc 將進(jìn)行解析，美化輸出并進(jìn)行編譯

 
 
 
  
  
  
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 ] "
  
  
  
 ,"--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 子集的編譯器已經(jīng)完成了。再說一次，你可以在 這里 看到完整的源文件。

用我們的編譯器運(yùn)行第一節(jié)的示例，產(chǎn)生的 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，你可以用以下命令運(yùn)行這段代碼：

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

• 最終練習(xí) : 編譯有多個(gè)表達(dá)式的程序而非僅編譯一個(gè)表達(dá)式。

網(wǎng)站標(biāo)題：用350行代碼從零開始，將Lisp編譯成JavaScript
轉(zhuǎn)載來于：http://www.dlmjj.cn/article/cohogcj.html