Created
March 21, 2016 03:12
-
-
Save sora0077/36ff6a5070f077870171 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// | |
// main.swift | |
// Formula | |
// | |
// Created by 林達也 on 2016/03/20. | |
// Copyright © 2016年 jp.sora0077. All rights reserved. | |
// | |
//: Playground - noun: a place where people can play | |
import Cocoa | |
protocol Acceptable {} | |
extension String: Acceptable {} | |
extension Symbol: Acceptable {} | |
extension Parser: Acceptable {} | |
extension Array: Acceptable {} | |
struct Numeric: Acceptable {} | |
struct Group: Acceptable { | |
let values: [Acceptable] | |
init(_ values: Acceptable...) { | |
self.values = values | |
} | |
} | |
enum Either<L: CustomStringConvertible, R: CustomStringConvertible>: CustomStringConvertible { | |
case left(L) | |
case right(R) | |
var forceLeft: L { | |
switch self { | |
case .left(let val): | |
return val | |
default: | |
print(self) | |
fatalError() | |
} | |
} | |
var forceRight: R { | |
switch self { | |
case .right(let val): | |
return val | |
default: | |
fatalError() | |
} | |
} | |
var description: String { | |
switch self { | |
case .left(let val): | |
return val.description | |
case .right(let val): | |
return val.description | |
} | |
} | |
} | |
protocol SignOrPattern: CustomStringConvertible { | |
var rawValue: String { get } | |
} | |
final class Tokens { | |
enum Pattern: String, SignOrPattern { | |
case Numeric = "^[+-]?([1-9][0-9]*|0)(\\.[0-9]+)?" | |
static let all: [Pattern] = [ | |
.Numeric | |
] | |
var description: String { | |
return "Numric" | |
} | |
} | |
enum Sign: String, SignOrPattern { | |
case LParen = "(" | |
case RParen = ")" | |
case Plus = "+" | |
case Minus = "-" | |
case Multiply = "*" | |
case Divide = "/" | |
static let all: [Sign] = [ | |
.LParen, | |
.RParen, | |
.Plus, | |
.Minus, | |
.Multiply, | |
.Divide | |
] | |
var description: String { | |
return "Symbol" | |
} | |
} | |
struct Token: CustomStringConvertible { | |
let type: SignOrPattern | |
let label: String | |
var description: String { | |
return "(type: \(type), label: \"\(label)\")" | |
} | |
} | |
private var pointer: Int = 0 | |
private var pointerStack: [Int] = [] | |
private var tokens: [Token] = [] | |
var token: Token? { | |
if tokens.count <= pointer { | |
return nil | |
} | |
return tokens[pointer] | |
} | |
init(source: String) { | |
var unread = source | |
while !unread.isEmpty { | |
unread = unread.stringByTrimmingCharactersInSet(NSCharacterSet.whitespaceCharacterSet()) | |
var tokenFound = false | |
for pattern in Pattern.all { | |
let regex = try! NSRegularExpression(pattern: pattern.rawValue, options: []) | |
let results = regex.matchesInString(unread, options: [], range: NSMakeRange(0, unread.utf16.count)) | |
if results.isEmpty { continue } | |
tokenFound = true | |
tokens.append(Token(type: pattern, label: { | |
let range = results[0].rangeAtIndex(0) | |
let start = unread.utf16.startIndex.advancedBy(range.location) | |
let end = start.advancedBy(range.length) | |
return String(unread.utf16[start..<end]) | |
}())) | |
let range = results[0].rangeAtIndex(0) | |
let start = unread.utf16.startIndex.advancedBy(range.length) | |
unread = String(unread.utf16[start..<unread.utf16.endIndex]) | |
} | |
if !tokenFound { | |
for symbol in Sign.all { | |
let endIndex = unread.startIndex.advancedBy(symbol.rawValue.characters.count) | |
if unread[unread.startIndex..<endIndex] == symbol.rawValue { | |
unread = unread.substringFromIndex(endIndex) | |
tokens.append(Token(type: symbol, label: symbol.rawValue)) | |
tokenFound = true | |
} | |
} | |
} | |
if !tokenFound { | |
print("Error") | |
} | |
} | |
} | |
var exhausted: Bool { | |
return pointer >= tokens.count | |
} | |
func check() -> Self { | |
pointerStack.append(pointer) | |
return self | |
} | |
func uncheck() -> Self { | |
pointerStack.removeLast() | |
return self | |
} | |
func next() -> Token? { | |
if pointer < tokens.count { | |
pointer += 1 | |
} | |
return token | |
} | |
func rewind() -> Self { | |
pointer = pointerStack.count > 0 ? pointerStack.removeLast() : 0 | |
return self | |
} | |
} | |
final class Parser { | |
typealias Parsed = Either<Double, Tokens.Token> | |
typealias Rule = (patterns: [Acceptable], handler: (inout [Parsed]) -> Double) | |
private var rules: [Rule] = [] | |
private let name: String | |
init(_ name: String) { | |
self.name = name | |
} | |
func accept(pattern: Acceptable, _ patterns: [Acceptable], _ handler: (inout [Parsed]) -> Double) -> Self { | |
rules.append((patterns: [pattern, patterns], handler: handler)) | |
return self | |
} | |
func accept(patterns: Acceptable..., _ handler: (inout [Parsed]) -> Double) -> Self { | |
rules.append((patterns: patterns, handler: handler)) | |
return self | |
} | |
func parse(tokens: Tokens) -> Double? { | |
func patternMatch(patterns: [Acceptable], inout parsed: [Parsed]) -> Bool { | |
var matched: [Parsed] = [] | |
func traverse() -> Bool { | |
for (idx, pattern) in patterns.enumerate() { | |
var pattern = pattern | |
if let str = pattern as? String { | |
pattern = Symbol(str) | |
} | |
print(self, tokens.token, idx, pattern, matched) | |
if let parser = pattern as? Parser { | |
if let node = parser.parse(tokens) { | |
matched.append(.left(node)) | |
} else { | |
return false | |
} | |
} else if let symbol = pattern as? Symbol { | |
switch symbol { | |
case .terminator(let val): | |
if let token = tokens.token where token.label == val { | |
matched.append(.right(token)) | |
tokens.next() | |
print("matched next: ", tokens.token) | |
} else { | |
return false | |
} | |
case .or(let lhs, let rhs): | |
func subpatternMatch() -> Bool { | |
for subpattern in [lhs, rhs] { | |
if patternMatch([subpattern], parsed: &matched) { | |
print("subpattern matched") | |
return true | |
} | |
} | |
return false | |
} | |
if !subpatternMatch() { | |
return false | |
} | |
} | |
} else if let patterns = pattern as? [Acceptable] { | |
while patternMatch(patterns, parsed: &matched) {} | |
} else if let group = pattern as? Group { | |
while patternMatch(group.values, parsed: &matched) {} | |
} else if tokens.exhausted { | |
return false | |
} else if let token = tokens.token | |
where pattern is Numeric && token.type.rawValue == Tokens.Pattern.Numeric.rawValue | |
{ | |
matched.append(.right(token)) | |
tokens.next() | |
} else { | |
return false | |
} | |
} | |
return true | |
} | |
tokens.check() | |
if !traverse() { | |
tokens.rewind() | |
return false | |
} | |
parsed.appendContentsOf(matched) | |
tokens.uncheck() | |
return true | |
} | |
for rule in rules { | |
var parsed: [Parsed] = [] | |
if patternMatch(rule.patterns, parsed: &parsed) { | |
let val = rule.handler(&parsed) | |
print("result: ", parsed, val) | |
return val | |
} | |
} | |
print("return: nil", self, tokens.token) | |
return nil | |
} | |
} | |
extension Parser: CustomStringConvertible { | |
var description: String { | |
return "Parser(\(name))" | |
} | |
func justify() -> Self { | |
return self | |
} | |
} | |
enum Symbol: StringLiteralConvertible { | |
case terminator(String) | |
case or(Acceptable, Acceptable) | |
init(_ value: String) { | |
self = .terminator(value) | |
} | |
init(stringLiteral value: String) { | |
self.init(value) | |
} | |
init(unicodeScalarLiteral value: String) { | |
self.init(value) | |
} | |
init(extendedGraphemeClusterLiteral value: String) { | |
self.init(value) | |
} | |
} | |
func ||(lhs: Acceptable, rhs: Acceptable) -> Symbol { | |
return .or(lhs, rhs) | |
} | |
let E = Parser("E") | |
let F = Parser("F") | |
let N = Parser("N") | |
E .accept(F, ["+" || "-", F]) { parsed in | |
var result = parsed.removeFirst().forceLeft | |
while !parsed.isEmpty { | |
let label = parsed.removeFirst().forceRight.label | |
let val = parsed.removeFirst().forceLeft | |
result = label == "+" ? result + val : result - val | |
} | |
return result | |
} | |
F .accept(N, ["*" || "/", N]) { parsed in | |
var result = parsed.removeFirst().forceLeft | |
while !parsed.isEmpty { | |
let label = parsed.removeFirst().forceRight.label | |
let val = parsed.removeFirst().forceLeft | |
result = label == "*" ? result * val : result / val | |
} | |
return result | |
} | |
N .accept("(", E, ")") { parsed in | |
let val = parsed[1].forceLeft | |
return val | |
} | |
.accept("+" || "-", N) { parsed in | |
let num = parsed[1].forceLeft | |
return parsed[0].forceRight.label == "+" ? num : -num | |
} | |
.accept(Numeric()) { parsed in | |
let val = Double(parsed[0].forceRight.label) | |
return val! | |
} | |
print(E.parse(Tokens(source: "1 + 2 * 3 - (4 + 5) / 3"))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment