1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2021-2022 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
public enum PEG<Element: Comparable & Hashable> {}
extension PEG {
public enum Pattern {
/// Match any element
case any
/// Match succeeds
case success
/// Match fails
case failure
/// Match a specific element
case element(Element)
/// Match one of many potential elements
case charactetSet((Element) -> Bool)
/// A literal sequence of elements
case literal(Array<Element>)
/// Try `p1` first, and only if it doesn't work, backtrack and try `p2`
indirect case orderedChoice(Pattern, Pattern)
/// Try each pattern in succession
indirect case concat([Pattern])
/// `p1 - p2` == `!p2 p1`, i.e. match `p1` so long as `p2` is not true
indirect case difference(Pattern, Pattern)
/// Repeat a pattern at least `n` times
indirect case `repeat`(Pattern, atLeast: Int)
indirect case repeatRange(Pattern, atLeast: Int, atMost: Int)
/// Match if `p1` matches, but does not consume input
indirect case and(Pattern)
/// Match if `p1` does not match. Does not consume input
indirect case not(Pattern)
/// Capture `p1`
indirect case capture(Pattern)
/// Reference a declared variable (e.g. for recursive patterns)
case variable(String)
// Some conveniences
/// The end of input
///
/// .end == .not(.any) == assertion { $1 == $0.endIndex }
case end
public static func many(_ p: Pattern) -> Pattern {
.repeat(p, atLeast: 0)
}
public static func oneOrMore(_ p: Pattern) -> Pattern {
.repeat(p, atLeast: 1)
}
public static func zeroOrOne(_ p: Pattern) -> Pattern {
.repeatRange(p, atLeast: 0, atMost: 1)
}
public static func range<RE: RangeExpression>(
_ re: RE
) -> Pattern where RE.Bound == Element {
.charactetSet({ re.contains($0) })
}
}
struct Production {
let name: String
let pattern: Pattern
var destructure: (name: String, pattern: Pattern) {
(name, pattern)
}
}
// Environment is, effectively, a list of productions
public typealias Environment = Dictionary<String, Pattern>
public struct Program {
public let start: String
public let environment: Environment
public init(start: String, environment: Environment) {
self.start = start
self.environment = environment
}
func checkInvariants() {
assert(environment[start] != nil)
}
var entry: Production {
Production(name: start, pattern: environment[start]!)
}
var destructure: (start: String, environment: Environment) {
(start, environment)
}
}
}
extension PEG.Pattern: CustomStringConvertible {
public var description: String {
switch self {
case .any: return "<any>"
case .success: return "<success>"
case .failure: return "<failure>"
case .element(let e): return "'\(e)'"
case .charactetSet(let s):
return "\(String(describing: s))"
case .literal(let l):
return "'\(l.map { "\($0)" }.joined())'"
case .orderedChoice(let lhs, let rhs):
return "(\(lhs) | \(rhs))"
case .concat(let s):
return s.map { "\($0)" }.joined(separator: " ")
case .difference(let lhs, let rhs): return "(\(lhs) - \(rhs))"
case .repeat(let p, let atLeast):
return "<repeat \(p) atLeast: \(atLeast)>"
case .repeatRange(let p, let atLeast, let atMost):
return "<repeat \(p) atLeast: \(atLeast) atMost: \(atMost)>"
case .and(let p): return "&(\(p))"
case .not(let p): return "!(\(p))"
case .capture(let p): return "<capture \(p)>"
case .variable(let v): return "\(v)"
case .end: return "<end>"
}
}
}
extension PEG.Pattern:
ExpressibleByExtendedGraphemeClusterLiteral,
ExpressibleByUnicodeScalarLiteral,
ExpressibleByStringLiteral
where Element == Character {
public typealias UnicodeScalarLiteralType = String
public typealias ExtendedGraphemeClusterLiteralType = String
public init(stringLiteral value: String) {
if value.count == 1 {
self = .element(value.first!)
} else {
self = .literal(Array(value))
}
}
}
extension PEG.Pattern {
public init(_ term: Self) {
self = term
}
public init(_ terms: Self...) {
self = .concat(terms)
}
}
|
