Что эквивалентно эпсилону в грамматической нотации ANTLR BNF? - PullRequest
Новая
       3

Что эквивалентно эпсилону в грамматической нотации ANTLR BNF?

4 голосов
/ 02 апреля 2011

Во время использования 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 ]

7 голосов
/ 02 апреля 2011

Ваш EM токен: 

EM : '' ;

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

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

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

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

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

2 голосов
/ 02 апреля 2011

Я не эксперт 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 ;

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

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

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

Наш инструментарий реинжиниринга программного обеспечения DMS - это такой инструмент трансформации программы, с правильно определенной грамматикой для предложений, следующее правило преобразования 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 ";

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

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

...