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

⌛️ 3 min.

1 + 1 を拡張して、1.0 + 1.0 を計算できるようにしていきます

Sponsor Link

環境＆対象

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

macOS Monterery beta 5
Xcode 13 beta5

1 + 1

前回、1 + 1 を “1”, “+”, “1” に分解して、計算できるようにしました。

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

今回は、前回作成した lexer を拡張して、1.0 (小数点付きの数字）を評価できるようにしていきます。

桁数の大きい数字を扱うときには、GroupSeparator と呼ばれる “,” をよく使います。
今回は、この GroupSeparator “,” を含んだ 1,000 のような数字も評価できるようにしていきます。

MEMO

この GroupSeparator は、日本では “,” ですが、欧州では “.” です。

日本では小数点は “.” ですが、欧州では “,” です。

この情報は、Locale が持っていますので、処理するときにハードコーディングせず Locale から取得して処理することが大切です。

String を Double に変換する

Swift の Double は、String を受け取り、Double に変換することができます。



let value = Double("123.45")
print(value)
// print-out
Optional(123.45)

let value2 = Double("Hello")
print(value2)
// print-out
nil

上記の実行例を見ると分かる通り、変換結果は Double? で、変換できなかったときには、nil が返されます。

今回は、この変換機能を使って、実装していきます。

Double -> String の変換は、GroupSeparator を知らない

ところが、この Double -> String の変換は、”,” を処理してくれません。


let value3 = Double("1,000")
print(value3)
// print-out
nil

ですので、読み取って、Double への変換を行う前に何らかの前処理が必要となります。

1 以外の数字を読み取る

前回は、”1″ 決め打ちで読み取っていましたが、数値をテキストから読み取ろうとするときに、数値表現とは？という疑問に行きつきます。

例えば、指数表現(1.0e+5)は対応するのか？、小数点表示の最初の 0 は省略可能か(0.9 ではなく .9 と書いて良いか)？など、どこまでの表現を受け付けるかを考えることが必要となります。

MEMO

ちなみに、”.9″ という表現は、Double は理解して変換してくれますが、Swift コンパイラーは、”正しい表現ではないので、0.9 と書きなさい”というエラーを出します。

読み取る数字

現在の “1” だけを読み取れる状態から少しだけの拡張としたいので、以下のような仕様にします。

数値として使用される文字は、0-9 と小数点、GroupingSeparator、＋、ーのみ
符号は先頭にのみ出現する
数値表現中に現れて計算を示唆することはできない i.e. 1+1 は、NG
符号を表す +, – は数値にくっつけて使用される必要がある
+1 は、数値としての 1 token として考慮されるが、+ 1 は、2 token であり、+ は演算子として処理される。つまり 1 + +1 は、1 + 1 の別表現であり、1 + + 1 は、不正なシンタックス。
指数表現は、不正な表現としてエラーになる(UnknownToken)

実装

テスト

最初にテストコードを書いていきます。


    func test_OneZeroPlusOneZero_ShouldBeOK_2() throws {
        let sut = BruteForceLexer("1.0 + 1.0")
        let tokens = try sut.lex()
        XCTAssertEqual(tokens.count, 3)
        let sutParser = MathExpressionParser(tokens)
        let expression = try XCTUnwrap(sutParser.parse())
        XCTAssertEqual(expression.calc(), 2)
    }

“1 + 1” だったものを “1.0 + 1.0” にしています。

ここまで書いたコードで実行してみると、lexer から “UnknownToken” が返されます。 “.” を知らないので、UnknownToken を返しています。ちなみに、現在の lexer は、”0″ も知りません。

つまり、まずは、lexer を修正していくことが必要となります。

CharacterSet

Scanner で文字を走査する際には、走査対象の文字集合を定義しておくと便利です。

以下では、上記仕様をベースにした走査すべき文字集合を定義しています。


extension CharacterSet {
    static var numericCharacters: CharacterSet {
        // (1)
        var numeric = CharacterSet.decimalDigits
        // (2)
        numeric.insert(charactersIn: Locale.current.groupingSeparator ?? "")
        numeric.insert(charactersIn: Locale.current.decimalSeparator ?? "")
        return numeric
    }
}

コード解説

CharacterSet に最初から数値文字のセットは定義されています
小数点(decimalSeparator) と GroupingSeparator を追加しています
存在しない場合は、”” として追加しています。

この CharacterSet を使って、文字列を走査していきます。

前回のコードを、CharacterSet.numericCharacters を使って scan するように変更しました。


class BruteForceLexer {
    let str: String

    init(_ str: String) {
        self.str = str
    }
    
    func lex() throws -> [Token]{
        var foundTokens: [Token] = []
        let scanner = Scanner(string: self.str)
        scanner.charactersToBeSkipped = CharacterSet.whitespaces // without newline
        
        while !scanner.isAtEnd {
            // if let _ = scanner.scanString(Token.One.rawValue) { // - 前回のコード
            if let numberLiteral = scanner.scanCharacters(from: CharacterSet.numericCharacters) {
                foundTokens.append(Token.One)
            } else if let _ = scanner.scanString(Token.Plus.rawValue) {
                foundTokens.append(Token.Plus)
            } else {
                throw MathParserError.UnknownToken
            }
        }
        return foundTokens
    }
}

こうすることで、先ほど追加したテストは通ります。

なお、1 以外の数値も Token として受け付けるようになったので、前回作成した以下のテストは通らなくなりました。


    func test_TwoPlusTwo_ShouldBeError() throws {
        let sut = BruteForceLexer("2 + 2")
        XCTAssertThrowsError(try sut.lex(), "error check failed") { error in
            XCTAssertEqual(error as? MathParserError,
                           MathParserError.UnknownToken)
        }
    }

“2” を Token として受け付けるために、UnknownToken が発生しなくなります。この機会に正しいテストに変更します。


    func test_TwoPlusTwo_ShouldBeOK_4() throws {
        let sut = BruteForceLexer("2 + 2")
        let tokens = try sut.lex()
        XCTAssertEqual(tokens.count, 3)
        let sutParser = MathExpressionParser(tokens)
        let expression = try XCTUnwrap(sutParser.parse())
        XCTAssertEqual(expression.calc(), 4)
    }

“2 + 2” なので、4 が算出されることを確認するテストです。現在の実装では、数式として “1 + 1” のみを想定した “2” しか返さないので、テストは、失敗します。

現在は、数値表現は読み込めている状態なので、それを Token として生成し、AST で計算するようにすれば良いはずです。

値を保持する Token

現在は、Token として、One と Plus しか存在しませんが、数値の値を保持できる Token を作り、One を廃止しましょう。

このような場合には、associated value を使った enum がぴったりです。
ただし、associated value 付き enum にすると、String に準拠することができなくなり、RawRepresentable でも無くなります。


enum Token {
    case Numeric(Double)
    case Plus
    
    static var numericCharacterSet: CharacterSet {
        return CharacterSet.numericCharacters
    }
    static var operatorCharacterSet: CharacterSet {
        var ope = CharacterSet()
        ope.insert(charactersIn: "+")
        return ope
    }
}

Token として数値の場合はその値を、associated value に持たせました。Plus のときには、”+” であることが自明なのでそのままです。（将来的に Operator にして、+-*/ へ対応していくことが予想されますが、まずは、シンプルにしています）

それぞれの Token 向けに scan するときに使用する CharacterSet も持たせました。

上記の enum にあわせてアップデートした lex は以下のようになります。


    func lex() throws -> [Token]{
        var foundTokens: [Token] = []
        let scanner = Scanner(string: self.str)
        scanner.charactersToBeSkipped = CharacterSet.whitespaces // without newline
        
        while !scanner.isAtEnd {
            if let numberLiteral = scanner.scanCharacters(from: Token.numericCharacterSet),
               let doubleValue = Double(numberLiteral) {
                foundTokens.append(Token.Numeric(doubleValue))
            } else if let _ = scanner.scanCharacters(from: Token.operatorCharacterSet) {
                foundTokens.append(Token.Plus)
            } else {
                throw MathParserError.UnknownToken
            }
        }
        return foundTokens
    }

これで、Token の Numeric には、数値が保存されるようになりますので、AST で正しく構文解析できれば数値に応じた計算ができるはずです。

Token の enum を変更したので、Parser もコンパイルエラーになります。修正します。


class MathExpressionParser {
    let tokens: [Token]
    init(_ tokens:[Token]) {
        self.tokens = tokens
    }
    func parse() -> MathExpression? {
        guard self.tokens.count == 3,
              case Token.Numeric(_) = self.tokens[0],
              case Token.Plus = self.tokens[1],
              case Token.Numeric(_) = self.tokens[2] else { return nil }
        
        return MathExpression(self.tokens[0], self.tokens[1], self.tokens[2])
    }
}

数値 + 数値という Token でなければエラーとしているところは変わりません。

次に、MathExpression の calc を Token が持つ数値を使った計算に変更します。


struct MathExpression {
    let lhs: Token
    let ope: Token
    let rhs: Token

    init(_ lhs: Token,_ ope: Token, _ rhs: Token) {
        self.lhs = lhs
        self.ope = ope
        self.rhs = rhs
    }
    
    func calc() -> Double? {
        if case Token.Numeric(let lhs) = lhs,
           case Token.Numeric(let rhs) = rhs {
            return lhs + rhs
        }
        return nil
    }
}

数値がおかしかった場合を考慮し、calc は Double? を返すように修正しています。

ここまでの修正で、これまでのテスト全てが通るようになります。1.0 + 1.0 は 2 になりますし、2 + 2 は 4 という計算結果が出ます。

記事の最初に説明した GroupSeparator を使ったテストを行なっていないので、テストを追加していきます。

GroupSeparator のテスト


    func test_1KPlus25K_ShouldBeOK_26K() throws {
        let sut = BruteForceLexer("1,000 + 25,000")
        let tokens = try sut.lex()
        XCTAssertEqual(tokens.count, 3)
        let sutParser = MathExpressionParser(tokens)
        let expression = try XCTUnwrap(sutParser.parse())
        XCTAssertEqual(expression.calc(), 26000)
    }

実行してみると、lexer から UnknownToken が返ります。CharacterSet には、”,” も追加していたはずです・・・

コードを見てみると、”1,000″ や “25,000” を Double に変換できずに、エラーとなっていました。

Double に変換できるようにするために、シンプルに文字列中の GroupingSeparator を取り除くようにします。(decimalSeparator を取り除くと値が変わってしまいます)

以下のように文字列処理し、Double に変換させます。


let groupingSeparator = Locale.current.groupingSeparator ?? ""
...
  let doubleValue = Double(numberLiteral.filter({ !(groupingSeparator.contains($0)) })) { ...

この変更で、GroupingSeparator を使った表現のテストも通るようになりました。

GroupingSeparator は理解できるようになったのですが、、数字の先頭の + や – には対応できていないので、次回以降で対応していきます。

その対応が終わった後で、＋以外の演算子を追加していきます。

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

数式を評価する lexer/parser を作る(2)

decimalSeparator, groupingSeparator は、Locale から取得して適切に使用して、文字列を数値に変換する
Token をその値をあわせて保持するのために associated value 付き enum を使った
小数点を考慮し、1.0 + 1.0 を処理し、2 を算出できた
1 以外の数字を考慮し、2 + 2 を処理し、4 を算出できた
GroupingSeparator を考慮し、1,000 + 2,000 を処理し、3,000 と算出できた

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