[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 + 1.0 を計算する) (4)

Swift

ここまでにつくってきた lexer/parser を拡張して、複数項の数式を評価できるようにします

環境&対象

以下の環境で動作確認を行なっています。

  • macOS Monterery beta 5
  • Xcode 13 beta5

前回までにやったこと

1.0 だけでなく、+1.0 も項として理解できるようになりました。つまり、"1.0 + 1.0" だけでなく、"1.0 + +1.0" も理解して評価できます。

さらに、演算子を + だけではなく、 +-*/ の四則演算をできるようにしました。

Swift[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
}
コード解説
  1. 最初に、一番初めの項を読みます。想定する文字列でなかったり、数値として認識できなければエラー
  2. 2つ目の項は、演算子のはずなので、演算子を意味する文字列でなかったり、対応している演算子(現在は2文字以上は非対応)でなければ、エラー
  3. 3つ目の項は、数値のはずなので、想定する文字列でなかったり、数値として認識できなければエラー
  4. 以降は、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
        }
    }
}
コード解説
  1. AST のノードが、数値であれば、その値を返します
  2. 数値でない時は、左側と右側のそれぞれを評価します
  3. 自身の演算子と左側・右側の値を使って、自身の評価値を計算します
注意
ここでは、四則演算全てを計算していますが、演算子の優先順序を考慮していないので、1 + 2 * 3 は、9 になってしまいます。

演算子の優先順序への対応は、生成される AST の構造で解決する予定なので、評価するためのコード自体はこのままで良い予定です。

できたこと:数式を評価する lexer/parser を作る(4)

数式を評価する lexer/parser を作る(4)
  • 3項以上持つ数式に対応した

説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です