CODEWITHSUNDEEP
rubyregex
Kvass
Kvass

Reputation: 8434

Ruby regular expressions for recursive grammar definitions?

How can I use regular expressions to validate a recursive grammar definition? For example, say I have the following grammar:

   alpha := <beta> gamma | <alpha> <beta>
   beta  := delta epsilon

This is just an example of what I mean by recursive definition - I'm not looking for a regular expression that specifically addresses this problem, but more how to approach problems like these with regular expressions.

Upvotes: 0

Views: 155

Answers (1)

Bart Kiers
Bart Kiers

Reputation: 170148

Here's a way to match a recursive pattern in Ruby 1.9, in this case an arbitrary level of nested braces:

#!/usr/bin/env ruby

text = "... { a { b { c } b } a { d } a } ...";
match = text.match(/(?<entire>\{(?:[^{}]+|\g<entire>)*\})/).captures
puts match

which will print:

{ a { b { c } b } a { d } a }

A quick break down of the pattern:

(?<entire>        # start named capture group called <entire>
  \{              #   match the literal '{'
  (?:             #   start non capture group 1
    [^{}]+        #     match one or more chars other than '{' and '}'
    |             #     OR
    \g<entire>    #     recursively match named group <entire>
  )*              #   end non capture group 1 and repeat it zero or more times
  \}              #   match the literal '}'
)                 # end named capture group called <entire>

Upvotes: 1

Related Questions