Regexp::Parser

A ruby gem for tokenizing, parsing, and transforming regular expressions.

Multilayered
- A scanner/tokenizer based on ragel
- A lexer that produces a “stream” of token objects.
- A parser that produces a “tree” of Expression objects (OO API)
Runs on ruby 1.8, 1.9, 2.x, and jruby (1.9 mode) runtimes.
Recognizes ruby 1.8, 1.9, and 2.x regular expressions See Supported Syntax

For an example of regexp_parser in use, see the meta_re project

Requirements

Ruby >= 1.8.7
Ragel >= 6.0, but only if you want to build the gem or work on the scanner.

Note: See the .travis.yml file for covered versions.

Install

Install the gem with:

gem install regexp_parser

Or, add it to your project’s Gemfile:

gem 'regexp_parser', '~> X.Y.Z'

See rubygems 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:

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.

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.

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:

Regexp::Scanner.scan( /(cat?([bhm]at)){3,5}/ ).map {|token| token[2]}
#=&gt; ["(", "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 any
of the other modules.
To keep the scanner simple® 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.

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 instantiates syntax objects for Ruby 2.0, 1.9, 1.8, and
checks a few of their implementation features.

require 'regexp_parser'

ruby_20 = Regexp::Syntax.new 'ruby/2.0'
ruby_20.implements? :quantifier,  :zero_or_one             # =&gt; true
ruby_20.implements? :quantifier,  :zero_or_one_reluctant   # =&gt; true
ruby_20.implements? :quantifier,  :zero_or_one_possessive  # =&gt; true
ruby_20.implements? :conditional, :condition               # =&gt; true

ruby_19 = Regexp::Syntax.new 'ruby/1.9'
ruby_19.implements? :quantifier,  :zero_or_one             # =&gt; true
ruby_19.implements? :quantifier,  :zero_or_one_reluctant   # =&gt; true
ruby_19.implements? :quantifier,  :zero_or_one_possessive  # =&gt; true
ruby_19.implements? :conditional, :condition               # =&gt; false

ruby_18 = Regexp::Syntax.new 'ruby/1.8'
ruby_18.implements? :quantifier,  :zero_or_one             # =&gt; true
ruby_18.implements? :quantifier,  :zero_or_one_reluctant   # =&gt; true
ruby_18.implements? :quantifier,  :zero_or_one_possessive  # =&gt; false
ruby_18.implements? :conditional, :condition               # =&gt; false

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 checkng if the tokens are implemented by
the given syntax version.

See the 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.

require 'regexp_parser'

Regexp::Lexer.scan /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 seperated because it’s followed
by a quantifier that only applies to it.

Regexp::Lexer.scan( /(cat?([b]at)){3,5}/ ).map {|token| token.text}
#=&gt; ["(", "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
wiki page for attributes and methods.

Example

require 'regexp_parser'

regex = /a?(b+(c)d)*(?[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 `(?[0-9]+)`
# visit: set `[0-9]+`
# exit: group `(?[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.

include_root  = true
indent_offset = include_root ? 1 : 0

tree.each_expression(include_root) do |exp, level_index|
  puts exp.strfregexp("%&gt;&gt; %c", indent_offset)
end

# Output
# &gt; Regexp::Expression::Root
#   &gt; Regexp::Expression::Literal
#   &gt; Regexp::Expression::Group::Capture
#     &gt; Regexp::Expression::Literal
#     &gt; Regexp::Expression::Group::Capture
#       &gt; Regexp::Expression::Literal
#     &gt; Regexp::Expression::Literal
#   &gt; Regexp::Expression::Group::Named
#     &gt; 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, and 2.x:

Note that not all of these are available in all versions of Ruby

Syntax Feature	Examples	⋯
Alternation	`a	b
Anchors	`^`, `$`, `\b`	✓
Character Classes	`[abc]`, `[^\\]`, `[a-d&&g-h]`, `[a=e=b]`	✓
Character Types	`\d`, `\H`, `\s`	✓
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)`	✓
Back-references		⋱
Named	`\k`	✓
Nest Level	`\k`	✓
Numbered	`\k<1>`	✓
Relative	`\k<-2>`	✓
Traditional	`\1` thru `\9`	✓
Capturing	`(abc)`	✓
Comments	`(?# comment text)`	✓
Named	`(?abc)`, `(?'name'abc)`	✓
Options	`(?mi-x:abc)`, `(?a:\s\w+)`	✓
Passive	`(?:abc)`	✓
Subexp. Calls	`\g`, `\g<1>`	✓
Keep	`\K`, `(ab\Kc	d\Ke)f`
Literals (utf-8)	`Ruby`, `ルビー`, `روبي`	✓
POSIX Classes	`[:alpha:]`, `[:^digit:]`	✓
Quantifiers		⋱
Greedy	`?`, `*`, `+`, `{m,M}`	✓
Reluctant (Lazy)	`??`, `*?`, `+?`, `{m,M}?`	✓
Possessive	`?+`, `*+`, `++`, `{m,M}+`	✓
String Escapes		⋱
Control	`\C-C`, `\cD`	✓
Hex	`\x20`, `\x{701230}`	✓
Meta	`\M-c`, `\M-\C-C`	✓
Octal	`\0`, `\01`, `\012`	✓
Unicode	`\uHHHH`, `\u{H+ H+}`	✓
Unicode Properties	_{(Unicode 7.0.0)}	⋱
Age	`\p{Age=5.2}`, `\P{age=7.0}`	✓
Classes	`\p{Alpha}`, `\P{Space}`	✓
Derived	`\p{Math}`, `\P{Lowercase}`	✓
General Categories	`\p{Lu}`, `\P{Cs}`	✓
Scripts	`\p{Arabic}`, `\P{Hiragana}`	✓
Simple	`\p{Dash}`, `\p{Extender}`	✓

Missing Features

Unicode blocks, e.g. \p{InArrows}, \p{InArmenian}. (h/t @gjtorikian for pointing it out)

Inapplicable Features

Some modifiers, like o and s, apply to the Regexp object itself and do not
appear in its source. Others such modifiers include the encoding modifiers e and n
See.
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]
Capture History: (?@...), (?@...) [See]

See something else missing? Please submit an issue

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, as ‘test’ is the default task.

In addition to the main test task, which runs all tests, there are also component specific test
tasks, which only run the tests for one component at a time. These are:

test:scanner
test:lexer
test:parser
test:expression
test:syntax

A special task ‘test:full’ generates the scanner’s code from the ragel source files and
runs all the tests. This task requires ragel to be installed.

The tests use ruby’s test/unit, so they can also be run with:

ruby -Ilib test/test_all.rb

This is useful when there is a need to focus on specific test files, for example:

ruby -Ilib test/scanner/test_properties.rb

It is sometimes helpful during development to focus on a specific test case, for example:

ruby -Ilib test/expression/test_base.rb -n test_expression_to_re

Building

Building the scanner and the gem requires 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

References

Documentation and books used while working on this project.

Ruby Flavors

Oniguruma Regular Expressions (Ruby 1.9.x) link
Onigmo Regular Expressions (Ruby >= 2.0) link

Regular Expressions

Mastering Regular Expressions, By Jeffrey E.F. Friedl (2nd Edition) book
Regular Expression Flavor Comparison link
Enumerating the strings of regular languages link
Stack Overflow Regular Expressions FAQ link

Unicode

Unicode Explained, By Jukka K. Korpela. book
Unicode Derived Properties link
Unicode Property Aliases link
Unicode Regular Expressions link
Unicode Standard Annex #44 link

Modules

Classes

Regexp::Parser

Requirements

Install

Usage

Components

Scanner

Example

Notes

Syntax

Example

Notes

Lexer

Example

Notes

Parser

Example

Supported Syntax

Missing Features

Inapplicable Features

Testing

Building

References

Ruby Flavors

Regular Expressions

Unicode

Copyright

Top-Level Classes

Top-Level Instance Methods