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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
|
# Regexp::Parser
[](http://badge.fury.io/rb/regexp_parser)
[](https://github.com/ammar/regexp_parser/actions)
[](https://github.com/ammar/regexp_parser/actions)
[](https://codeclimate.com/github/ammar/regexp_parser/badges)
A Ruby gem for tokenizing, parsing, and transforming regular expressions.
* Multilayered
* A scanner/tokenizer based on [Ragel](http://www.colm.net/open-source/ragel/)
* A lexer that produces a "stream" of [Token objects](https://github.com/ammar/regexp_parser/wiki/Token-Objects)
* A parser that produces a "tree" of [Expression objects (OO API)](https://github.com/ammar/regexp_parser/wiki/Expression-Objects)
* Runs on Ruby 2.x, 3.x and JRuby runtimes
* Recognizes Ruby 1.8, 1.9, 2.x and 3.x regular expressions [See Supported Syntax](#supported-syntax)
_For examples of regexp_parser in use, see [Example Projects](#example-projects)._
---
## Requirements
* Ruby >= 2.0
* Ragel >= 6.0, but only if you want to build the gem or work on the scanner.
---
## Install
Install the gem with:
`gem install regexp_parser`
Or, add it to your project's `Gemfile`:
```gem 'regexp_parser', '~> X.Y.Z'```
See the badge at the top of this README or [rubygems](https://rubygems.org/gems/regexp_parser)
for the the latest version number.
---
## Usage
The three main modules are **Scanner**, **Lexer**, and **Parser**. Each of them
provides a single method that takes a regular expression (as a Regexp object or
a string) and returns its results. The **Lexer** and the **Parser** accept an
optional second argument that specifies the syntax version, like 'ruby/2.0',
which defaults to the host Ruby version (using RUBY_VERSION).
Here are the basic usage examples:
```ruby
require 'regexp_parser'
Regexp::Scanner.scan(regexp)
Regexp::Lexer.lex(regexp)
Regexp::Parser.parse(regexp)
```
All three methods accept a block as the last argument, which, if given, gets
called with the results as follows:
* **Scanner**: the block gets passed the results as they are scanned. See the
example in the next section for details.
* **Lexer**: after completion, the block gets passed the tokens one by one.
_The result of the block is returned._
* **Parser**: after completion, the block gets passed the root expression.
_The result of the block is returned._
All three methods accept either a `Regexp` or `String` (containing the pattern)
- if a String is passed, `options` can be supplied:
```ruby
require 'regexp_parser'
Regexp::Parser.parse(
"a+ # Recognizes a and A...",
options: ::Regexp::EXTENDED | ::Regexp::IGNORECASE
)
```
---
## Components
### Scanner
A Ragel-generated scanner that recognizes the cumulative syntax of all
supported syntax versions. It breaks a given expression's text into the
smallest parts, and identifies their type, token, text, and start/end
offsets within the pattern.
#### Example
The following scans the given pattern and prints out the type, token, text and
start/end offsets for each token found.
```ruby
require 'regexp_parser'
Regexp::Scanner.scan(/(ab?(cd)*[e-h]+)/) do |type, token, text, ts, te|
puts "type: #{type}, token: #{token}, text: '#{text}' [#{ts}..#{te}]"
end
# output
# type: group, token: capture, text: '(' [0..1]
# type: literal, token: literal, text: 'ab' [1..3]
# type: quantifier, token: zero_or_one, text: '?' [3..4]
# type: group, token: capture, text: '(' [4..5]
# type: literal, token: literal, text: 'cd' [5..7]
# type: group, token: close, text: ')' [7..8]
# type: quantifier, token: zero_or_more, text: '*' [8..9]
# type: set, token: open, text: '[' [9..10]
# type: set, token: range, text: 'e-h' [10..13]
# type: set, token: close, text: ']' [13..14]
# type: quantifier, token: one_or_more, text: '+' [14..15]
# type: group, token: close, text: ')' [15..16]
```
A one-liner that uses map on the result of the scan to return the textual
parts of the pattern:
```ruby
Regexp::Scanner.scan(/(cat?([bhm]at)){3,5}/).map { |token| token[2] }
#=> ["(", "cat", "?", "(", "[", "b", "h", "m", "]", "at", ")", ")", "{3,5}"]
```
#### Notes
* The scanner performs basic syntax error checking, like detecting missing
balancing punctuation and premature end of pattern. Flavor validity checks
are performed in the lexer, which uses a syntax object.
* If the input is a Ruby **Regexp** object, the scanner calls #source on it to
get its string representation. #source does not include the options of
the expression (m, i, and x). To include the options in the scan, #to_s
should be called on the **Regexp** before passing it to the scanner or the
lexer. For the parser, however, this is not necessary. It automatically
exposes the options of a passed **Regexp** in the returned root expression.
* To keep the scanner simple(r) and fairly reusable for other purposes, it
does not perform lexical analysis on the tokens, sticking to the task
of identifying the smallest possible tokens and leaving lexical analysis
to the lexer.
* The MRI implementation may accept expressions that either conflict with
the documentation or are undocumented, like `{}` and `]` _(unescaped)_.
The scanner will try to support as many of these cases as possible.
---
### Syntax
Defines the supported tokens for a specific engine implementation (aka a
flavor). Syntax classes act as lookup tables, and are layered to create
flavor variations. Syntax only comes into play in the lexer.
#### Example
The following fetches syntax objects for Ruby 2.0, 1.9, 1.8, and
checks a few of their implementation features.
```ruby
require 'regexp_parser'
ruby_20 = Regexp::Syntax.for 'ruby/2.0'
ruby_20.implements? :quantifier, :zero_or_one # => true
ruby_20.implements? :quantifier, :zero_or_one_reluctant # => true
ruby_20.implements? :quantifier, :zero_or_one_possessive # => true
ruby_20.implements? :conditional, :condition # => true
ruby_19 = Regexp::Syntax.for 'ruby/1.9'
ruby_19.implements? :quantifier, :zero_or_one # => true
ruby_19.implements? :quantifier, :zero_or_one_reluctant # => true
ruby_19.implements? :quantifier, :zero_or_one_possessive # => true
ruby_19.implements? :conditional, :condition # => false
ruby_18 = Regexp::Syntax.for 'ruby/1.8'
ruby_18.implements? :quantifier, :zero_or_one # => true
ruby_18.implements? :quantifier, :zero_or_one_reluctant # => true
ruby_18.implements? :quantifier, :zero_or_one_possessive # => false
ruby_18.implements? :conditional, :condition # => false
```
Syntax objects can also be queried about their complete and relative feature sets.
```ruby
require 'regexp_parser'
ruby_20 = Regexp::Syntax.for 'ruby/2.0' # => Regexp::Syntax::V2_0_0
ruby_20.added_features # => { conditional: [...], ... }
ruby_20.removed_features # => { property: [:newline], ... }
ruby_20.features # => { anchor: [...], ... }
```
#### Notes
* Variations on a token, for example a named group with angle brackets (< and >)
vs one with a pair of single quotes, are specified with an underscore followed
by two characters appended to the base token. In the previous named group example,
the tokens would be :named_ab (angle brackets) and :named_sq (single quotes).
These variations are normalized by the syntax to :named.
---
### Lexer
Sits on top of the scanner and performs lexical analysis on the tokens that
it emits. Among its tasks are; breaking quantified literal runs, collecting the
emitted token attributes into Token objects, calculating their nesting depth,
normalizing tokens for the parser, and checking if the tokens are implemented by
the given syntax version.
See the [Token Objects](https://github.com/ammar/regexp_parser/wiki/Token-Objects)
wiki page for more information on Token objects.
#### Example
The following example lexes the given pattern, checks it against the Ruby 1.9
syntax, and prints the token objects' text indented to their level.
```ruby
require 'regexp_parser'
Regexp::Lexer.lex(/a?(b(c))*[d]+/, 'ruby/1.9') do |token|
puts "#{' ' * token.level}#{token.text}"
end
# output
# a
# ?
# (
# b
# (
# c
# )
# )
# *
# [
# d
# ]
# +
```
A one-liner that returns an array of the textual parts of the given pattern.
Compare the output with that of the one-liner example of the **Scanner**; notably
how the sequence 'cat' is treated. The 't' is separated because it's followed
by a quantifier that only applies to it.
```ruby
Regexp::Lexer.scan(/(cat?([b]at)){3,5}/).map { |token| token.text }
#=> ["(", "ca", "t", "?", "(", "[", "b", "]", "at", ")", ")", "{3,5}"]
```
#### Notes
* The syntax argument is optional. It defaults to the version of the Ruby
interpreter in use, as returned by RUBY_VERSION.
* The lexer normalizes some tokens, as noted in the Syntax section above.
---
### Parser
Sits on top of the lexer and transforms the "stream" of Token objects emitted
by it into a tree of Expression objects represented by an instance of the
Expression::Root class.
See the [Expression Objects](https://github.com/ammar/regexp_parser/wiki/Expression-Objects)
wiki page for attributes and methods.
#### Example
```ruby
require 'regexp_parser'
regex = /a?(b+(c)d)*(?<name>[0-9]+)/
tree = Regexp::Parser.parse(regex, 'ruby/2.1')
tree.traverse do |event, exp|
puts "#{event}: #{exp.type} `#{exp.to_s}`"
end
# Output
# visit: literal `a?`
# enter: group `(b+(c)d)*`
# visit: literal `b+`
# enter: group `(c)`
# visit: literal `c`
# exit: group `(c)`
# visit: literal `d`
# exit: group `(b+(c)d)*`
# enter: group `(?<name>[0-9]+)`
# visit: set `[0-9]+`
# exit: group `(?<name>[0-9]+)`
```
Another example, using each_expression and strfregexp to print the object tree.
_See the traverse.rb and strfregexp.rb files under `lib/regexp_parser/expression/methods`
for more information on these methods._
```ruby
include_root = true
indent_offset = include_root ? 1 : 0
tree.each_expression(include_root) do |exp, level_index|
puts exp.strfregexp("%>> %c", indent_offset)
end
# Output
# > Regexp::Expression::Root
# > Regexp::Expression::Literal
# > Regexp::Expression::Group::Capture
# > Regexp::Expression::Literal
# > Regexp::Expression::Group::Capture
# > Regexp::Expression::Literal
# > Regexp::Expression::Literal
# > Regexp::Expression::Group::Named
# > Regexp::Expression::CharacterSet
```
_Note: quantifiers do not appear in the output because they are members of the
Expression class. See the next section for details._
---
## Supported Syntax
The three modules support all the regular expression syntax features of Ruby 1.8,
1.9, 2.x and 3.x:
_Note that not all of these are available in all versions of Ruby_
| Syntax Feature | Examples | ⋯ |
| ------------------------------------- | ------------------------------------------------------- |:--------:|
| **Alternation** | `a\|b\|c` | ✓ |
| **Anchors** | `\A`, `^`, `\b` | ✓ |
| **Character Classes** | `[abc]`, `[^\\]`, `[a-d&&aeiou]`, `[a=e=b]` | ✓ |
| **Character Types** | `\d`, `\H`, `\s` | ✓ |
| **Cluster Types** | `\R`, `\X` | ✓ |
| **Conditional Exps.** | `(?(cond)yes-subexp)`, `(?(cond)yes-subexp\|no-subexp)` | ✓ |
| **Escape Sequences** | `\t`, `\\+`, `\?` | ✓ |
| **Free Space** | whitespace and `# Comments` _(x modifier)_ | ✓ |
| **Grouped Exps.** | | ⋱ |
|   _**Assertions**_ | | ⋱ |
|   _Lookahead_ | `(?=abc)` | ✓ |
|   _Negative Lookahead_ | `(?!abc)` | ✓ |
|   _Lookbehind_ | `(?<=abc)` | ✓ |
|   _Negative Lookbehind_ | `(?<!abc)` | ✓ |
|   _**Atomic**_ | `(?>abc)` | ✓ |
|   _**Absence**_ | `(?~abc)` | ✓ |
|   _**Back-references**_ | | ⋱ |
|   _Named_ | `\k<name>` | ✓ |
|   _Nest Level_ | `\k<n-1>` | ✓ |
|   _Numbered_ | `\k<1>` | ✓ |
|   _Relative_ | `\k<-2>` | ✓ |
|   _Traditional_ | `\1` through `\9` | ✓ |
|   _**Capturing**_ | `(abc)` | ✓ |
|   _**Comments**_ | `(?# comment text)` | ✓ |
|   _**Named**_ | `(?<name>abc)`, `(?'name'abc)` | ✓ |
|   _**Options**_ | `(?mi-x:abc)`, `(?a:\s\w+)`, `(?i)` | ✓ |
|   _**Passive**_ | `(?:abc)` | ✓ |
|   _**Subexp. Calls**_ | `\g<name>`, `\g<1>` | ✓ |
| **Keep** | `\K`, `(ab\Kc\|d\Ke)f` | ✓ |
| **Literals** _(utf-8)_ | `Ruby`, `ルビー`, `روبي` | ✓ |
| **POSIX Classes** | `[:alpha:]`, `[:^digit:]` | ✓ |
| **Quantifiers** | | ⋱ |
|   _**Greedy**_ | `?`, `*`, `+`, `{m,M}` | ✓ |
|   _**Reluctant** (Lazy)_ | `??`, `*?`, `+?` \[1\] | ✓ |
|   _**Possessive**_ | `?+`, `*+`, `++` \[1\] | ✓ |
| **String Escapes** | | ⋱ |
|   _**Control** \[2\]_ | `\C-C`, `\cD` | ✓ |
|   _**Hex**_ | `\x20`, `\x{701230}` | ✓ |
|   _**Meta** \[2\]_ | `\M-c`, `\M-\C-C`, `\M-\cC`, `\C-\M-C`, `\c\M-C` | ✓ |
|   _**Octal**_ | `\0`, `\01`, `\012` | ✓ |
|   _**Unicode**_ | `\uHHHH`, `\u{H+ H+}` | ✓ |
| **Unicode Properties** | _<sub>([Unicode 13.0.0])</sub>_ | ⋱ |
|   _**Age**_ | `\p{Age=5.2}`, `\P{age=7.0}`, `\p{^age=8.0}` | ✓ |
|   _**Blocks**_ | `\p{InArmenian}`, `\P{InKhmer}`, `\p{^InThai}` | ✓ |
|   _**Classes**_ | `\p{Alpha}`, `\P{Space}`, `\p{^Alnum}` | ✓ |
|   _**Derived**_ | `\p{Math}`, `\P{Lowercase}`, `\p{^Cased}` | ✓ |
|   _**General Categories**_ | `\p{Lu}`, `\P{Cs}`, `\p{^sc}` | ✓ |
|   _**Scripts**_ | `\p{Arabic}`, `\P{Hiragana}`, `\p{^Greek}` | ✓ |
|   _**Simple**_ | `\p{Dash}`, `\p{Extender}`, `\p{^Hyphen}` | ✓ |
[Unicode 13.0.0]: https://www.unicode.org/versions/Unicode13.0.0/
**\[1\]**: Ruby does not support lazy or possessive interval quantifiers.
Any `+` or `?` that follows an interval quantifier will be treated as another,
chained quantifier. See also [#3](https://github.com/ammar/regexp_parser/issue/3),
[#69](https://github.com/ammar/regexp_parser/pull/69).
**\[2\]**: As of Ruby 3.1, meta and control sequences are [pre-processed to hex
escapes when used in Regexp literals](https://github.com/ruby/ruby/commit/11ae581),
so they will only reach the scanner and will only be emitted if a String or a Regexp
that has been built with the `::new` constructor is scanned.
##### Inapplicable Features
Some modifiers, like `o` and `s`, apply to the **Regexp** object itself and do not
appear in its source. Other such modifiers include the encoding modifiers `e` and `n`
[See](http://www.ruby-doc.org/core-2.5.0/Regexp.html#class-Regexp-label-Encoding).
These are not seen by the scanner.
The following features are not currently enabled for Ruby by its regular
expressions library (Onigmo). They are not supported by the scanner.
- **Quotes**: `\Q...\E` _[[See]](https://github.com/k-takata/Onigmo/blob/7911409/doc/RE#L499)_
- **Capture History**: `(?@...)`, `(?@<name>...)` _[[See]](https://github.com/k-takata/Onigmo/blob/7911409/doc/RE#L550)_
See something missing? Please submit an [issue](https://github.com/ammar/regexp_parser/issues)
_**Note**: Attempting to process expressions with unsupported syntax features can raise
an error, or incorrectly return tokens/objects as literals._
## Testing
To run the tests simply run rake from the root directory.
The default task generates the scanner's code from the Ragel source files and runs
all the specs, thus it requires Ragel to be installed.
Note that changes to Ragel files will not be reflected when running `rspec` on its own,
so to run individual tests you might want to run:
```
rake ragel:rb && rspec spec/scanner/properties_spec.rb
```
## Building
Building the scanner and the gem requires [Ragel](http://www.colm.net/open-source/ragel/)
to be installed. The build tasks will automatically invoke the 'ragel:rb' task to generate
the Ruby scanner code.
The project uses the standard rubygems package tasks, so:
To build the gem, run:
```
rake build
```
To install the gem from the cloned project, run:
```
rake install
```
## Example Projects
Projects using regexp_parser.
- [capybara](https://github.com/teamcapybara/capybara) is an integration testing tool
that uses regexp_parser to convert Regexps to css/xpath selectors.
- [js_regex](https://github.com/jaynetics/js_regex) converts Ruby regular expressions
to JavaScript-compatible regular expressions.
- [meta_re](https://github.com/ammar/meta_re) is a regular expression preprocessor
with alias support.
- [mutant](https://github.com/mbj/mutant) manipulates your regular expressions
(amongst others) to see if your tests cover their behavior.
- [repper](https://github.com/jaynetics/repper) is a regular expression
pretty-printer and formatter for Ruby.
- [rubocop](https://github.com/rubocop-hq/rubocop) is a linter for Ruby that
uses regexp_parser to lint Regexps.
- [twitter-cldr-rb](https://github.com/twitter/twitter-cldr-rb) is a localization helper
that uses regexp_parser to generate examples of postal codes.
## References
Documentation and books used while working on this project.
#### Ruby Flavors
* Oniguruma Regular Expressions (Ruby 1.9.x) [link](https://github.com/kkos/oniguruma/blob/master/doc/RE)
* Onigmo Regular Expressions (Ruby >= 2.0) [link](https://github.com/k-takata/Onigmo/blob/master/doc/RE)
#### Regular Expressions
* Mastering Regular Expressions, By Jeffrey E.F. Friedl (2nd Edition) [book](http://oreilly.com/catalog/9781565922570/)
* Regular Expression Flavor Comparison [link](http://www.regular-expressions.info/refflavors.html)
* Enumerating the strings of regular languages [link](http://www.cs.dartmouth.edu/~doug/nfa.ps.gz)
* Stack Overflow Regular Expressions FAQ [link](http://stackoverflow.com/questions/22937618/reference-what-does-this-regex-mean/22944075#22944075)
#### Unicode
* Unicode Explained, By Jukka K. Korpela. [book](http://oreilly.com/catalog/9780596101213)
* Unicode Derived Properties [link](http://www.unicode.org/Public/UNIDATA/DerivedCoreProperties.txt)
* Unicode Property Aliases [link](http://www.unicode.org/Public/UNIDATA/PropertyAliases.txt)
* Unicode Regular Expressions [link](http://www.unicode.org/reports/tr18/)
* Unicode Standard Annex #44 [link](http://www.unicode.org/reports/tr44/)
---
##### Copyright
_Copyright (c) 2010-2022 Ammar Ali. See LICENSE file for details._
|
