Regular Expressions

A grammar that reads PCRE - the notation the %token lines of every other example here are written in:

1(?<year>[0-9]{4})-(?P<month>[0-9]{2})-(?:[0-9]{2})
2(?i)^\Afoo(?=bar)(?!baz)(?<=qux)end\z$
3a?b??c?+d*e*?f*+g+h+?i++j{2}k{2,5}l{2,5}?m{2,}+

Almost all of the work happens in the lexer, and the parser that follows is three rules long: an alternation of concatenations of quantified things.

That split is the lesson. A character class is one token - \[\^?\]?(?:\\.|\[:\^?[a-z]++:\]|[^\]])*+\] - because inside [...] every character stands for itself, * and | included; letting the parser see the pieces would mean teaching it to un-see them. The same goes for (?#...), (?<name> and (?(1), each of which ends at a character of its own and is read whole.

And where two spellings begin alike, the longer one is declared first: \?\+ before \?\? before \?, and the \(\?<= of a lookbehind before the \(\?P?< of a named group. The lexer takes the first pattern that matches, not the longest, so the order is the rule.

Grammar

  1/**
  2 * -----------------------------------------------------------------------------
  3 *  PCRE
  4 * -----------------------------------------------------------------------------
  5 *
  6 * The pattern a Perl-compatible regular expression is written of, without the
  7 * delimiters and the modifiers around it.
  8 *
  9 * @see https://github.com/hoaproject/Regex/blob/master/Source/Grammar.pp
 10 */
 11
 12%pragma root Expression
 13
 14/**
 15 * -----------------------------------------------------------------------------
 16 *  Groups
 17 * -----------------------------------------------------------------------------
 18 *
 19 *  A group is told from another by what is written past its parenthesis, so
 20 *  the longer spelling is declared before the shorter one it begins with.
 21 *
 22 *  A comment, a name and a reference each end at a character of their own, so
 23 *  each is read whole rather than by switching the reading over to a lexer of
 24 *  its own.
 25 */
 26
 27%token T_INTERNAL_OPTION        \(\?[\-+]?[imsxUXn]++\)
 28
 29%token T_COMMENT_GROUP          \(\?#((?:\\.|[^)])*+)\)
 30
 31%token T_LOOKAHEAD              \(\?=
 32%token T_NEGATIVE_LOOKAHEAD     \(\?!
 33%token T_LOOKBEHIND             \(\?<=
 34%token T_NEGATIVE_LOOKBEHIND    \(\?<!
 35
 36%token T_NAMED_REFERENCE        \(\?\(<((?:\\.|[^>])++)>\)
 37%token T_RELATIVE_REFERENCE     \(\?\(([+\-][0-9]++)\)
 38%token T_ABSOLUTE_REFERENCE     \(\?\(([0-9]++)\)
 39// The assertion a condition is written on opens with a parenthesis of its own
 40%token T_ASSERTION_REFERENCE    \(\?(?=\()
 41
 42%token T_NAMED_CAPTURING        \(\?P?<((?:\\.|[^>])++)>
 43%token T_NON_CAPTURING          \(\?:
 44%token T_NON_CAPTURING_RESET    \(\?\|
 45%token T_ATOMIC_GROUP           \(\?>
 46%token T_CAPTURING_OPEN         \(
 47%token T_CAPTURING_CLOSE        \)
 48
 49/**
 50 * -----------------------------------------------------------------------------
 51 *  Character Class
 52 * -----------------------------------------------------------------------------
 53 *
 54 *  Every character of a class stands for itself, an operator and a quantifier
 55 *  included, so a class is read whole rather than by the tokens it is written
 56 *  of. A bracket written first closes nothing, and a backslash escapes the
 57 *  character past it.
 58 */
 59
 60%token T_CHARACTER_CLASS        \[\^?\]?(?:\\.|\[:\^?[a-z]++:\]|[^\]])*+\]
 61
 62/**
 63 * -----------------------------------------------------------------------------
 64 *  Quantifiers
 65 * -----------------------------------------------------------------------------
 66 */
 67
 68%token T_ZERO_OR_ONE_POSSESSIVE   \?\+
 69%token T_ZERO_OR_ONE_LAZY         \?\?
 70%token T_ZERO_OR_ONE              \?
 71%token T_ZERO_OR_MORE_POSSESSIVE  \*\+
 72%token T_ZERO_OR_MORE_LAZY        \*\?
 73%token T_ZERO_OR_MORE             \*
 74%token T_ONE_OR_MORE_POSSESSIVE   \+\+
 75%token T_ONE_OR_MORE_LAZY         \+\?
 76%token T_ONE_OR_MORE              \+
 77%token T_EXACTLY_N                \{[0-9]++\}
 78%token T_N_TO_M_POSSESSIVE        \{[0-9]++,[0-9]++\}\+
 79%token T_N_TO_M_LAZY              \{[0-9]++,[0-9]++\}\?
 80%token T_N_TO_M                   \{[0-9]++,[0-9]++\}
 81%token T_N_OR_MORE_POSSESSIVE     \{[0-9]++,\}\+
 82%token T_N_OR_MORE_LAZY           \{[0-9]++,\}\?
 83%token T_N_OR_MORE                \{[0-9]++,\}
 84
 85/**
 86 * -----------------------------------------------------------------------------
 87 *  Literals
 88 * -----------------------------------------------------------------------------
 89 *
 90 *  The last of them reads any character at all, so it is declared last.
 91 */
 92
 93%token T_ALTERNATION            \|
 94%token T_CHARACTER              \\(?:[aefnrt]|c[\x00-\x7f])
 95%token T_DYNAMIC_CHARACTER      \\(?:[0-7]{3}|x[0-9a-fA-F]{2}|x\{[0-9a-fA-F]++\})
 96%token T_CHARACTER_TYPE         \\(?:[CdDhHNRsSvVwWX]|[pP]\{[^}]++\})
 97%token T_ANCHOR                 \\[bBAZzG]|\^|\$
 98%token T_MATCH_POINT_RESET      \\K
 99// A bracket opens a class and never stands for itself, so it is written "\["
100%token T_LITERAL                \\.|[^\[]
101
102/**
103 * -----------------------------------------------------------------------------
104 *  Expression
105 * -----------------------------------------------------------------------------
106 */
107
108Expression
109  : Alternation()
110  ;
111
112Alternation
113  : Concatenation() (::T_ALTERNATION:: Concatenation())*
114  ;
115
116Concatenation
117  : (InternalOptions() | Assertion() | Condition() | Quantification())+
118  ;
119
120// (?i), (?-x)
121InternalOptions
122  : <T_INTERNAL_OPTION>
123  ;
124
125// (?=...), (?<!...)
126Assertion
127  : ( <T_LOOKAHEAD>
128    | <T_NEGATIVE_LOOKAHEAD>
129    | <T_LOOKBEHIND>
130    | <T_NEGATIVE_LOOKBEHIND>
131    )
132    Alternation() ::T_CAPTURING_CLOSE::
133  ;
134
135// (?(1)yes|no), (?(<name>)yes|no), (?(?=...)yes|no)
136Condition
137  : ( <T_NAMED_REFERENCE>
138    | <T_RELATIVE_REFERENCE>
139    | <T_ABSOLUTE_REFERENCE>
140    | ::T_ASSERTION_REFERENCE:: Assertion()
141    )
142    Concatenation()?
143    (::T_ALTERNATION:: Concatenation()?)?
144    ::T_CAPTURING_CLOSE::
145  ;
146
147Quantification
148  : (CharacterClass() | Simple()) Quantifier()?
149  ;
150
151Quantifier
152  : <T_ZERO_OR_ONE_POSSESSIVE>
153  | <T_ZERO_OR_ONE_LAZY>
154  | <T_ZERO_OR_ONE>
155  | <T_ZERO_OR_MORE_POSSESSIVE>
156  | <T_ZERO_OR_MORE_LAZY>
157  | <T_ZERO_OR_MORE>
158  | <T_ONE_OR_MORE_POSSESSIVE>
159  | <T_ONE_OR_MORE_LAZY>
160  | <T_ONE_OR_MORE>
161  | <T_EXACTLY_N>
162  | <T_N_TO_M_POSSESSIVE>
163  | <T_N_TO_M_LAZY>
164  | <T_N_TO_M>
165  | <T_N_OR_MORE_POSSESSIVE>
166  | <T_N_OR_MORE_LAZY>
167  | <T_N_OR_MORE>
168  ;
169
170// [a-z], [^0-9], [[:alpha:]]
171CharacterClass
172  : <T_CHARACTER_CLASS>
173  ;
174
175Simple
176  : Group()
177  | Literal()
178  ;
179
180Group
181  : <T_COMMENT_GROUP>
182  | ( <T_NAMED_CAPTURING>
183    | <T_NON_CAPTURING>
184    | <T_NON_CAPTURING_RESET>
185    | <T_ATOMIC_GROUP>
186    | ::T_CAPTURING_OPEN::
187    )
188    Alternation() ::T_CAPTURING_CLOSE::
189  ;
190
191Literal
192  : <T_CHARACTER>
193  | <T_DYNAMIC_CHARACTER>
194  | <T_CHARACTER_TYPE>
195  | <T_ANCHOR>
196  | <T_MATCH_POINT_RESET>
197  | <T_LITERAL>
198  ;

Usage

1use Phplrt\Compiler\Compiler;
2use Phplrt\Source\File;
3use Phplrt\Source\Source;
4
5$parser = new Compiler()
6    ->load(new File(__DIR__ . '/grammar.pp3'))
7    ->getParser();
8
9$pattern = $parser->parse(new Source('(?<year>[0-9]{4})-[0-9]{2}'));

The pattern is read without the delimiters and the modifiers around it, so strip the /.../i before handing it over. What comes back is enough to count the groups in a pattern, to rename them, to explain a regular expression to a human, or to generate a string that matches one.

25+ more grammars. phplrt/grammars collects ready to read grammars for real languages - JSON5, TSV, semantic versions, DQL, PHQL, JMS types, PSR-5 and Doctrine annotations, Symfony expressions, Go! AOP pointcuts, Praspel contracts and more - each with sample inputs and a test that keeps it honest.