語法分析器
語法分析通常是作為編譯器或者解釋器的一個組件出現的，它是一種特別的程序，接收非結構化的數據(比如文本、任何種類的符號、數字或者字符流)，輸出結構化的數據為結果。比如將csv(逗號分隔值)文本文件解析為二維數組;將Json或者xml解析為樹形數據結構。
目前實際上已經有比較成熟的工具(比如Yacc、ANTLR等)可以根據語法規則自動生成語法分析器的實現代碼，而且執行效率很高。
面向組合子編程
在函數式編程中，面向組合子編程是一種很常用的設計方式。它不同於面向對象編程中常見的由上而下的構建方式，它是一種由下而上的思維模式，它的設計過程首先是抽象、構建最基本的數據類型，然後定義最基礎的函數操作，然後由這些基礎組件逐步構建出複雜的程序。
而這其中基本的數據類型和基礎的函數操作(法則)是需要儘量正交的，提煉出它們是非常考驗設計經驗，所以反覆創造函數、精煉函數、微調數據類型是設計過程中一直進行的事情。
代數設計
通常的面向組合子設計需要先定下數據類型和基本函數，但是還有一種方式是先定函數（法則）再定具體數據類型，這種方式就叫代數設計，下面我們會以這種方式從頭實現一個簡單的語法解析器
開始吧
我們的目標是實現一個通用的語法解析器，所以從最簡單的字符串分析起，比如“asbdkajsfbaks”之類的亂序字母組合。
正如上面所説，我們最開始先不定義數據類型，而是以Parser<T>來代表，意思是輸出T類型的結構化數據的語法分析器。
首先我們創建一個最最簡單的分析器：僅識別一個字符的分析器
fun char(c: Char): Parser<Char>同時我們還需要一個可以執行語法分析器的函數：
fun <T> run(parser: Parser<T>, input: String): Either<ParseError, T>它接收語法分析器Parser<T>和待解析的字符串input，輸出可能成功的T結構化數據或者ParseError錯誤。這裏的ParseError同樣是我們目前先不定義的數據類型，用於指代解析錯誤。
它們可以以這樣使用：
run(char('c'), 'c'.toString()) // -> Right('c')那麼自然而言可以實現一個識別整個字符串的分析器：
fun string(s: String): Parser<String>它對於任意字符串s應該滿足：
run(string(s), s) // -> Right(s)那麼衍生一下，實現識別兩個字符串中任意一個的：
fun orString(s1: String, s2: String): Parser<String>這個實現並不太通用，我們稍微修改一下（為了方便使用這裏添加了中綴語法）：
infix fun <A> Parser<A>.or(p: Parser<A>): Parser<A>這樣它應該可以這樣來使用：
run(string("aaaa") or string("bbbb"), "aaaa") // -> Right("aaaa")
run(string("aaaa") or string("bbbb"), "bbbb") // -> Right("bbbb")這樣我們雖然可以識別各種字符串了，但只能識別一次，我們看能不能讓它可以重複識別：
fun <A> listOfN(n: Int, p: Parser<A>): Parser<List<A>>這樣它應該可以這樣來使用：
run(listOfN(4, string("ab") or string("cde")), "abcdeabcde") // -> Right("abcdeabcde")按照上面這種思路，我們還可以創造出很多的操作函數：
// 返回對應char的重複次數，比如對於"aaab"，charCount('a')結果為3
fun charCount(c: Char): Parser<Int>
// `a`字符零個或多個、然後緊跟着一個或多個`b`字符，返回`a``b`字符的個數
fun pairCount(a: Char, b: Char): Parser<Pair<Int, Int>>
//等等相信讀到這裏你也可以想出非常多的分析任務
等等
等一下，這些函數似乎包含很多重複內容，我們提煉組合子重要的是精煉成最小的原語集、相關的法則。所以我們嘗試提煉一下上面這些操作的共通。
首先，對於fun charCount(c: Char): Parser<Int>該如何實現？它是原語嗎？
其實fun charCount(c: Char): Parser<Int>函數就是提取Parser<List<T>>list中的size，但如果需要的是list的其他屬性呢，所以fun charCount(c: Char): Parser<Int>肯定不是一個原語，它可以看作Parser<List<T>> --size--> Parser<Int>
那麼可以先提取一個分析重複字符的分析器，它是一個原語組合子：
fun <T> zeroOrMany(p: Parser<T>): Parser<List<T>>這裏的
zeroOrMany以及上文的listOfN其實和or已經有很大的不同了，雖然他們同樣是組合多個Parser，但or是上下組合，而它們是左右組合<----------------> +------------------------------------------+ | | | +---------+ | | | Parser1 +-->Parser2--->Parser3--->... | | | | | +--+---------+-----------------------------+ | Parser2 | ^ | | | | Parser3 | | | | v | ... | | | +---------+
Parser<List<T>>到Parser<Int>可以提出另一個組合子：
fun <A, B> Parser<A>.map(f: (A) -> B): Parser<B>那麼charCount就可以變為：
fun charCount(c: Char): Parser<Int> =
zeroOrMany(char(c)).map { it.size }同樣，char(c: Char): Parser<Char>實際上也可以用string()原語來實現：
fun char(c: Char): Parser<Char> =
string(c.toString).map { it.first() }而這時我們還需要一個函數succeed()它對於輸入的任意字符串都會成功地返回值，它可以實現為：
fun <A> succeed(a: A): Parser<A> =
string("").map { a }回頭看一下，charCount(c: Char): Parser<Int>上述的實現實際並不高效，它會把所有匹配的字符串先轉換成List、再取size。那能不能直接返回匹配的string呢。
我們將這個原語命名為slice：
fun <A> slice(p: Parser<A>): Parser<String>這樣我們可以更高效地實現charCount()了：
fun charCount(c: Char): Parser<Int> =
slice(char(c)).map { it.lenght }再看一下zeroOrMany()函數，如果我們想要擴展一下實現oneOrMany()，即識別一個或者多個重複p。
感覺上它不是一個原語，而是可以通過組合zeroOrMany()函數來實現，可以看作一個p之後接着一個zeroOrMany(p)。
換句話説這時我們需要一個連接兩個Parser的函數，在前一個執行成功後執行後一個：
fun <A, B> product(p1: Parser<A>, p2: Parser<B>): Parser<Pair<A, B>>oneOrMany()可以實現為：
fun <T> Parser<T>.oneOrMany(): Parser<List<T>> =
product(this, { this@oneOrMany.oneOrMany() }).map { (a, list) -> listOf(a) + list }我們可以還可以實現一個類似product的函數map2:
fun <A, B, C> map2(p1: Parser<A>, p2: () -> Parser<B>, f: (A, B) -> C): Parser<C>實際上map2也是一個原語級的函數，它和product可以互相實現
而zeroOrMany()也可以由map2來實現：
fun <T> Parser<T>.zeroOrMany(): Parser<List<T>> =
map2(this, { this@zeroOrMany.zeroOrMany() }) { f, l -> listOf(f) + l } or succeed(emptyList())zeroOrMany()的實現中遞歸調用了自己，所以這裏不能使用嚴格求值，否則會在調用的時候直接棧溢出。所以這裏我們使用了惰性求值改寫map2的第二個參數。
當然，我們還可以在不改寫第二個參數的情況下實現非嚴格求值，只需要實現一個單獨的組合子即可：fun <A> lazyParser(p: () -> Parser<A>): Parser<A>大家可以自己嘗試來實現一下
到目前為止我們的原語已經提取的差不多了，最後還有一點需求目前是完成不了的。
比如我們想要先分析一個數字，然後後面接若干個等量的字符，比如“0”、“1a”、“2aa”、“3aaa”。這個需求中後面的Parser是需要根據前一個Parser的結果來決定的。
為了這個需求我們需要引入一個大家比較熟悉的原語flatMap：
fun <A, B> Parser<A>.flatMap(f: (A) -> Parser<B>): Parser<B>flatMap這個函數非常強大，它甚至可以直接實現上面我們提取的部分原語product、map、map2,它原語集中可以承擔左右組合Parser的功能（其他原語都只是上下組合Parser），而它之所以為“原語”，是所有需要左右組合的需求都可以由它來實現。這樣我們的基本原語集進一步精簡了。
最後，check用的原語目前只有string()，為了方便除此之外還需要一個更強大的基本識別原語，這就是可以分析正則表達式的原語regex
fun regex(r: Regex): Parser<String>
理論上而言regex並不是必須的，用其他原語可以實現類似的功能，但這樣做效率並不高
OK，開始構建語法吧
到目前為止我們已經提取了6個基本原語了：
interface Parsers {
fun string(s: String): Parser<String>
fun regex(r: Regex): Parser<String>
fun <A> succeed(a: A): Parser<A>
fun <A> slice(p: Parser<A>): Parser<String>
infix fun <A> Parser<A>.or(p: Parser<A>): Parser<A>
fun <A, B> Parser<A>.flatMap(f: (A) -> Parser<B>): Parser<B>
}以及一些擴展的函數。實際上到目前為止我們已經可以用這些函數來分析語法了，不僅可以分析上下文無關的Json，甚至可以分析上下文相關的C++!
那麼就讓我們開始寫一個Json的分析器吧。
雖然到目前為止我們並沒有具體定義Parser類型以及實際實現上面的6個原語，這導致我們現在其實是沒有辦法實際運行。
但我們還是可以繼續，而且這樣可以讓我們不再受具體實現的限制，反而更容易地精簡我們的函數
對於Json，大家應該還是很熟悉了，也可以閲讀它的語法説明 。
我們首先需要構建一下Json的結構化數據，即最後輸出的數據類型：
sealed class JSON {
object JNull : JSON()
data class JNumber(val num: Double) : JSON()
data class JString(val s: String) : JSON()
data class JBool(val bool: Boolean) : JSON()
data class JArray(val list: List<JSON>) : JSON()
data class JObject(val map: Map<String, JSON>) : JSON()
}這裏會使用一些基於基本原語擴展的簡單函數來方便編寫：
// 直接將解析的結果替換為指定的數據
fun <A, B> Parser<A>.cast(b: B): Parser<B> =
slice(this).map { b }
// 忽略第二個Parser的解析內容
fun <A, B> skipR(p: Parser<A>, end: () -> Parser<B>): Parser<A> =
product(p, lazyParser(end)).map { (a, _) -> a }
// 忽略第一個Parser的解析內容
fun <A, B> skipL(start: Parser<A>, p2: () -> Parser<B>): Parser<B> =
map2(slice(start), p2) { _, b -> b }
// 匹配空白字符
fun whitespace(): Parser<String> = regex("\\s*".toRegex())
// 忽略匹配的Parser右邊接着的空白字符
fun <A> token(p: Parser<A>): Parser<A> =
skipR(p, { whitespace() })
// 匹配浮點數
fun double(): Parser<Double> =
token("[-+]?([0-9]*\\.)?[0-9]+([eE][-+]?[0-9]+)?".r()).map { it.toDouble() }首先我們實現對於數據類型的識別，比如布爾值（true,false）,浮點數（0.314）,空值（null）,字符串（”string value“）
其中比較複雜的是字符串的識別，它的語法是以"開始並以"結尾的範圍內的所有字符串：
// 匹配指定字符結尾的字符串內容
fun thru(s: String): Parser<String> = regex((".*?" + Pattern.quote(s)).toRegex())
fun quoted(): Parser<String> =
skipL(string("\""), { thru("\"").map { it.dropLast(1) } })其他的就很簡單了：
fun Parsers.lit(): Parser<JSON> =
token(string("null")).cast(JNull) or
token(string("true")).cast(JBool(true)) or
token(string("false")).cast(JBool(false)) or
double().map { JNumber(it) } or
token(quoted()).map { JString(it) }接着我們來實現對數組的識別：
[ "HPQ", "IBM", "YHOO", "DELL", "GOOG" ]這裏需要添加兩個工具函數：
// 對”範圍“識別的函數，即取指定字符開始到指定字符結束範圍內數據的函數
fun <A> surround(start: Parser<out Any>, stop: Parser<out Any>, p: () -> Parser<A>) =
skipR(skipL(start, p), { stop })
// 以p2為間隔，提取p序列的函數，即`p p2 p p2 p...`
fun <A> oneOrMoreSep(p: Parser<A>, p2: Parser<Any>): Parser<List<A>> =
map2(p, { skipL(p2, { p }).zeroOrMany() }) { h, l -> h cons l }
fun <A> zeroOrMoreSep(p: Parser<A>, p2: Parser<Any>): Parser<List<A>> =
oneOrMoreSep(p, p2) or succeed(emptyList())然後就可以很輕鬆地構建array的分析器了：
fun Parsers.array(): Parser<JSON> = surround(token(string("[")), token(string("]"))) {
zeroOrMoreSep(value(), token(string(","))).map { vs -> JArray(vs) }
}由於array中的item可以是Json中的任意數據，所以這裏的value()是我們之後會實現的Json整體分析器
最後就剩下object的識別了，其實object和array很相似，只是中間的值還需要進一步按照:為分割符進一步解析為key和value
所以我們先來構造key-value的分析器（Json的key必須為字符串）：
fun Parsers.keyval(): Parser<Pair<String, JSON>> =
product(token(quoted()), { skipL(token(string(":")), { value() }) })然後幾乎和array一樣的方式構造：
fun Parsers.obj(): Parser<JSON> = surround(token(string("{")), token(string("}"))) {
zeroOrMoreSep(keyval(), token(string(","))).map { kvs -> JObject(kvs.toMap()) }
}正如上文所説，我們需要構建一個代表所有Json可識別item的函數value()：
fun Parsers.value(): Parser<JSON> = lit() or obj() or array()Json的分析器已經接近完成了，最後將這些分析子組合起來：
fun jsonParser(p: Parsers): Parser<JSON> = p.run { skipL(whitespace(), { obj() or array() }) }完成！
還有一點收尾工作
在沒有具體實現的情況下，我們也已經實現了Json分析器。但為了可以運行它，我們最後還是以最簡單的方式實現一個Parser<>和Parsers
根據不同的實現方式，Parser可以支持字符串流、File流、網絡流等等，但這裏為了簡單隻提供完整字符串的輸入實現，大家可以嘗試實現其他種類的輸入
首先看Parser<>，正如最開始説的，它是接收**非結構化的數據**，輸出結構化的數據為結果，那麼可以看為：
(String) -> T但回顧我們解析的過程其實是在逐步消費input的過程：解析出一段數據、消耗一段字符串，Parser然後繼續解析下一段數據，以此往復
所以，分析器Parser<>需要的輸入除了原本的輸入字符串之外還需要一個目前已經“消費”的位置信息，input可以改寫為：
data class ParseState(val input: String, val offset: Int = 0)
(ParseState) -> T同時解析結果不能只返回解析的結果，還需要返回此解析結果消耗了多少字符：
data class Result<T>(val a: T, val length: Int)
(ParseState) -> Result<T>同時，返回的結果並不一定是成功的，完全有可能解析出錯，所以返回值也需要包裝一下：
(ParseState) -> Either<Throwable, Result<T>>Either這個類型其實也可以融入到Result中，簡化一下：
sealed class Result<T> {
data class Success<A>(val a: A, val length: Int) : Result<A>()
data class Failure<A>(val error: Throwable) : Result<A>()
}
(ParseState) -> Result<T>這樣，最簡單的Parser<>就定義出來了：
typealias Parser<T> = (ParseState) -> Result<T>接着就是實現Parsers的六個原語了，這個比較簡單，大家可以自己嘗試一下，Sample代碼會在最後一起給出
總結
本文帶大家一步步實現了一個簡單的通用語法分析器，它的功能很簡單，但進一步擴展可以實現很多高級特性：標記、錯誤定位、高級錯誤日誌、分支控制等等。
希望大家通過這一趟旅程可以稍微體會一下函數範式中構建程序的方式，本身而言它和其他構建方式沒有孰高孰低，在特定領域選擇更合適的即可，希望可以為大家在某些程序設計中提供一種新的思維方式。
import java.util.regex.Pattern
interface Parsers {
fun <T> Parser<T>.parseOrThrow(input: String): T
fun string(s: String): Parser<String>
fun regex(r: Regex): Parser<String>
fun <A> succeed(a: A): Parser<A>
fun <A> slice(p: Parser<A>): Parser<String>
infix fun <A> Parser<A>.or(p2: Parser<A>): Parser<A>
fun <A, B> Parser<A>.flatMap(f: (A) -> Parser<B>): Parser<B>
fun <A> lazyParser(p: () -> Parser<A>): Parser<A> =
succeed(Unit).flatMap { p() }
fun <A, B> Parser<A>.map(f: (A) -> B): Parser<B> =
flatMap { a -> succeed(f(a)) }
fun <A, B> product(p1: Parser<A>, p2: () -> Parser<B>): Parser<Pair<A, B>> =
p1.flatMap { a -> p2().map { b -> Pair(a, b) } }
fun <A, B, C> map2(p1: Parser<A>, p2: () -> Parser<B>, f: (A, B) -> C): Parser<C> =
p1.flatMap { a -> p2().map { b -> f(a, b) } }
fun <T> Parser<T>.zeroOrMany(): Parser<List<T>> =
map2(this, { this@zeroOrMany.zeroOrMany() }) { f, l -> listOf(f) + l } or succeed(emptyList())
fun <T> Parser<T>.oneOrMany(): Parser<List<T>> =
product(this, { this@oneOrMany.oneOrMany() }).map { (a, list) -> listOf(a) + list }
// 直接將解析的結果替換為指定的數據
fun <A, B> Parser<A>.cast(b: B): Parser<B> =
slice(this).map { b }
// 忽略第二個Parser的解析內容
fun <A, B> skipR(p: Parser<A>, end: () -> Parser<B>): Parser<A> =
product(p, end).map { (a, _) -> a }
// 忽略第一個Parser的解析內容
fun <A, B> skipL(start: Parser<A>, p2: () -> Parser<B>): Parser<B> =
map2(slice(start), p2) { _, b -> b }
// 匹配空白字符
fun whitespace(): Parser<String> = regex("\\s*".toRegex())
// 忽略匹配的Parser右邊接着的空白字符
fun <A> token(p: Parser<A>): Parser<A> =
skipR(p, { whitespace() })
// 匹配浮點數
fun double(): Parser<Double> =
token(regex("[-+]?([0-9]*\\.)?[0-9]+([eE][-+]?[0-9]+)?".toRegex())).map { it.toDouble() }
// 匹配指定字符結尾的字符串內容
fun thru(s: String): Parser<String> = regex((".*?" + Pattern.quote(s)).toRegex())
fun quoted(): Parser<String> =
skipL(string("\""), { thru("\"").map { it.dropLast(1) } })
// 對”範圍“識別的函數，即取指定字符開始到指定字符結束範圍內數據的函數
fun <A> surround(start: Parser<out Any>, stop: Parser<out Any>, p: () -> Parser<A>) =
skipR(skipL(start, p), { stop })
// 以p2為間隔，提取p序列的函數，即`p p2 p p2 p...`
fun <A> oneOrMoreSep(p: Parser<A>, p2: Parser<Any>): Parser<List<A>> =
map2(p, { skipL(p2, { p }).zeroOrMany() }) { h, l -> h cons l }
fun <A> zeroOrMoreSep(p: Parser<A>, p2: Parser<Any>): Parser<List<A>> =
oneOrMoreSep(p, p2) or succeed(emptyList())
}
infix fun <T> T.cons(l: List<T>): List<T> = listOf(this) + l
sealed class Result<T> {
data class Success<A>(val a: A, val length: Int) : Result<A>()
data class Failure<A>(val error: Throwable) : Result<A>()
}
data class ParseState(val input: String, val offset: Int = 0)
typealias Parser<T> = (ParseState) -> Result<out T>
object SimpleParsers : Parsers {
override fun <T> Parser<T>.parseOrThrow(input: String): T {
val result = this@parseOrThrow(ParseState(input = input))
return when(result) {
is Result.Success -> result.a
is Result.Failure -> throw result.error
}
}
override fun string(w: String): Parser<String> =
{ state ->
val msg = "'" + w + "'"
val i = firstNonmatchingIndex(state.input, w, state.offset)
if (i == -1) // they matched
Result.Success(w, w.length)
else
Result.Failure(RuntimeException(msg))
}
override fun regex(r: Regex): Parser<String> =
{ state ->
val match = r.findPrefixOf(state.input.substring(state.offset, state.input.length))
if (match != null)
Result.Success(match, match.length)
else
Result.Failure(RuntimeException("Expected: " + r))
}
override fun <A> succeed(a: A): Parser<A> =
{ Result.Success(a, 0) }
override fun <A> slice(p: Parser<A>): Parser<String> =
{ state ->
val result = p(state)
when(result) {
is Result.Success -> Result.Success(state.input.substring(state.offset, state.offset + result.length), result.length)
is Result.Failure -> Result.Failure(result.error)
}
}
override fun <A> Parser<A>.or(p2: Parser<A>): Parser<A> =
{ s ->
val resultX = this(s)
when(resultX) {
is Result.Failure -> p2(s)
else -> resultX
}
}
override fun <A, B> Parser<A>.flatMap(f: (A) -> Parser<B>): Parser<B> =
{ s ->
val resultA = this(s)
when(resultA) {
is Result.Success -> {
val resultB = f(resultA.a)(s.copy(offset = s.offset + resultA.length))
when(resultB) {
is Result.Success -> resultB.copy(length = resultB.length + resultA.length)
else -> resultB
}
}
is Result.Failure -> Result.Failure<B>(resultA.error)
}
}
fun firstNonmatchingIndex(s1: String, s2: String, offset: Int): Int {
var i = 0
while (i < s1.length && i < s2.length && i + offset < s1.length) {
if (s1[i + offset] != s2[i]) return i
i += 1
}
return if (s1.length - offset >= s2.length) -1
else s1.length - offset
}
fun Regex.findPrefixOf(source: CharSequence): String? {
val m = this.toPattern().matcher(source)
return if (m.lookingAt())
m.group()
else
null
}
}
sealed class JSON {
object JNull : JSON()
data class JNumber(val num: Double) : JSON()
data class JString(val s: String) : JSON()
data class JBool(val bool: Boolean) : JSON()
data class JArray(val list: List<JSON>) : JSON()
data class JObject(val map: Map<String, JSON>) : JSON()
companion object {
fun Parsers.lit(): Parser<JSON> =
token(string("null")).cast<String, JSON>(JNull) or
token(string("true")).cast(JBool(true)) or
token(string("false")).cast(JBool(false)) or
double().map { JNumber(it) } or
token(quoted()).map { JString(it) }
fun Parsers.array(): Parser<JSON> = surround(token(string("[")), token(string("]"))) {
zeroOrMoreSep(value(), token(string(","))).map { vs -> JArray(vs) }
}
fun Parsers.keyval(): Parser<Pair<String, JSON>> =
product(token(quoted()), { skipL(token(string(":")), { value() }) })
fun Parsers.obj(): Parser<JSON> = surround(token(string("{")), token(string("}"))) {
zeroOrMoreSep(keyval(), token(string(","))).map { kvs -> JObject(kvs.toMap()) }
}
fun Parsers.value(): Parser<JSON> = lit() or obj() or array()
fun jsonParser(p: Parsers): Parser<JSON> = p.run { skipL(whitespace(), { obj() or array() }) }
}
}
// Sample
val jsonTxt = """
{
"Company name" : "Microsoft Corporation",
"Ticker" : "MSFT",
"Active" : true,
"Price" : 30.66,
"Shares outstanding" : 8.38e9,
"Related companies" : [ "HPQ", "IBM", "YHOO", "DELL", "GOOG" ]
}
""".trimIndent()
fun main(args: Array<String>) {
val json: Parser<JSON> = JSON.jsonParser(SimpleParsers)
println(SimpleParsers.run { json.parseOrThrow(jsonTxt) })
}
