{"id":921,"date":"2013-07-22T11:03:04","date_gmt":"2013-07-22T05:33:04","guid":{"rendered":"http:\/\/ramkulkarni.com\/blog\/?p=921"},"modified":"2013-07-22T11:03:04","modified_gmt":"2013-07-22T05:33:04","slug":"capturing-absolute-offsets-for-javaccjjtree-tokens","status":"publish","type":"post","link":"http:\/\/ramkulkarni.com\/blog\/capturing-absolute-offsets-for-javaccjjtree-tokens\/","title":{"rendered":"Capturing absolute offsets for JavaCC\/JJTree tokens"},"content":{"rendered":"

I use JavaCC<\/a> for generating parsers in Java. And use JJTree<\/a> to create AST after parsing. JJTree creates nodes of the AST and you can configure JavaCC options to capture tokens in the node – i.e. if you want each node to contain start and end tokens. The default code generated by JavaCC creates Token class with offsets that are relative to the starting offset of the line. It has fields like beginLine, beginColumn, endLine and endColumn. Here the line numbers are absolute line numbers (starting from 1) and column fields contain offsets (again starting from 1) within the corresponding\u00a0lines.
\nHowever many times you want to capture absolute offsets of tokens in the input stream, and not just relative offset in the line. I wish there was a JavaCC option<\/a> to enable this. But it is not too complex if you want to do it yourself.<\/p>\n

To explain how to do this, I will take a grammer file that is generated by the JavaCC wizard of JavaCC Eclipse plugin<\/a>. This is the default grammer file it generates –<\/p>\n

\/**<\/span>\n*<\/span> JJTree file<\/span>\n*\/<\/span>\n\noptions<\/span>{<\/span>\n\u00a0\u00a0JDK_VERSION <\/span>=<\/span>\"1.5\"<\/span>;<\/span>\n}<\/span>\n\nPARSER_BEGIN<\/span>(<\/span>eg2<\/span>)<\/span>\npackage<\/span> test<\/span>;<\/span>\n\npublic<\/span>class<\/span> eg2 <\/span>{<\/span>\n\u00a0\u00a0<\/span>public<\/span>static<\/span>void<\/span> main<\/span>(<\/span>String<\/span> args<\/span>[<\/span>]<\/span>)<\/span>{<\/span>\n\u00a0\u00a0\u00a0\u00a0<\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Reading from standard input...\"<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0<\/span>System<\/span>.<\/span>out<\/span>.<\/span>print<\/span>(<\/span>\"Enter an expression like <\/span>\\\"<\/span>1+(2+3)*var;<\/span>\\\"<\/span> :\"<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0eg2 parser <\/span>=<\/span>new<\/span> eg2<\/span>(<\/span>System<\/span>.<\/span>in<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0<\/span>try<\/span>{<\/span>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0SimpleNode startNode <\/span>=<\/span> parser<\/span>.<\/span>Start<\/span>(<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0startNode<\/span>.<\/span>dump<\/span>(<\/span>\"\"<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Thank you.\"<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0<\/span>}<\/span>catch<\/span>(<\/span>Exception<\/span> e<\/span>)<\/span>{<\/span>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>\"Oops.\"<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>e<\/span>.<\/span>getMessage<\/span>(<\/span>)<\/span>)<\/span>;<\/span>\n\u00a0\u00a0\u00a0\u00a0<\/span>}<\/span>\n\u00a0\u00a0<\/span>}<\/span>\n}<\/span>\nPARSER_END<\/span>(<\/span>eg2<\/span>)<\/span>\n\nSKIP <\/span>:\n{\n  \" \"<\/span>\n| \"<\/span>\\t<\/span>\"<\/span>\n| \"<\/span>\\n<\/span>\"<\/span>\n| \"<\/span>\\r<\/span>\"<\/span>\n| <\"\/\/\"<\/span> (~[\"<\/span>\\n<\/span>\"<\/span>,\"<\/span>\\r<\/span>\"<\/span>])* (\"<\/span>\\n<\/span>\"<\/span>|\"<\/span>\\r<\/span>\"<\/span>|\"<\/span>\\r<\/span>\\n<\/span>\"<\/span>)>\n| <\"\/*\"<\/span> (~[\"*\"<\/span>])* \"*\"<\/span> (~[\"\/\"<\/span>] (~[\"*\"<\/span>])* \"*\"<\/span>)* \"\/\"<\/span>>\n}\nTOKEN <\/span>: \/* LITERALS *\/<\/span>\n{\n  < INTEGER_LITERAL:\n        <DECIMAL_LITERAL> ([\"l\"<\/span>,\"L\"<\/span>])?\n      | <HEX_LITERAL> ([\"l\"<\/span>,\"L\"<\/span>])?\n      | <OCTAL_LITERAL> ([\"l\"<\/span>,\"L\"<\/span>])?\n  >\n|  < #DECIMAL_LITERAL: [\"1\"<\/span>-\"9\"<\/span>] ([\"0\"<\/span>-\"9\"<\/span>])* >\n|  < #HEX_LITERAL: \"0\"<\/span> [\"x\"<\/span>,\"X\"<\/span>] ([\"0\"<\/span>-\"9\"<\/span>,\"a\"<\/span>-\"f\"<\/span>,\"A\"<\/span>-\"F\"<\/span>])+ >\n|  < #OCTAL_LITERAL: \"0\"<\/span> ([\"0\"<\/span>-\"7\"<\/span>])* >\n}\nTOKEN <\/span>: \/* IDENTIFIERS *\/<\/span>\n{\n  < IDENTIFIER: <LETTER> (<LETTER>|<DIGIT>)* >\n|  < #LETTER: [\"_\"<\/span>,\"a\"<\/span>-\"z\"<\/span>,\"A\"<\/span>-\"Z\"<\/span>] >\n|  < #DIGIT: [\"0\"<\/span>-\"9\"<\/span>] >\n}\n\nSimpleNode Start():{}\n{\n  Expression() \";\"<\/span>\n  { return<\/span> jjtThis; }\n}\nvoid<\/span> Expression():{ }\n{\n  AdditiveExpression()\n}\nvoid<\/span> AdditiveExpression():{}\n{\n  MultiplicativeExpression() ( ( \"+\"<\/span> | \"-\"<\/span> ) MultiplicativeExpression() )*\n}\nvoid<\/span> MultiplicativeExpression():{}\n{\n  UnaryExpression() ( ( \"*\"<\/span> | \"\/\"<\/span> | \"%\"<\/span> ) UnaryExpression() )*\n}\nvoid<\/span> UnaryExpression():{}\n{\n  \"(\"<\/span> Expression() \")\"<\/span> | Identifier() | Integer<\/span>()\n}\nvoid<\/span> Identifier():{}\n{\n  <IDENTIFIER>\n}\nvoid<\/span> Integer<\/span>():{}\n{\n  <INTEGER_LITERAL>\n}<\/pre>\n
I have slightly modified the main function so as not to use eg2 class as a static class. Above is a grammer for parsing simple arithmetic expressions like 1 + 2 * ( 3 +4) etc. Now consider the following input (with new lines) –
\n1 +
\n2 * (3+4);
\nFor ‘1’, JavaCC generates token with beginLine=1 and beginColumn=1. For ‘2’ it generates Token with beginLine=2 and beginColumn=1. However you might want to know the absolute position of ‘2’ in the input stream. BTW, the AST nodes generated by the above grammer will not contain start and end tokens. You will need to set JavaCC option ‘TRACK_TOKENS’ to true.<\/p>\n
To capture absolute offsets, we need to modify SimpleCharStream class to keep track of total chars read and create an additional field in the Token class to store absolute offsets. However we need to to go through some intermediate steps to do this.<\/p>\n
Setting additional JavaCC options:<\/h2>\n
Set following options in the grammer file –<\/p>\n
options<\/span>{<\/span>\n\u00a0\u00a0JDK_VERSION <\/span>=<\/span>\"1.5\"<\/span>;<\/span>\n\u00a0\u00a0TRACK_TOKENS <\/span>=<\/span>true<\/span>;<\/span>\n\u00a0\u00a0TOKEN_EXTENDS <\/span>=<\/span>\"BaseToken\"<\/span>; \/\/specify package if not in the same as the parser <\/span>\n\u00a0\u00a0<\/span>COMMON_TOKEN_ACTION<\/span>=<\/span>true<\/span>;<\/span>\n}<\/span><\/pre>\n
We will not modify Token class to add a field for the absolute offset, but we will specify the parent class for Token. This is done using option TOKEN_EXTENDS.
\nWe want a hook in the token manager to set absolute offset after a new Token is created. So we set COMMON_TOKEN_ACTION. When this is set to true, TokenManager calls\u00a0CommonTokenAction after creating a new Token. This method must be declared in the\u00a0TOKEN_MGR_DECLS<\/a> section.<\/p>\n
Create Base Class for Token<\/h2>\n
public<\/span> class<\/span> BaseToken {\n\tpublic<\/span> int<\/span> absoluteBeginColumn = 0;\n\tpublic<\/span> int<\/span> absoluteEndColumn = 0;\n}<\/pre>\n
Modify\u00a0SimpleCharStream<\/h2>\n
This class reads input from the input stream (such as file), buffers it and keeps track of current token offset. You can specify initial buffer size for this class. SimpleCharStream reads from the input stream and stores data in a char buffer (of the size you specified or default). When all the chars in the buffer are read (by the TokenManager) and more data is available to read, then it expands the buffer.<\/p>\n
We will add two fields to this class –<\/p>\n
protected<\/span> int totalCharsRead = 0;\nprotected<\/span> int absoluteTokenBengin = 0;<\/pre>\n
As the name suggests, totalCharsRead keeps count of total chars read from the input stream. And absoluteTokenBegin points to absolute offset of beginning of a new Token. We will add an accessor function for\u00a0absoluteTokenBegin –<\/p>\n
public<\/span> final<\/span> int getAbsoluteTokenBengin() {\n    return<\/span> absoluteTokenBengin;\n}<\/pre>\n
We will increment totalChars read whenever a character is read from the buffer and we will decrement it when character is but back in the buffer (in backup function). The read \u00a0and backup functions look as below after modifications –<\/p>\n
\/** Read a character. *\/<\/span>\n  public<\/span> char readChar() throws<\/span> java.io.IOException\n  {\n    if<\/span> (inBuf > 0)\n    {\n      --inBuf;\n\n      if<\/span> (++bufpos == bufsize)\n        bufpos = 0;\n\n      totalCharsRead++;<\/strong>\n      return<\/span> buffer[bufpos];\n    }\n\n    if<\/span> (++bufpos >= maxNextCharInd)\n      FillBuff();\n\n    totalCharsRead++;<\/strong>\n    char<\/span> c = buffer[bufpos];\n\n    UpdateLineColumn(c);\n    return<\/span> c;\n  }\n\n\/** Backup a number of characters. *\/<\/span>\n  public<\/span> void backup(int amount) {\n\n    inBuf += amount;\n    totalCharsRead -= amount;<\/strong>\n    if<\/span> ((bufpos -= amount) < 0)\n      bufpos += bufsize;\n  }<\/pre>\n
Modifications are highlighted in bold. Next, we will modify BeginToken function to set\u00a0absoluteTokenBengin –<\/p>\n
\/** Start. *\/<\/span>\n  public<\/span> char BeginToken() throws<\/span> java.io.IOException\n  {\n    tokenBegin = -1;\n    char<\/span> c = readChar();\n    tokenBegin = bufpos;\n    absoluteTokenBengin = totalCharsRead;<\/strong>\n\n    return<\/span> c;\n  }<\/pre>\n
Modify TokenManager<\/h2>\n
Finally we will add method\u00a0CommonTokenAction to the token manager. As mentioned above, we need to add this function to TOKEN_MGR_DECLS section of the grammer file –<\/p>\n
TOKEN_MGR_DECLS <\/span>:\n{\n\tpublic<\/span> void<\/span> CommonTokenAction(Token t)\n\t{\n\t\tt.absoluteBeginColumn = getCurrentTokenAbsolutePosition();\n\t\tt.absoluteEndColumn = t.absoluteBeginColumn + t.image.length();\n\t}\n\n\tpublic<\/span> int<\/span> getCurrentTokenAbsolutePosition()\n\t{\n\t\tif<\/span> (input_stream instanceof<\/span> SimpleCharStream)\n\t\t\treturn<\/span> ((SimpleCharStream)input_stream).getAbsoluteTokenBengin();\n\t\treturn<\/span> -1;\n\t}\n}<\/pre>\n
This is not related to the problem we are trying to solve, but if you have to write a large block of Java code in TOKEN_MGR_DECLS, which could be delegated to parser class, then you might want to use TOKEN_MANAGER_USES_PARSER option. If set to true, JavaCC creates TokenManager class with a field, parser, that holds reference to the main parser class. Then from within\u00a0TOKEN_MGR_DECLS, you can call methods on the parser object.<\/p>\n
You can easily test if the absolute offsets are set in the Token by debugging the code. Or you can also modify dump method of SimpleNode to print additional token information –<\/p>\n
\/* Override this method if you want to customize how the node dumps<\/span>\n\u00a0\u00a0\u00a0\u00a0\u00a0out its children. *\/<\/span>\n\n  public<\/span> void dump(String prefix) {\n    System<\/span>.out.println(toString(prefix));\n    printTokenInfo(prefix);\n    if<\/span> (children != null<\/span>) {\n      for<\/span> (int<\/span> i = 0; i < children.length; ++i) {\n        SimpleNode n = (SimpleNode)children[i];\n        if<\/span> (n != null<\/span>) {\n          n.dump(prefix + \" \"<\/span>);\n        }\n      }\n    }\n  }\n}\n\n\/\/New method added to print token information<\/span>\n  public<\/span> void printTokenInfo(String prefix)\n  {\n\t  prefix += \"<\/span>\\t<\/span>\"<\/span>;\n\t  System<\/span>.out.println(prefix + \"StartCol = \"<\/span> + firstToken.beginColumn +\n\t\t\t  \" AbsStartCol = \"<\/span> + firstToken.absoluteBeginColumn + \" - \"<\/span> +\n\t\t\t  firstToken.image);\n\t  System<\/span>.out.println(prefix + \"EndCol = \"<\/span> + lastToken.beginColumn +\n\t\t\t  \" AbsEndCol = \"<\/span> + lastToken.absoluteBeginColumn + \" - \"<\/span> +\n\t\t\t  lastToken.image);\n  }<\/pre>\n
Now, for the input –
\n1 +
\n2 * (3+4);
\nfollowing output will be printed –<\/p>\n
Start\n\tStartCol = 1 AbsStartCol = 1 Image - 1\n\tEndCol = 10 AbsEndCol = 14 Image - ;\n Expression\n \tStartCol = 1 AbsStartCol = 1 Image - 1\n \tEndCol = 9 AbsEndCol = 13 Image - )\n  AdditiveExpression\n  \tStartCol = 1 AbsStartCol = 1 Image - 1\n  \tEndCol = 9 AbsEndCol = 13 Image - )\n   MultiplicativeExpression\n   \tStartCol = 1 AbsStartCol = 1 Image - 1\n   \tEndCol = 1 AbsEndCol = 1 Image - 1\n    UnaryExpression\n    \tStartCol = 1 AbsStartCol = 1 Image - 1\n    \tEndCol = 1 AbsEndCol = 1 Image - 1\n     Integer\n     \tStartCol = 1 AbsStartCol = 1 Image - 1\n     \tEndCol = 1 AbsEndCol = 1 Image - 1\n   MultiplicativeExpression\n   \tStartCol = 1 AbsStartCol = 5 Image - 2\n   \tEndCol = 9 AbsEndCol = 13 Image - )\n    UnaryExpression\n    \tStartCol = 1 AbsStartCol = 5 Image - 2\n    \tEndCol = 1 AbsEndCol = 5 Image - 2\n     Integer\n     \tStartCol = 1 AbsStartCol = 5 Image - 2\n     \tEndCol = 1 AbsEndCol = 5 Image - 2\n    UnaryExpression\n    \tStartCol = 5 AbsStartCol = 9 Image - (\n    \tEndCol = 9 AbsEndCol = 13 Image - )\n     Expression\n     \tStartCol = 6 AbsStartCol = 10 Image - 3\n     \tEndCol = 8 AbsEndCol = 12 Image - 4\n      AdditiveExpression\n      \tStartCol = 6 AbsStartCol = 10 Image - 3\n      \tEndCol = 8 AbsEndCol = 12 Image - 4\n       MultiplicativeExpression\n       \tStartCol = 6 AbsStartCol = 10 Image - 3\n       \tEndCol = 6 AbsEndCol = 10 Image - 3\n        UnaryExpression\n        \tStartCol = 6 AbsStartCol = 10 Image - 3\n        \tEndCol = 6 AbsEndCol = 10 Image - 3\n         Integer\n         \tStartCol = 6 AbsStartCol = 10 Image - 3\n         \tEndCol = 6 AbsEndCol = 10 Image - 3\n       MultiplicativeExpression\n       \tStartCol = 8 AbsStartCol = 12 Image - 4\n       \tEndCol = 8 AbsEndCol = 12 Image - 4\n        UnaryExpression\n        \tStartCol = 8 AbsStartCol = 12 Image - 4\n        \tEndCol = 8 AbsEndCol = 12 Image - 4\n         Integer\n         \tStartCol = 8 AbsStartCol = 12 Image - 4\n         \tEndCol = 8 AbsEndCol = 12 Image - 4\nThank you.<\/pre>\n
– Ram Kulkarni<\/p>\n","protected":false},"excerpt":{"rendered":"
I use JavaCC for generating parsers in Java. And use JJTree to create AST after parsing. JJTree creates nodes of the AST and you can configure JavaCC options to capture tokens in the node – i.e. if you want each node to contain start and end tokens. The default code generated by JavaCC creates Token … <\/p>\n
Continue reading “Capturing absolute offsets for JavaCC\/JJTree tokens”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"Capturing absolute offsets for JavaCC\/JJTree tokens http:\/\/wp.me\/p2g9O8-eR","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[76,1],"tags":[77,39,74],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p2g9O8-eR","jetpack-related-posts":[],"_links":{"self":[{"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/posts\/921"}],"collection":[{"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/comments?post=921"}],"version-history":[{"count":0,"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/posts\/921\/revisions"}],"wp:attachment":[{"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/media?parent=921"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/categories?post=921"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ramkulkarni.com\/blog\/wp-json\/wp\/v2\/tags?post=921"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}