自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

從Java走進(jìn)Scala:構(gòu)建計(jì)算器 解析器組合子入門

作者：Ted Neward
開發(fā) 后端
本文繼續(xù)討論一個(gè)簡(jiǎn)單的計(jì)算器 DSL，以展示函數(shù)性語(yǔ)言在構(gòu)建“外部”DSL 的強(qiáng)大功能，并在此過(guò)程中解決將文本輸入轉(zhuǎn)換成用于解釋的 AST 的問(wèn)題。為了解析文本輸入，作者引入了 解析器組合子（parser combinator），這是一個(gè)專門為這項(xiàng)任務(wù)設(shè)計(jì)的標(biāo)準(zhǔn) Scala 庫(kù)。

回憶一下我們的英雄所處的困境：在試圖創(chuàng)建一個(gè) DSL（這里只不過(guò)是一種非常簡(jiǎn)單的計(jì)算器語(yǔ)言）時(shí)，他創(chuàng)建了包含可用于該語(yǔ)言的各種選項(xiàng)的樹結(jié)構(gòu)：

◆二進(jìn)制加/減/乘/除運(yùn)算符

◆一元反運(yùn)算符

◆數(shù)值

它背后的執(zhí)行引擎知道如何執(zhí)行那些操作，它甚至有一個(gè)顯式的優(yōu)化步驟，以減少獲得結(jié)果所需的計(jì)算。

最后的 代碼 是這樣的：

清單 1. 計(jì)算器 DSL：AST 和解釋器

  1. package com.tedneward.calcdsl  
  2. {  
  3.   private[calcdsl] abstract class Expr  
  4.   private[calcdsl]  case class Variable(name : String) extends Expr  
  5.   private[calcdsl]  case class Number(value : Double) extends Expr  
  6.   private[calcdsl]  case class UnaryOp(operator : String, arg : Expr) extends Expr  
  7.   private[calcdsl]  case class BinaryOp(operator : String, left : Expr, right : Expr)   
  8.    extends Expr  
  9.  
  10.   object Calc  
  11.   {  
  12.     /**  
  13.      * Function to simplify (a la mathematic terms) expressions  
  14.      */ 
  15.     def simplify(e : Expr) : Expr =  
  16.     {  
  17.       e match {  
  18.         // Double negation returns the original value  
  19.         case UnaryOp("-", UnaryOp("-", x)) => simplify(x)  
  20.     
  21.         // Positive returns the original value  
  22.         case UnaryOp("+", x) => simplify(x)  
  23.     
  24.         // Multiplying x by 1 returns the original value  
  25.         case BinaryOp("*", x, Number(1)) => simplify(x)  
  26.     
  27.         // Multiplying 1 by x returns the original value  
  28.         case BinaryOp("*", Number(1), x) => simplify(x)  
  29.     
  30.         // Multiplying x by 0 returns zero  
  31.         case BinaryOp("*", x, Number(0)) => Number(0)  
  32.     
  33.         // Multiplying 0 by x returns zero  
  34.         case BinaryOp("*", Number(0), x) => Number(0)  
  35.     
  36.         // Dividing x by 1 returns the original value  
  37.         case BinaryOp("/", x, Number(1)) => simplify(x)  
  38.     
  39.         // Dividing x by x returns 1  
  40.         case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)  
  41.     
  42.         // Adding x to 0 returns the original value  
  43.         case BinaryOp("+", x, Number(0)) => simplify(x)  
  44.     
  45.         // Adding 0 to x returns the original value  
  46.         case BinaryOp("+", Number(0), x) => simplify(x)  
  47.     
  48.         // Anything else cannot (yet) be simplified  
  49.         case _ => e  
  50.       }  
  51.     }  
  52.       
  53.     def evaluate(e : Expr) : Double =  
  54.     {  
  55.       simplify(e) match {  
  56.         case Number(x) => x  
  57.         case UnaryOp("-", x) => -(evaluate(x))  
  58.         case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))  
  59.         case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))  
  60.         case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))  
  61.         case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))  
  62.       }  
  63.     }  
  64.   }  
  65. }  

