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 + 1″ という 項+演算子+項 という形から始まり、”1.0 + 2.0 + 3.0″ という 複数項(3項以上)の項を持つ数式を、その Token を理解する lexer まで作りました。
[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 + 1.0 を計算する) (4)
ここまでの実装では 演算子の順番を考慮していないため、1 + 2 * 3 は、 (1 + 2) * 3 となり、9 となってしまいます。
*、/ を、+、- よりも優先して計算する仕組みを入れていきます。
2項+演算子な数式
2項+演算子な数式を表す AST(Abstract Syntax Tree)
+やーは、2項演算子であることから、2分木をつかった AST を使っています。
(項+演算子+項)を AST で表す時は、シンプルでした。AST は、以下のようなツリーです。
flowchart TD 演算子 --> 左項 演算子 --> 右項
2項+演算子な数式を表す AST をつかった 数式計算
今回の実装では、AST を上から評価していく実装をしています。
AST の各ノードには、演算子か、数値が記録されています。
AST の最上位ノードは、演算子。最下位ノード(複数あります)は、数値を持っています。
1+2を表すと 最上位ノードは + となり、+ の左側子ノードに 1、右側子ノードには 2 が記録されます。
flowchart TD + --> 1 + --> 2
数式の値を計算するときには、最上位のノードに着目し、左側子ノードの値を右側子ノードの値を、演算子を使って処理します。
1+2 の AST に対しては、以下のように計算することになります。
- + のノードに着目します。
- 左側の子ノードを確認すると 値 1 を持っています。
- 右側の子ノードを確認すると 値 2 を持っています。
- ノードの演算子は、+ だったので、1+2 を計算して、3 を ノードの値とします。
- 最上位ノードなので、全体の値(式の値)は、3 となり 計算は終了です。
複数項(3項以上)対応
複数項(3項以上)を表す AST
3項以上の項がある数式では、以下のように 木の高さを増やして 表現します。
1 + 2 – 3 は、以下のような AST になります。

複数項(3項以上)を表す ASTを使った評価値計算
- 最上位の – のノードに着目します
- 左側の子ノードを確認すると + のノードだとわかります
- +ノードに着目します
- (+ノードの)左側子ノードは、1 という値を持っています。
- (+ノードの)右側子ノードは、2 という値を持っています。
- 1 + 2 = 3 という値が +ノードの値となります。
- -ノードの着目に戻ります。左側子ノードの値がわかったので、右側子ノードを確認すると 3 を持っています。
- ーノードの 左側子ノードの値 3 と 右側子ノードの値 3 がわかったので、演算子 ー を使用して、 3 – 3 = 0 と計算します
- ーノードは、最上位ノードなので ーノードの値が式の値となります
優先度のある演算子への対応
演算子が+と-だけであれば良いのですが、*と/に対応しようとするとその順番を考慮することが必要となります。
1 + 2 3 は (1 + 2) 3 = 9 ではなく、1 + (2 * 3) = 7 という結果が期待されます。
先の AST をつかった計算方法を考慮すると 1 + 2 * 3 は、以下のような AST になる必要があります。
flowchart TD + --> 1 + --> * * --> 2 * --> 3
計算してみましょう
- 最上位の + のノードに着目します
- 左側の子ノードを確認すると 1 という値を持っています
- 右側の子ノードを確認すると * のノードだとわかります
- * のノードに着目します
- (*ノードの)左側子ノードは、2 という値を持っています。
- (*ノードの)右側子ノードは、3 という値を持っています。
- 2 * 3 = 6 という値が *ノードの値となります。
- +ノードの着目に戻ります。右側子ノードの値がわかりました(つまり、左側・右側の両方わかりました)
- +ノードの左側子ノードの値 1 と 右側子ノードの値 6 がわかったので、演算子 + を使用して、1 + 6 = 7 と計算します
- +ノードは、最上位ノードなので、+ノードの値が式の値となります
実装
作りたい AST が見えてきたので、テストから書いていきます。
parser テスト
1 + 2 * 3 をテストケースとしています。生成された AST の構成詳細を確認しています。
func test_parse_5TokensPlusTimes_successToParse() throws {
let tokens = [Token.Numeric(1.0), Token.Operator("+"), Token.Numeric(2.0), Token.Operator("*"), Token.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, .Numeric(1.0))
let right = try XCTUnwrap(expression.right)
try XCTAssertTokenEqual(right.token, .Operator("*"))
let rightLeft = try XCTUnwrap(right.left)
try XCTAssertTokenEqual(rightLeft.token, .Numeric(2.0))
let rightRight = try XCTUnwrap(right.right)
try XCTAssertTokenEqual(rightRight.token, .Numeric(3.0))
let result = try XCTUnwrap(expression.calc())
XCTAssertEqual(result, 7.0, accuracy: 0.001) // 1.0 + 2.0 * 3.0 = 7.0
}
parser 実装
2分木に対して 新しい演算子と新しい項を追加する関数を 以下の2種類作りました。
新しい演算子を2分木の最上位ノードにする(addTermWithLowPriorityOperator)
これまでの2分木を左側子ノード、新しい項を右側子ノードとした2分木を返す関数
新しい演算子を2分木の右側子ノードとする(addTermWithHighPriorityOperator)
これまでの2分木の右側子ノードは、新しい演算子の左側子ノードとし、新しい項は、新しい演算子の右側子ノードとした2分木を返す関数
flowchart TD + --> 1 + --> 2
flowchart TD + --> 1 + --> * * --> 2 * --> 3
上記のような関数を使用することで、parse 関数は以下のようになります。
class MathExpressionParser {
typealias Error = MathExpressionParserError
func parse(_ tokens:[Token]) throws -> MathExpression {
guard tokens.count > 0 else { throw Error.InvalidExpression }
var index:Int = 0
// get 1st token, confirm it is numeric
let firstToken = tokens[index]
guard firstToken.isNumeric else { throw Error.InvalidExpression }
index += 1
var mathExpression = MathExpression(firstToken)
while (index tokens.count) {
guard (tokens.count - index) >= 2 else { throw Error.InvalidExpression }
// should see operator first, then numeric
let opeToken = tokens[index]
index += 1
let rightToken = tokens[index]
index += 1
var nextExpression: MathExpression
if mathExpression.token.isNumeric {
nextExpression = try mathExpression.addTermWithLowPriorityOperator(ope: opeToken, right: rightToken)
} else if mathExpression.topTokenPriority < opeToken.priority { // new ope is "*" or "/"
nextExpression = try mathExpression.addTermWithHighPriorityOperator(ope: opeToken, right: rightToken)
} else {
nextExpression = try mathExpression.addTermWithLowPriorityOperator(ope: opeToken, right: rightToken)
}
mathExpression = nextExpression
}
return mathExpression
}
}
上記コードで作成したテストコードをパスすることが確認できます。
パースだけでなく、値計算(Calc) のテストも行っています
できたこと:数式を評価する lexer/parser を作る(5)
- 優先度に差異のある演算子を扱うためには、優先度に合わせた AST を作成して計算する
説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。
Sponsor Link