Created
May 10, 2025 15:57
-
-
Save jeffersonmourak/f6812bfc5421962270835293afae1ebe to your computer and use it in GitHub Desktop.
This file contains hidden or 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
| import Foundation | |
| enum ParserError: Error { | |
| case UnknownToken(String) | |
| case BadToken(String) | |
| case Ouch(String) | |
| case IdentifierNotDefined(String) | |
| case UnexpectedToken(String) | |
| } | |
| enum Token: CustomStringConvertible, Equatable { | |
| case Id(String) | |
| case Op(String) | |
| case Eof | |
| init(_ char: String.SubSequence) { | |
| self = char.firstMatch(of: /[0-9]|[A-Z]|[a-z]/) != nil ? .Id(String(char)) : .Op(String(char)) | |
| } | |
| init(_ char: String) { | |
| self = char.firstMatch(of: /[0-9]|[A-Z]|[a-z]/) != nil ? .Id(String(char)) : .Op(String(char)) | |
| } | |
| var description: String { get { | |
| switch self { | |
| case .Id(let char): "Id(\(char))" | |
| case .Op(let char): "Op(\(char))" | |
| case .Eof: "$" | |
| } | |
| }} | |
| static func bindigPower(_ op: String) throws -> (Float, Float) { | |
| if op == "=" { return (0.2, 0.1) } | |
| if op == "+" || op == "-" { return (1.0, 1.1) } | |
| if op == "*" || op == "/" { return (2.0, 2.1) } | |
| if op == "^" || op == "&" { return (3.1, 3.0) } | |
| throw ParserError.UnknownToken(op) | |
| } | |
| var isOp: Bool { | |
| get { | |
| switch self { | |
| case .Op(_): true | |
| default: false | |
| } | |
| } | |
| } | |
| var isEof: Bool { | |
| get { | |
| switch self { | |
| case .Eof: true | |
| default: false | |
| } | |
| } | |
| } | |
| var char: String { | |
| get { | |
| switch self { | |
| case .Id(let v): v | |
| case .Op(let o): o | |
| case .Eof: "$" | |
| } | |
| } | |
| } | |
| } | |
| struct Lexer { | |
| var tokens: [Token] = [] | |
| init(_ input: String) { | |
| for char in input.split(separator: "") { | |
| if char == " " { continue } | |
| tokens.insert(Token(char), at: 0) | |
| } | |
| } | |
| mutating func next() -> Token { self.tokens.popLast() ?? .Eof } | |
| func peek() -> Token { self.tokens.last ?? .Eof } | |
| } | |
| enum Expression: CustomStringConvertible { | |
| case Id(String) | |
| case Op(String, [Expression]) | |
| var description: String { get { | |
| switch self { | |
| case .Id(let char): "Id(\(char))" | |
| case .Op(let char, let ids): "Op(\(char), \(ids)" | |
| } | |
| }} | |
| static func from(_ input: String) throws -> Expression { | |
| var lexer = Lexer(input) | |
| return try parseExpression(&lexer, 0) | |
| } | |
| var isAssignment: (String, Expression)? { | |
| get { | |
| switch self { | |
| case .Op(let char, let exps): do { | |
| if char == "=" { | |
| let lho = exps[0] | |
| let content = exps[1] | |
| if lho.char.firstMatch(of: /[0-9]]/) == nil { | |
| return (lho.char, content) | |
| } | |
| } | |
| return nil | |
| } | |
| default: return nil | |
| } | |
| } | |
| } | |
| func eval(_ assignments: inout [String: Float]) throws -> Float { | |
| switch self { | |
| case .Id(let v): do { | |
| if v.firstMatch(of: /[0-9]/) != nil { | |
| return Float(v)! | |
| } | |
| if assignments.keys.contains(v) { | |
| return assignments[v]! | |
| } | |
| throw ParserError.IdentifierNotDefined(v) | |
| } | |
| case .Op(let v, let expressions): do { | |
| let lhs = try expressions[0].eval(&assignments) | |
| let rhs = try expressions[1].eval(&assignments) | |
| switch v { | |
| case "+": return lhs + rhs | |
| case "-": return lhs - rhs | |
| case "*": return lhs * rhs | |
| case "/": return lhs / rhs | |
| case "^": return Float(pow(Double(lhs), Double(rhs))) | |
| case "&": return Float(pow(Double(lhs), 1 / Double(rhs))) | |
| default: throw ParserError.UnexpectedToken(v) | |
| } | |
| } | |
| } | |
| } | |
| func processPostFix(_ stack: inout [Token]) -> [Token] { | |
| switch self { | |
| case .Id(let value): | |
| return [Token(value)] | |
| case .Op(let op, let exps): do { | |
| let lhs = exps[0].processPostFix(&stack) | |
| let rhs = exps[1].processPostFix(&stack) | |
| let oBp = (try! Token.bindigPower(op)).0 | |
| let lBp = (try? Token.bindigPower(lhs.last!.char).0) ?? 0 | |
| let rBp = (try? Token.bindigPower(rhs.last!.char).0) ?? 0 | |
| let cBp = max(lBp, rBp) | |
| if (oBp < cBp) { | |
| stack.append(Token(op)) | |
| return lhs + rhs | |
| } | |
| return lhs + rhs + [Token(op)] | |
| } | |
| } | |
| } | |
| func asPostFix() -> [Token] { | |
| var stack: [Token] = [] | |
| var output = self.processPostFix(&stack) | |
| while !stack.isEmpty { | |
| output.append(stack.popLast()!) | |
| } | |
| return output | |
| } | |
| var char: String { | |
| get { | |
| switch self { | |
| case .Id(let char): char | |
| case .Op(let char, _): char | |
| } | |
| } | |
| } | |
| } | |
| func parseExpression(_ lexer: inout Lexer, _ minBp: Float) throws -> Expression { | |
| var lhs: Expression = try { | |
| do { | |
| switch lexer.next() { | |
| case .Id(let v): return .Id(v) | |
| case .Op(let o): throw ParserError.Ouch(o) | |
| case .Eof: throw ParserError.BadToken("EOF") | |
| } | |
| } catch ParserError.Ouch(let op) { | |
| if op != "(" { | |
| throw ParserError.BadToken(op) | |
| } | |
| let pTree = try parseExpression(&lexer, 0) | |
| let nextToken = lexer.next() | |
| if nextToken.char != ")" { | |
| throw ParserError.BadToken(nextToken.char) | |
| } | |
| return pTree | |
| }} () | |
| while true { | |
| let nextOp = lexer.peek() | |
| if nextOp == .Eof || nextOp.char == ")" { | |
| break | |
| } | |
| if !nextOp.isOp { | |
| lhs = .Id("\(lhs.char)\(nextOp.char)") | |
| _ = lexer.next() | |
| continue | |
| } | |
| let op = nextOp.char | |
| let (lbp, rbp) = try Token.bindigPower(op) | |
| if lbp < minBp { | |
| break | |
| } | |
| _ = lexer.next() | |
| let rhs = try parseExpression(&lexer, rbp) | |
| lhs = .Op(op, [lhs, rhs]) | |
| } | |
| return lhs | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment