Swiftpack.co - Package - kareman/Patterns

Swift 5.3 SPM

Patterns

Patterns is a Swift library for Parser Expression Grammars (PEGs). It can be used to create expressions similar to regular expressions (like regex’es) and grammars (for parsers).

For general information about PEGs, see the original paper or Wikipedia.

Example of using Patterns in a playground

To try out Patterns in a playground, open Playground/Playground.xcworkspace in Xcode (does not work in Xcode 12 beta 5 or earlier).

Note

Patterns requires Swift 5.3, which is currently in beta. If using Xcode, version 12 (also in beta) is required.

Example

let text = "This is a point: (43,7), so is (0, 5). But my final point is (3,-1)."

let number = ("+" / "-" / "") • digit+
let point = "(" • Capture(name: "x", number)
	• "," • " "¿ • Capture(name: "y", number) • ")"

struct Point: Codable {
	let x, y: Int
}

let points = try Parser(search: point).decode([Point].self, from: text)
// points == [Point(x: 43, y: 7), Point(x: 0, y: 5), Point(x: 3, y: -1)]

See also:

Usage

Patterns are defined directly in code, instead of in a text string.

Note: Long patterns can give the Swift type checker a lot to think about, especially long series of a / b / c / etc.... To improve build times, try to split a long pattern into multiple shorter ones.

Standard PEG

"text"

Text within double quotes matches that exact text, no need to escape special letters with \. If you want to turn a string variable s into a pattern, use Literal(s).

OneOf(...)

This is like character classes ([...]) from regular expressions, and matches 1 character. OneOf("aeiouAEIOU") matches any single character in that string, and OneOf("a"..."e") matches any of "abcde". They can also be combined, like OneOf("aeiou", punctuation, "x"..."z"). To match any character except ..., use OneOf(not: ...).

You can also implement one yourself:

OneOf(description: "ten") { character in
	character.wholeNumberValue == 10
}

It takes a closure @escaping (Character) -> Bool and matches any character for which the closure returns true. The description parameter is only used when creating a textual representation of the pattern.

a • b • c

The • operator (Option-8 on U.S. keyboards, Option-Q on Norwegian ones) first matches a, then b and then c. It is used to create a pattern from a sequence of other patterns.

a*

matches 0 or more, as many as it can (it is greedy, like the regex a*?). So a pattern like a* • a will never match anything because the a* pattern will always match all it can, leaving nothing left for the last a.

a+

matches 1 or more, also as many as it can (like the regex a+?).

a¿

makes a optional, but it always matches if it can (the ¿ character is Option-Shift-TheKeyWith?OnIt on most keyboards).

a / b

This first tries the pattern on the left. If that fails it tries the pattern on the right. This is ordered choice, once a has matched it will never go back and try b if a later part of the expression fails. This is the main difference between PEGs and most other grammars and regex'es.

&&a • b

The "and predicate" first verifies that a matches, then moves the position in the input back to where a began and continues with b. In other words it verifies that both a and b match from the same position. So to match one ASCII letter you can use &&ascii • letter.

!a • b

The "not predicate" verifies that a does not match, then just like above it moves the position in the input back to where a began and continues with b. You can read it like "b and not a".

Grammars

The main advantage of PEGs over regular expressions is that they support recursive expressions. These expressions can contain themselves, or other expressions that in turn contain them. Here is how you can parse simple arithmetic expressions:

let arithmetic = Grammar { g in
	g.all     <- g.expr • !any
	g.expr    <- g.sum
	g.sum     <- g.product • (("+" / "-") • g.product)*
	g.product <- g.power • (("*" / "/") • g.power)*
	g.power   <- g.value • ("^" • g.power)¿
	g.value   <- digit+ / "(" • g.expr • ")"
}

This will parse expressions like "1+2-3^(4*3)/2".

The top expression is called first. • !any means it must match the entire string, because only at the end of the string is there no characters. If you want to match multiple arithmetic expressions in a string, comment out the first expression. Grammars use dynamic properties so there is no auto-completion for the expression names.

Additions

