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

Swift

数式 "1 + 2 * 3" のような表現を計算できるような プログラムを作ってみます。

環境&対象

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

  • macOS Monterery beta 6
  • Xcode 13 beta5

Lexer/Parser

文字列を解析してコンピュータ処理を行うために使われるものに、Lexer や Parser があります。

Lexer

Lexer は、渡された一連の文字列を意味ごとの区切りで区切ります。

例えば、"1 + 2 * 3" は、"1","+","2","*","3" というように分解されます。(一般に、分解された要素を Token と呼びます)

一見 当たり前のようですが、難しいこともあります。例えば、1000単位で、カンマを入れられている文字列 "1,000 + 23,000" を計算しようとして、"1", "000", "+", "23", "000" とされてしまうと、何がなにやらわからなくなってしまいます。

もちろん、この時の期待は、"1000", "+", "23000" という分解です。

MEMO
どのように分解してほしいかは、どのような目的に使用したいかで異なります。

ですので、lexer/parser は、カスタマイズしたくなるケースが大半です。

C/C++ では、yacc/lex というパーサーを作るプログラムがあり、非常に便利だったのですが、Swift には、ないため 自分で作る必要があります。

なお、1,000 の "," は、groupSeparator と呼ばれるものです。日本では、"," が普通ですが、欧州では、"." が普通です。(欧州では、"," が小数点を表します)

Parser

Parser は、Token の配列を受け取り、AST (Abstract Syntax Tree) と呼ばれる構造にします。
例えば 受け取った Token 配列が ["1000", "+", "2300"] とすると 以下のような AST を返してくれることを期待します。

flowchart TD + --> 1000 + --> 2300

このような構造に変換されることで、左辺と右辺がある和の式 と理解でき、合計値として 3300 (= 1000 + 2300) を返すことができるようになります。

文字列走査用クラス Scanner

Swift の String は、Reference にも書かれているように "A Unicode string value that is a collection of characters" です。

一見すると C 言語の char[] と同じように扱えるように読めてしまいますが、Unicode string であることがポイントです。Unicode は、1文字を最大 4 byte 使って表現するため、String 中で次の文字を取得するという操作が非常に複雑です。

例えば、String の部分文字列にアクセスするためには、myString[1] のようなアクセスはできず、常に、.firstIndex(...) のような形で取得できる Index 型を使用してアクセスする必要があります。

String に対して lexer/parser を作る時にはこの特徴を考慮して作らないといけません。

そのためかどうかはわかりませんが、String を走査するためのクラス Scanner が用意されています。

Scanner クラスのメソッド

Apple のドキュメントは、こちら

さまざまなメソッドが用意されています。以下は、一例です。

  • 次の文字列が特定の文字列/CharacterSetであれば返す:scanString/scanCharacters
  • 特定の文字列/CharacterSet が見つかるまで探す: scanUpToString/scanUpToCharacters
  • 現在の走査位置: scanLocation (参照だけでなく、設定することもできます)

プロジェクトの準備

数式を処理すること自体は、iOS/macOS いずれのアプリにしてもあまり関係はないはずなので、自環境では、macOS の (single document)アプリ向けのプロジェクトを作りました。

"Includes Tests" にチェックを入れて作成することで、テストターゲットも自動で追加されます。

当面 UnitTest を使った TDD で作成していき、アプリケーションにして動作させないので、iOS/macOS いずれでも問題ありません。

最初に作成される <プロジェクト名>Tests.swift として作成されているテストテンプレートに、テストコードを追加していくと簡単に進めます。

超簡単 Lexer を作る

最初は非常に簡単な Lexer から作ってみます。 クラス名は BruteForceLexer として作ってみます。

テスト

実装する前にテストを書くことで、どのような API にしたいのかが明確になります。


final class BruteForceLexer_Tests: XCTestCase {
    func test_OnePlusOne_ShouldBeOK_2() throws {
        let sut = BruteForceLexer("1 + 1")
        // (1)
        let tokens = try sut.lex()
        // (2)
        XCTAssertEqual(tokens.count, 3)
        let sutParser = MathExpressionParser(tokens)
        // (3)
        let expression = try XCTUnwrap(sutParser.parse())
        // (4)
        XCTAssertEqual(expression.calc(), 2)
    }

コード解説
  1. "1 + 1" を lexer で処理し、token の配列が返ります
  2. 返される token は "1", "+", "1" のハズなので、合計は 3つのハズです
  3. lexer で生成された token を Parser に渡して、AST を作ります
  4. AST から 数値計算できるはずなので、計算結果が 2 であることを確認します

ちなみに、BruteForceLexer も MathExpressionParser も作っていないので、この時点ではコンパイルエラーです。

BruteForceLexer

最初のバージョンは力技なので、BruteForceLexer という名前をつけました。

最初に、lexer が生成し、parser が処理していく token を定義します。併せて、走査中のエラーも定義しました。


enum Token: String, RawRepresentable {
    case One = "1"
    case Plus = "+"
}
enum MathParserError: Error {
    case UnknownToken
}

数字としては、"1" しか現れませんし、演算子も "+" しか現れないことを想定しているので、非常にシンプルです。

lexer も "1" か "+" のみで構成されている文字列を想定しています。空白文字は、スキップして読み、"1" か "+" 以外の文字が出現した時は、Error にしています。


class BruteForceLexer {
    let str: String

