Parsey

Swift Parser Combinator Framework

In addition to simple combinators, Parsey supports source location/range tracking, backtracking prevention, and custom error messages.

Features

Combinator interface
- |, ~~, ~~>, <~~, ^^ combinator operators
Lexer primitives:
- Lexer.whitespace, Lexer.signedInteger, ...
Regex-like combinators:
- Postfix .+ for .many().
  - Example: let arrayLiteral = "[" ~~> expression.+ <~~ "]"
- Postfix .* for .manyOrNone().
  - Example: let classDef = (attribute | method).*
- Postfix .? for .optional().
  - Example: let declaration = "let" ~~> id ~~ (":" ~~> type).? ~~ ("=" ~~> expression)
- Postfix + for .manyConcatenated().
  - Example: let skippedSpaces = (Lexer.space | Lexer.tab)+
- Infix + for .concatenatingResult(with:).
  - Example: let type = Lexer.upperLetter + Lexer.letter*
- Lexer.regex(_:) for directly applying regular expressions.
  - Example: let id = Lexer.regex("[a-zA-Z][a-zA-Z0-9]*")
Backtracking prevention
- .! postfix operator or .nonbacktracking()
Parser tagging for error messages
- <!-- operator or .tagged(_:)

Rich error messages with source location

For example:

Parse failure at 2:4 ----
(+ %% 1 -20) 2 3)
   ^~~~~~~~~~~~~~
Expecting an expression, but found "%"

Source range tracking

^^^ operator or .mapParse(_:)
For example, S-expression \n(+ \n\n(+ +1 -20) 2 3) gets parsed to the following range-tracked AST:

Expr:(2:1..<4:16):[
    ID:(2:2..<2:3):+,
    Expr:(4:1..<4:11):[
        ID:(4:2..<4:3):+,
        Int:(4:4..<4:6):1,
        Int:(4:7..<4:10):-20],
    Int:(4:12..<4:13):2,
    Int:(4:14..<4:15):3]

Requirements

Swift 3
Any operating system

Package

To use it in your Swift project, add the following dependency to your Swift package description file.

    .Package(url: "https://github.com/rxwei/Parsey", majorVersion: 1)

⚙ Examples

0️⃣ An LLVM Compiler Frontend written in Swift using Parsey

The COOL Programming Language

1️⃣ Parse Left-associative Infix Expressions with Operator Precedence

indirect enum Expression {
    case integer(Int)
    case symbol(String)
    case infix(String, Expression, Expression)
}

enum Grammar {
    static let integer = Lexer.signedInteger
        ^^ {Int($0)!} ^^ Expression.integer

    static let symbol = Lexer.regex("[a-zA-Z][0-9a-zA-Z]*")
        ^^ Expression.symbol

    static let addOp = Lexer.anyCharacter(in: "+-")
        ^^ { op in { Expression.infix(op, $0, $1) } }
    
    static let multOp = Lexer.anyCharacter(in: "*/")
        ^^ { op in { Expression.infix(op, $0, $1) } }

    /// Left-associative multiplication
    static let multiplication = (integer | symbol).infixedLeft(by: multOp)

    /// Left-associative addition
    static let addition = multiplication.infixedLeft(by: addOp)

    static let expression: Parser<Expression> = addition
}

try print(Grammar.expression.parse("2"))
/// Output:
/// Expression.integer(2)

try print(Grammar.expression.parse("2+1+2*a"))
/// Output:
/// Expression.infix("+",
///                  .infix("+", .integer(2), .integer(1)),
///                  .infix("*", .integer(2), .symbol("a")))

2️⃣ Parse S-Expressions

indirect enum Expr {
    case sExp([Expr])
    case int(Int)
    case id(String)
}

enum Grammar {
    static let whitespaces = (Lexer.space | Lexer.tab | Lexer.newLine)+
    static let anInt = Lexer.signedInteger ^^ { Int($0)! } ^^ Expr.int
    static let anID = Lexer.regex("[a-zA-Z_+\\-*/][0-9a-zA-Z_+\\-*/]*") ^^ Expr.id
    static let aSExp: Parser<Expr> =
        "(" ~~> (anExp.!).many(separatedBy: whitespaces).amid(whitespaces.?) <~~ ")"
        ^^ Expr.sExp
    static let anExp = anInt | anID | aSExp <!-- "an expression"
}

/// Success
try Grammar.anExp.parse("(+ (+ 1 -20) 2 3)")
/// Output: Expr.sExp(...)

/// Failure
try Grammar.anExp.parse("(+ \n(+ %% 1 -20) 2 3)")
/// Output: Parse failure at 2:4 ----
///         (+ %% 1 -20) 2 3)
///            ^~~~~~~~~~~~~~
///         Expecting an expression, but found "%"

3️⃣ Parse S-Expressions with Source Range Tracking

indirect enum Expr {
    case sExp([Expr], SourceRange)
    case int(Int, SourceRange)
    case id(String, SourceRange)
}

enum Grammar {
    static let whitespaces = (Lexer.space | Lexer.tab | Lexer.newLine)+

    static let anInt = Lexer.signedInteger 
        ^^^ { Expr.int(Int($0.target)!, $0.range) }

    static let anID = Lexer.regex("[a-zA-Z_+\\-*/][0-9a-zA-Z_+\\-*/]*")
        ^^^ { Expr.id($0.target, $0.range) }

    static let aSExp: Parser<Expr> =
        "(" ~~> (anExp.!).many(separatedBy: whitespaces).amid(whitespaces.?) <~~ ")"
        ^^^ { Expr.sExp($0.target, $0.range) }

    static let anExp = anInt | anID | aSExp <!-- "an expression"
}

/// Success
try Grammar.anExp.parse("(+ (+ 1 -20) 2 3)")
/// Output: Expr.sExp(...)

/// Failure
try Grammar.anExp.parse("(+ \n(+ %% 1 -20) 2 3)")
/// Output: Parse failure at 2:4 ----
///         (+ %% 1 -20) 2 3)
///            ^~~~~~~~~~~~~~
///         Expecting an expression, but found "%"

Dependency

Funky - Functional Programming Library

License

MIT License

Cheap and reliable Node.js hosting starts at $3/month, and $1/month static HTML hosting

rxwei / Parsey

Programming Languages

Labels

Projects that are alternatives of or similar to Parsey