SmallDeskSoftware 
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″ を評価するところから始まり、小数点と groupSeparator(,) を理解できるようになり、”1.0 + 1.0” が評価できるようになりました。
[Swift] 数式を評価する lexer/parser を作る (1.0 + 1.0 を計算する) (2)
+1.0 + +1.0
前回対応した 1.0 + 1.0 と何が違うかというと “+” がついていることです。
人間の目には、大したことない違いですが、コンピュータからすると、この + は、演算子なのか？ 符号なのか？ 判断が必要となります。
符号としては、+ 以外にも – も考えられます。
演算子としては、さらに多くの要素が考えられますが、ここでは、+ – * / の4つに制限して考えてみます。いわゆる四則演算です。
符号への対応
どうやって Token を判別するかは難しいところなのですが、ここでは、出現位置による仮定で処理してしまうことにします。
つまり、式 = ＜第１項＞＜演算子＞＜第２項＞ という構造になっていると想定していきます。
このような想定に立てば、項に登場する文字として、前回は使った文字列である 数値＋”,.” に “+-” を入れれば良いことになります。
そして、Double がその文字列を 数値に変換できなければ、項として不正であったとして扱いにします。
+1.0 を理解できるかのテスト
最初に “+1.0” が理解できるかを確認するテストを作成しておきます。
func test_PlusOneZeroPlusPlusOneZero() throws {
let sut = BruteForceLexer("+1.0 + +1.0")
let tokens = sut.lex()
XCTAssertEqual(tokens.count, 3)
let sutParser = MathExpressionParser(tokens)
let expression = try XCTUnwrap(sutParser.parse())
XCTAssertEqual(expression.calc(), 2)
}
正しく Token に分解されれば、3つの Token になり、Token が正しく生成されれば + の計算は既にできるはずなのでうまくいくはずです。
前回までのコードを使って実行してみると、５つの Token が見つかり、その後計算できずにエラーとなります。
まだ対応するコードを実装していないので、予想通りの結果です。
項を表現する要素としての + と –
前回、CharacterSet の extension として、numericCharacters を定義しましたが、その定義に 追加することにします。
extension CharacterSet {
static var numericCharacters: CharacterSet {
var numeric = CharacterSet.decimalDigits
numeric.insert(charactersIn: "+-.,") // +- を追加
return numeric
}
}
上記を追加してから、テストをあらためて実行すると、テストをパスすることがわかります。
+2.0 + -1.0 も確認
なんとなく気になったので、”+2.0 + -1.0″ の計算ができるかもテストを追加してみました。
func test_PlusTwoZeroPlusMinusOneZero() throws {
let sut = BruteForceLexer("+2.0 + -1.0")
let tokens = sut.lex()
XCTAssertEqual(tokens.count, 3)
let sutParser = MathExpressionParser(tokens)
let expression = try XCTUnwrap(sutParser.parse())
XCTAssertEqual(expression.calc(), 1)
}
2 – 1 = 1 なので、結果は１になるはずです。動作させてみると パスします。（１以外の数値も対応していますので、想定通りです）
四則演算への対応
四則演算のテスト
例によって テストコードを作ってから実装していきます。以下は、減算、乗算、除算のテストです。
func test_PlusTwoZeroMinusMinusOneZero() throws {
let sut = BruteForceLexer("+2.0 - -1.0")
let tokens = sut.lex()
XCTAssertEqual(tokens.count, 3)
let sutParser = MathExpressionParser(tokens)
let expression = try XCTUnwrap(sutParser.parse())
XCTAssertEqual(expression.calc(), 3)
}
func test_PlusTwoZeroTimesMinusThreeZero() throws {
let sut = BruteForceLexer("+2.0 * -3.0")
let tokens = sut.lex()
XCTAssertEqual(tokens.count, 3)
let sutParser = MathExpressionParser(tokens)
let expression = try XCTUnwrap(sutParser.parse())
XCTAssertEqual(expression.calc(), -6)
}
func test_PlusSixZeroDivideMinusThreeZero() throws {
let sut = BruteForceLexer("+6.0 / -3.0")
let tokens = sut.lex()
XCTAssertEqual(tokens.count, 3)
let sutParser = MathExpressionParser(tokens)
let expression = try XCTUnwrap(sutParser.parse())
XCTAssertEqual(expression.calc(), -2)
}
動作させてみると、＋ 以外の演算子を知らないので、エラーとなります。（想定通りです）
四則演算対応 @ lexer
lexer での四則演算への対応は簡単です。
CharacterSet の extension で定義していた operatorCharacters に、四則演算の文字を追加すれば完了です。
extension CharacterSet {
static var operatorCharacters: CharacterSet {
var ope = CharacterSet()
ope.insert(charactersIn: "+-*/")
return ope
}
}
lex 関数も以下のように変更して、演算子として読み込んだ文字を Token として記録するようにします。
class BruteForceLexer {
let str: String
let numericCharacterSet = CharacterSet.numericCharacters
let groupingSeparator = Locale.current.groupingSeparator ?? ""
init(_ str: String) {
self.str = str
}
func lex() -> [Token]{
var foundTokens: [Token] = []
let scanner = Scanner(string: self.str)
scanner.charactersToBeSkipped = CharacterSet.whitespaces // without newline
while !scanner.isAtEnd {
// read 1st token
if let numericString = scanner.scanCharacters(from: CharacterSet.numericCharacters),
let value = Double(numericString.filter({ !(groupingSeparator.contains($0)) })) {
foundTokens.append(Token.Numeric(value))
}
// read 2nd token
if let ope = scanner.scanCharacters(from: CharacterSet.operatorCharacters) {
guard ope.count == 1 else { fatalError("too much operation characters") }
if let opeString = ope.first {
foundTokens.append(Token.Operator(String(opeString)))
}
}
// read 3rd token
if let numericString = scanner.scanCharacters(from: CharacterSet.numericCharacters),
let value = Double(numericString.filter({ !(groupingSeparator.contains($0)) })) {
foundTokens.append(Token.Numeric(value))
}
break
}
return foundTokens
}
}
四則演算対応 @ parser
parser 側は、演算子の種類を確認して、適切な計算をしないといけません。
struct Expression {
let lhs: Double //Term.Value
let ope: String
let rhs: Double //Term.Value
init(_ lhs: Double,_ symbol: String, _ rhs: Double) {
self.lhs = lhs
self.ope = symbol
self.rhs = rhs
}
func calc() -> Double {
if ope == "+" {
return lhs + rhs
} else if ope == "-" {
return lhs - rhs
} else if ope == "*" {
return lhs * rhs
} else if ope == "/" {
return lhs / rhs
}
fatalError("Unknown operator")
}
}
上記のコードで、テストをパスすることが確認できるようになります。
ここまでの実装では、＜第１項＞＜演算子＞＜第２項＞という表現しか理解できません。
次回以降で、より多くの項を処理できるようにしつつ、演算子の優先順位の実装を考えていきます。
できたこと：数式を評価する lexer/parser を作る(3)
- 項に符号がついているケースへの対応を実装した
- 四則演算は、演算子を記録しておき、計算時に処理を分岐させた
- +1.0 * -2.3 というような数式も計算できるようになった
説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。
関連記事:
Sponsor Link
