ANTLR BNF 语法符号中 epsilon 的等价物是什么？

Question

在利用 ANTLR 3.3 期间，我正在更改当前语法以支持不带括号的输入。这是我的语法的第一个版本：

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; } ;

然后我以这种方式更改它以支持适当的功能：

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; } ;

但是我遇到了以下错误：

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

有人知道我如何克服这个错误吗？

Answer 1

您的 EM 标记：

EM : '' ;

无效：您无法匹配词法分析器规则中的空字符串。

要匹配 epsilon （什么也没有），你应该这样做：

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

当然，注释 /* epsilon */ 可以安全地删除。

请注意，当您按照当前语法执行此操作时，ANTLR 会抱怨可以使用多个替代项来匹配规则。这是因为你的语法不明确。

Answer 2

我不是 ANTLR 专家，但您可以尝试：

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

如果您想要运算符的传统优先级，这不会成功，但这是另一个问题。

编辑：OP提高了赌注；他也想要优先权。我会在半路上遇见他，因为那不是一部分
原来的问题。我已经为使 IMPLIES 的语法添加了优先级
优先级低于其他运算符，并将其留给 OP 来弄清楚如何完成其​​余的操作。

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

OP还问，“如何将 (!p 或 q ) 转换为 p -> q”。我认为他应该
作为一个单独的问题提出了这个问题。不过，我已经来了。
他需要做的是在树上行走，寻找他没有的模式
喜欢，然后将树更改为他所做的树，然后漂亮地打印答案。
使用 ANTLR 可以完成这一切，这是部分原因
它很受欢迎。

实际上，按程序遍历树并检查节点
类型，并且拼接旧节点并拼接新节点是可行的，但是皇家PitA。
特别是如果您想对大量转换执行此操作。

更有效的方法是使用
程序转换系统，允许表达表面语法模式以进行匹配和替换。程序转换系统当然包括解析机器和更强大的系统，让您（实际上坚持）您定义
前面的语法就像你的 ANTLR 一样。

我们的DMS Software Reengineering Toolkit就是这样一个程序转换工具，并且具有适当定义的命题语法，
以下DMS转换规则将执行OP的附加请求：

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 ";

“...”是“域符号”，例如来自proplogic域的表面语法，“\”是元转义符，
因此“\p”和“\q”代表proplogic语法中的任意项。请注意，应用时规则必须达到“跨”优先级，因为“NOT \p OR \q”不是公式，而“\p IMPLIES \q”是； DMS 负责处理所有这些（“公式 -> 公式”表示法是 DMS 知道要做什么的方式）。该规则进行树到树重写。生成的树可以通过 DMS 进行漂亮打印。

您可以看到非常相似的完整示例，例如 传统代数和重写规则的语法简化代数方程。