代码地址
这个示例为希望被解析的表达式编写解析器，并为这些表达式编写一个求值器，然后将其嵌入界面中。
解析
基于解析器组合算子中的算术表达式解析器，引入额外的抽象层级。
之前，编写的解析器会直接返回计算结果。比如在解析 “2*3” 这样的乘法表达式时:
let multiplication = curry { return $0*($1 ?? 1) }<^>integer<*>(character{ $0 == "*" }*>integer).optional
multiplication 的类型是 Parser，也就是说，在这个传入字符串 “2*3” 并执行解析器之后， 会返回整数值 6。只有在表达式中不含有对任何外部数据的依赖的时候，才能够直接将结果计算出来。然而，在电子表格中，希望可以表达类似于 A3 这样对其它单元格值的引用，或者是像 SUM(A1:A3) 这样的函数调用。
要支持这些特性，解析器需要将输入的字符串转换为一棵抽象语法树 (abstract syntax tree, AST)，这是一种用于描述表达式内容的中间表现形式。在转换为抽象语法树后，可以取得这些结构化的数据，再对其做实际的计算。将这种中间表现形式定义为一个枚举:
indirect enum Expression {
case int(Int)
case reference(String, Int)
case infix(Expression, String, Expression)
case funcation(String, Expression)
}
枚举 Expression 包含四个枚举值:
- int表示简单的数值。
- reference表示对其它单元格内值的引用，比如"A3"。其中，列引用被指定为从"A"开始的大写字母。而行引用则被定义为从 0 开始的数字。枚举值 reference 有两个关联值，一个字符串和一个整数，用于储存该引用的行与列。
- infix表示类似"A2+3"这样位于运算符左右侧两个参数之间的一次运算。枚举值infix中的关联值储存了运算符左侧的表达式，运算符本身，以及右侧的表达式。
- function表示一个类似于"SUM(A1:A3)"这样的函数调用。第一个关联值是函数名，第二个则是函数的参数(在这个示例中，函数只能够接收单个参数)。
在有了的 Expression 枚举之后，就可以为每种表达式编写一个解析器了。
枚举值 int 的解析器，可以利用解析器组合算子中的整数解析器，然后将整数结果封装为一个 Expression 类型:
extension Expression {
static var intParser: Parser<Expression> {
return { int($0) } <^> integer
}
}
if let v = Expression.intParser.run("123") { print(v) }
/*输出：
(Spreadsheet.Expression.int(123), "")
*/
行列坐标的解析器，先定义一个大写字母的解析器，然后将大写字母的解析器与一个整数解析器合并起来，再将解析结果封装为枚举值 .reference:
let capitalLetter = character { CharacterSet.uppercaseLetters.contains($0) }
extension Expression {
static var referenceParser: Parser<Expression> {
return curry { reference(String($0), $1) } <^> capitalLetter <*> integer
}
}
if let v = Expression.referenceParser.run("A3") { print(v) }
/*输出：
(Spreadsheet.Expression.reference("A", 3), "")
*/
枚举值 .function的解析器，需要解析出一个函数名 (一个或更多个大写字 母)，以及接下来的圆括号中的表达式。在此，圆括号中的表达式将只支持形如 “A1:A2” 的 参数类型。需要先定义三个额外的辅助函数。首先添加函数 string创建一个用于匹配特定字符串的解析器，使用已有的函数 character 就来实现。接着为 Parser 定义一个便利方法，用来将当前解析器封装在一个用于解析左右圆括号的 解析器中。然后定义一个将接受三个参数的非柯里化函数转化为柯里化函数的函数。这样就可以继续为函数表达式编写解析器了:
func string(_ string: String) -> Parser<String> {
return Parser<String> { input in
var remainder = input
for c in string {
let paser = character { $0 == c }
guard let (_, newRemainder) = paser.run(remainder) else { return nil }
remainder = newRemainder
}
return (string, remainder)
}
}
if let v = string("SUM").run("SUM") { print(v) }
/*输出：
("SUM", "")
*/
extension Parser {
var parenthesized: Parser<Result> {
return string("(") *> self <* string(")")
}
}
if let v = string("SUM").parenthesized.run("(SUM)") { print(v) }
/*输出：
("SUM", "")
*/
func curry<A, B, C, D>(_ f: @escaping (A, B, C) -> D) -> (A) -> (B) -> (C) -> D {
return { a in { b in { c in f(a, b, c) } } }
}
extension Expression {
static var funcationParser: Parser<Expression> {
let name = ({ String($0) } <^> capitalLetter.many1)
let argument = curry { infix($0, $1, $2) } <^> referenceParser <*> string(":") <*> referenceParser
return curry { funcation($0, $1) } <^> name <*> argument.parenthesized
}
}
if let v = Expression.funcationParser.run("SUM(A1:A2)") { print(v) }
/*输出：
(Spreadsheet.Expression.funcation("SUM", Spreadsheet.Expression.infix(Spreadsheet.Expression.reference("A", 1), ":", Spreadsheet.Expression.reference("A", 2))), "")
*/
在 functionParser 中，首先定义了一个用于解析函数名的解析器。接下来则为函数的参数 定义了解析器，该参数是一个使用 “:” 作为运算符的 .infix 表达式，并以另外两个单元格的引用作为运算参数。最后按照先解析函数名，再解析圆括号里函数参数的顺序，将上述解析器进行了合并。
定义一个对整数进行运算表达式解析器，不过这个 解析器可以处理多个运算符。先定义一个解析器 calculation，用于解析跟随在整数之后的 “+” 或 “-” 或 “*” 或 “/” 符号:
let calculation = curry { ($0, $1) } <^> (string("+") <|> string("-") <|> string("*") <|> string("/")) <*> intParser
该解析器的结果是一个包含运算符与整数的多元组。接着可以定义一个能够零次或多次解析输入字符串的解析器，像... <^> intParser <*> calculation.many1这样。需要编写一个用来合并右侧两个解析器结果的函数。这个函数要接收的参数类型是已知的，它们分别是一个 (从 intParser 返回的) Expresssion，以及一个由解析器 calculation.many1 返回的元素类型为多元组 (String, Expression) 的数组:
func combineOperands(first: Expression, rest: [(String, Expression)]) -> Expression {
return rest.reduce(first) { Expression.infix($0, $1.0, $1.1) }
}
上述函数使用了 reduce 将第一个表达式与之后由 .infix 表达式返回的 (operator, expression) 合并。先可以像这样编写第一版 infixParser 了:
extension Expression {
static var infixParser: Parser<Expression> {
let calculation = curry { ($0, $1) } <^> (string("+") <|> string("-") <|> string("*") <|> string("/")) <*> intParser
return curry(combineOperands(first:rest:)) <^> intParser <*> calculation.many1
}
}
if let v = Expression.infixParser.run("10+5-3") { print(v) }
/*输出：
(Spreadsheet.Expression.infix(Spreadsheet.Expression.infix(Spreadsheet.Expression.int(10), "+", Spreadsheet.Expression.int(5)), "-", Spreadsheet.Expression.int(3)), "")
*/
if let v = Expression.infixParser.run("2*3*4") { print(v) }
/*输出：
(Spreadsheet.Expression.infix(Spreadsheet.Expression.infix(Spreadsheet.Expression.int(2), "*", Spreadsheet.Expression.int(3)), "*", Spreadsheet.Expression.int(4)), "")
*/
需要再解决运算只能在整数间进行的限制，为此引入了 primitiveParser，它能够解析出任意可以被算术运算符进行运算的元素:
func lazy<A>(parser: @autoclosure @escaping () -> Parser<A>) -> Parser<A> {
return Parser<A> { parser().run($0) }
}
extension Expression {
static var primitiveParser: Parser<Expression> {
return return intParser <|> referenceParser <|> funcationParser
}
static var parser = lazy(parser: infixParser) <|> lazy(parser: infixParser).parenthesized <|> primitiveParser
}
primitiveParser 使用了选择解析运算符 <|>，定义中可运算的元素可以是一个整数，一个单元 格引用，或者一个函数调用。
parser 使用了选择解析运算符 <|>，定义中可运算的元素可以是一个子表达式，是一个被圆括号括起的子表达式，或者一个primitiveParser。这里最重要的部分是对辅助函数 lazy 的使用。必须确保任意表达式的解析器 parser 仅在必要时才被求值。否则将会陷入无尽的循环之中。为了实现这个功能，lazy 使用 @autoclosure 将参数封装在了一个函数中。
现在可以用 primitiveParser 替换 intPaser 来编写之前的 infixParser :
extension Expression {
static var infixParser: Parser<Expression> {
let calculation = curry { ($0, $1) } <^> (string("+") <|> string("-") <|> string("*") <|> string("/")) <*> primitiveParser
return curry(combineOperands(first:rest:)) <^> primitiveParser <*> calculation.many1
}
}
/*输出：
(Spreadsheet.Expression.infix(Spreadsheet.Expression.infix(Spreadsheet.Expression.int(2), "+", Spreadsheet.Expression.int(4)), "*", Spreadsheet.Expression.funcation("SUM", Spreadsheet.Expression.infix(Spreadsheet.Expression.reference("A", 1), ":", Spreadsheet.Expression.reference("A", 2)))), "")
*/
求值
求值阶段的目标是将一棵 Expression 树转换为一个实际的结果。首先定义一 个 Result 类型:
enum Result {
case int(Int)
case list([Result])
case error(String)
}
Result 类型共有三个枚举值:
- int用于结果为整数的表达式的求值，比如"2*3"或是"SUM(A1:A3)"(假设在单元格A1 - 至 A3 中的值都是合法的)。
- list用于返回多个结果的表达式的求值。在示例中，只有像"A1:A3"这样的表达式会发生这种情况，这些表达式通常为 “SUM” 或是 “MIN” 这类函数的参数。
- error表示在求值过程中出现的错误，在其关联值中会储存错误的详细说明。
对 Expression 进行求值，会在其拓展中添加一个 evaluate 方法，参数 context 是一个数组，其中包含了该电子表格中其他单元格的所有表达式，这是为了能够处理像是 A2 这样的单元格引用。简单起?将该电子表格限制为只有一列单元格，这样就可以使用一个简单的数组来表示所有的表达式了。
接下来只需要对 Expression 中不同的枚举值依次进行匹配，然后返回对应的 Result 值 就可以了。下面是 evaluate 方法:
extension Expression {
func evaluate(context: [Expression?]) -> Result {
switch self {
case let .int(x):
return .int(x)
case let .reference(_, row):
return context[row]?.evaluate(context: context) ?? Result.error("Invalid reference \(self)")
case .funcation:
return evaluateFunction(context: context) ?? .error("Invalid function call \(self)")
case let .infix(l, op, r):
return self.evaluateArithmetic(context: context) ?? self.evaluateList(context: context) ?? .error("Invalid operator \(op) for operands \(l), \(r)")
}
}
}
第一个匹配条件 .int 很容易处理。.int 的关联值已经是一个整数值，只需要提取该值然后返回一个 .int 结果值就可以了。
第二个匹配条件 .reference 则稍微复杂一些。考虑到电子表格被限制为仅有一列，只需要匹配对 A 列单元格的引用，并且将第二个关联值与变量 row 进行 绑定。在获得被引用单元格的行坐标后，利用 context 参数查询该单元格的表达式，并且 为其表达式递归地调用 evaluate。在该引用不存在的情况下，将一个 .error 作为结果值返回。
第三个匹配条件 .function，只是将求值任务转移给了 Expression 另一个被命名为 evaluateFunction 的方法。虽然可以将这部分代码也写入 evaluate 方法中，但为了避免单个方法太过冗?决定将这个步骤提了出来。evaluateFuction 的代码如下:
extension Expression {
func evaluateFunction(context: [Expression?]) -> Result? {
guard case let Expression.funcation(name, parameter) = self, case let .list(list) = parameter.evaluate(context: context) else {
return nil
}
switch name {
case "SUM":
return list.reduce(.int(0), lift(+))
case "MIN":
return list.reduce(.int(Int.max), lift { min($0, $1) })
default:
return .error("Unknown function \(name)")
}
}
}
guard 语句会先检查该方法是否确实被 .function 枚举值调用，然后确定表达式中函数的参数求值后的结果是否为一个 .list。如果不满足以上某个条件，会直接返回 nil。
剩下的 switch 语句并不复杂:为每个函数名实现一个匹配条件，然后利用 reduce 对从 parameter 中求得的列表进行相应的计算就可以了。
这里要提到一个重要的细节，list 是一个元素类型为 Result 的数组。因此不能直接使用标准的算术运算符 (比如 “+”) 或是函数 (比如 min)。为此定义一个函数 lift，用于将任 意类型为 (Int, Int) -> Int 的函数转换为一个类型为 (Result, Result) -> Result 的函数:
func lift(_ op: @escaping (Int, Int) -> Int) -> (Result, Result) -> Result {
return { lhs, rhs in
guard case let (Result.int(x), Result.int(y)) = (lhs, rhs) else {
return .error("Invalid operands \(lhs), \(rhs) for integer operator")
}
return .int(op(x, y))
}
}
在这里必须先确保处理的确实是两个 Result.int 值，否则会返回一个 .error 作为结果。一旦获取了两个整数，就可以由参数传入的运算函数 op 来计算结果，并将其再封装回一个 Result.int 值。
evaluate 方法要处理的最后一个条件是枚举值 .infix。将对 .infix 表达式的求值代码拆分到了 Expression 的两个拓展中。第一个是 evaluateArithmetic。这个方法尝试在当 .infix 表达式是一个算术表达式时对其进行求值，如果求值失败则会返回 nil:
extension Expression {
func evaluateArithmetic(context: [Expression?]) -> Result? {
guard case let .infix(l, op, r) = self else {
return nil
}
let x = l.evaluate(context: context)
let y = r.evaluate(context: context)
switch op {
case "+":
return lift(+)(x, y)
case "-":
return lift(-)(x, y)
case "*":
return lift(*)(x, y)
case "/":
return lift(/)(x, y)
default:
return nil
}
}
}
由于这个方法可以被任意的 Expression 调用，需要先检查是否真的在处理一个 .infix 表达式。同样使用 guard 语句来直接获取关联值:左侧的表达式，运算符，以及右侧的表达式。
接着会为左右两侧的表达式调用 evaluate，然后通过 switch 语句匹配运算符来计算结果。这里又一次使用了 lift 函数，使像是两个 Result 值相加这样的运算变得可行。这里要注意不必再考虑 x 或 y 可能不是 .int 的情况，lift 函数会搞定的。
Expression 中第二个用于计算 .infix 表达式的方法用于处理列表运算符，比如 “A1:A3”:
extension Expression {
func evaluateList(context: [Expression?]) -> Result? {
guard case let .infix(l, op, r) = self, op == ":", case let .reference(_, row1) = l, case let .reference(_, row2) = r else {
return nil
}
return .list((row1...row2).map{ Expression.reference("A", $0).evaluate(context: context) })
}
}
再一次先检查 evvaluateList 是否被适当的 Expression 调用。在 guard 语句中，检查了是否在处理一个 .infix 表达式，其中的运算符是否是一个 “:”，以及左右两个表达式是不是引用 “A” 列中某个单元格的 .reference。如果不匹配其中任何一个条件，会直接返回 nil。
如果所有的检查都通过，会对从 row1 开始，到包括 row2 在内的所有序列值进行映射，对这些单元格中的表达式依次进行求值，再将映射得到的结果封装在 .list 中作为结果返回。
以上就是需要在 Expression 的 evaluate 方法中实现的全部内容了。考虑到总是希望在对某个单元格求值时先求得 context 中另一个单元格的值 (需要能解决对单元格的引用)， 添加一个额外的便利方法来对一个表达式数组进行求值:
func evaluate(expressions: [Expression?]) -> [Result] {
return expressions.map{ $0?.evaluate(context: expressions) ?? .error("Invalid expression \($0)") }
}
现在可以定义一个示例表达式的数组并尝试对它们进行求值:
let expressions: [Expression] = [
.infix(.infix(.int(1), "+", .int(2)), "*", .int(3)),
.infix(.reference("A", 0), "*", .int(3)),
.funcation("SUM", .infix(.reference("A", 0), ":", .reference("A", 1)))
]
print(evaluate(expressions: expressions))
/*输出：
[Spreadsheet.Result.int(9), Spreadsheet.Result.int(27), Spreadsheet.Result.int(36)]
*/
用户界面
构建了上图中用于嵌入解析与求值代码的用户界面。然而这个应用还有诸多限制，代码也还有很大的优化空间。比如一个单元格不能使用混合运算；不必因为用户修改了单个单元格的内容就对所有的单元格进行解析和求值；如果 10 个单元格同时引用了一 个单元格，那么这个单元格会被求值 10 次……
