title: Simple Ragel Example that Balances Parentheses?
body: <p>Here is a starting point for a grammar:</p>
  
  <pre><code>%%{
    machine xo;
  
    char = "x" | "o";
    group = "(" char* ")";
    main := group;
  }%%
  </code></pre>
  
  <p>It handles <code>(xxxx(oo)()xx)</code>, for example. How do I extend it to allow nested groups; e.g. <code>(xxxx(o(x)o)()xx</code>?</p>
  
  <p>I know recursion is not, generally, supported by one Ragel machine. So this won't work:</p>
  
  <pre><code>group = "(" ( char | group )* ")";
  </code></pre>
  
  <p>From the <a href="http://www.complang.org/ragel/ragel-guide-6.7.pdf" rel="nofollow noreferrer">Ragel State Machine Compiler User Guide (PDF)</a>: (bold text added for emphasis):</p>
  
  <blockquote>
    <p>"In general Ragel cannot handle recursive structures because the grammar is interpreted as a regular language. However, depending on what needs to be parsed it is sometimes practical to implement the recursive parts <strong>using manual coding techniques</strong>. This often works in cases where the recursive structures are simple and easy to recognize, such as in the balancing of parentheses."</p>
    
    <p>"One approach to parsing recursive structures is to use actions that increment and decrement counters or otherwise recognize the entry to and exit from recursive structures and then jump to the appropriate machine defnition using fcall and fret. Alternatively, semantic conditions can be used to test counter variables.</p>
    
    <p>"A more traditional approach is to call a separate parsing function (expressed in the host lan- guage) when a recursive structure is entered, then later return when the end is recognized."</p>
  </blockquote>
  
  <p>From <a href="http://www.colm.net/pipermail/ragel/2007-November/000422.html" rel="nofollow noreferrer">a mailing list discussion on nested brackets</a>, the same three approaches are mentioned:</p>
  
  <blockquote>
    <ol>
    <li><p>Specify a growable stack using prepush and postpop and then use fcall
    and fret.</p></li>
    <li><p>Counting and then verify in actions or conditions.</p></li>
    <li><p>Call a new parsing function (in the host language) when the recursive
    structure is entered.</p></li>
    </ol>
  </blockquote>
  
  <p>Can you point me to an example of each -- preferably using my example above -- in Ruby? Thanks!</p>