    init(_ str: String) {
        self.str = str
    }
    
    func lex() throws -> [Token]{
        var foundTokens: [Token] = []
        let scanner = Scanner(string: self.str)
        // (1)
        scanner.charactersToBeSkipped = CharacterSet.whitespaces
        // (2)
        while !scanner.isAtEnd {
            // (3)
            if let _ = scanner.scanString(Token.One.rawValue) {
                // (4)
                foundTokens.append(Token.One)
            // (5)
            } else if let _ = scanner.scanString(Token.Plus.rawValue) {
                // (6)
                foundTokens.append(Token.Plus)
            } else {
                // (7)
                throw MathParserError.UnknownToken
            }
        }
        // (8)
        return foundTokens
    }
}
コード解説
  1. Scanner で走査するときに、whitespaces として定義されている文字は無視するように設定しています
  2. scanner での走査が文字列の最後に辿り着くまで、繰り返します
  3. "1" をスキャンできるか試します
  4. "1" をスキャンできたのであれば、Token.One を記録します
  5. "+" をスキャンできるか試します
  6. "+" がスキャンできたのであれば、Token.Plus を記録します
  7. スキャンした文字が、"1"、"+" のいずれでもないときは Error を throw します
  8. 最後までスキャンできたのであれば、見つかった Token の配列を返します

想定としては、"1 + 1" に対して lexer から返される Token 列は、[Token.One, Token.Plus, Token.One] のハズです。

MathExpressionParser

lexer から返される Token 列から、 数式の AST を返す Parser を作ります。名前は、MathExpressionParser にしました。

まずは、AST の定義ですが、"1 + 1" を表現するだけなので、適当です(汗


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 {
        return 2.0 // 1 + 1
    }
}

本来であれば、1 を数値として保持する必要があるのでしょうが、1 しか処理対処としていないので、決め打ちしてます。

数式を評価する calc も "1 + 1" に対しては、"2" を返すだけです。

以下の MathExpressionParser も、"1 + 1" 決め打ちのため、簡単なエラーチェックだけを入れてます


class MathExpressionParser {
    let tokens: [Token]
    // (1)
    init(_ tokens:[Token]) {
        self.tokens = tokens
    }
    // (2)
    func parse() -> MathExpression? {
        guard self.tokens.count == 3,
              case Token.One = self.tokens[0],
              case Token.Plus = self.tokens[1],
              case Token.One = self.tokens[2] else { return nil }
        return MathExpression(self.tokens[0], self.tokens[1], self.tokens[2])
    }
}
コード解説
  1. token 列を渡されて初期化されます
  2. "1 + 1" だったならば、MathExpression を返し、そうでなければ nil を返すようにしました

上記のコードで 最初に作成したテストコードは、動くようになります。

エラー処理の確認

"1 + 1"を評価するためのコードだけでも、どのようなエラーをどの段階で返すのかをきちんと考える必要があることがわかってきます。

未知の Token が出てくるケース

例えば、"2 + 2" を解析しようとすると、"2" を(lexer は) 知らないのでエラーになります。


    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)
        }
    }

未知の Token "2" が出現するので、例外が投げられてきます。投げられた例外が想定している MathParserError.UnknownToken であるかも確認しています。

AST を作成できないケース

例えば、"1 1 1" は、既知の Token だけですが、数式としてはおかしいです。今回の設計では、lexer ではなく、parser で数式としての AST を作成できない(nil を返す) としてします。

以下のテストコードで確認できます。


    func test_OneOneOne_ParserShouldReturnNil() throws {
        // (1)
        let sut = BruteForceLexer("1 1 1")
        // (2)
        let tokens = sut.lex()
        // (3)
        XCTAssertEqual(tokens.count, 3)
        // (4)
        let sutParser = MathExpressionParser(tokens)
        // (5)
        XCTAssertNil(sutParser.parse())
    }
コード解説
  1. "1 1 1" を解析対象として lexer を作ります
  2. 解析し、token 配列を受け取ります
  3. token 配列に3つの要素が含まれていることを確認します (Token.One, Token.One, Token.One が返り値となります)
  4. lexer から返された Token 列を parse して、AST を作ろうとします
  5. AST 作成に失敗していることを確認します。

lexer/parser いずれも、エラー時にどのタイミングでどのような情報を返すかは、使用したい状況により異なります。

可能な限りの分析結果を返してほしいケースもありそうですし、エラーとわかったら できるだけはやく 戻ってほしいケースもありそうです。

いずれにしても、とりあえず(?)、"1 + 1" を理解して計算する lexer/parser は作れました。(1+1 の実計算については、解の 2 を直接実装していますが・・・)

次回以降で、"1" 以外の数値も計算対象にして "+" 以外の計算もできる ように拡張していきます。

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

数式を評価する lexer/parser を作る
  • 文字列を走査するための、lexer/parser それぞれの役割を確認した
  • Scanner クラスを使用して、文字列を走査した
  • 1 + 1 を処理し、2 を出力できた

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

コメントを残す

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