Выражения в переводчике CoCo в ANTLR

Я разбираю грамматики CoCo / R в утилите для автоматизации перевода CoCo -> ANTLR. Основная грамматика ANTLR:

rule '=' expression '.' ;

expression
     : term ('|' term)*
         -> ^( OR_EXPR term term* )
     ;
term
     : (factor (factor)*)? ;

factor
     : symbol
     | '(' expression ')'
         -> ^( GROUPED_EXPR expression )
     | '[' expression']'
         -> ^( OPTIONAL_EXPR expression)
     | '{' expression '}'
         -> ^( SEQUENCE_EXPR expression)
     ;

symbol
     : IF_ACTION
     | ID (ATTRIBUTES)?
     | STRINGLITERAL
     ;

Моя проблема связана с такими конструкциями:

CS = { ExternAliasDirective }
         { UsingDirective }
         EOF .

CS приводит к AST с узлом OR_EXPR, но без "|" персонаж действительно появляется. Я уверен, что это связано с определением выражения, но я не вижу другого способа написать правила.

Я экспериментировал с этим, чтобы разрешить двусмысленность.

// explicitly test for the presence of an '|' character
expression
@init { bool ored = false; }
     : term {ored = (input.LT(1).Type == OR); } (OR term)*
         ->  {ored}? ^(OR_EXPR term term*)
         ->            ^(LIST term term*)

Это работает, но этот взлом укрепляет мою убежденность в том, что что-то фундаментальное не так.

Любые советы очень ценятся.


antlr parsing abstract-syntax-tree grammar cocor
person J Evans    schedule 02.03.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Ваше правило:

expression
  : term ('|' term)*
      -> ^( OR_EXPR term term* )
  ;

всегда заставляет правило перезаписи создавать дерево с корнем типа OR_EXPR. Вы можете создать «дополнительные правила перезаписи» следующим образом:

expression
  :  (term -> REWRITE_RULE_X) ('|' term -> ^(REWRITE_RULE_Y))*
  ;

А чтобы устранить двусмысленность в грамматике, проще всего включить глобальное отслеживание с возвратом, что можно сделать в разделе options { ... } вашей грамматики.

Быстрая демонстрация:

grammar CocoR;

options {
  output=AST;
  backtrack=true;
}

tokens {
  RULE;
  GROUP;
  SEQUENCE;
  OPTIONAL;
  OR;
  ATOMS;
}

parse
  :  rule EOF -> rule
  ;

rule
  :  ID '=' expr* '.' -> ^(RULE ID expr*)
  ;

expr
  :  (a=atoms -> $a) ('|' b=atoms -> ^(OR $expr $b))*
  ;

atoms
  :  atom+ -> ^(ATOMS atom+)
  ;

atom
  :  ID
  |  '(' expr ')' -> ^(GROUP expr)
  |  '{' expr '}' -> ^(SEQUENCE expr)
  |  '[' expr ']' -> ^(OPTIONAL expr)
  ;

ID
  :  ('a'..'z' | 'A'..'Z') ('a'..'z' | 'A'..'Z' | '0'..'9')*
  ;

Space
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

с вводом:

CS = { ExternAliasDirective }
     { UsingDirective }
     EOF .

производит AST:

введите описание изображения здесь

и ввод:

foo = a | b ({c} | d [e f]) .

производит:

введите описание изображения здесь

Класс для проверки:

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
    public static void main(String[] args) throws Exception {
        /*
        String source = 
                "CS = { ExternAliasDirective } \n" +
                "{ UsingDirective }            \n" + 
                "EOF .                           ";
        */
        String source = "foo = a | b ({c} | d [e f]) .";
        ANTLRStringStream in = new ANTLRStringStream(source);
        CocoRLexer lexer = new CocoRLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        CocoRParser parser = new CocoRParser(tokens);
        CocoRParser.parse_return returnValue = parser.parse();
        CommonTree tree = (CommonTree)returnValue.getTree();
        DOTTreeGenerator gen = new DOTTreeGenerator();
        StringTemplate st = gen.toDOT(tree);
        System.out.println(st);
    }
}

и с выходными данными этого класса я использовал следующий веб-сайт для создания AST-изображений: http://graph.gafol.net/

HTH

РЕДАКТИРОВАТЬ

Чтобы учесть epsilon (пустую строку) в ваших OR выражениях, вы можете попробовать что-нибудь (быстро протестированное!) Вроде этого:

expr
  :  (a=atoms -> $a) ( ( '|' b=atoms -> ^(OR $expr $b)
                       | '|'         -> ^(OR $expr NOTHING)
                       )
                     )*
  ;

который анализирует источник:

foo = a | b | .

в следующий AST:

введите описание изображения здесь

person Bart Kiers    schedule 02.03.2011
comment
Да, именно так, трюк с двойной перезаписью работает неплохо. Теперь, чтобы найти способ сохранить пустые (обнуляемые) параметры ... Визуализация графа аккуратная, к сожалению, я пока не могу убедить версию генератора дерева C # правильно маркировать узлы, сгенерированные graph.gafol.net. - person J Evans; 03.03.2011
comment
Барт, это выходит за рамки служебного долга. еще раз спасибо. - person J Evans; 03.03.2011
comment
@G Forty, рад помочь! - person Bart Kiers; 03.03.2011

arrow_upward
0
arrow_downward

Производство для expression явно говорит, что он может возвращать только узел OR_EXPR. Вы можете попробовать что-то вроде:

expression
     : 
     term
     |
     term ('|' term)+
         -> ^( OR_EXPR term term* )
     ;

Далее вы можете использовать:

term
     : factor*;
person Apalala    schedule 02.03.2011