使用其他表达式中的表达式评估树

Question

对于初学者，如果我在这件事上不够准确，我想道歉。

grammar Test;

@parser::header {#pragma warning disable 3021}
@lexer::header {#pragma warning disable 3021}

prog                       : expression? EOF;
expression                 : TEXT #text
                       | shift_left #shiftLeft
                       | shift_right #shiftRight
                       | upper_case #upperCase
                       | lower_case #lowerCase
                       | substring #ssubstring
                       | expression CONCANTENATE expression #concatenate
                       ;
substring : SUBSTRING OBRACKET expression COMMA NUMBER COMMA NUMBER CBRACKET;
shift_left : SHIFT_LEFT OBRACKET expression COMMA NUMBER CBRACKET;
shift_right : SHIFT_RIGHT OBRACKET expression COMMA NUMBER CBRACKET;
upper_case  : UPPER OBRACKET expression CBRACKET;
lower_case : LOWER OBRACKET expression CBRACKET;

compileUnit
    :   EOF
    ;

/*
 * Lexer Rules
 */

fragment L          : ('L'|'l') ;
fragment E          : ('E'|'e') ;
fragment F          : ('F'|'f') ;
fragment T          : ('T'|'t') ;
fragment U          : ('U'|'u') ;
fragment P          : ('P'|'p') ;
fragment R          : ('R'|'r') ;
fragment O          : ('O'|'o') ;
fragment W          : ('W'|'w') ;
fragment I          : ('I'|'i') ;
fragment G          : ('G'|'g') ;
fragment H          : ('H'|'h') ;
fragment S          : ('S'|'s') ;
fragment B          : ('B'|'b') ;
fragment N          : ('N'|'n') ;

COMMA               : ',';
OBRACKET            : '(';
CBRACKET            : ')';
CONCANTENATE        : '+';

NUMBER              : [1-9] (DIGIT)*;
DIGIT               : [0-9];


SHIFT_RIGHT         : R I G H T;
UPPER               : U P P E R;
LOWER               : L O W E R;
SUBSTRING           : S U B S T R I N G;
SHIFT_LEFT          : L E F T;

TEXT                : '"' .*? '"';
WHITESPACE          : (' '|'\t'|'\r'|'\n')+ -> skip ;

WS
   :   ' ' -> channel(HIDDEN)
   ;

我想要实现的是评估树（或者换句话说 - 能够实际执行简单的操作）。语法的整个思想是对字符串执行简单的操作。问题本身是我不知道如何实际遍历树并评估其表达式。我在这里举个例子会容易得多：

"upper(left("text"),2)" <- 这个操作是一个嵌套操作，它应该： 1. 将 "text" 向左移动 2（什么并不重要）实际上确实如此）。 2. Return 移位值 "up"。 3. 上层表达式应该收集 left() 产生的任何内容并做它的事情，在这种情况下，将 "text" 转换为大写。

整个 "nested expressions" 都是导致问题的原因。我已经实现了我自己的访问者 class 并且我有很多方法可以重写，例如表达式、子字符串、shiftright 等等——全部取自语法但我不知道如何在我的情况下使用它们面对，使用什么方法才能真正使用语法。

Answer 1

首先，你有很多几乎相同的名字，比如 shift_left 和 shiftLeft 只是在乞求引入错误，所以我强烈建议你重构你的语法：

expression : text
           | shiftLeft
           | shiftRight
           | upperCase
           | lowerCase
           | substring
           | concatenate
           ;
text : TEXT;
substring : SUBSTRING OBRACKET expression COMMA NUMBER COMMA NUMBER CBRACKET;
shiftLeft : SHIFT_LEFT OBRACKET expression COMMA NUMBER CBRACKET;
shiftRight : SHIFT_RIGHT OBRACKET expression COMMA NUMBER CBRACKET;
upperCase  : UPPER OBRACKET expression CBRACKET;
lowerCase : LOWER OBRACKET expression CBRACKET;
concatenate : expression CONCANTENATE expression;

或：

expression : TEXT #text
           | SHIFT_LEFT OBRACKET expression COMMA NUMBER CBRACKET #shiftLeft
           | SHIFT_RIGHT OBRACKET expression COMMA NUMBER CBRACKET #shiftRight
           | UPPER OBRACKET expression CBRACKET #upperCase
           | LOWER OBRACKET expression CBRACKET #lowerCase
           | SUBSTRING OBRACKET expression COMMA NUMBER COMMA NUMBER CBRACKET #substring
           | expression CONCANTENATE expression #concatenate
           ;

我会选择后者，因为它生成的树更简单。

要访问嵌套表达式，只需对子表达式递归调用 Visit，然后适当组合结果。因此，涵盖您的示例的访问者可能看起来像这样：

override String VisitText(TextContext ctx) {
    return ctx.TEXT().Text();
}

override String VisitUpper(UpperContext ctx) {
    return Visit(ctx.expression()).ToUpper();
}

override String VisitShiftLeft(ShiftLeftContext ctx) {
    int n = int.Parse(ctx.NUMBER().Text());
    // I'm assuming here that "shift left by N" means "remove N first chars"
    return Visit(ctx.expression()).Substring(n);
}

其他表达式类型的访问方法将遵循相同的逻辑。

Answer 2

感谢@sepp2k - 我将整个解决方案放在访问者的 C# 中：

public sealed class TreeEvaluationVisitor : TestBaseVisitor<Object> {

   public override object VisitText([NotNull] TestParser.TextContext context) {

        int string_length = context.TEXT().ToString().Length;
        return context.TEXT().ToString().Substring(1, string_length - 2);     
        //Substring() up here is for omitting the quote marks in the final output
    }

    public override object VisitUpperCase([NotNull] TestParser.UpperCaseContext context) {

        int string_length = Visit(context.expression()).ToString().Length;
        return Visit(context.expression()).ToString().ToUpper();
    }

    public override object VisitLowerCase([NotNull] TestParser.LowerCaseContext context) {

        int string_length = Visit(context.expression()).ToString().Length;
        return Visit(context.expression()).ToString().ToLower();
    }

    public override object VisitShiftLeft([NotNull] TestParser.ShiftLeftContext context) {

        int n = int.Parse(context.NUMBER().ToString());
        return sh_left(Visit(context.expression()).ToString(), n);
    }

    public override object VisitShiftRight([NotNull] TestParser.ShiftRightContext context) {

        int n = int.Parse(context.NUMBER().ToString());
        return sh_right(Visit(context.expression()).ToString(), n);
    }

    public override object VisitConcatenate([NotNull] TestParser.ConcatenateContext context) {
        string left = Visit(context.expression(0)).ToString();
        string right = Visit(context.expression(1)).ToString();

        return left + right;
    }

    public override object VisitSubstring([NotNull] TestParser.SubstringContext context) {

        int n1 = int.Parse(context.NUMBER(0).ToString());
        int n2 = int.Parse(context.NUMBER(1).ToString());

        return Visit(context.expression()).ToString().Substring(n1, n2);

    }

    //shift methods for shifting strings, i. e. left("abc",2) -> result = cab
    private static string sh_left(string chain, int amount) {  

        return (chain.Substring(amount) + chain.Substring(0, amount));

    }
    private static string sh_right(string chain, int amount) {

        return chain.Substring(chain.Length - amount) 
               + chain.Substring(0, chain.Length - amount);

    }

使用其他表达式中的表达式评估树

Evaluate tree with expression inside other expression

c#

antlr

antlr4