Что является эквивалентом для Эпсилон в нотации ANTLR грамматики БНФ?

Во время использования преимуществ 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: ''

Знает ли кто-нибудь, что я могу преодолеть эту ошибку?

2 4
validation antlr3

2 ответа:

Ваш EM токен: 

EM : '' ;

Недопустимо: вы не можете сопоставить пустую строку в правилах лексера.

Чтобы соответствовать эпсилону (ничего), вы должны сделать: 

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

Конечно, комментарий /* epsilon */ можно смело удалять.

Обратите внимание, что когда вы делаете это подобным образом в вашей текущей грамматике, ANTLR будет жаловаться, что могут быть правила, соответствующие нескольким альтернативам. Это потому, что ваша грамматика неоднозначна.

6

Я не эксперт по ANTLR, но вы можете попробовать:

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

Если вы хотите традиционный приоритет операторов, это не поможет, но это уже другая проблема.

Правка: ОП поднял ставку; он тоже хочет получить приоритет. Я встречусь с ним на полпути, так как это не было частью об изначальном вопросе. Я добавил приоритет к грамматике, которая делает подразумеваемые более низкий приоритет, чем у других операторов,и предоставьте ОП выяснить, как сделать все остальное.

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

ОП дополнительно спросил: "как чтобы преобразовать (!p или q) в p - > q". Я думаю, что он должен это сделать. задали это как отдельный вопрос. Однако я уже здесь. То, что ему нужно сделать, это ходить по дереву, ища узор, которого он не видит. мол, и дерево поменяй на то, что он делает, а потом допечатай ответ. Все это можно сделать с помощью ANTLR, которая является частью причины это популярно.

Как практический вопрос, процедурно прогуливаясь по дереву и проверяя узел типы, и сращивание старых узлов и сращивание новых выполнимо, но Пита королевская. Особенно если вы хотите сделать это для многих преобразований.

Более эффективный способ сделать это-использовать система преобразования программ , которая позволяет выражать поверхностные синтаксические шаблоны для сопоставления и замены. Системы преобразования программ, конечно, включают в себя механизмы синтаксического анализа, а более мощные позволяют вам (и действительно настаивают), что вы определяете грамматика впереди, как и вы для ANTLR.

Наш реинжиниринг программного обеспечения DMS 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 ";

The " ... "является" доменной нотацией", например, поверхностным синтаксисом из проплогической области, " \ " - это мета-эскейпы, так "\P" и "\Q" и представляют собой произвольные срок от proplogic грамматики. Обратите внимание, что правило должно достигать" поперечных " уровней приоритета при применении, поскольку "не \p или \q" не является формула и "\p подразумевает \q " есть; DMS заботится обо всем этом (нотация "формула -> формула" - это то, как DMS знает, что делать). Это правило выполняет переписывание от дерева к дереву. Полученное дерево может быть prettyprinted с помощью DMS.

Вы можете увидеть полный пример чего-то очень похожего, например, грамматику для обычной алгебры и правило переписывания для упрощения алгебраических уравнений.
2