There are predefined OneOf patterns for all the boolean is... properties of Swift's Character: letter, lowercase, uppercase, punctuation, whitespace, newline, hexDigit, digit, ascii, symbol, mathSymbol, currencySymbol.

They all have the same name as the last part of the property, except for wholeNumber, which is renamed to digit because wholeNumber sounds more like an entire number than a single digit.

There is also alphanumeric, which is a letter or a digit.

any

Matches any character. !any matches only the end of the text.

Line()

Matches a single line, not including the newline characters. So Line() • Line() will never match anything, but Line() • "\n" • Line() matches 2 lines.

Line.Start() matches at the beginning of the text, and after any newline characters. Line.End() matches at the end of the text, and right before any newline characters. They both have a length of 0, which means the next pattern will start at the same position in the text.

Word.Boundary()

Matches the position right before or right after a word. Like Line.Start() and Line.End() it also has a length of 0.

a.repeat(...)

a.repeat(2) matches 2 of that pattern in a row. a.repeat(...2) matches 0, 1 or 2, a.repeat(2...) matches 2 or more and a.repeat(3...6) between 3 and 6.

Skip() • a • b

Finds the first match of a • b from the current position.

Parsing

To actually use a pattern, pass it to a Parser:

let parser = try Parser(search: a)
for match in parser.matches(in: text) {
	// ...
}

Parser(search: a) searches for the first match for a. It is the same as Parser(Skip() • a).

The .matches(in: String) method returns a lazy sequence of Match instances.

Often we are only interested in parts of a pattern. You can use the Capture pattern to assign a name to those parts:

let text = "This is a point: (43,7), so is (0, 5). But my final point is (3,-1)."

let number = ("+" / "-" / "") • digit+
let point = "(" • Capture(name: "x", number)
	• "," • " "¿ • Capture(name: "y", number) • ")"

struct Point: Codable {
	let x, y: Int
}

let parser = try Parser(search: point)
let points = try parser.decode([Point].self, from: text)

Or you can use subscripting:

let pointsAsSubstrings = parser.matches(in: text).map { match in
	(text[match[one: "x"]!], text[match[one: "y"]!])
}

You can also use match[multiple: name] to get an array if captures with that name may be matched multiple times. match[one: name] only returns the first capture of that name.

Inputs

By default, patterns have String as their input type. But you can use any BidirectionalCollection with Hashable elements for input. Just explicitly specify the input type of the first pattern, and the rest should get it automatically:

let text = "This is a point: (43,7), so is (0, 5). But my final point is (3,-1).".utf8

let digit = OneOf<String.UTF8View>(UInt8(ascii: "0")...UInt8(ascii: "9"))
let number = ("+" / "-" / "") • digit+
let point = "(" • Capture(name: "x", number)
	• "," • " "¿ • Capture(name: "y", number) • ")"

struct Point: Codable {
	let x, y: Int
}

let parser = try Parser(search: point)
let pointsAsSubstrings = parser.matches(in: text).map { match in
	(text[match[one: "x"]!], text[match[one: "y"]!])
}

Parser.decode can (currently) only take String as input, but .matches handles all types.

Setup

Swift Package Manager

Add this to your Package.swift file:

dependencies: [
    .package(url: "https://github.com/kareman/Patterns.git", from: "0.1.0"),
]

or choose “Add Package Dependency” from within Xcode.

Implementation

Patterns is implemented using a virtual parsing machine, similar to how LPEG is implemented, and the backtrackingvm function described here.

Contributing

Contributions are most welcome 🙌.

License

MIT

Patterns
Copyright © 2019

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

Github

link
Stars: 3

Dependencies

Used By

Total: 0

Releases