#p#

前一篇文章的讀者應(yīng)該還記得，我布置了一個(gè)挑戰(zhàn)任務(wù)，要求改進(jìn)優(yōu)化步驟，進(jìn)一步在樹中進(jìn)行簡(jiǎn)化處理，而不是像清單 1 中的代碼那樣停留在最頂層。Lex Spoon 發(fā)現(xiàn)了我認(rèn)為是最簡(jiǎn)單的優(yōu)化方法：首先簡(jiǎn)化樹的 “邊緣”（每個(gè)表達(dá)式中的操作數(shù)，如果有的話），然后利用簡(jiǎn)化的結(jié)果，再進(jìn)一步簡(jiǎn)化頂層的表達(dá)式，如清單 2 所示：

清單 2. 簡(jiǎn)化、再簡(jiǎn)化

  1. /*  
  2.  * Lex's version:  
  3.  */ 
  4. def simplify(e: Expr): Expr = {  
  5.   // first simplify the subexpressions  
  6.   val simpSubs = e match {  
  7.     // Ask each side to simplify  
  8.     case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))  
  9.     // Ask the operand to simplify  
  10.     case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))  
  11.     // Anything else doesn't have complexity (no operands to simplify)  
  12.     case _ => e  
  13.   }  
  14.  
  15.   // now simplify at the top, assuming the components are already simplified  
  16.   def simplifyTop(x: Expr) = x match {  
  17.     // Double negation returns the original value  
  18.     case UnaryOp("-", UnaryOp("-", x)) => x  
  19.  
  20.     // Positive returns the original value  
  21.     case UnaryOp("+", x) => x  
  22.  
  23.     // Multiplying x by 1 returns the original value  
  24.     case BinaryOp("*", x, Number(1)) => x  
  25.  
  26.     // Multiplying 1 by x returns the original value  
  27.     case BinaryOp("*", Number(1), x) => x  
  28.  
  29.     // Multiplying x by 0 returns zero  
  30.     case BinaryOp("*", x, Number(0)) => Number(0)  
  31.  
  32.     // Multiplying 0 by x returns zero  
  33.     case BinaryOp("*", Number(0), x) => Number(0)  
  34.  
  35.     // Dividing x by 1 returns the original value  
  36.     case BinaryOp("/", x, Number(1)) => x  
  37.  
  38.     // Dividing x by x returns 1  
  39.     case BinaryOp("/", x1, x2) if x1 == x2 => Number(1)  
  40.  
  41.     // Adding x to 0 returns the original value  
  42.     case BinaryOp("+", x, Number(0)) => x  
  43.  
  44.     // Adding 0 to x returns the original value  
  45.     case BinaryOp("+", Number(0), x) => x  
  46.  
  47.     // Anything else cannot (yet) be simplified  
  48.     case e => e  
  49.   }  
  50.   simplifyTop(simpSubs)  
  51. }  

在此對(duì) Lex 表示感謝。

#p#

解析

現(xiàn)在是構(gòu)建 DSL 的另一半工作：我們需要構(gòu)建一段代碼，它可以接收某種文本輸入并將其轉(zhuǎn)換成一個(gè) AST。這個(gè)過(guò)程更正式的稱呼是解析（parsing）（更準(zhǔn)確地說(shuō)，是標(biāo)記解釋（tokenizing）、詞法解析（lexing） 和語(yǔ)法解析）。

以往，創(chuàng)建解析器有兩種方法：

手工構(gòu)建一個(gè)解析器。

通過(guò)工具生成解析器。

