点渐渐连成了线
作者：@nixzhu
在前一篇解析器组合子之后，我对它算是入了门。最近同事想写一个HTML到Attributed String的转换器，但用第三方库生成的中间数据结构不能满足要求，因此我提议用解析器组合子来做这一步，我以为一个晚上就能搞定。
结果很明显，没有成功。原因是我实现的的解析器组合子还太弱，不能处理左递归（在解析JSON时这刚好不是一个问题）。
处理左递归并不是一件简单的事（至少对我来讲），因此睡了一觉之后，我想到了第二个方案：基于栈的解析。
简单来说，HTML是一些配对标签包裹着字符串或其它配对标签的序列。在解析的过程中，判断当前Token的表意，来决定是否将其压入栈中，或者从栈中取出对应的Token来合成“值”并重新压入栈中。最后，我们将栈中的数据变成一个序列即可。
如果我们只关注特定的一些标签，例如加粗、斜体、段落、链接。那么Token的定义可如下：
enum Token {
case plainText(string: String)
case beginBoldTag
case endBoldTag
case beginItalicTag
case endItalicTag
case beginParagraphTag
case endParagraphTag
case beginAnchorTag(href: String)
case endAnchorTag
}解析器组合子并非一无是处，在没有左递归的场合，它依然能工作得很好。比如生成Token串的这一步。
例如解析纯文本：
let plainText: Parser<Token> = {
let letter = satisfy({ $0 != "<" && $0 != ">" })
let string = map(many1(letter)) { String($0) }
return map(string) { .plainText(string: $0) }
}()解析加粗开始标签：
let beginBoldTag: Parser<Token> = map(word("<b>")) { _ in .beginBoldTag }等等，都很容易写出。
然后利用这些小的解析器，我们就可以做tokenize了：
func tokenize(_ htmlString: String) -> [Token] {
var tokens: [Token] = []
var remainder = htmlString.characters
let parsers = [
plainText,
beginBoldTag,
endBoldTag,
beginItalicTag,
endItalicTag,
beginParagraphTag,
endParagraphTag,
beginAnchorTag,
endAnchorTag
]
while true {
guard !remainder.isEmpty else { break }
let remainderLength = remainder.count
for parser in parsers {
if let (token, newRemainder) = parser(remainder) {
tokens.append(token)
remainder = newRemainder
}
}
let newRemainderLength = remainder.count
guard newRemainderLength < remainderLength else {
break
}
}
return tokens
}接下来该做解析了，先定义解析的目标，这与我们之前对（简化的）HTML的分析一致：
indirect enum Value {
case plainText(string: String)
case boldTag(value: Value)
case italicTag(value: Value)
case paragraphTag(value: Value)
case anchorTag(href: String, value: Value)
case sequence(values: [Value])
}不过需要考虑的是，我们压入栈中的元素可能是Token，也可能是Value，但我们也知道Swift的Array只能装同一种类型的数据。因此我们用enum包装一下：
enum Element {
case token(Token)
case value(Value)
}这样，Stack就很容易实现了：
class Stack {
var array: [Element] = []
func push(_ element: Element) {
array.append(element)
}
func pop() -> Element? {
guard !array.isEmpty else { return nil }
return array.removeLast()
}
}最后，我们编写解析函数：
func parse(_ tokens: [Token]) -> Value {
let stack = Stack() // # 1
var next = 0
func _parse() -> Bool {
guard next < tokens.count else { // # 3
return false
}
let token = tokens[next]
switch token {
case .plainText(let string): // # 4
stack.push(.value(.plainText(string: string)))
case .beginBoldTag: // # 5
stack.push(.token(.beginBoldTag))
case .endBoldTag: // # 6
var elements: [Element] = []
while let element = stack.pop() {
if case .token(let value) = element {
if case .beginBoldTag = value {
break
}
}
elements.append(element)
}
if elements.count == 1 { // # 7
let element = elements[0]
if let value = element.value {
stack.push(.value(.boldTag(value: value)))
} else {
print("todo: \(elements)")
}
} else {
stack.push(.value(.boldTag(value: .sequence(values: elements.reversed().map({ $0.value }).flatMap({ $0 })))))
}
case .beginItalicTag:
stack.push(.token(.beginItalicTag))
case .endItalicTag:
// ...
case .beginParagraphTag:
stack.push(.token(.beginParagraphTag))
case .endParagraphTag:
// ...
case .beginAnchorTag(let href):
stack.push(.token(.beginAnchorTag(href: href)))
case .endAnchorTag:
// ...
}
return true
}
while true { // # 2
if !_parse() {
break
}
next += 1
}
return .sequence(values: stack.array.map({ $0.value }).flatMap({ $0 })) // # 8
}我将类似的部分删除了，简单说明一下：
- 先创建一个栈，定义next指针，它用来从tokens数组中取下一个token；
- 然后我们不停地调用
_parse()函数，当然每次都要增加next，同时利用_parse()的返回值来做循环的退出； - 在
_parse()中，确保next不越界（刚好做退出条件），然后判断当前的token； - 遇到plainText，直接压入栈中；
- 遇到开始标签，也压入栈中；
- 遇到结束标签，就从栈中取出对应到此结束标签的开始标签及之间的所有元素；
- 通过判断元素的个数，我们决定是将其变成某个特定标签的Value再压入栈中，还是将其变为sequence（注意顺序）作为对应标签的value；
- 最后将栈中的所有元素作为sequence变成Value返回。
大概的逻辑就这么多。如果要解析更多标签，可对应增加Token和Value的case以及解析判断。
你可在此处获取完整的Playground代码。
写解析器是一项很好的编程活动，除了能提高代码编写技术（将多种知识结合起来），也能丰富我们的思考方式。事实上，我认为与编译器相关的技术，例如解析器、自动机、中间表示等都是很实在的技术，日常学习或重温都很有好处。同样，作为程序员，也要时时温习数据结构与算法。
欢迎转载，但请一定注明出处！ https://github.com/nixzhu/dev-blog