Почему анализатор, сгенерированный ANTLR, повторно использует объекты контекста?

Question

Я пытаюсь создать интерпретатор для простого языка программирования с использованием ANTLR.Я хотел бы добавить функцию рекурсии.

До сих пор я реализовал определение и вызов функций с возможностью использования нескольких операторов возврата, а также локальных переменных.Чтобы добиться наличия локальных переменных, я расширил парциальный класс парсера FunctionCallContext со словарем для них.Я могу успешно использовать их один раз.Кроме того, когда я снова вызываю ту же функцию из себя (рекурсивно), синтаксический анализатор создает новый объект контекста для нового вызова функции, как я и ожидал.Однако если я создам «более глубокую» рекурсию, третий контекст вызова функции будет таким же, как второй (с тем же хеш-кодом и теми же локальными переменными).

Моя (обновленная) грамматика:

    grammar BatshG;
/*
 * Parser Rules
 */
compileUnit: ( (statement) | functionDef)+;
statement:      print  ';'
            |   println ';'
            |   assignment ';'
            |   loopWhile
            |   branch 
            |   returnStatement ';'
            |   functionCall ';'
;

branch:
          'if' '(' condition=booleanexpression ')' 
                trueBranch=block 
            ('else' falseBranch=block)?;
loopWhile:
          'while' '(' condition=booleanexpression ')' 
                whileBody=block 
;

block: 
                statement
            |   '{' statement* '}';

numericexpression:      
                MINUS onepart=numericexpression               #UnaryMinus
            |   left=numericexpression op=('*'|'/') right=numericexpression  #MultOrDiv
            |   left=numericexpression op=('+'|'-') right=numericexpression  #PlusOrMinus
            |   number=NUMERIC                                      #Number
            |   variableD                                       #NumVariable
;
stringexpression: 
                left=stringexpression PLUSPLUS right=stringexpression #Concat   
            |   string=STRING #String
            |   variableD                                       #StrVariable
            |   numericexpression #NumberToString
;
booleanexpression:
                        left=numericexpression relationalOperator=('<' | '>' | '>=' | '<=' | '==' | '!=' ) right=numericexpression #RelationalOperation
                    |   booleanliteral #Boolean
                    |   numericexpression #NumberToBoolean
;
booleanliteral: trueConst | falseConst ;
trueConst :  'true'          ;
falseConst :  'false'                ;

assignment : varName=IDENTIFIER EQUAL  right=expression;
expression: numericexpression | stringexpression | functionCall | booleanexpression;
println: 'println' '(' argument=expression ')'; 
print: 'print' '(' argument=expression ')';

functionDef: 'function' funcName= IDENTIFIER
                        '(' 
                            (functionParameters=parameterList)?
                        ')'
                            '{' 
                                statements=statementPart?
                            '}' 
;

statementPart:  statement* ;
returnStatement: ('return' returnValue=expression );
parameterList : paramName=IDENTIFIER (',' paramName=IDENTIFIER)*;

functionCall: funcName=IDENTIFIER '(' 
            (functionArguments=argumentList)?
')';
argumentList: expression (',' expression)*;
variableD: varName=IDENTIFIER;
///*
// * Lexer Rules
// */
NUMERIC: (FLOAT | INTEGER);
PLUSPLUS: '++';
MINUS: '-';
IDENTIFIER: [a-zA-Z_][a-zA-Z0-9_]* ;

EQUAL  :            '='              ;