- 2020-08-23 12:49:25

  • Simplify .range(of:) and SearchCache.

  • Readme: add note about long build times.

  • Make Pattern Equatable. (#44)

    Make AnyPattern not use protocol type.

  • Set Swift version to 5.3.

    CI: use 5.3-DEVELOPMENT-SNAPSHOT-2020-08-08-a on Linux. Cannot use just 5.3 on linux, and when using 5.3-DEVELOPMENT-SNAPSHOT-2020-08-08-a on macOS it cannot find XCTest.

  • Merge pull request #45 from kareman/Generic-input

    Support generic input

  • Merge pull request #47 from kareman/Readme-require-Swift-5.3

    Readme: require Swift 5.3. Add part about pattern input types. Split up readme unit test to avoid warning about it taking too long to type check.

  • GitHub-related stuff (#51)

    Update bug-report.md CI test: don’t run on non-code related changes. Update feature-request.md

  • Fix bug where not all .skip were replaced.

    setupSkip(at: i) adds 1 new instruction somewhere after ì, so we cant loop over self.indices directly.

  • Update dependency swift-argument-parser. (#54)

  • PatternsTests: Only warn when expressions take long to build.

    Not entire functions.

  • Improve and fix documentation for Skip.

  • Merge pull request #55 from kareman/documentation

    Add documentation

  • Restore all former String performance tests.

  • Make separate utf8 performance tests.

  • Make instructions @usableFromInline.

  • Merge pull request #56 from kareman/Optimise-after-adding-generic-Input

    Specifically specialize for String and UTF8View. It stopped happening automatically after making Pattern.Input generic. Makes a huge difference in performance.

  • Rename Word.boundary to Word.Boundary().

  • Rename Line.start to Line.Start(). Likewise with Line.end.

    To make things more consistent, and to allow automatically returning a type with the correct Input type. Which is only possible with a function/initialiser.

  • Don't use Pattern.Instructions outside of its file.

    It sometimes causes compiler crashes, it doesn't in this case but we might as well be consistent and never use it.

  • Document Skip() even more.

- 2020-07-07 15:13:52

  • unicode_properties: Don't use string interpolation.
  • Readme: remove Cartage installation instructions.
  • Rename Instruction.split to .choice, remove first parameter.
  • More Instruction renaming. Added documentation.
  • Convert Capture from a struct to a function.
  • 'flatten' Capture to make it easier for Skip to see what comes after it.
  • Add Instruction.choiceEnd.
  • Move some instructions as far back as possible.
  • Add proper support for ‘Skip’ in preprocessing.
  • Undo "'flatten' Capture to make it easier for Skip to see what comes after it."
  • ‘.choice’ must always add to the stack.
  • All moved .checkIndex should be first.
  • Merge pull request #37 from kareman/ProperSkip
  • Replace instruction '.function' with '.search'.
  • Make VMBacktrackEngine a struct.
  • Remove ability to do Skip(a), as it had no effect.
  • Playground: import dependency, add showParserView function.
  • Merge pull request #38 from kareman/cleanup
  • Improve playground example and screenshot.
  • Readme: add ‘OneOf(not: ...)’.
  • Add testPlaygroundExample.
  • Add mapPrefix.
  • Simplify, move optimisation methods to MutableCollection.
  • Set associativity for '•' operator to 'left'.
  • Add documentation and @inlineable.
  • Reinstate Capture as a struct.
  • Fix optimisations of !OneOf • Oneof and &&OneOf • OneOf.
  • Add documentation, remove unused code.
  • Add documentation, and @inlinable / @usableFromInline.
  • Rename Concat left/right to first/second.
  • Add documentation, and @inlinable / @usableFromInline.
  • Make Grammar.patterns an array.
  • Merge pull request #39 from kareman/simplify
  • Add testPEGGrammar.
  • PerformanceTests: only measure CPU metrics in current thread.
  • Recalibrate performance tests.
  • Move and add SkipTests.
  • Add tail call optimisation to Grammars.
  • Support 'g.a <- " " • Skip() • g.b'. Properly support inserting instructions.
  • Merge pull request #40 from kareman/addSkipTests
  • Add testBeforeGrammarCallInChoice. placeSkipCommit: .fail isn't fatal.
  • Add documentation, some small renaming.
  • Add Wiki generation workflow.
  • Remove support for CocoaPods.
  • Generate wiki (#42) Use kareman/swift-doc@support-kareman-Patterns
  • Add documentation to the top level common patterns.