[Scala] 建置簡單的 ReSturcutredText Parser Part 1

2011-12-04 17:53 墳墓 (Brian Hsu)

前言

話說轉到 Pelican 之前，自然是找過有沒有其他的 Java / Scala 解決方案的，也想過干脆自己硬幹一個。不過很可惜的，找到的東西都不是很滿意，唯一的一套 Java reStructuredText Parser 用起來也很不順手……

所以，乾脆自己來試著用 Scala 寫一個簡易的 reStructuredText 的 parser，畢竟一直以來都有聽說過 Scala 的 Parser Combinator 多厲害又多厲害，但沒有實際用過，實在不太能理解其中的原理。

所以這一系列就是試著一步一步實作一個簡單的 reStructuredText 的 parser。

什麼是 Parser？

什麼是 Parser 應該不用說了吧？簡單地說就是一個將 A 格式的輸入，轉成 B 格式的輸出的工具。

在 Scala 的觀點來說，一個 Parser 就是一個 function，他的原型是：

def apply(i:Input): ParseResult[T]

其中 ParserResult 的定義如下：

sealed abstract class ParseResult[+T] {
    def get: T
    val next: Input
}
case class Success[+T](result: T, override val next: Input) extends ParseResult[T] {
    def get: T = result
}
sealed abstract class NoSuccess(val msg: String, override val next: Input) extends ParseResult[Nothing] {
    def get: Nothing = error("No result when parsing failed")
}
case class Failure(override val msg: String, override val next: Input) extends NoSuccess(msg, next)
case class Error(override val msg: String, override val next: Input) extends NoSuccess(msg, next)

也就是說一個 Parser 在處理輸入後，可能會產生出以下幾種狀況：

Success
parse 成功
Failure
parse 失敗，但剩下的東西可以繼續 parse
Error
parse 失敗，而且是不可恢復的錯誤，停止 parse

什麼是 Combinator？

那什麼是 Combinator 呢？簡單地來說，Combinator 是一個『輸入是函式，輸出也是函式的函式』，拜 Scala 的 Functional Programming 支援所賜，這樣的東西在 Scala 裡是很容易達成的。

舉一個簡單的例子，在下面的程式碼裡，我們先定義了一個 double(i: Int): Int 和一個 plusOne(i: Int):: Int 的函式，接著再用 andThen 將兩個函式組合成另一個新的函式 doubleThenPlus。

scala> def double(i: Int) = i * 2
double: (i: Int)Int

scala> def plusOne(i: Int) = i + 1
plusOne: (i: Int)Int

scala> val doubleThenPlus = double _ andThen plusOne
doubleThenPlus: Int => Int = <function1>

scala> doubleThenPlus(3)    // 等於 plusOne(double(3))
res0: Int = 7

這就是 Combinator 的概念，andThen 的輸入是一個函式，而反回值是另一個函式。透過這個方式，我們可以用簡單的東西組合出另一個比較複雜的東西。

reStructuredText 的 Inline Markup

因為我們是剛開始，所以野心先不要放得太大，先將目標放在處理比較簡單的部份：reStructuredText 的行內格式化語法。

總共要處理的有以下三種狀況：

輸入 輸出
this is a ``test``. this is a <literal>test</literal>.
this is a **test**. this is a <bold>test</bold>.
this is a *test*. this is a <emphsis>test</emphsis>.

Scala RegualrParsers

要處理像上述的狀況，用 Regular Expression 是最方便的，我們可以用 regex 來描述我們想要的語法，然後剩下的就交給 RegularParsers 做處理，他會幫我們處理吃 Token 和 Parse 的這類瑣事。

因為程式碼並不長，所以我們直接來看完整的程式碼，以下是使用 RegularParsers 時的實際狀況：

import scala.util.parsing.combinator._

trait InlineFormatterParser
{
    this: RegexParsers =>

    val literal = """\B``(.)*?``\B""".r ^^ toCodeTag    // ``code literal``
    val bold = """\B\*\*(.)*?\*\*\B""".r ^^ toBoldTag   // **bold text**
    val italic = """\B\*(.)*?\*\B""".r ^^ toItalicTag   // *italic text*

