Databases
StackOverflow2013
Postsdbo
POWill this 'algorithm' for nullable and first work (in a parser)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWill this 'algorithm' for nullable and first work (in a parser)?
    primarykey
    data
    text
    <p>Working through this for fun: <a href="http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/" rel="nofollow noreferrer">http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/</a></p> <p>Example calculation of nullable and first uses a fixed-point calculation. (see section 3.8)</p> <p>I'm doing things in Scheme and relying a lot on recursion.</p> <p>If you try to implement nullable or first via recursion, it should be clear you'll recur infinitely on a production like </p> <p><code>N -&gt; N a b</code></p> <p>where N is a non-terminal and a,b are terminals.</p> <p>Could this be solved, recursively, by maintaining a set of non-terminals seen on the left hand side of production rules, and ignoring them after we have accounted for them once? </p> <p>This seems to work for nullable. What about for first?</p> <p><strong>EDIT:</strong> This is what I have learned from playing around. Source code link at bottom.</p> <p>Non terminals cannot be ignored in the calculation of first unless they are nullable. </p> <p>Consider:</p> <pre><code>N -&gt; N a N -&gt; X N -&gt; </code></pre> <p>Here we can ignore <code>N</code> in <code>N a</code> because <code>N</code> is nullable. We can replace <code>N -&gt; N a</code> with <code>N -&gt; a</code> and deduce that <code>a</code> is a member of <code>first(N)</code>.</p> <p>Here we cannot ignore <code>N</code>:</p> <pre><code>N -&gt; N a N -&gt; M M -&gt; b </code></pre> <p>If we ignored the <code>N</code> in <code>N -&gt; N a</code> we would deduce that <code>a</code> is in <code>first(N)</code> which is false. Instead, we see that N is not nullable, and hence when calculating first, we can omit any production where <code>N</code> is found as the first symbol in the RHS.</p> <p>This yields:</p> <pre><code>N -&gt; M M -&gt; b </code></pre> <p>which tells us <code>b</code> is in <code>first(N)</code>.</p> <p>Source Code: <a href="http://gist.github.com/287069" rel="nofollow noreferrer">http://gist.github.com/287069</a></p> <p>So ... does this sound OK?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USz5h
    1. USz5h
    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. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWill this 'algorithm' for nullable and first work (in a parser)?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWill this 'algorithm' for nullable and first work (in a parser)?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWill this 'algorithm' for nullable and first work (in a parser)?
      1. USSebastian Paaske Tørholm
      1. VTFavorite
    1. COYou not only have an infinite recursion program, but even on a computer with infinite compute capacity, you haven't provided any way to terminate this production - what other values can N have that don't include N?
      singulars
      1. POWill this 'algorithm' for nullable and first work (in a parser)?
      1. USAlex Brown
    2. COSorry, that was just one sample rule to illustrate my point. I'll try to fill out the question on my lunch break, and show some code, sample data, etc.
      singulars
      1. POWill this 'algorithm' for nullable and first work (in a parser)?
      1. USz5h
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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