我們可以試著手工構(gòu)建這個(gè)解析器，方法是手動(dòng)地從輸入流中取出一個(gè)字符，檢查該字符，然后根據(jù)該字符以及在它之前的其他字符（有時(shí)還要根據(jù)在它之后的字符）采取某種行動(dòng)。對(duì)于較小型的語(yǔ)言，手工構(gòu)建解析器可能更快速、更容易，但是當(dāng)語(yǔ)言變得更龐大時(shí)，這就成了一個(gè)困難的問(wèn)題。

除了手工編寫解析器外，另一種方法是用工具生成解析器。以前有 2 個(gè)工具可以實(shí)現(xiàn)這個(gè)目的，它們被親切地稱作lex（因?yàn)樗梢粋€(gè) “詞法解析器”）和 yacc（“Yet Another Compiler Compiler”）。對(duì)編寫解析器感興趣的程序員沒(méi)有手工編寫解析器，而是編寫一個(gè)不同的源文件，以此作為 “l(fā)ex” 的輸入，后者生成解析器的前端。然后，生成的代碼會(huì)與一個(gè) “grammar” 文件 —— 它定義語(yǔ)言的基本語(yǔ)法規(guī)則（哪些標(biāo)記中是關(guān)鍵字，哪里可以出現(xiàn)代碼塊，等等）—— 組合在一起，并且輸入到 yacc 生成解析器代碼。

由于這是 Computer Science 101 教科書，所以我不會(huì)詳細(xì)討論有限狀態(tài)自動(dòng)機(jī)（finite state automata）、LALR 或 LR 解析器，如果需要深入了解請(qǐng)查找與這個(gè)主題相關(guān)的書籍或文章。

同時(shí)，我們來(lái)探索 Scala 構(gòu)建解析器的第 3 個(gè)選項(xiàng)：解析器組合子（parser combinators），它完全是從 Scala 的函數(shù)性方面構(gòu)建的。解析器組合子使我們可以將語(yǔ)言的各種片段 “組合” 成部件，這些部件可以提供不需要代碼生成，而且看上去像是一種語(yǔ)言規(guī)范的解決方案。

解析器組合子

了解 Becker-Naur Form（BNF）有助于理解解析器組合子的要點(diǎn)。BNF 是一種指定語(yǔ)言的外觀的方法。例如，我們的計(jì)算器語(yǔ)言可以用清單 3 中的 BNF 語(yǔ)法進(jìn)行描述：

清單 3. 對(duì)語(yǔ)言進(jìn)行描述

  1. input ::= ws expr ws eoi;  
  2.  
  3. expr ::= ws powterm [{ws '^' ws powterm}];  
  4. powterm ::= ws factor [{ws ('*'|'/') ws factor}];  
  5. factor ::= ws term [{ws ('+'|'-') ws term}];  
  6. term ::= '(' ws expr ws ')' | '-' ws expr | number;  
  7.  
  8. number ::= {dgt} ['.' {dgt}] [('e'|'E') ['-'] {dgt}];  
  9. dgt ::= '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9';  
  10. ws ::= [{' '|'\t'|'\n'|'\r'}];  

語(yǔ)句左邊的每個(gè)元素是可能的輸入的集合的名稱。右邊的元素也稱為 term，它們是一系列表達(dá)式或文字字符，按照可選或必選的方式進(jìn)行組合。（同樣，BNF 語(yǔ)法在 Aho/Lam/Sethi/Ullman 等書籍中有更詳細(xì)的描述，請(qǐng)參閱 參考資料）。

用 BNF 形式來(lái)表達(dá)語(yǔ)言的強(qiáng)大之處在于，BNF 和 Scala 解析器組合子不相上下；清單 4 顯示使用 BNF 簡(jiǎn)化形式后的清單 3：

清單 4. 簡(jiǎn)化、再簡(jiǎn)化

  1. expr   ::= term {'+' term | '-' term}  
  2. term   ::= factor {'*' factor | '/' factor}  
  3. factor ::= floatingPointNumber | '(' expr ')' 

其中花括號(hào)（{}）表明內(nèi)容可能重復(fù)（0 次或多次），豎線（|）表明也/或的關(guān)系。因此，在讀清單 4 時(shí)，一個(gè) factor 可能是一個(gè) floatingPointNumber（其定義在此沒(méi)有給出），或者一個(gè)左括號(hào)加上一個(gè) expr 再加上一個(gè)右括號(hào)。

在這里，將它轉(zhuǎn)換成一個(gè) Scala 解析器非常簡(jiǎn)單，如清單 5 所示：

清單 5. 從 BNF 到 parsec

  1. package com.tedneward.calcdsl  
  2. {  
  3.   object Calc  
  4.   {  
  5.     // ...  
  6.     
  7.     import scala.util.parsing.combinator._  
  8.     
  9.     object ArithParser extends JavaTokenParsers  
  10.     {  
  11.       def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)  
  12.       def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)  
  13.       def factor : Parser[Any] = floatingPointNumber | "("~expr~")"   
  14.         
  15.       def parse(text : String) =  
  16.       {  
  17.         parseAll(expr, text)  
  18.       }  
  19.     }  
  20.  
  21.     def parse(text : String) =  
  22.     {  
  23.       val results = ArithParser.parse(text)  
  24.       System.out.println("parsed " + text + " as " + results + " which is a type " 
  25.        + results.getClass())  
  26.     }  
  27.    
  28.  // ...  
  29.   }  
  30. }  

BNF 實(shí)際上被一些解析器組合子語(yǔ)法元素替換：空格被替換為 ~ 方法（表明一個(gè)序列），重復(fù)被替換為 rep 方法，而選擇則仍然用 | 方法來(lái)表示。文字字符串是標(biāo)準(zhǔn)的文字字符串。

從兩個(gè)方面可以看到這種方法的強(qiáng)大之處。首先，該解析器擴(kuò)展 Scala 提供的 JavaTokenParsers 基類（后者本身又繼承其他基類，如果我們想要一種與 Java 語(yǔ)言的語(yǔ)法概念不那么嚴(yán)格對(duì)齊的語(yǔ)言的話），其次，使用 floatingPointNumber 預(yù)設(shè)的組合子來(lái)處理解析一個(gè)浮點(diǎn)數(shù)的細(xì)節(jié)。

這種特定的（一個(gè)中綴計(jì)算器的）語(yǔ)法很容易使用（這也是在那么多演示稿和文章中看到它的原因），為它手工構(gòu)建一個(gè)解析器也不困難，因?yàn)?BNF 語(yǔ)法與構(gòu)建解析器的代碼之間的緊密關(guān)系使我們可以更快、更容易地構(gòu)建解析器。

#p#

解析器組合子概念入門

為了理解其中的原理，我們必須簡(jiǎn)要了解解析器組合子的實(shí)現(xiàn)。實(shí)際上，每個(gè) “解析器” 都是一個(gè)函數(shù)或一個(gè) case 類，它接收某種輸入，并產(chǎn)生一個(gè) “解析器”。例如，在最底層，解析器組合子位于一些簡(jiǎn)單的解析器之上，這些解析器以某種輸入讀取元素（一個(gè) Reader）作為輸入，并生成某種可以提供更高級(jí)的語(yǔ)義的東西（一個(gè) Parser）：

清單 6. 一個(gè)基本的解析器

  1. type Elem  
  2.  
  3. type Input = Reader[Elem]  
  4.  
  5. type Parser[T] = Input => ParseResult[T]  
  6.  
  7. sealed abstract class ParseResult[+T]  
  8. case class Success[T](result: T, in: Input) extends ParseResult[T]  
  9. case class Failure(msg: String, in: Input) extends ParseResult[Nothing]  

