1 posts in topic
Flat View  Flat View

Posted By:   Sandip_Chitale
Posted On:   Wednesday, April 25, 2001 05:39 PM

How to sequentialize JavaCC TOKENS and SPECIAL_TOKENS ?


Posted By:   Sandip_Chitale  
Posted On:   Wednesday, April 25, 2001 05:42 PM

Here is a small piece of code to sequentialize(if there is
such a word) JavaCC tokens. If you have used the JavaCC parser generator,
you may know that, the JavaCC grammer specification allows what are called
as SPECIAL_TOKEN. These kinds of tokens are ignored by the parser but
are not discarded. Instead they hang off of the next significant
token in a backward chain. That is very good.

Here is how the token stream looks -

|-ST1==ST2==ST3--+ |-ST4--+
| |

For example, by making comments SPECIAL_TOKENs, a source tranforming
tools can pass on the user's comments to the output. That is fine an dandy.
However this token stream is hard to work with.

I have written some piece of code which flattens this and converts it to -


It does two things -

  1. It uses specialToken pointer for backword chaining - effectively
    converting the original single linked list to doubly linked list.

  2. It remembers the fact that a toke was a SPECIAL_TOKEN by inverting the
    sign of Token.kind.

Here is the code -

public class JavaCCUtilities {

public static int getKind(Token t)
// return the absolute value
return Math.abs(t.kind);

public static Token sequentializeATokenAndGetLeadingToken(Token t)
// The following statement determines that there are no special tokens
// and returns control to the caller.
if (t.specialToken == null)
return t;

Token tmp_t = t.specialToken;
// mark as special token.
tmp_t.kind = - tmp_t.kind;

// this chains the regular token t to the end of last specialToken
tmp_t.next = t;

// The following walks back the special token chain until it
// reaches the first special token after the previous regular
// token. It also marks them as special.
while (tmp_t.specialToken != null) {
tmp_t = tmp_t.specialToken;

// mark as special token.
tmp_t.kind = - tmp_t.kind;

return tmp_t;

public static Token sequentializeTokensAndGetLeadingToken(Token t)
// obvious
if (t == null) {
return null;

// get the leading token.
Token firstToken = sequentializeATokenAndGetLeadingToken(t);

// remeber t as last token
Token lastToken = t;

// while there are more regular tokens
while (lastToken.next != null) {

// get the leading token of next token
Token leadingToken =

// backward chain
leadingToken.specialToken = lastToken;

// temporary holder
Token tmpNext = lastToken.next;

// forward chain
lastToken.next = leadingToken;

// next step
lastToken = tmpNext;

return firstToken;

public static void printSequentialTokens(Token firstToken)
while (firstToken != null && firstToken.kind != 0) {
System.out.println(((firstToken.kind < 0) ? "Special :" : "Regular :") +
getKind(firstToken) + ": " + firstToken.image);
firstToken = firstToken.next;

}// JavaCCUtilities
About | Sitemap | Contact