JavaCC Problem - Generated code doesn't find all parse errors

Question

Just started with JavaCC. But I have a strange behaviour with it. I want to verify input int the form of tokens (letters and numbers) wich are concatenated with signs (+, -, /) and wich can contain parenthesis. I hope that was understandable :)

In the main method is a string, which should produce an error, because it has one opening but two closing parenthesis, but I do not get a parse exception --> Why?

Does anybody have a clue why I don't get the exception?

I was struggling with left recursion and choice conflicts with my initial try, but managed to get over them. Maybe there I introduced the problem?!

Oh - and maybe my solution is not very good - ignore this fact... or better, give some advice ;-)

File: CodeParser.jj

 options {
   STATIC=false;
 }

 PARSER_BEGIN(CodeParser)

 package com.testing;

 import java.io.StringReader;
 import java.io.Reader;

 public class CodeParser {

     public CodeParser(String s) 
     {
         this((Reader)(new StringReader(s))); 

     }

     public static void main(String args[])
     {
         try
         {
               /** String has one open, but two closing parenthesis --> should produce parse error */
               String s = "A+BC+-(2XXL+A/-B))";
               CodeParser parser = new CodeParser(s);
               parser.expression();
         }
         catch(Exception e)
         {
               e.printStackTrace();
         }
     }
 }
 PARSER_END(CodeParser)

 TOKEN:
 {
  <code : ("-")?(["A"-"Z", "0"-"9"])+ >
  | <op : ("+"|"/") >
  | <not : ("-") >
  | <lparenthesis : ("(") >
  | <rparenthesis : (")") >
 }

 void expression() :
 {
 }
 {
  negated_expression() | parenthesis_expression() | LOOKAHEAD(2) operator_expression() | <code>
 }

 void negated_expression() :
 {
 }
 {
       <not>parenthesis_expression()
 }

 void parenthesis_expression() :
 {
 }
 {
        <lparenthesis>expression()<rparenthesis>
 }

 void operator_expression() :
 {
 }
 {
       <code><op>expression()
 }

Edit - 11/16/2009

Now I gave ANTLR a try.

I changed some terms to better match my problem domain. I came up with the following code (using the answers on this site), which seems to do the work now:

grammar Code;

CODE    :   ('A'..'Z'|'0'..'9')+;
OP  :   '+'|'/';

start   :   terms EOF;
terms   :   term (OP term)*;
term    :   '-'? CODE
    |   '-'? '(' terms ')';

And by the way... ANTLRWORKS is a great tool for debugging/visualizing! Helped me a lot.

Additional info
Above code matches stuff like:

(-Z19+-Z07+((FV+((M005+(M272/M276))/((M278/M273/M642)+-M005)))/(FW+(M005+(M273/M278/M642)))))+(-Z19+-Z07+((FV+((M005+(M272/M276))/((M278/M273/M642/M651)+-M005)))/(FW+(M0))))

Answer 1

What kgregory says is the right answer. You can see this if you build the grammar with the DEBUG_PARSER option and then run it:

$ javacc -debug_parser -output_directory=com/testing/ CodeParser.jj && javac com/testing/*.java && java -cp . com.testing.CodeParser
Java Compiler Compiler Version 5.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file CodeParser.jj . . .
File "TokenMgrError.java" is being rebuilt.
File "ParseException.java" is being rebuilt.
File "Token.java" is being rebuilt.
File "SimpleCharStream.java" is being rebuilt.
Parser generated successfully.
Call:   expression
  Call:   operator_expression
    Consumed token: <<code>: "A" at line 1 column 1>
    Consumed token: <<op>: "+" at line 1 column 2>
    Call:   expression
      Call:   operator_expression
        Consumed token: <<code>: "BC" at line 1 column 3>
        Consumed token: <<op>: "+" at line 1 column 5>
        Call:   expression
          Call:   negated_expression
            Consumed token: <"-" at line 1 column 6>
            Call:   parenthesis_expression
              Consumed token: <"(" at line 1 column 7>
              Call:   expression
                Call:   operator_expression
                  Consumed token: <<code>: "2XXL" at line 1 column 8>
                  Consumed token: <<op>: "+" at line 1 column 12>
                  Call:   expression
                    Call:   operator_expression
                      Consumed token: <<code>: "A" at line 1 column 13>
                      Consumed token: <<op>: "/" at line 1 column 14>
                      Call:   expression
                        Consumed token: <<code>: "-B" at line 1 column 15>
                      Return: expression
                    Return: operator_expression
                  Return: expression
                Return: operator_expression
              Return: expression
              Consumed token: <")" at line 1 column 17>
            Return: parenthesis_expression
          Return: negated_expression
        Return: expression
      Return: operator_expression
    Return: expression
  Return: operator_expression
Return: expression

See that? The last token consumed is the second to last character - the second to last right parenthesis.

If you want the exception, again, like kgregory said, you could add a new top-level production called "file" or "data" or something and end it with an token. That way any dangling parens like this would cause an error. Here's an grammar that does that:

options {
  STATIC=false;
}

PARSER_BEGIN(CodeParser)
package com.testing;

import java.io.StringReader;
import java.io.Reader;

public class CodeParser {

    public CodeParser(String s) 
    {
        this((Reader)(new StringReader(s))); 

    }

    public static void main(String args[])
    {
        try
        {
              /** String has one open, but two closing parenthesis --> should produce parse error */
              String s = "A+BC+-(2XXL+A/-B))";
              CodeParser parser = new CodeParser(s);
              parser.file();
        }
        catch(Exception e)
        {
              e.printStackTrace();
        }
    }
}
PARSER_END(CodeParser)

