StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Ok, I got it. But unfortunately I cannot publish all my code here as-is. I will try to outline solution anyway, and please ask questions if something is not clear.</p> <p>JFlex uses its own <code>Symbol</code> class. Look here: JFlex.jar/java_cup.runtime/Symbol.class</p> <p>You will see a couple of constructors added:</p> <pre class="lang-java prettyprint-override"><code>public Symbol(int id, Symbol left, Symbol right, Object o){ this(id,left.left,right.right,o); } public Symbol(int id, Symbol left, Symbol right){ this(id,left.left,right.right); } </code></pre> <p>The key here is <code>Object o</code>, which is the value of Symbol.</p> <p>Define your own class to represent an AST tree node, and another one to represent lexer token. Granted, you can use the same class, but I found it more clear to use different classes to distinguish between the two. Both JFlex and CUP will generate java code, and it is easy to get your tokens and nodes mixed-up.</p> <p>Then, in your parser.flex, in the lexical rules sections, you want to do something like this for each token:</p> <pre><code>{float_lit} { return symbol(sym.NUMBER, createToken(yytext(), yycolumn)); } </code></pre> <p>Do this for all your tokens. Your createToken could be something like this:</p> <pre><code>%{ private LexerToken createToken(String val, int start) { LexerToken tk = new LexerToken(val, start); addToken(tk); return tk; } }% </code></pre> <p>Now let's move on to parser.cup. Declare all your terminals to be of type <code>LexerToken</code>, and all your non-terminals to be of type <code>Node</code>. You want to read CUP manual, but for quick refresher, a terminal would be anything recognized by the lexer (e.g. numbers, variables, operators), and non-terminal would be parts of your grammar (e.g. expression, factor, term...).</p> <p>Finally, this all comes together in the grammar definition. Consider the following example:</p> <pre><code> factor ::= factor:f TIMES:times term:t {: RESULT = new Node(times.val, f, t, times.start); :} | factor:f DIVIDE:div term:t {: RESULT = new Node(div.val, f, t, div.start); :} | term:t {: RESULT = t; :} ; </code></pre> <p>Syntax <code>factor:f</code> means you alias the factor's value to be <code>f</code>, and you can refer to it in the following section <code>{: ... :}</code>. Remember, our terminals have values of type <code>LexerToken</code>, and our non-terminals have values that are <code>Node</code>s.</p> <p>Your term in expression may have the following definition:</p> <pre><code> term ::= LPAREN expr:e RPAREN {: RESULT = new Node(e.val, e.start); :} | NUMBER:n {: RESULT = new Node(n.val, n.start); :} ; </code></pre> <p>When you successfully generate the parser code, you will see in your parser.java the part where the parent-child relationship between nodes is established:</p> <pre class="lang-java prettyprint-override"><code> case 16: // term ::= UFUN LPAREN expr RPAREN { Node RESULT =null; int ufleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).left; int ufright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)).right; LexerToken uf = (LexerToken)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-3)).value; int eleft = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).left; int eright = ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-1)).right; Node e = (Node)((java_cup.runtime.Symbol) CUP$parser$stack.elementAt(CUP$parser$top-1)).value; RESULT = new Node(uf.val, e, null, uf.start); CUP$parser$result = parser.getSymbolFactory().newSymbol("term",0, ((java_cup.runtime.Symbol)CUP$parser$stack.elementAt(CUP$parser$top-3)), ((java_cup.runtime.Symbol)CUP$parser$stack.peek()), RESULT); } return CUP$parser$result; </code></pre> <p>I am sorry that I cannot publish complete code example, but hopefully this will save someone a few hours of trial and error. Not having complete code is also good because it won't render all those CS homework assignments useless.</p> <p>As a proof of life, here's a pretty-print of my sample AST.</p> <p>Input expression:</p> <pre><code>T21 + 1A / log(max(F1004036, min(a1, a2))) * MIN(1B, 434) -LOG(xyz) - -3.5+10 -.1 + .3 * (1) </code></pre> <p>Resulting AST:</p> <pre><code>|--[+] |--[-] | |--[+] | | |--[-] | | | |--[-] | | | | |--[+] | | | | | |--[T21] | | | | | |--[*] | | | | | |--[/] | | | | | | |--[1A] | | | | | | |--[LOG] | | | | | | |--[MAX] | | | | | | |--[F1004036] | | | | | | |--[MIN] | | | | | | |--[A1] | | | | | | |--[A2] | | | | | |--[MIN] | | | | | |--[1B] | | | | | |--[434] | | | | |--[LOG] | | | | |--[XYZ] | | | |--[-] | | | |--[3.5] | | |--[10] | |--[.1] |--[*] |--[.3] |--[1] </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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