如何處理有上下文關係的解析

想像一下若我們要解析開頭為數字，然後後面為 0 到 n 個字元 'a'，以下的字串皆滿足此需求：0、1a、2aa、4aaaa，

但 昨天 的 product function 無法滿足這個需求，因為 product 所接受的 Parser，會對所有輸入做解析，並無法做到先解析 'a'，然後在拿剩下的輸入做後續解析，

這個時候又得請我們的老朋友 flatMap 出來了。

def flatMap[A, B](p: Parser[A])(f: A => Parser[B]): Parser[B]

Exercise D21-1

因為有了 flatMap，我們可以嘗試用 flatMap 實現 product。

def product[A, B](p: Parser[A], p2: Parser[B]): Parser[(A, B)]

Exercise D21-2

請使用 flatMap 實現 map。

def map[A, B](a: Parser[A])(f: A => B): Parser[B]

Error 處理

目前在 Day 19 的 Parsers 介面只定義了 ParseError 這個型態參數當做錯誤型態，現在我們來試著探討一種可能的處理錯誤方法，

首先我們可以用一個挺直覺的方式，把錯誤訊息 msg 指派給 Parser p，p 失敗時 ParserError 會以某種方式使用到 msg，

def label[A](msg: String)(p: Parser[A]): Parser[A]

在來若想知道是輸入中的哪個字元有解析錯誤，我們可以用一個 Location 類別來表示，

case class Location(input: String, offset: Int = 0):

  lazy val line = input.slice(0, offset + 1).count(_ == '\n') + 1

  lazy val col = input.slice(0, offset + 1).lastIndexOf('\n') match
    case -1 => offset + 1
    case lineStart => offset - lineStart

那如果解析器很大的話要怎辦，一個個寫不太講究，

val p = label("first error msg")(string("abra")) **
 string(" ").many **  // 忽略空白
 label("second error msg")(string("cadabra"))

我們可以用一個 function 來表示巢狀的 label，

def scope[A](msg: String)(p: Parser[A]): Parser[A]

跟 label 不同的地方是，scope 不會把 msg 附加到 Parser 上，當 Parser 失敗時，它僅僅會多添加額外的訊息在錯誤中，什麼意思呢？

首先我們先來定義 ParserError 類別，該類別能取得 Location 和 String 等相關錯誤資訊，

case class ParseError(stack: List[(Location, String)] = Nil)

然後當 p.run(s) 解析失敗時的回傳是 Left(e1)，若是 (scope(msg)(p)).run(s) 失敗時的回傳是 Left(e2)，e2.stack.head 會是 msg，而 e2.stack.tail 則會是 e1。

現在有 ParserError 這個類別了，我們原先的 Parsers 介面就不在需要 ParserError 型態參數。

trait Parsers[Parser[+_]]

核心 API

最後來整理一下這 3 天推導定律過程中，哪些是我們的核心 API，

• string(s) 辨識字串 s。
• label(e)(p) 當解析器 p 失敗時，將錯誤訊息用 e 取代。
• slice(p) 當解析器 p 成功時，取得部份的 input。
• scope(e)(p) 當解析器 p 失敗時，新增 e 到 error stack 中。
• flatMap(p)(f) 執行解析器 p，以依序執行的方式將該結果用在第 2 個 parser 上。
• or(p1, p2) 當 p1 解析失敗時解析 p2。
• attemp(p) 延遲解析器的 commit 直到它成功。
• regex(s) 辨識正則表示式 s。

attemp, regex 因為篇幅關係沒有介紹到，我們可以參考 JSON 解析器的實作來試著了解它們的功用，

最後 Parsers 的程式如下（為求呼叫方便把一些核心 API 放到 extension 底下，故有把一些實作程式做過調整）：

trait Parsers[Parser[+_]]:

  def string(s: String): Parser[String]

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

  extension[A] (p: Parser[A])

    def run(input: String): Either[ParseError, A]

    def or(p2: => Parser[A]): Parser[A]

    def slice: Parser[String]

    def label(msg: String): Parser[A]

    def scope(msg: String): Parser[A]
		
    def flatMap[B](f: A => Parser[B]): Parser[B]

    def attempt: Parser[A]

    infix def |(p2: => Parser[A]): Parser[A] = p.or(p2)

    def many: Parser[List[A]] =
      p.map2(p.many)(_ :: _) | succeed(Nil)

    def map[B](f: A => B): Parser[B] =
      p.flatMap(a => succeed(f(a)))

    def product[B](p2: => Parser[B]): Parser[(A, B)] =
      p.flatMap(a => p2.map(b => (a, b)))

    def map2[B, C](p2: => Parser[B])(f: (A, B) => C): Parser[C] =
      p.product(p2).map((a, b) => f(a, b))

  def char(c: Char): Parser[Char] =
    string(c.toString).map(_.charAt(0))

	def succeed[A](a: A): Parser[A] =
    string("").map(_ => a)


case class Location(input: String, offset: Int = 0):

  lazy val line = input.slice(0, offset + 1).count(_ == '\n') + 1

  lazy val col = input.slice(0, offset + 1).lastIndexOf('\n') match
    case -1 => offset + 1
    case lineStart => offset - lineStart

  def toError(msg: String): ParseError =
    ParseError(List((this, msg)))
  
case class ParseError(stack: List[(Location, String)] = Nil)

JSON 解析器

直接看 程式 來了解 JSON 解析器怎麼實現 Parsers 吧，當你執行該程式時會得到下面結果：

input 1

{
  "Company name" : "Microsoft Corporation",
  "Ticker"  : "MSFT",
  "Active"  : true,
  "Price"   : 30.66,
  "Shares outstanding" : 8.38e9,
  "Related companies" : [ "HPQ", "IBM", "YHOO", "DELL", "GOOG" ]
}

result 1

JObject(HashMap(Shares outstanding -> JNumber(8.38E9), Price -> JNumber(30.66), Company name -> JString(Microsoft Corporation), Related companies -> JArray(Vector(JString(HPQ), JString(IBM), JString(YHOO), JString(DELL), JString(GOOG))), Ticker -> JString(MSFT), Active -> JBool(true)))

input 2

{
  "Company name" ; "Microsoft Corporation"
}

result 2

2.1 object
3.18 ':'

  "Company name" ; "Microsoft Corporation"
                 ^

input 3

[
  [ "HPQ", "IBM",
  "YHOO", "DELL" ++
  "GOOG"
  ]
]

result 3

2.1 array
3.3 array
4.18 ']'

  "YHOO", "DELL" ++

總結

我們將 Parsers 介面的核心 API 一步步透過找定律的方式推導出來，先以代數性質來設計 API 的好處是怎麼表達各資料型態這件事變的不重要了，就像一開始的 Parser 始終都是個介面的型態參數而已，我們著重在 function 彼此間的關係，而不是內部的實現程式該怎麼寫；最後選擇了 JSON 來實作 Parsers。

Day 21 - Exercise answer