TOKEN:
{
        <code : ("-")?(["A"-"Z", "0"-"9"])+ >
        | <op : ("+"|"/") >
        | <not : ("-") >
        | <lparenthesis : ("(") >
        | <rparenthesis : (")") >
}

void file() : {} {
  expression() <EOF>
}
void expression() :
{
}
{
        negated_expression() | parenthesis_expression() | LOOKAHEAD(2) operator_expression() | <code>
}

void negated_expression() :
{
}
{
      <not>parenthesis_expression()
}

void parenthesis_expression() :
{
}
{
       <lparenthesis>expression()<rparenthesis>
}

void operator_expression() :
{
}
{
      <code><op>expression()
}

And a sample run:

$ javacc -debug_parser -output_directory=com/testing/ CodeParser.jj && javac com/testing/*.java && java -cp . com.testing.CodeParser
Java Compiler Compiler Version 5.0 (Parser Generator)
(type "javacc" with no arguments for help)
Reading from file CodeParser.jj . . .
File "TokenMgrError.java" is being rebuilt.
File "ParseException.java" is being rebuilt.
File "Token.java" is being rebuilt.
File "SimpleCharStream.java" is being rebuilt.
Parser generated successfully.
Call:   file
  Call:   expression
    Call:   operator_expression
      Consumed token: <<code>: "A" at line 1 column 1>
      Consumed token: <<op>: "+" at line 1 column 2>
      Call:   expression
        Call:   operator_expression
          Consumed token: <<code>: "BC" at line 1 column 3>
          Consumed token: <<op>: "+" at line 1 column 5>
          Call:   expression
            Call:   negated_expression
              Consumed token: <"-" at line 1 column 6>
              Call:   parenthesis_expression
                Consumed token: <"(" at line 1 column 7>
                Call:   expression
                  Call:   operator_expression
                    Consumed token: <<code>: "2XXL" at line 1 column 8>
                    Consumed token: <<op>: "+" at line 1 column 12>
                    Call:   expression
                      Call:   operator_expression
                        Consumed token: <<code>: "A" at line 1 column 13>
                        Consumed token: <<op>: "/" at line 1 column 14>
                        Call:   expression
                          Consumed token: <<code>: "-B" at line 1 column 15>
                        Return: expression
                      Return: operator_expression
                    Return: expression
                  Return: operator_expression
                Return: expression
                Consumed token: <")" at line 1 column 17>
              Return: parenthesis_expression
            Return: negated_expression
          Return: expression
        Return: operator_expression
      Return: expression
    Return: operator_expression
  Return: expression
Return: file
com.testing.ParseException: Encountered " ")" ") "" at line 1, column 18.
Was expecting:
    <EOF> 

  at com.testing.CodeParser.generateParseException(CodeParser.java:354)
  at com.testing.CodeParser.jj_consume_token(CodeParser.java:238)
  at com.testing.CodeParser.file(CodeParser.java:34)
  at com.testing.CodeParser.main(CodeParser.java:22)

Voila! An exception.

Answer 2

From the Java CC FAQ:

4.7 I added a LOOKAHEAD specification and the warning went away; does that mean I fixed the problem?

No. JavaCC will not report choice conflict warnings if you use a LOOKAHEAD specification. The absence of a warning doesn't mean that you've solved the problem correctly, it just means that you added a LOOKAHEAD specification.

I would start by trying to get rid of the conflict without using a lookahead first.

Answer 3

The problem is that you don't get the error when using the parser, correct? Not that the parser generator is claiming that the grammar is incorrect (which seems to be the discussion in the other answer).

If that's the case, then I suspect that you're seeing the problem because the parser properly matches the expression production, then ignores subsequent input. I haven't used JavaCC for a long time, but iirc it didn't throw an error for not reaching end-of-stream.

Most grammars have an explicit top-level production to match the entire file, looking something like this (I'm sure the syntax is wrong, as I said, it's been a long time):

input : ( expression ) *

Or, there's probably an EOF token that you can use, if you want to process just a single expression.