STRING : '"' (~["\r\n] | '""')* '"'          ;

INTEGER: [0-9] [0-9]*;
DIGIT : [0-9]                       ;
FRAC : '.' DIGIT+                   ;
EXP : [eE] [-+]? DIGIT+  ;
FLOAT : DIGIT* FRAC EXP?             ;
WS: [ \n\t\r]+ -> channel(HIDDEN);

    ///*
    // * Lexer Rules
    // */
    NUMERIC: (FLOAT | INTEGER);
    PLUSPLUS: '++';
    MINUS: '-';
    IDENTIFIER: [a-zA-Z_][a-zA-Z0-9_]* ;
    EQUAL  :            '='              ;
    STRING : '"' (~["\r\n] | '""')* '"'          ;
    INTEGER: [0-9] [0-9]*;
    DIGIT : [0-9]                       ;
    FRAC : '.' DIGIT+                   ;
    EXP : [eE] [-+]? DIGIT+  ;
    FLOAT : DIGIT* FRAC EXP?             ;
    WS: [ \n\t\r]+ -> channel(HIDDEN);

Мой частичный класс парсера, написанный мной (не сгенерированная часть):

    public partial class BatshGParser
{
    //"extensions" for contexts:
    public partial class FunctionCallContext
    {
        private Dictionary<string, object> localVariables = new Dictionary<string, object>();
        private bool isFunctionReturning;
        public FunctionCallContext()
        {
           localVariables = new Dictionary<string, object>();
           isFunctionReturning = false;
        }

        public Dictionary<string, object> LocalVariables { get => localVariables; set => localVariables = value; }
        public bool IsFunctionReturning { get => isFunctionReturning; set => isFunctionReturning = value; }
    }

    public partial class FunctionDefContext
    {
        private List<string> parameterNames;

        public FunctionDefContext()
        {
            parameterNames = new List<string>();
        }
        public List<string> ParameterNames { get => parameterNames; set => parameterNames = value; }
    }
}

И соответствующие части (и, возможно, немного больше) моего посетителя:

         public class BatshGVisitor : BatshGBaseVisitor<ResultValue>
    {
        public ResultValue Result { get; set; }
        public StringBuilder OutputForPrint { get; set; }
        private Dictionary<string, object> globalVariables = new Dictionary<string, object>();
        //string = function name
        //object = parameter list
        //object =  return value
        private Dictionary<string, Func<List<object>, object>> globalFunctions = new Dictionary<string, Func<List<object>, object>>();
        private Stack<BatshGParser.FunctionCallContext> actualFunctions = new Stack<BatshGParser.FunctionCallContext>();

        public override ResultValue VisitCompileUnit([NotNull] BatshGParser.CompileUnitContext context)
        {
            OutputForPrint = new StringBuilder("");

            isSearchingForFunctionDefinitions = true;
            var resultvalue = VisitChildren(context);
            isSearchingForFunctionDefinitions = false;
            resultvalue = VisitChildren(context);
            Result = new ResultValue() { ExpType = "string", ExpValue = resultvalue.ExpValue ?? null };

            return Result;
        }
        public override ResultValue VisitChildren([NotNull] IRuleNode node)
        {
            if (this.isSearchingForFunctionDefinitions)
            {
                for (int i = 0; i < node.ChildCount; i++)
                {
                    if (node.GetChild(i) is BatshGParser.FunctionDefContext)
                    {
                        Visit(node.GetChild(i));
                    }
                }
            }
            return base.VisitChildren(node);
        }
        protected override bool ShouldVisitNextChild([NotNull] IRuleNode node, ResultValue currentResult)
        {
            if (isSearchingForFunctionDefinitions)
            {
                if (node is BatshGParser.FunctionDefContext)
                {
                    return true;
                }
                else
                    return false;
            }
            else
            {
                if (node is BatshGParser.FunctionDefContext)
                {
                    return false;
                }
                else
                    return base.ShouldVisitNextChild(node, currentResult);
            }
        }

        public override ResultValue VisitFunctionDef([NotNull] BatshGParser.FunctionDefContext context)
        {

            string functionName = null;
            functionName = context.funcName.Text;
            if (context.functionParameters != null)
            {
                List<string> plist = CollectParamNames(context.functionParameters);
                context.ParameterNames = plist;
            }
            if (isSearchingForFunctionDefinitions)
                globalFunctions.Add(functionName,
                (
                delegate(List<object> args)
                    {
                        var currentMethod = (args[0] as BatshGParser.FunctionCallContext);
                        this.actualFunctions.Push(currentMethod);
                        //args[0] is the context
                        for (int i = 1; i < args.Count; i++)
                        {

                            currentMethod.LocalVariables.Add(context.ParameterNames[i - 1],
                                (args[i] as ResultValue).ExpValue
                                );
                        }

                    ResultValue retval = null;
                        retval = this.VisitStatementPart(context.statements);

                        this.actualFunctions.Peek().IsFunctionReturning = false;
                        actualFunctions.Pop();
                        return retval;
                    }
                 )
            );
            return new ResultValue()
            {

            };
        }       

        public override ResultValue VisitStatementPart([NotNull] BatshGParser.StatementPartContext context)
        {
            if (!this.actualFunctions.Peek().IsFunctionReturning)
            {
                return VisitChildren(context);
            }
            else
            {
                return null;
            }
        }

        public override ResultValue VisitReturnStatement([NotNull] BatshGParser.ReturnStatementContext context)
        {
            this.actualFunctions.Peek().IsFunctionReturning = true;
            ResultValue retval = null;
            if (context.returnValue != null)
            {
                retval = Visit(context.returnValue);
            }

            return retval;
        }

                public override ResultValue VisitArgumentList([NotNull] BatshGParser.ArgumentListContext context)
        {
            List<ResultValue> argumentList = new List<ResultValue>();
            foreach (var item in context.children)
            {
                var tt = item.GetText();
                if (item.GetText() != ",")
                {
                    ResultValue rv = Visit(item);
                    argumentList.Add(rv);
                }
            }
            return
                new ResultValue()
                {
                    ExpType = "list",
                    ExpValue = argumentList ?? null
                };
        }

        public override ResultValue VisitFunctionCall([NotNull] BatshGParser.FunctionCallContext context)
        {
            string functionName = context.funcName.Text;
            int hashcodeOfContext = context.GetHashCode();
            object functRetVal = null;
            List<object> argumentList = new List<object>()
            {
                context
                //here come the actual parameters later
            };

            ResultValue argObjects = null;
            if (context.functionArguments != null)
            {
                argObjects = VisitArgumentList(context.functionArguments);
            }

            if (argObjects != null )
            {
                if (argObjects.ExpValue is List<ResultValue>)
                {
                    var argresults = (argObjects.ExpValue as List<ResultValue>) ?? null;
                    foreach (var arg in argresults)
                    {
                        argumentList.Add(arg);
                    }
                }
            }

            if (globalFunctions.ContainsKey(functionName))
            {
                {
                    functRetVal = globalFunctions[functionName]( argumentList );
                }
            }

            return new ResultValue()
            {
                ExpType = ((ResultValue)functRetVal).ExpType,
                ExpValue = ((ResultValue)functRetVal).ExpValue
            };
        }

        public override ResultValue VisitVariableD([NotNull] BatshGParser.VariableDContext context)
        {

            object variable;
            string variableName = context.GetChild(0).ToString();
            string typename = "";

            Dictionary<string, object> variables = null;
            if (actualFunctions.Count > 0)
            {
                Dictionary<string, object> localVariables = 
                    actualFunctions.Peek().LocalVariables;
                if (localVariables.ContainsKey(variableName))
                {
                    variables = localVariables;
                }
            }
            else
            {
                variables = globalVariables;
            }

            if (variables.ContainsKey(variableName))
            {
                variable = variables[variableName];

                typename = charpTypesToBatshTypes[variable.GetType()];
            }
            else
            {

                Type parentContextType = contextTypes[context.parent.GetType()];
                typename = charpTypesToBatshTypes[parentContextType];
                variable = new object();

                if (typename.Equals("string"))
                {
                    variable = string.Empty;
                }
                else
                {
                    variable = 0d;
                }
            }

            return new ResultValue()
            {
                ExpType = typename,
                ExpValue = variable
            };
        }           
        public override ResultValue VisitAssignment([NotNull] BatshGParser.AssignmentContext context)
        {
            string varname = context.varName.Text;
            ResultValue varAsResultValue = Visit(context.right);
            Dictionary<string, object> localVariables = null;

            if (this.actualFunctions.Count > 0)
            {
                localVariables = 
                    actualFunctions.Peek().LocalVariables;
                if (localVariables.ContainsKey(varname))
                {
                    localVariables[varname] = varAsResultValue.ExpValue;
                }
                else
                if (globalVariables.ContainsKey(varname))
                {
                    globalVariables[varname] = varAsResultValue.ExpValue;
                }
                else
                {
                    localVariables.Add(varname, varAsResultValue.ExpValue);
                }
            }
            else
            {
                if (globalVariables.ContainsKey(varname))
                {
                    globalVariables[varname] = varAsResultValue.ExpValue;
                }
                else
                {
                    globalVariables.Add(varname, varAsResultValue.ExpValue);
                }
            }
            return varAsResultValue;
        }
}

Что может вызвать проблему?Спасибо!

Answer 1

Почему анализатор, сгенерированный ANTLR, повторно использует объекты контекста?

Это не так.Каждый вызов функции в вашем исходном коде будет соответствовать ровно одному FunctionCallContext объекту, и он будет уникальным.Они должны были бы быть, даже для двух полностью идентичных вызовов функций, потому что они также содержат метаданные, например, где в источнике появляется вызов функции - и это, очевидно, будет отличаться между вызовами, даже если все остальное одинаково.

Чтобы проиллюстрировать это, рассмотрим следующий исходный код:

function f(x) {
  return f(x);
}
print(f(x));

Это создаст дерево, содержащее ровно два объекта FunctionCallContext - один для строки 2 и один для строки 4. Оба они будут обаотличаться - у них обоих будут дочерние узлы, ссылающиеся на имя функции f и аргумент x, но у них будет другая информация о местоположении и другой хэш-код - как и у дочерних узлов.Здесь ничего не используется повторно.

Что может вызвать проблему?

Тот факт, что вы видите один и тот же узел несколько раз, просто связан с тем, что выВы посещаете одну и ту же часть настоящего несколько раз.Это совершенно нормальная вещь для вашего варианта использования, но в вашем случае это вызывает проблему, потому что вы сохранили изменяемые данные в объекте, предполагая, что вы получите свежий FunctionCall объект каждый раз, когда вызов функции происходит при запускевремя - а не каждый раз, когда в исходном коде появляется вызов функции.

Это не то, как работают деревья разбора (они представляют структуру исходного кода, а не последовательность вызовов, которые могут произойти во время выполнения),поэтому вы не можете использовать FunctionCallContext объекты для хранения информации о конкретном вызове функции во время выполнения.В общем, я бы посчитал плохой идеей вставлять изменяемое состояние в объекты контекста.

Вместо этого вы должны поместить изменяемое состояние в объект посетителя.Для вашей конкретной проблемы это означает наличие стека вызовов, содержащего локальные переменные каждого вызова функции времени выполнения.Каждый раз, когда функция начинает выполнение, вы можете поместить кадр в стек, и каждый раз, когда функция выходит, вы можете выдвинуть ее.Таким образом, вершина стека всегда будет содержать локальные переменные выполняемой в данный момент функции.

---

PS: это не связано с вашей проблемой, но обычные правила приоритета в арифметических выражениях таковы, что+ имеет тот же приоритет, что и -, а * имеет тот же приоритет, что и /.В вашей грамматике приоритет / больше, чем *, а приоритет - выше +.Это означает, что, например, 9 * 5 / 3 будет иметь значение 5, когда оно должно быть 15 (при условии обычных правил для целочисленной арифметики).

Чтобы исправить это + и -, а также * и / должны быть частью одного и того же правила, поэтому они имеют одинаковый приоритет:

| left=numericexpression op=('*'|'/') right=numericexpression #MulOrDiv
| left=numericexpression op=('+'|'-') right=numericexpression #PlusOrMinus