Прогноз DFA и охват

Начиная с этой грамматики: https://stackoverflow.com/a/14287002/1082002 я бы реализовал простую грамматику, которая принимает и оценивает простой язык следующим образом:

{ 
   if a==c { 
      a
      if a==b { 
         b 
      } else { 
         c 
      }
   }

}

Итак, если a==c, он выполняет a и оценивает if a==b, если это правда, он выполняет b, иначе c. Очень просто.

Грамматика синтаксического анализатора и грамматика дерева таковы:

TreeEvaluator.g (комбинированная грамматика для создания AST)

grammar TreeEvaluator;

options { 
    output = AST;
}

tokens { 
    CONDBLOCK;
    CODEBLOCK;
    DEFAULT;
}


compilationUnit : block EOF -> block;

condition       : cif elif* celse? -> ^(IF cif elif* celse?);
cif             : IF expr block -> ^(CONDBLOCK expr block);
elif            : ELIF expr block -> ^(CONDBLOCK expr block);
celse           : ELSE block -> ^(DEFAULT block); 
expr            : ID EQ^ ID;
block           : LCUR instruction* RCUR -> ^(CODEBLOCK instruction*);
instruction     : ID | condition;

IF  : 'if';
ELIF: 'elif';
ELSE: 'else';
LCUR: '{';
RCUR: '}';
EQ  : '==';
ID  : ('a'..'z'|'A'..'Z')+;
WS  : (' '|'\t'|'\f'|'\r'|'\n')+ {skip();};

AstTreeEvaluatorParser.g (парсер дерева)

tree grammar AstTreeEvaluatorParser;

options { 
    output = AST;
    tokenVocab = TreeEvaluator;
    ASTLabelType = CommonTree;
}

@members { 
    private static final class Evaluation {
        boolean matched = false; 
        boolean done = false;
    }

    private java.util.HashMap<String, Integer> vars = new java.util.HashMap<String, Integer>();

    public void addVar(String name, int value){
        vars.put(name, value);
    }

}

compilationUnit : block+;

block        : ^(CODEBLOCK instruction*);

instruction  : ifStat | ID;

ifStat       
@init { Evaluation eval = new Evaluation(); }
         : ^(IF condition[eval]* defcond[eval]?) 
         ;

condition [Evaluation eval]
         : ^(CONDBLOCK exp {if ($exp.value) eval.matched = true;} evalblock[eval])
         ;

defcond [Evaluation eval] 
         : ^(DEFAULT {eval.matched = true;} evalblock[eval]) //force a match
         ;

evalblock [Evaluation eval]     
         : {eval.matched && !eval.done}? //Only do this when a condition is matched but not finished 
        block                //call the execution code
        {eval.done = true;}  //evaluation is complete.
         | ^(CODEBLOCK .*)  //read the code node and continue without executing
         ;

exp returns [boolean value]
        : ^(EQ lhs=ID rhs=ID)
        {$value = vars.get($lhs.getText()) == vars.get($rhs.getText());}
        ;

Проблема заключается в том, что DFA, сгенерированный для предсказания правила evalblock, имеет метод SpecialStateTransition(), который ссылается на параметр eval (как указано в правиле), но в сгенерированном классе Java этот параметр не виден.

Я не понимаю, почему, и если есть способ избежать этой проблемы.


person marka.thore    schedule 14.03.2013    source источник


Ответы (1)


У вас есть семантический предикат (синтаксис {...}?), который содержит ссылку на значение, которое изменяется действием (синтаксис {...}). В вашем случае значением являются поля Evaluation.matched и Evaluation.done.

Вы должны полностью избегать этой ситуации — никогда¹ не включайте предикат, зависящий от выполняемого действия. Вместо этого проверьте эти значения в действиях, заключив код action в if (eval.matched && !eval.done) { ... }.

¹ Некоторые люди пишут грамматики, взаимодействующие таким образом, но я строго избегаю этого из-за потенциальных проблем, подобных тем, которые вы видите, и других, которые еще хуже.

person Sam Harwell    schedule 14.03.2013
comment
Хорошо, так что вы предлагаете мне делать в моем случае? Я ищу способ выполнить ветку (если условие истинно) или полностью ее пропустить. Вот почему я решил использовать семантический предикат, потому что, если условия ложны, я мог бы пропустить поддерево с ^(CODEBLOCK .*), которое потребляет все токены. В моем языке много разных инструкций, я должен повторять эту проверку if (eval.matched && !eval.done) везде? - person marka.thore; 14.03.2013