Sponsor Link
環境&対象
- macOS Monterery beta 5
- Xcode 13 beta5
lexer/ parser を作ってみるシリーズ
[Swift] 数式を評価する lexer/parser を作る (1 + 1 を計算する) (1)
[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 を計算する) (2)
[Swift] 数式を評価する lexer/parser を作る (+1.0 + +1.0 を計算する) (3)
[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 + 1.0 を計算する) (4)
[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 * 1.0 を計算する) (5)
前回までにやったこと
1.0 だけでなく、+1.0 も項として理解できるようになりました。つまり、”1.0 + 1.0″ だけでなく、”1.0 + +1.0″ も理解して評価できます。
さらに、演算子を + だけではなく、 +-*/ の四則演算をできるようにしました。
[Swift] 数式を評価する lexer/parser を作る (+1.0 + +1.0 を計算する) (3)
+- だけでなく、 */ に対応したことで、演算子の順序を考える必要が出てくることになるのですが、
現在は、2項+演算子 ( 1.0 + 2.0 ) であり、複数の演算子が出てこないので、演算子の計算順序の問題は出てきません。
現時点で評価できる数式は、ずいぶんと制限のある式だけなので、もう少し拡張していきます。
- 3項以上を持つ数式を評価できるようにする
“1.0 + 2.0 + 3.0” を評価できるようになる - 演算子の優先順位を理解して評価できるようにする
“1.0 + 2.0 * 3.0” を評価すると 7.0 になる
3項以上を持つ数式評価への対応
3項以上を持つ数式とは?
これまでは、”1.0 + 1.0″ のような <項>+<演算子>+<項>という数式を対象としていました。
この項数が3以上である数式とは、<項>+<演算子>+<項>+<演算子>+・・・・・+<演算子>+<項>という数式になります。
全く自由な形式ではなくて、以下のような形で、2つの項の間には常に演算子が存在し、数式の最後には、項がくる必要があります。
<項>+ (<演算子>+<項>) + (<演算子>+<項>) + (<演算子>+<項>) + (<演算子>+<項>) + (<演算子>+<項>)
つまり、
“1.0 + 2.0 + 3.0″ は評価できるようになりますが、”1.0 + 2.0 + ” や “1.0 + 2.0 3.0 + 4.0” は数式として不正と判断しますということです。
テスト -> 実装 の繰り返し
テストは、おおきく3つの部分にわかれます。lexer 部分のテストと parser 部分のテスト、評価計算のテスト です。
lexer テスト
以下のようなテストコードを追加します。(演算子の計算順序は、まだテスト対象としていません)
3項以上の数式を渡して、適切な数の Token が確認できるか、各 Token が正しく認識されているか をテストしています。
func test_lexer_multipleTerms_5terms() throws {
let sut = BruteForceLexer()
let tokens = try XCTUnwrap(sut.lex("2.0 * 2.1 + 2.2"))
XCTAssertEqual(tokens.count, 5)
XCTAssertEqual(try XCTUnwrap(tokens[0].doubleValue), 2.0, accuracy: 0.0001)
XCTAssertEqual(tokens[1].opeString, "*")
XCTAssertEqual(try XCTUnwrap(tokens[2].doubleValue), 2.1, accuracy: 0.0001)
XCTAssertEqual(tokens[3].opeString, "+")
XCTAssertEqual(try XCTUnwrap(tokens[4].doubleValue), 2.2, accuracy: 0.0001)
}
テストコードを書きやすくするために、Token の定義にアクセサを定義しています。また、エラーを明確にするために、lexer からは Error を throw するように変更しました
lexer 対象文字列は、lex 関数の引数で受けるようにしました。
前回までに作成したコードを修正していないので、実行しようとしても コンパイルエラーです。
lexer 実装
以下のような実装にしました。
class BruteForceLexer {
typealias Error = MathLexerError
let numericCharacterSet = CharacterSet.numericCharacters
let groupingSeparator = Locale.current.groupingSeparator ?? ""
func lex(_ string: String) throws -> [Token] {
var foundTokens: [Token] = []
let scanner = Scanner(string: string)
scanner.charactersToBeSkipped = CharacterSet.whitespaces
guard !scanner.isAtEnd else { return foundTokens }
// (1) read 1st token
guard let numericString = scanner.scanCharacters(from: CharacterSet.numericCharacters) else { throw Error.InvalidExpression }
guard let value = Double(numericString.filter({ !(groupingSeparator.contains($0)) })) else { throw Error.InvalidToken }
foundTokens.append(Token.Numeric(value))
while !scanner.isAtEnd {
// (2) read 2nd token
guard let ope = scanner.scanCharacters(from: CharacterSet.operatorCharacters) else { throw Error.InvalidExpression }
guard ope.count == 1 else { throw Error.InvalidToken }
foundTokens.append(Token.Operator(String(ope.first!)))
// (3) read 3rd token
guard let numericString = scanner.scanCharacters(from: CharacterSet.numericCharacters) else { throw Error.InvalidExpression }
guard let value = Double(numericString.filter({ !(groupingSeparator.contains($0)) })) else { throw Error.InvalidToken }
foundTokens.append(Token.Numeric(value))
}
return foundTokens
}
}
enum MathLexerError: Error {
case InvalidToken
case InvalidExpression
}
- 最初に、一番初めの項を読みます。想定する文字列でなかったり、数値として認識できなければエラー
- 2つ目の項は、演算子のはずなので、演算子を意味する文字列でなかったり、対応している演算子(現在は2文字以上は非対応)でなければ、エラー
- 3つ目の項は、数値のはずなので、想定する文字列でなかったり、数値として認識できなければエラー
- 以降は、2つ目の項、3つ目の項 の評価を 4,5番目、6,7番目へと 文字列を全て走査し終わるまで繰り返し適用していきます。
parser テスト
Token が切り出せた後は、parser が Token 列から AST (Abstract Syntax Tree) を生成します。
“1.0 + 2.0 – 3.0”は、どのような AST になるかを考えて、以下のような AST を作ることとしました。
flowchart TD - --> + - --> 3.0 + --> 1.0 + --> 2.0
ポイントは、2分木を繰り返して、局所的には2項と演算子を持つ構造を ネストさせることで、より複雑な数式を保持する点です。
今回は、生成された AST の内容もチェックするテストコードにしました。
func test_parse_5Tokens_successToParse() throws {
let tokens: [Token] = [.Numeric(1.0), .Operator("+"), .Numeric(2.0), .Operator("-"), .Numeric(3.0)]
let sut = MathExpressionParser()
let expression = try XCTUnwrap(sut.parse(tokens))
try XCTAssertTokenEqual(expression.token, .Operator("-"))
let left = try XCTUnwrap(expression.left)
try XCTAssertTokenEqual(left.token, .Operator("+"))
let leftLeft = try XCTUnwrap(left.left)
try XCTAssertTokenEqual(leftLeft.token, .Numeric(1.0))
let leftRight = try XCTUnwrap(left.right)
try XCTAssertTokenEqual(leftRight.token, .Numeric(2.0))
let right = try XCTUnwrap(expression.right)
try XCTAssertTokenEqual(right.token, .Numeric(3.0))
}
Token が期待と一致しているかの XCTAssertTokenEqual を便利関数として使っています。
parser 実装
それまでの結果としての AST を左側の子供に持つように、新しい演算子と項を使って、新しい AST を作ります。
func parse(_ tokens:[Token]) throws -> MathExpression? {
guard tokens.count > 0 else { return nil }
var index:Int = 0
// get 1st token, confirm it is numeric
let firstToken = tokens[index]
index += 1
guard firstToken.isNumeric else { return nil }
var mathExpression = MathExpression(firstToken)
while (index tokens.count) {
guard (tokens.count - index) >= 2 else { return nil }
// should see operator first, then numeric
let opeToken = tokens[index]
index += 1
let rightToken = tokens[index]
index += 1
guard opeToken.isOperator, rightToken.isNumeric else { return nil }
let nextExpression = MathExpression(opeToken, left: mathExpression, right: MathExpression(rightToken))
mathExpression = nextExpression
}
return mathExpression
}
上記コードで作成したテストコードをパスすることが確認できます。
eval テスト
AST を作った後に、計算できなければいけないので、MathExpression の calc も拡張します。
AST をテスト用に単独で構築するのが手間だったので、parser のテストに calc も追記してテストすることとしました。
func test_parse_5Tokens_successToParse() throws {
let tokens: [Token] = [.Numeric(1.0), .Operator("+"), .Numeric(2.0), .Operator("-"), .Numeric(3.0)]
let sut = MathExpressionParser()
let expression = try XCTUnwrap(sut.parse(tokens))
try XCTAssertTokenEqual(expression.token, .Operator("-"))
let left = try XCTUnwrap(expression.left)
try XCTAssertTokenEqual(left.token, .Operator("+"))
let leftLeft = try XCTUnwrap(left.left)
try XCTAssertTokenEqual(leftLeft.token, .Numeric(1.0))
let leftRight = try XCTUnwrap(left.right)
try XCTAssertTokenEqual(leftRight.token, .Numeric(2.0))
let right = try XCTUnwrap(expression.right)
try XCTAssertTokenEqual(right.token, .Numeric(3.0))
XCTAssertEqual(try XCTUnwrap(expression.calc()), 0.0, accuracy: 0.0001) // 1 + 2 - 3 = 0
}
この段階では、演算子の優先順序を考慮していないので、* や / を混ぜると(コードを修正しても)テストにパスできません。
TDD では 1つづつ 進めていくのがポイントです。
eval 実装
AST は、2分木の形なので、最上位ノードから、左側の計算 -> 右側の計算 -> 自分の計算 という形で木構造を評価します。
class MathExpression {
var token: Token
public var left: MathExpression? = nil
public var right: MathExpression? = nil
public weak var parent: MathExpression? = nil
public init(_ token: Token) {
self.token = token
}
public init(_ token: Token, left: MathExpression? = nil, right: MathExpression? = nil, parent: MathExpression? = nil ) {
self.token = token
self.parent = parent
self.left = left
self.right = right
}
var topTokenPriority:Int {
return token.priority
}
func calc() throws -> Double {
// (1)
if token.isNumeric {
guard let doubleValue = token.doubleValue else { throw MathExpressionError.ErrorInEvaluation }
return doubleValue
}
// (2)
guard let leftValue = try left?.calc() else { throw MathExpressionError.ErrorInEvaluation }
guard let rightValue = try right?.calc() else { throw MathExpressionError.ErrorInEvaluation }
guard let opeString = token.opeString else { throw MathExpressionError.InvalidAST }
// (3)
switch opeString {
case "+":
return leftValue + rightValue
case "-":
return leftValue - rightValue
case "*":
return leftValue * rightValue
case "/":
return leftValue / rightValue
default:
throw MathExpressionError.InvalidAST
}
}
}
- AST のノードが、数値であれば、その値を返します
- 数値でない時は、左側と右側のそれぞれを評価します
- 自身の演算子と左側・右側の値を使って、自身の評価値を計算します
ここでは、四則演算全てを計算していますが、演算子の優先順序を考慮していないので、1 + 2 * 3 は、9 になってしまいます。
演算子の優先順序への対応は、生成される AST の構造で解決する予定なので、評価するためのコード自体はこのままで良い予定です。
できたこと:数式を評価する lexer/parser を作る(4)
- 3項以上持つ数式に対応した
説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。
Sponsor Link