Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><code>FIRST(X)</code> = the terminals which can appear first when trying parse the non-terminal <code>X</code>. If it can match an empty string, epsilon is also included.</p> <p><code>FOLLOW(X)</code> = the terminals which can appear immediately after the non-terminal <code>X</code>. This is a union of the FIRST-sets of all symbols appearing after <code>X</code> in any parsing rule.</p> <p>Read more: <a href="http://en.wikipedia.org/wiki/LL_parser" rel="nofollow">LL parser</a></p> <p>The clues given are:</p> <ol> <li><p><code>FIRST(A)</code>, <code>FIRST(S)</code> &rArr; All of the derivations of <code>A</code> and <code>S</code> respectively, must either begin with the terminal <code>b</code>, or be zero-length.</p> <blockquote> <p><code>S</code> &rarr; <code>b</code> ... | &epsilon;<br> <code>A</code> &rarr; <code>b</code> ... | &epsilon;</p> </blockquote></li> <li><p><code>FOLLOW(S)</code> &rArr; There must be some construction where <code>S</code> is followed by the terminal <code>a</code>, or a non-terminal which can begin with <code>a</code>. (Neither <code>A</code> nor <code>S</code> qualify).</p> <blockquote> <p><code>S</code> &rarr; <code>b</code> <code>S</code> <code>a</code> | &epsilon;<br> <code>A</code> &rarr; <code>b</code> ... | &epsilon;</p> </blockquote></li> <li><p><code>FOLLOW(A)</code> &rArr; There must be some construction where <code>A</code> is followed by each of the terminals <code>a</code> and <code>b</code>, or some non-terminal which can begin with those.</p> <blockquote> <p><code>S</code> &rarr; <code>b</code> <code>S</code> <code>a</code> | &epsilon;<br> <code>A</code> &rarr; <code>b</code> <code>A</code> <code>b</code> | <code>b</code> <code>A</code> <code>a</code> | &epsilon;</p> </blockquote></li> <li><p><code>FOLLOW(A)</code> &rArr; Assuming <code>S</code> is the start-symbol, <code>A</code> must appear at the end of some branch of <code>S</code>, possibly followed by other nullable non-terminals.</p> <blockquote> <p><code>S</code> &rarr; <code>b</code> <code>S</code> <code>a</code> | <code>A</code> | &epsilon;<br> <code>A</code> &rarr; <code>b</code> <code>A</code> <code>b</code> | <code>b</code> <code>A</code> <code>a</code> | &epsilon;</p> </blockquote> <p>(NB. Adding <code>A</code> to <code>S</code> did not break the constraint on <code>FIRST(S)</code>)</p></li> </ol> <p>We can make the grammar a little smaller:</p> <blockquote> <p><code>S</code> &rarr; <code>b</code> <code>S</code> <code>a</code> | <code>A</code> | &epsilon;<br> <code>A</code> &rarr; <code>b</code> <code>A</code> <code>b</code> | &epsilon;</p> </blockquote> <p>We can no longer generate strings like "<code>bbbabb</code>", but it does not violate the constraints.</p>
    singulars
    1. This table or related slice is empty.
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. This table or related slice is empty.
    2. VO
      singulars
      1. This table or related slice is empty.
 

Querying!

 
Guidance

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload