Databases
StackOverflow2013
Postsdbo
POProducing Expressions from This Grammar with Recursive Descent
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POProducing Expressions from This Grammar with Recursive Descent
    primarykey
    data
    text
    <p>I've got a simple grammar. Actually, the grammar I'm using is more complex, but this is the smallest subset that illustrates my question.</p> <pre><code>Expr ::= Value Suffix | "(" Expr ")" Suffix Suffix ::= "-&gt;" Expr | "&lt;-" Expr | Expr | epsilon </code></pre> <p><code>Value</code> matches identifiers, strings, numbers, et cetera. The <code>Suffix</code> rule is there to eliminate left-recursion. This matches expressions such as:</p> <pre><code>a -&gt; b (c -&gt; (d) (e)) </code></pre> <p>That is, a graph where <code>a</code> goes to both <code>b</code> and the result of <code>(c -&gt; (d) (e))</code>, and <code>c</code> goes to <code>d</code> and <code>e</code>. I'm trying to produce an abstract syntax tree for these expressions, but I'm running into difficulty because all of the operators can accept any number of operands on each side. I'd rather keep the logic for producing the AST within the recursive descent parsing methods, since it avoids having to duplicate the logic of extracting an expression. My current strategy is as follows:</p> <ol> <li><p>If a <code>Value</code> appears, push it to the output.</p></li> <li><p>If a <code>From</code> or <code>To</code> appears:</p> <ol> <li><p>Output a separator.</p></li> <li><p>Get the next <code>Expr</code>.</p></li> <li><p>Create a <code>Link</code> node.</p></li> <li><p>Pop the first set of operands from output into the <code>Link</code> until a separator appears.</p></li> <li><p>Erase the separator discovered.</p></li> <li><p>Pop the second set of operands into the <code>Link</code> until a separator.</p></li> <li><p>Push the <code>Link</code> to the output.</p></li> </ol></li> </ol> <p>If I run this through without obeying steps 2.3&ndash;2.7, I get a list of values and separators. For the expression quoted above, <code>a -&gt; b (c -&gt; (d) (e))</code>, the output should be:</p> <pre><code>A sep_1 B sep_2 C sep_3 D E </code></pre> <p>Applying the <code>To</code> rule would then yield:</p> <pre><code>A sep_1 B sep_2 (link from C to {D, E}) </code></pre> <p>And subsequently:</p> <pre><code>(link from A to {B, (link from C to {D, E})}) </code></pre> <p>The important thing to note is that <code>sep_2</code>, crucial to delimit the left-hand operands of the second <code>-&gt;</code>, does not appear, so the parser believes that the expression was actually written:</p> <pre><code>a -&gt; (b c -&gt; (d) (e)) </code></pre> <p>In order to solve this with my current strategy, I would need a way to produce a separator between adjacent expressions, but only if the current expression is a <code>From</code> or <code>To</code> expression enclosed in parentheses. If that's possible, then I'm just not seeing it and the answer ought to be simple. If there's a better way to go about this, however, then please let me know!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJon Purdy
    1. USJon Purdy
    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. POProducing Expressions from This Grammar with Recursive Descent
      1. USollydbg23
      1. VTFavorite
    1. This table or related slice is empty.
 

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