換句話說(shuō)，Elem 是一種抽象類型，用于表示任何可被解析的東西，最常見的是一個(gè)文本字符串或流。然后，Input 是圍繞那種類型的一個(gè) scala.util.parsing.input.Reader（方括號(hào)表明 Reader 是一個(gè)泛型；如果您喜歡 Java 或 C++ 風(fēng)格的語(yǔ)法，那么將它們看作尖括號(hào)）。然后，T 類型的 Parser 是這樣的類型：它接受一個(gè) Input，并生成一個(gè) ParseResult，后者（基本上）屬于兩種類型之一：Success 或 Failure。

顯然，關(guān)于解析器組合子庫(kù)的知識(shí)遠(yuǎn)不止這些 — 即使 ~ 和 rep 函數(shù)也不是幾個(gè)步驟就可以得到的 — 但是，這讓您對(duì)解析器組合子的工作原理有基本的了解。“組合” 解析器可以提供解析概念的越來(lái)越高級(jí)的抽象（因此稱為 “解析器組合子”；組合在一起的元素提供解析行為）。

我們還沒(méi)有完成，是嗎？

我們?nèi)匀粵](méi)有完成。通過(guò)調(diào)用快速測(cè)試解析器可以發(fā)現(xiàn)，解析器返回的內(nèi)容并不是計(jì)算器系統(tǒng)需要的剩余部分：

清單 7. 第一次測(cè)試失敗？

  1. package com.tedneward.calcdsl.test  
  2. {  
  3.   class CalcTest  
  4.   {  
  5.     import org.junit._, Assert._  
  6.    
  7.  // ...  
  8.       
  9.     @Test def parseNumber =  
  10.     {  
  11.       assertEquals(Number(5), Calc.parse("5"))  
  12.       assertEquals(Number(5), Calc.parse("5.0"))  
  13.     }  
  14.   }  
  15. } 

這次測(cè)試會(huì)在運(yùn)行時(shí)失敗，因?yàn)榻馕銎鞯?parseAll 方法不會(huì)返回我們的 case 類 Number（這是有道理的，因?yàn)槲覀儧](méi)有在解析器中建立 case 類與解析器的產(chǎn)生規(guī)則之間的關(guān)系）；它也沒(méi)有返回一個(gè)文本標(biāo)記或整數(shù)的集合。

相反，解析器返回一個(gè) Parsers.ParseResult，這是一個(gè) Parsers.Success 實(shí)例（其中有我們想要的結(jié)果）；或者一個(gè) Parsers.NoSuccess、Parsers.Failure 或 Parsers.Error（后三者的性質(zhì)是一樣的：解析由于某種原因未能正常完成）。

假設(shè)這是一次成功的解析，要得到實(shí)際結(jié)果，必須通過(guò) ParseResult 上的 get 方法來(lái)提取結(jié)果。這意味著必須稍微調(diào)整 Calc.parse 方法，以便通過(guò)測(cè)試。如清單 8 所示：

清單 8. 從 BNF 到 parsec

  1. package com.tedneward.calcdsl  
  2. {  
  3.   object Calc  
  4.   {  
  5.     // ...  
  6.     
  7.     import scala.util.parsing.combinator._  
  8.     
  9.     object ArithParser extends JavaTokenParsers  
  10.     {  
  11.       def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)  
  12.       def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)  
  13.       def factor : Parser[Any] = floatingPointNumber | "("~expr~")"   
  14.         
  15.       def parse(text : String) =  
  16.       {  
  17.         parseAll(expr, text)  
  18.       }  
  19.     }  
  20.  
  21.     def parse(text : String) =  
  22.     {  
  23.       val results = ArithParser.parse(text)  
  24.       System.out.println("parsed " + text + " as " + results + " which is a type " 
  25.          + results.getClass())  
  26.    results.get  
  27.     }  
  28.    
  29.  // ...  
  30.   }  
  31. }  

成功了！真的嗎？