    val newlines = """(\s)""".r // 換行符號
    val words = """(.)""".r     // 任意字元

    val inline = (literal | bold | italic | words | newlines)*

    def toCodeTag(s: String) = "<literal>" + s.drop(2).dropRight(2) + "</literal>"
    def toBoldTag(s: String) = "<strong>" + s.drop(2).dropRight(2) + "</strong>"
    def toItalicTag(s: String) = "<emphasis>" + s.drop(1).dropRight(1) + "</emphasis>"
}

首先，我們宣告了 InlineFormatterParser 這個 trait，並且指定他的 this 的型態是 RegexParsers，這代表了這個 trait 只能被 mixin 到 RegexParsers 這個類別中，來增加該類別的功能。

換句話說，我們可以假設 InlineFormatterParser 本身就是一個 RegexParsers 的子類別，可以使用任何 RegexParsers 類別內開放出來的東西。

這個 trait 的重點其實在以下這三行：

val literal = """\B``(.)*?``\B""".r ^^ toCodeTag    // ``code literal``
val bold = """\B\*\*(.)*?\*\*\B""".r ^^ toBoldTag   // **bold text**
val italic = """\B\*(.)*?\*\B""".r ^^ toItalicTag   // *italic text*

首先，我們可以看到每一行的型式都是：

"""somestring""".r ^^ someMethod

.r 是 Scala 提供的一個字串方法，會將字串轉成 Regex 物件，所以上面的程式碼實際上會被轉成：

new Regex("""somestring""") ^^ someMethod

但 Regex 物件並不是 Parser 對吧，而且並沒有 ^^ 這個運算子啊，而且 ^^ 又是什麼？但如果我們仔細觀察 RegexParsers 的話，會發現裡面定義了這個方法：

implicit def regex (r: Regex): Parser[String]

由於他是一個 implicit 方法，所以當有 Regex 物件呼叫到 Parser[String] 才有的 ^^ 方法時，Scala 會自動幫你呼叫 regex 這個函式。套用這個規則，上面的程式碼就會變成：

val parser = regex(new Regex("""somestring"""))
parser ^^ someMethod

OK，我們現在有一個 parser 了，那 ^^ 又是什麼呢？答案是：Combinator！他的參數是一個函式，而反回值是另一個函式 (parser)！而他的意思是：如果 parser 成功地 parse 的話，就被被 parse 的那個 token 交給 someMethod 處理，取得我們要的 parse 後的結果。

有了上面的認知，現在下面的程式看起來應該很簡單了：

val literal = """\B``(.)*?``\B""".r ^^ toCodeTag    // ``code literal``
val bold = """\B\*\*(.)*?\*\*\B""".r ^^ toBoldTag   // **bold text**
val italic = """\B\*(.)*?\*\B""".r ^^ toItalicTag   // *italic text*

def toCodeTag(s: String) = "<literal>" + s.drop(2).dropRight(2) + "</literal>"
def toBoldTag(s: String) = "<strong>" + s.drop(2).dropRight(2) + "</strong>"
def toItalicTag(s: String) = "<emphasis>" + s.drop(1).dropRight(1) + "</emphasis>"

我們定義了 literal bold italic 這三個簡單的 parser，用來 parse 這三種狀況。

嘿！等一會兒，那不屬於上面這三種格式的部份怎麼辦？！總不能把他吃光光唄？所以我們再加上下面兩個 parser 用來處理那些輸入等於輸出的部份：

val newlines = """(\s)""".r // 換行符號
val words = """(.)""".r     // 任意字元

請注意在這兩個 parser 裡，我們沒有呼叫 ^^ 方法來設定轉換函式，所以他吃到什麼就會吐出什麼，所以除了符合上面三個格式化語法之外的資料，就會維持原樣。

最後，我們要處理的資料，當然不會只有一個 token，所以我們加入了最後一條規則：

val inline = (literal | bold | italic | words | newlines)*

再一次，這行裡面的 | 和 * 都是 combinator。

| 是說先把資料丟到第一個 parser，如果失敗就嚐試第二個 parser……依此類推，直到其中一個 parser 成功，或全都失敗。

* 則和 .r 一樣都是一個 method，他代表的意思是說將前面的 parser 重覆 N 次。

