What is the equivalent for epsilon in ANTLR BNF grammar notation?

Question

During taking advantage of ANTLR 3.3, I'm changing the current grammar to support inputs without parenthesis too. Here's the first version of my grammar :

grammar PropLogic;

        NOT : '!' ;
        OR  : '+' ;
        AND : '.' ;
        IMPLIES : '->' ;
        SYMBOLS : ('a'..'z') | '~' ;
        OP : '(' ;
        CP : ')' ;

    prog    : formula EOF ;


    formula : NOT formula
        | OP formula( AND formula CP | OR formula CP | IMPLIES formula CP)
        | SYMBOLS ;


    WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+    { $channel = HIDDEN; } ;

Then I changed it this way to support the appropriate features :

grammar PropLogic;

    NOT : '!' ;
    OR  : '+' ;
    AND : '.' ;
    IMPLIES : '->' ;
    SYMBOL : ('a'..'z') | '~' ;
    OP : '(' ;
    CP : ')' ;
    EM : '' ;

prog    : formula EOF ;


formula : OP formula( AND formula CP | OR formula CP | IMPLIES formula CP)
    | ( NOT formula | SYMBOL )( AND formula | OR formula | IMPLIES formula | EM ) ;


WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+    { $channel = HIDDEN; } ;

But I've been faced with following error :

error<100>:  syntax error: invalid char literal: ''
error<100>:  syntax error: invalid char literal: ''

Does anybody know that how can I overcome this error?

Devoirs

Answer 1

Your EM token:

EM : '' ;

is invalid: you can't match an empty string in lexer rules.

To match epsilon (nothing), you should do:

rule 
  :  A 
  |  B 
  |  /* epsilon */ 
  ;

Of course, the comment /* epsilon */ can safely be removed.

Note that when you do it like that in your current grammar, ANTLR will complain that there can be rules matched using multiple alternatives. This is because your grammar is ambiguous.

Gyniatrics

Well I changed the grammar and based on your anticipation, it does not work. I'm just trying tp validate the input to check that if it's a propositional logic statement or not. – Devoirs

@Amirh, I said that simply applying what I just answered would result in ANTLR producing an error. I just answered your question why you got the error: error<100>: syntax error: invalid char literal: ''. Good luck. – Gyniatrics

Thanks for bringing your answer back. Well How can I make it work? it's just a propositional logic grammar. btw based on Ira's grammar, can I access to elements of the pars tree? I just want to convert some strings to another equivalent form? and after that find '->' which is on the root and do it recursively with other sub-trees. Is this possible through Ira's grammar? – Devoirs

@Amirh, these comment boxes are not well suited for questions (I need more info from you than you provide in these small comment-areas). I consider this question of yours answered. If you have another one, feel free to create a new question. Good luck. – Gyniatrics

Answer 2

I'm not an ANTLR expert, but you might try:

formula : term ((AND | OR | IMPLIES ) term )*;
term :  OP formula CP | NOT term | SYMBOL ;

If you want traditional precedence of operators this won't do the trick, but that's another issue.

EDIT: OP raised the ante; he wants precedence too. I'll meet him halfway, since it wasn't part of the orginal question. I've added precedence to the grammar that makes IMPLIES the lower precedence than other operators, and leave it to OP to figure out how to do the rest.

 formula:  disjunction ( IMPLIES disjunction )* ;
 disjunction:  term (( AND | OR ) term )* ;
 term:  OP formula CP | NOT term | SYMBOL ;

OP additionally asked, "how to convert (!p or q ) into p -> q". I think he should have asked this as a separate question. However, I'm already here. What he needs to do is walk the tree, looking for the pattern he doesn't like, and change the tree into one he does, and then prettyprint the answer. It is possible to do all this with ANTLR, which is part of the reason it is popular.

As a practical matter, procedurally walking the tree and checking the node types, and splicing out old nodes and splicing in new is doable, but a royal PitA. Especially if you want to do this for lots of transformations.

A more effective way to do this is to use a program transformation system, which allows surface syntax patterns to be expressed for matching and replacement. Program transformation systems of course include parsing machinery and more powerful ones let you (and indeed insist) that you define a grammar up front much as you for ANTLR.

Our DMS Software Reengineering Toolkit is such a program transformation tool, and with a suitably defined grammar for propositions, the following DMS transformation rule would carry out OP's additional request:

domain proplogic; // tell DMS to use OP's definition of logic as a grammar

rule normalize_implies_from_or( p: term, q: term): formula -> formula
  " NOT \p OR \q " -> " \p IMPLIES \q ";

The " ... " is "domain notation", e.g, surface syntax from the proplogic domain, the "\" are meta-escapes, so "\p" and "\q" represent any arbitrary term from the proplogic grammar. Notice the rule has to reach "across" precedence levels when being applied, as "NOT \p OR \q" isn't a formula and "\p IMPLIES \q" is; DMS takes care of all this (the "formula -> formula" notation is how DMS knows what to do). This rule does a tree-to-tree rewrite. The resulting tree can be prettyprinted by DMS.

You can see a complete example of something very similar, e.g., a grammar for conventional algebra and rewrite rule to simplify algebraic equations.

Carlisle

@Amirh, as Ira already mentioned, if you want operator precedence, you need to change your parser rules. With Ira's suggestion your source is simply evaluated from left to right. – Gyniatrics

@Bart Kiers, Yeah, thanks for your note. Actually I haven't finished yet. I'm going to ask more questions. As you know it's just the second one. – Devoirs

Just wanted to make sure you understood it was not a matter of "hopefully" not getting difficulties with operator precedence. If you want to have one of AND, OR or IMPLIES have a lower (or higher) precedence than the others, you need to change the rules of your parser grammar. Anyway, best of luck! – Gyniatrics

@Bart Kiers, The more I think I see that I'm going to face some serious issues without operator precedence. for example when I want to change an OR expression to a -> form, then how can I be sure I choosed the right one. I'm going take back that green mark. It seems I should not rush into it. I also rushed into it yesterday :( but I don't take back my support vote. – Devoirs

for example I want to convert (!p OR q) to (p -> q), so does Ira's grammar help me to find the correct (!p OR q) or it can just give me a wrong one like (r -> !p OR q) which is ((r -> !p) OR q) ??? – Devoirs

@Amirh: You specifically asked how the error with the '' could be overcome. Both Bart and I provided specific answers that resolved that issue. From that point of view, you should award the checkmark to one of us. That fact that neither of us coded a complete, working grammar that handles all the additional issues you might have faced (I suggested you might need precedence because is traditional, Bart said your description was inadequate) is not a reasonable requirement to answer the question you originally posed. – Carlisle

@Ira Baxter Thank you so much. you're right both of you solved the problem mentioned in the question. – Devoirs