對(duì)不起，還沒(méi)有成功。運(yùn)行測(cè)試表明，解析器的結(jié)果仍不是我前面創(chuàng)建的 AST 類型（expr 和它的親屬），而是由 List 和 String 等組成的一種形式。雖然可以將這些結(jié)果解析成 expr 實(shí)例并對(duì)其進(jìn)行解釋，但是肯定還有另外一種方法。

確實(shí)有另外一種方法。為了理解這種方法的工作原理，您將需要研究一下解析器組合子是如何產(chǎn)生非 “標(biāo)準(zhǔn)” 的元素的（即不是 String 和 List）。用適當(dāng)?shù)男g(shù)語(yǔ)來(lái)說(shuō)就是解析器如何才能產(chǎn)生一個(gè)定制的元素（在這里，就是 AST 對(duì)象）。這個(gè)主題下一次再討論。

在下一期中，我將和您一起探討解析器組合子實(shí)現(xiàn)的基礎(chǔ)，并展示如何將文本片段解析成一個(gè) AST，以便進(jìn)行求值（然后進(jìn)行編譯）。

結(jié)束語(yǔ)

顯然，我們還沒(méi)有結(jié)束（解析工作還沒(méi)有完成），但是現(xiàn)在有了基本的解析器語(yǔ)義，接下來(lái)只需通過(guò)擴(kuò)展解析器產(chǎn)生元素來(lái)生成 AST 元素。

對(duì)于那些想領(lǐng)先一步的讀者，可以查看 ScalaDocs 中描述的 ^^ 方法，或者閱讀 Programming in Scala 中關(guān)于解析器組合子的小節(jié)；但是，在此提醒一下，這門語(yǔ)言比這些參考資料中給出的例子要復(fù)雜一些。

當(dāng)然，您可以只與 String 和 List 打交道，而忽略 AST 部分，拆開返回的 String 和 List，并重新將它們解析成 AST 元素。但是，解析器組合子庫(kù)已經(jīng)包含很多這樣的內(nèi)容，沒(méi)有必要再重復(fù)一遍。

【相關(guān)閱讀】

  1. Scala編程語(yǔ)言專題
  2. 從Java走進(jìn)Scala:簡(jiǎn)單的計(jì)算器 case類和模式匹配
  3. 從Java走進(jìn)Scala:包和訪問(wèn)修飾符
  4. 從Java走進(jìn)Scala:使用元組、數(shù)組和列表
  5. 從Java走進(jìn)Scala:當(dāng)繼承中的對(duì)象遇到函數(shù)
責(zé)任編輯：yangsai 來(lái)源： IBMDW
Scala計(jì)算器解析
相關(guān)推薦

2009-06-19 13:16:36

Scala計(jì)算器解析器組合子

2009-06-19 11:13:47

Scalacase類模式匹配

2009-09-28 11:01:39

從Java走進(jìn)Scal

2009-08-21 16:17:25

ScalaTwitter API

2009-06-17 11:44:22

Scala控制結(jié)構(gòu)

2019-07-05 08:39:39

GoSQL解析器

2009-07-15 10:14:25

Scala并發(fā)性

2009-12-09 09:15:47

從Java走進(jìn)ScalTwitter API

2009-02-04 17:32:03

ibmdwJavaScala

2020-12-02 10:13:45

JacksonJDK解析器

2011-09-16 14:13:15

Windows7計(jì)算器

2009-01-03 14:39:00

ibmdwSpirit

2009-10-14 11:14:38

ScitterScalaTwitter

2009-06-16 17:54:38

Scala類語(yǔ)法語(yǔ)義

2009-03-19 09:26:05

RSS解析器MagpieRSS

2009-06-17 13:57:25

Scala元組數(shù)組

2009-06-16 17:09:17

Scala面向?qū)ο?/a>函數(shù)編程

2022-09-08 11:35:45

Python表達(dá)式函數(shù)

2022-09-09 00:25:48

Python工具安全

2010-02-22 16:51:03

Python 解析器
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)