<html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>2.2. Parsing sequences</title><link rel="stylesheet" href="fptools.css" type="text/css"><meta name="generator" content="DocBook XSL Stylesheets V1.73.2"><link rel="start" href="index.html" title="Happy User Guide"><link rel="up" href="sec-using.html" title="Chapter 2. Using Happy"><link rel="prev" href="sec-using.html" title="Chapter 2. Using Happy"><link rel="next" href="sec-Precedences.html" title="2.3. Using Precedences"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">2.2. Parsing sequences</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="sec-using.html">Prev</a> </td><th width="60%" align="center">Chapter 2. Using <span class="application">Happy</span></th><td width="20%" align="right"> <a accesskey="n" href="sec-Precedences.html">Next</a></td></tr></table><hr></div><div class="sect1" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="sec-sequences"></a>2.2. Parsing sequences</h2></div></div></div><p>A common feature in grammars is a <span class="emphasis"><em>sequence</em></span> of a
particular syntactic element. In EBNF, we'd write something
like <code class="literal">n+</code> to represent a sequence of one or more
<code class="literal">n</code>s, and <code class="literal">n*</code> for zero or more.
<span class="application">Happy</span> doesn't support this syntax explicitly, but
you can define the equivalent sequences using simple
productions.</p><p>For example, the grammar for <span class="application">Happy</span> itself
contains a rule like this:</p><pre class="programlisting">
prods : prod { [$1] }
| prods prod { $2 : $1 }
</pre><p>In other words, a sequence of productions is either a
single production, or a sequence of productions followed by a
single production. This recursive rule defines a sequence of
one or more productions.</p><p>One thing to note about this rule is that we used
<span class="emphasis"><em>left recursion</em></span> to define it - we could have written
it like this:</p><a class="indexterm" name="id2496054"></a><pre class="programlisting">
prods : prod { [$1] }
| prod prods { $1 : $2 }
</pre><p>The only reason we used left recursion is that
<span class="application">Happy</span> is more efficient at parsing left-recursive
rules; they result in a constant stack-space parser, whereas
right-recursive rules require stack space proportional to the
length of the list being parsed. This can be extremely
important where long sequences are involved, for instance in
automatically generated output. For example, the parser in GHC
used to use right-recursion to parse lists, and as a result it
failed to parse some <span class="application">Happy</span>-generated modules due
to running out of stack space!</p><p>One implication of using left recursion is that the resulting
list comes out reversed, and you have to reverse it again to get
it in the original order. Take a look at the
<span class="application">Happy</span> grammar for Haskell for many examples of
this.</p><p>Parsing sequences of zero or more elements requires a
trivial change to the above pattern:</p><pre class="programlisting">
prods : {- empty -} { [] }
| prods prod { $2 : $1 }
</pre><p>Yes - empty productions are allowed. The normal
convention is to include the comment <code class="literal">{- empty -}</code> to
make it more obvious to a reader of the code what's going
on.</p><div class="sect2" lang="en"><div class="titlepage"><div><div><h3 class="title"><a name="sec-separators"></a>2.2.1. Sequences with separators</h3></div></div></div><p>A common type of sequence is one with a
<span class="emphasis"><em>separator</em></span>: for instance function bodies in C
consist of statements separated by semicolons. To parse this
kind of sequence we use a production like this:</p><pre class="programlisting">
stmts : stmt { [$1] }
| stmts ';' stmt { $3 : $1 }
</pre><p>If the <code class="literal">;</code> is to be a <span class="emphasis"><em>terminator</em></span>
rather than a separator (i.e. there should be one following
each statement), we can remove the semicolon from the above
rule and redefine <code class="literal">stmt</code> as</p><pre class="programlisting">
stmt : stmt1 ';' { $1 }
</pre><p>where <code class="literal">stmt1</code> is the real definition of statements.</p><p>We might like to allow extra semicolons between
statements, to be a bit more liberal in what we allow as legal
syntax. We probably just want the parser to ignore these
extra semicolons, and not generate a ``null statement'' value
or something. The following rule parses a sequence or zero or
more statements separated by semicolons, in which the
statements may be empty:</p><pre class="programlisting">
stmts : stmts ';' stmt { $3 : $1 }
| stmts ';' { $1 }
| stmt { [$1] }
| {- empty -} { [] }
</pre><p>Parsing sequences of <span class="emphasis"><em>one</em></span> or more possibly
null statements is left as an exercise for the reader...</p></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="sec-using.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="sec-using.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="sec-Precedences.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 2. Using <span class="application">Happy</span> </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> 2.3. Using Precedences</td></tr></table></div></body></html>