實際使用

上面我們定義了簡單的 InlineFormatterParser，但如果無法真的使用，那一切就白費了功夫了。

那要怎樣使用我們定義出來的 Parser 呢？一樣先來看一下程式碼：

object RSTParser extends RegexParsers with InlineFormatterParser
{
    override val skipWhitespace = false

    val rst = inline

    def run(s: String) = parseAll(rst, s) match {
        case Success(xs, next) => xs.mkString
        case _ => "fail"
    }
}

val content = """
 ``This``, is a syntax test ``code `here`` . Hello ``World``
 **This**, is a syntax test **code `here** . Hello ``World``
 *This*, is a syntax test *code `here* . Hello *World*

"""
println ("Hello World:" + RSTParser.run(content))

在這段程式碼中，我們宣告了一個繼承了 RegexParsers 和 mixin 了 InlineFormatterParser 的物件，然後將 skipWhitespace 設成 fasle，要不然 RegexParsers 預設會把空白吃掉，但我們必須保留原始輸入的空白，所以一定要有這個設定。

接下來，我們定義了一個 val rst = inline，這只是為了方便將來我們擴充新的 parser 進去，實際上真正重要的是 run 這個方法。

def run(s: String) = parseAll(rst, s) match {
    case Success(xs, next) => xs.mkString
    case _ => "fail"
}

在這個方法裡面，我們呼叫了 RegexParsers 內的 parseAll 函式，給他一個 parser rst 以及我們要 parse 的資料 s，然後確認 parse 的結果：如果成功，就將 xs 這個 List[String] 組合成字串，失敗的話則返回 "fail" 字串。

最後把所有東西都組合起來，完整的程式碼長得像下面一樣：

import scala.util.parsing.combinator._

trait InlineFormatterParser
{
    this: RegexParsers =>

    val literal = """\B``(.)*?``\B""".r ^^ toCodeTag    // ``code literal``
    val bold = """\B\*\*(.)*?\*\*\B""".r ^^ toBoldTag   // **bold text**
    val italic = """\B\*(.)*?\*\B""".r ^^ toItalicTag   // *italic text*

    val newlines = """(\s)""".r // 換行符號
    val words = """(.)""".r     // 任意字元

    val inline = (literal | bold | italic | words | newlines)*

    def toCodeTag(s: String) = "<literal>" + s.drop(2).dropRight(2) + "</literal>"
    def toBoldTag(s: String) = "<strong>" + s.drop(2).dropRight(2) + "</strong>"
    def toItalicTag(s: String) = "<emphasis>" + s.drop(1).dropRight(1) + "</emphasis>"
}

object RSTParser extends RegexParsers with InlineFormatterParser
{
    override val skipWhitespace = false

    val rst = inline

    def run(s: String) = parseAll(rst, s) match {
        case Success(xs, next) => xs.mkString
        case _ => "fail"
    }
}

val content = """
 ``This``, is a syntax test ``code `here`` . Hello ``World``
 **This**, is a syntax test **code `here** . Hello ``World``
 *This*, is a syntax test *code `here* . Hello *World*

"""

println ("Hello World:" + RSTParser.run(content))

所以上述程式碼的執行結果就會成為：

brianhsu@USBGentoo ~/siRST $ scala test.scala
Hello World:
 <literal>This</literal>, is a syntax test <literal>code `here</literal> . Hello <literal>World</literal>
 <strong>This</strong>, is a syntax test <strong>code `here</strong> . Hello <literal>World</literal>
 <emphasis>This</emphasis>, is a syntax test <emphasis>code `here</emphasis> . Hello <emphasis>World</emphasis>

結論

上面只是個很簡單的 parser，不過可以看出 Parser Combinator 大致上的概念－－先寫出小的 parser 組件，再用這些組件組出另一個比較大的 parser。

另外從這個例子裡也可以看出 Scala 的簡潔和優雅，只需要用大約 30 行的程式碼就可以寫出一個簡單的 parser，而且只要了解背後的原理，就會發現整支程式還滿好理解的。 :-)

繼續閱讀 | 回應 | 分類：寫程式 | 標籤：Scala reStructuredText Parser  

回響