NTERA/NTERA.Engine/Compiler/Parser.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NTERA.Engine.Compiler
{
	public class Parser
	{
		protected Lexer Lexer { get; }

		protected FunctionDefinition SelfDefinition { get; }

		protected ICollection<FunctionDefinition> FunctionDefinitions { get; }
		protected ICollection<FunctionDefinition> ProcedureDefinitions { get; }
		protected ICollection<FunctionVariable> ConstantDefinitions { get; }
		protected ICollection<FunctionVariable> GlobalVariables { get; }
		protected ICollection<FunctionVariable> LocalVariables { get; }
		protected ICollection<Keyword> ExplicitKeywords { get; }

		protected CSVDefinition CsvDefinition { get; }


		protected List<ParserError> Errors { get; } = new List<ParserError>();
		protected List<ParserError> Warnings { get; } = new List<ParserError>();


		protected IEnumerator<Token> Enumerator { get; }

		protected bool hasPeeked = false;
		protected Token peekedToken = Token.Unknown;
		
		protected Token GetNextToken(bool peek = false)
		{
			if (peek && hasPeeked)
				return peekedToken;

			if (!hasPeeked)
				Enumerator.MoveNext();

			peekedToken = Enumerator.Current;

			hasPeeked = peek;
			return Enumerator.Current;
		}

		protected Marker CurrentPosition => new Marker(Lexer.TokenMarker.Pointer + SelfDefinition.Position.Pointer,
			Lexer.TokenMarker.Line + SelfDefinition.Position.Line - 1,
			Lexer.TokenMarker.Column);

		public Parser(string input, FunctionDefinition selfDefinition, ICollection<FunctionDefinition> functionDefinitions, ICollection<FunctionDefinition> procedureDefinitions, ICollection<FunctionVariable> globalVariables, ICollection<FunctionVariable> localVariables, ICollection<Keyword> explicitKeywords, CSVDefinition csvDefinition, ICollection<FunctionVariable> constantDefinitions)
		{
			Lexer = new Lexer(input);
			Enumerator = Lexer.GetEnumerator();

			SelfDefinition = selfDefinition;
			FunctionDefinitions = functionDefinitions;
			ProcedureDefinitions = procedureDefinitions;
			ConstantDefinitions = constantDefinitions;
			GlobalVariables = globalVariables;
			LocalVariables = localVariables;
			ExplicitKeywords = explicitKeywords;
			CsvDefinition = csvDefinition;
		}

		public IEnumerable<ExecutionNode> Parse(out List<ParserError> errors, out List<ParserError> warnings)
		{
			List<ExecutionNode> nodes = new List<ExecutionNode>();

			using (Enumerator)
			{
				do
				{
					var node = ParseLine(out var error);

					if (error != null)
					{
						Errors.Add(error);
						nodes.Add(new ExecutionNode
						{
							Type = "error",
							Metadata =
							{
								["message"] = error.ErrorMessage,
								["symbol"] = error.SymbolMarker.ToString()
							},
							Symbol = error.SymbolMarker
						});

						//resynchronize to a new line
						while (Enumerator.MoveNext()
							   && Enumerator.Current != Token.NewLine
							   && Enumerator.Current != Token.EOF)
						{
						}
					}
					else if (node != null)
					{
						nodes.Add(node);
					}

					hasPeeked = false;
				} while (Enumerator.MoveNext());
			}

			errors = Errors;
			warnings = Warnings;

			if (errors.Count == 0)
				PostProcess(nodes);

			return nodes;
		}

		#region Processor

		protected ExecutionNode ParseLine(out ParserError error)
		{
			error = null;

			switch (Enumerator.Current)
			{
				case Token.Identifer:

					if (IsVariable(Lexer.Identifier))
					{
						string variableName = Lexer.Identifier;

						ValueType type = 0;
						
						if (GlobalVariables.Any(x => x.Name.Equals(variableName, StringComparison.OrdinalIgnoreCase)))
							type = GlobalVariables.First(x => x.Name.Equals(variableName, StringComparison.OrdinalIgnoreCase)).ValueType;
						else if (LocalVariables.Any(x => x.Name.Equals(variableName, StringComparison.OrdinalIgnoreCase)))
							type = LocalVariables.First(x => x.Name.Equals(variableName, StringComparison.OrdinalIgnoreCase)).ValueType;
						else if (ConstantDefinitions.Any(x => x.Name.Equals(variableName, StringComparison.OrdinalIgnoreCase)))
							type = ConstantDefinitions.First(x => x.Name.Equals(variableName, StringComparison.OrdinalIgnoreCase)).ValueType;

						var node = new ExecutionNode
						{
							Type = "assignment",
							Symbol = CurrentPosition
						};

						var variable = GetVariable(out error);
						if (error != null)
							return null;

						if (GetNextToken() != Token.Equal
							&& Enumerator.Current != Token.Increment
							&& Enumerator.Current != Token.Decrement
							&& Enumerator.Current != Token.Append
							&& !Enumerator.Current.IsArithmetic())
						{
							error = new ParserError($"Unexpected token, expecting assignment: {Enumerator.Current}", CurrentPosition);
							return null;
						}

						ExecutionNode value;

						if (Enumerator.Current == Token.Increment)
						{
							value = OperateNodes(variable, CreateConstant(1, CurrentPosition), Token.Plus);
						}
						else if (Enumerator.Current == Token.Decrement)
						{
							value = OperateNodes(variable, CreateConstant(1, CurrentPosition), Token.Minus);
						}
						else if (Enumerator.Current == Token.Append)
						{
							value = OperateNodes(variable, Expression(out error), Token.Plus);
							if (error != null)
								return null;
						}
						else if (Enumerator.Current != Token.Equal)
						{
							Token arithmeticToken = Enumerator.Current;

							if (GetNextToken() != Token.Equal)
							{
								error = new ParserError($"Unexpected token, expecting assignment: {Enumerator.Current}", CurrentPosition);
								return null;
							}

							ExecutionNode newValue = Expression(out error);

							value = OperateNodes(variable, newValue, arithmeticToken);
						}
						else
						{
							value = type == ValueType.String
								? ParseString(out error, true, true)
								: Expression(out error);
						}

						if (error != null)
							return null;

						node.SubNodes = new[]
						{
							variable,
							new ExecutionNode
							{
								Type = "value",
								SubNodes = new[] { value }
							}
						};

						return node;
					}
					else if (Lexer.Identifier.Equals("CASE", StringComparison.OrdinalIgnoreCase))
					{
						var node = new ExecutionNode
						{
							Type = "case",
							Symbol = CurrentPosition
						};

						List<ExecutionNode> subNodes = new List<ExecutionNode>();

						do
						{
							if (GetNextToken(true) == Token.NewLine
								|| GetNextToken(true) == Token.EOF)
								break;

							var value = Expression(out error);
							if (error != null)
								return null;

							if (Enumerator.Current == Token.To)
							{
								var value2 = Expression(out error);
								if (error != null)
									return null;

								subNodes.Add(new ExecutionNode
								{
									Type = "case-to",
									SubNodes = new[] { value, value2 }
								});

								continue;
							}

							subNodes.Add(new ExecutionNode
							{
								Type = "case-exact",
								SubNodes = new[] { value }
							});
						} while (Enumerator.Current == Token.Comma);

						if (Enumerator.Current != Token.NewLine
							&& Enumerator.Current != Token.EOF)
						{
							error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
							return null;
						}

						node.SubNodes = subNodes.ToArray();
						return node;
					}
					else if (Lexer.Identifier.Equals("CALL", StringComparison.OrdinalIgnoreCase)
							 || Lexer.Identifier.Equals("TRYCALL", StringComparison.OrdinalIgnoreCase))
					{
						Enumerator.MoveNext();

						if (Enumerator.Current != Token.Identifer)
						{
							error = new ParserError($"Expecting a call to a function, got token instead: {Enumerator.Current}", CurrentPosition);
							return null;
						}

						Marker symbolMarker = CurrentPosition;
						string target = Lexer.Identifier;
						List<ExecutionNode> parameters = new List<ExecutionNode>();

						if (ProcedureDefinitions.All(x => !x.Name.Equals(target, StringComparison.OrdinalIgnoreCase)))
						{
							error = new ParserError($"Could not find procedure: {Lexer.Identifier}", CurrentPosition);
							return null;
						}

						Enumerator.MoveNext();

						while (Enumerator.Current != Token.NewLine
							   && Enumerator.Current != Token.EOF
							   && Enumerator.Current != Token.RParen)
						{
							parameters.Add(Expression(out error));
							if (error != null)
							{
								error = new ParserError($"{error.ErrorMessage} (target [{target}])", error.SymbolMarker);
								return null;
							}

							if (Enumerator.Current != Token.Comma
								&& Enumerator.Current != Token.RParen
								&& Enumerator.Current != Token.NewLine
								&& Enumerator.Current != Token.EOF)
							{
								error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
								return null;
							}
						}

						if (Enumerator.Current == Token.RParen)
							Enumerator.MoveNext();


						if (Enumerator.Current != Token.NewLine
							&& Enumerator.Current != Token.EOF)
						{
							error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
							return null;
						}

						return CallMethod(target, symbolMarker, parameters.ToArray());
					}
					else if (Lexer.Identifier.Equals("CALLFORM", StringComparison.OrdinalIgnoreCase)
							 || Lexer.Identifier.Equals("TRYCALLFORM", StringComparison.OrdinalIgnoreCase)
							 || Lexer.Identifier.Equals("TRYCCALLFORM", StringComparison.OrdinalIgnoreCase)
							 || Lexer.Identifier.Equals("TRYJUMPFORM", StringComparison.OrdinalIgnoreCase))

					{
						string statementName = Lexer.Identifier;

						var node = new ExecutionNode
						{
							Type = "callform",
							Metadata =
							{
								["try"] = statementName.StartsWith("TRY").ToString()
							},
							Symbol = CurrentPosition
						};

						ExecutionNode nameValue = null;
						List<ExecutionNode> parameters = new List<ExecutionNode>();

						Enumerator.MoveNext();

						do
						{
							ExecutionNode newValue = null;

							if (Enumerator.Current == Token.Identifer)
							{
								newValue = CreateConstant(Lexer.Identifier, CurrentPosition);
							}
							else if (Enumerator.Current == Token.OpenBracket)
							{
								newValue = Expression(out error);
								if (error != null)
									return null;
							}
							else if (Enumerator.Current == Token.LParen)
							{
								break;
							}
							else
							{
								error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
								return null;
							}

							nameValue = nameValue == null
								? newValue
								: OperateNodes(nameValue, newValue, Token.Plus);

							Enumerator.MoveNext();
						} while (Enumerator.Current != Token.Comma
								 && Enumerator.Current != Token.NewLine
								 && Enumerator.Current != Token.EOF);


						while (Enumerator.Current != Token.NewLine
							   && Enumerator.Current != Token.EOF
							   && Enumerator.Current != Token.RParen)
						{
							parameters.Add(Expression(out error));
							if (error != null)
							{
								error = new ParserError($"{error.ErrorMessage} (statement [{statementName}])", error.SymbolMarker);
								return null;
							}

							if (Enumerator.Current != Token.Comma
								&& Enumerator.Current != Token.NewLine
								&& Enumerator.Current != Token.EOF
								&& Enumerator.Current != Token.RParen)
							{
								error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
								return null;
							}
						}

						node.SubNodes = new[]
						{
							new ExecutionNode
							{
								Type = "name",
								SubNodes = new[] { nameValue }
							},
							new ExecutionNode
							{
								Type = "parameters",
								SubNodes = parameters.ToArray()
							},
						};

						return node;
					}
					else if (Lexer.Identifier.Equals("BEGIN", StringComparison.OrdinalIgnoreCase))
					{
						var node = new ExecutionNode
						{
							Type = "statement",
							Metadata =
							{
								["name"] = "BEGIN"
							},
							Symbol = CurrentPosition
						};

						Enumerator.MoveNext();

						if (Enumerator.Current != Token.Identifer)
						{
							error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
							return null;
						}

						node.SubNodes = new[] { CreateConstant(Lexer.Identifier, CurrentPosition) };

						return node;
					}
					else //treat as statement
					{
						string statementName = Lexer.Identifier;

						var node = new ExecutionNode
						{
							Type = "statement",
							Metadata =
							{
								["name"] = statementName
							},
							Symbol = CurrentPosition
						};

						List<ExecutionNode> parameters = new List<ExecutionNode>();

						Keyword keyword = ExplicitKeywords.FirstOrDefault(x => x.Name == statementName);

						if (keyword?.ImplicitString == true)
						{
							var value = ParseString(out error, true, keyword.ImplicitFormatted);
							if (error != null)
								return null;

							if (value != null)
								parameters.Add(value);

							node.SubNodes = parameters.ToArray();

							return node;
						}

						if (GetNextToken(true) == Token.NewLine
							|| GetNextToken(true) == Token.EOF)
						{
							return node;
						}

						if (GetNextToken(true) == Token.Colon
							|| GetNextToken(true) == Token.Equal)
						{
							error = new ParserError($"Undeclared variable: {statementName}", node.Symbol);
							return null;
						}

						while (Enumerator.Current != Token.NewLine
							   && Enumerator.Current != Token.EOF)
						{
							parameters.Add(Expression(out error));
							if (error != null)
							{
								error = new ParserError($"{error.ErrorMessage} (statement [{statementName}])", error.SymbolMarker);
								return null;
							}

							if (Enumerator.Current != Token.Comma
								&& Enumerator.Current != Token.NewLine
								&& Enumerator.Current != Token.EOF)
							{
								error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
								return null;
							}
						}

						node.SubNodes = parameters.ToArray();

						return node;
					}

				case Token.AtSymbol:
				case Token.Sharp:
					while (Enumerator.MoveNext()
						   && Enumerator.Current != Token.NewLine
						   && Enumerator.Current != Token.EOF)
					{
					}

					return null;

				case Token.NewLine:
				case Token.EOF:
					return null;

				default:
					error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
					return null;
			}
		}

		protected bool IsVariable(string identifier)
		{
			return GlobalVariables.Any(x => x.Name.Equals(identifier, StringComparison.OrdinalIgnoreCase))
				   || LocalVariables.Any(x => x.Name.Equals(identifier, StringComparison.OrdinalIgnoreCase))
				   || ConstantDefinitions.Any(x => x.Name.Equals(identifier, StringComparison.OrdinalIgnoreCase));
		}

		protected ExecutionNode GetVariable(out ParserError error)
		{
			string variableName = Lexer.Identifier;
			Marker symbol = CurrentPosition;

			List<ExecutionNode> indices = new List<ExecutionNode>();

			error = null;

			while (GetNextToken(true) == Token.Colon)
			{
				GetNextToken();
				var token = GetNextToken();

				if (token == Token.LParen)
				{
					indices.Add(Expression(out error));
					if (error != null)
						return null;

					if (Enumerator.Current != Token.RParen)
					{
						error = new ParserError("Invalid expression - Expected right bracket", CurrentPosition);
						return null;
					}
				}
				else if (token == Token.Value)
				{
					indices.Add(CreateConstant(Lexer.Value, CurrentPosition));
				}
				else if (token == Token.Identifer)
				{
					if (CsvDefinition.VariableIndexDictionary.TryGetValue(variableName, out var varTable)
						&& varTable.TryGetValue(Lexer.Identifier, out int index))
					{
						indices.Add(CreateConstant(index, CurrentPosition));
						continue;
					}

					if (IsVariable(Lexer.Identifier))
					{
						var subNode = new ExecutionNode
						{
							Type = "variable",
							Metadata =
							{
								["name"] = Lexer.Identifier
							},
							Symbol = CurrentPosition
						};

						indices.Add(subNode);
						continue;
					}

					if (FunctionDefinitions.Any(x => x.Name == Lexer.Identifier))
					{
						indices.Add(GetFunction(out error));
						if (error != null)
							return null;

						continue;
					}

					error = new ParserError($"Unknown identifier: {Lexer.Identifier}", CurrentPosition);
					return null;
				}
			} 

			return GetVariable(variableName, symbol, indices.ToArray());
		}

		protected ExecutionNode GetFunction(out ParserError error)
		{
			error = null;
			Marker symbolMarker = CurrentPosition;
			List<ExecutionNode> parameters = new List<ExecutionNode>();

			string functionName = Lexer.Identifier;

			if (GetNextToken() != Token.LParen)
			{
				error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
				return null;
			}

			while (Enumerator.Current == Token.Comma
				   || Enumerator.Current == Token.LParen)
			{
				if (GetNextToken(true) == Token.RParen)
					break;

				if (GetNextToken(true) == Token.Comma)
				{
					var defaultValue = new ExecutionNode
					{
						Type = "defaultvalue",
						Symbol = CurrentPosition
					};

					parameters.Add(defaultValue);
					GetNextToken();
					continue;
				}

				parameters.Add(Expression(out error));
				if (error != null)
					return null;

				if (Enumerator.Current != Token.Comma
					&& Enumerator.Current != Token.RParen)
				{
					error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
					return null;
				}
			}

			if (Enumerator.Current != Token.RParen)
			{
				error = new ParserError($"Unexpected token: {Enumerator.Current}", CurrentPosition);
				return null;
			}

			if (hasPeeked)
			{
				GetNextToken();
			}

			var functionDefinition = FunctionDefinitions.FirstOrDefault(x => x.Name == functionName
																			 && (x.Parameters.Length >= parameters.Count
																				 || x.Parameters.Any(y => y.IsArrayParameter)));

			if (functionDefinition == null)
			{
				error = new ParserError($"No matching method with same amount of parameters: {functionName} ({parameters.Count})", CurrentPosition);
				return null;
			}

			return CallMethod(functionName, symbolMarker, parameters.ToArray());
		}

		private static readonly Dictionary<Token, int> OrderOfOps = new Dictionary<Token, int>
		{
			{ Token.Or, 0 }, { Token.And, 0 }, { Token.Not, 0 },
			{ Token.Equal, 1 }, { Token.NotEqual, 1 },
			{ Token.Less, 1 }, { Token.More, 1 }, { Token.LessEqual, 1 }, { Token.MoreEqual, 1 },
			{ Token.Plus, 2 }, { Token.Minus, 2 },
			{ Token.Asterisk, 3 }, { Token.Slash, 3 }, { Token.Modulo, 3 },
			{ Token.Caret, 4 }, { Token.ShiftLeft, 4 }, { Token.ShiftRight, 4 }
		};

		protected ExecutionNode Expression(out ParserError error, bool useModulo = true, bool ternaryString = false)
		{
			error = null;
			var operators = new Stack<Token>();
			var operands = new Stack<ExecutionNode>();
			Token token;

			void ProcessOperation(out ParserError localError)
			{
				localError = null;

				Token op = operators.Pop();

				if (op.IsUnary() && operands.Count == 1)
				{
					var operand = operands.Pop();

					operands.Push(new ExecutionNode
					{
						Type = "operation",
						Metadata =
						{
							["type"] = GetOperationName(op),
							["unary"] = "true"
						},
						SubNodes = new[]
						{
							operand
						}
					});
				}
				else if (operands.Count >= 2)
				{
					ExecutionNode right = operands.Pop();
					ExecutionNode left = operands.Pop();

					operands.Push(new ExecutionNode
					{
						Type = "operation",
						Metadata =
						{
							["type"] = GetOperationName(op),
							["unary"] = "false"
						},
						SubNodes = new[]
						{
							left,
							right
						}
					});
				}
				else
					localError = new ParserError("Invalid expression - not enough operands", CurrentPosition);
			}

			void AttemptUnaryConversion(out ParserError localError)
			{
				localError = null;

				while (operators.Count > 0
					   && operators.Peek().IsUnary())
				{
					ProcessOperation(out localError);
					if (localError != null)
						return;
				}
			}

			while ((token = GetNextToken()) != Token.NewLine
				   && token != Token.EOF
				   && token != Token.Comma
				   && token != Token.Colon
				   && token != Token.To
				   && token != Token.CloseBracket
				   && token != Token.RParen
				   && token != Token.QuestionMark
				   && token != Token.Sharp
				   && (!ternaryString || token != Token.TernaryEscape)
				   && (useModulo || token != Token.Modulo))
			{
				if (token == Token.Value)
				{
					operands.Push(CreateConstant(Lexer.Value, CurrentPosition));

					AttemptUnaryConversion(out error);
					if (error != null)
						return null;
				}
				else if (token == Token.QuotationMark || token == Token.AtSymbol)
				{
					operands.Push(ParseString(out error, false, false));
					if (error != null)
						return null;
				}
				else if (token == Token.Identifer)
				{
					if (FunctionDefinitions.Any(x => x.Name == Lexer.Identifier))
					{
						operands.Push(GetFunction(out error));
						if (error != null)
							return null;
					}
					else if (IsVariable(Lexer.Identifier))
					{
						operands.Push(GetVariable(out error));
						if (error != null)
							return null;
					}
					else
					{
						Warnings.Add(new ParserError($"Unknown identifier: {Lexer.Identifier}", CurrentPosition));
						break;
					}
				}
				else if (token == Token.TernaryEscape)
				{
					operands.Push(Expression(out error, useModulo, true));
					if (error != null)
						return null;
				}
				else if (token.IsArithmetic())
				{
					if (!operands.Any() && token.IsUnary())
					{
						operators.Push(token);
						continue;
					}

					if (!operands.Any() && !token.IsUnary())
					{
						error = new ParserError($"Invalid unary operator: {token}", CurrentPosition);
						return null;
					}

					while (operators.Any() && OrderOfOps[token] <= OrderOfOps[operators.Peek()])
					{
						ProcessOperation(out error);
						if (error != null)
							return null;
					}

					operators.Push(token);
				}
				else if (token == Token.LParen)
				{
					operands.Push(Expression(out var localError));
					if (localError != null)
					{
						error = localError;
						return null;
					}
				}
				else if (token == Token.RParen)
				{
					break;
				}
				else
				{
					error = new ParserError($"Unexpected token: {token}", CurrentPosition);
					return null;
				}
			}

			while (operators.Any())
			{
				ProcessOperation(out error);
				if (error != null)
					return null;
			}

			if (!operands.Any())
			{
				error = new ParserError("Invalid expression - Empty operand stack", CurrentPosition);
				return null;
			}

			var result = operands.Pop();

			if (token != Token.QuestionMark)
				return result;

			var resultTrue = ternaryString ? ParseString(out error, useModulo, true, true) : Expression(out error, useModulo, false);
			if (error != null)
				return null;

			var resultFalse = ternaryString ? ParseString(out error, useModulo, true, true) : Expression(out error, useModulo, false);
			if (error != null)
				return null;

			return CallMethod("__INLINEIF", CurrentPosition, result, resultTrue, resultFalse);
		}

		protected ExecutionNode ParseString(out ParserError error, bool implicitString, bool canFormat = false, bool nestedTernary = false)
		{
			error = null;
			ExecutionNode value = null;

			if (Lexer.IsPeeking)
				Lexer.GetNextChar();

			if (nestedTernary && (Lexer.CurrentChar == '?' || Lexer.CurrentChar == '#'))
				Lexer.GetNextChar();

			if (!implicitString)
			{
				if (Lexer.CurrentChar == '@')
				{
					canFormat = true;
					Lexer.GetNextChar();
				}

				if (Lexer.CurrentChar == '"')
				{
					Lexer.GetNextChar();
				}
			}
			else
			{
				if (char.IsWhiteSpace(Lexer.CurrentChar))
					Lexer.GetNextChar();
			}

			StringBuilder currentBlock = new StringBuilder();
			void commitBlock()
			{
				if (currentBlock.Length == 0)
					return;

				ExecutionNode stringBlock = CreateConstant(currentBlock.ToString(), CurrentPosition);

				value = value == null
					? stringBlock
					: OperateNodes(value, stringBlock, Token.Plus);

				currentBlock.Clear();
			}

			while ((Lexer.CurrentChar != '"' || implicitString)
				   && Lexer.CurrentChar != '\n'
				   && Lexer.CurrentChar != '\0')
			{
				if (Lexer.CurrentChar == '\r')
				{
					Lexer.GetNextChar();
					continue;
				}

				if (nestedTernary && Lexer.CurrentChar == '#')
					break;

				if (canFormat && Lexer.CurrentChar == '\\')
				{
					Lexer.GetNextChar();

					if (Lexer.CurrentChar == '@')
					{
						if (nestedTernary)
							break;

						var expressionValue = Expression(out error, true, true);
						if (error != null)
							return null;

						commitBlock();

						value = value == null
							? expressionValue
							: OperateNodes(value, expressionValue, Token.Plus);
					}
					else if (Lexer.CurrentChar == 'n')
					{
						currentBlock.Append('\n');

						Lexer.GetNextChar();
						continue;
					}

					currentBlock.Append(Lexer.CurrentChar);

					Lexer.GetNextChar();
					continue;
				}

				if (canFormat && (Lexer.CurrentChar == '{' || Lexer.CurrentChar == '%'))
				{
					bool useModulo = Lexer.CurrentChar != '%';

					List<ExecutionNode> formatParams = new List<ExecutionNode>();

					Marker symbolMarker = CurrentPosition;

					do
					{
						var expressionValue = Expression(out error, useModulo, nestedTernary);
						if (error != null)
							return null;

						formatParams.Add(expressionValue);
					} while (Enumerator.Current == Token.Comma);

					var formattedValue = CallMethod("__FORMAT", symbolMarker, formatParams.ToArray());

					commitBlock();

					value = value == null
						? formattedValue
						: OperateNodes(value, formattedValue, Token.Plus);

					Lexer.GetNextChar();
					continue;
				}

				currentBlock.Append(Lexer.CurrentChar);
				Lexer.GetNextChar();
			}

			if (!nestedTernary && !implicitString && (Lexer.CurrentChar == '\0' || Lexer.CurrentChar == '\n'))
			{
				error = new ParserError("Was expecting string to be closed", CurrentPosition);
				return null;
			}

			commitBlock();

			value = value ?? CreateConstant("", CurrentPosition);

			return value;
		}

		private static readonly Dictionary<Token, string> OperationNames = new Dictionary<Token, string>
		{
			[Token.Plus] = "add",
			[Token.Asterisk] = "multiply",
			[Token.Minus] = "subtract",
			[Token.Slash] = "divide",
		};

		public static string GetOperationName(Token token)
		{
			return OperationNames.TryGetValue(token, out string result)
				? result
				: token.ToString();
		}

		public static ExecutionNode CreateConstant(Value value, Marker symbolMarker)
		{
			return new ExecutionNode
			{
				Type = "constant",
				Metadata =
				{
					["type"] = value.Type.ToString(),
					["value"] = value.ToString()
				},
				Symbol = symbolMarker
			};
		}

		public static ExecutionNode OperateNodes(ExecutionNode left, ExecutionNode right, Token token)
		{
			return new ExecutionNode
			{
				Type = "operation",
				Metadata =
				{
					["type"] = GetOperationName(token)
				},
				SubNodes = new[]
				{
					left,
					right
				}
			};
		}

		public static ExecutionNode CallMethod(string methodName, Marker symbolMarker, params ExecutionNode[] parameters)
		{
			return new ExecutionNode
			{
				Type = "call",
				Metadata =
				{
					["target"] = methodName
				},
				Symbol = symbolMarker,
				SubNodes = new[]
				{
					new ExecutionNode
					{
						Type = "parameters",
						SubNodes = parameters.ToArray()
					}
				}
			};
		}

		public static ExecutionNode GetVariable(string variableName, Marker marker, params ExecutionNode[] indexNodes)
		{
			var node = new ExecutionNode
			{
				Type = "variable",
				Metadata =
				{
					["name"] = variableName
				},
				SubNodes = indexNodes,
				Symbol = marker
			};

			if (indexNodes.Length > 0)
				node.SubNodes = new[]
				{
					new ExecutionNode
					{
						Type = "index",
						SubNodes = indexNodes
					}
				};

			return node;
		}

		#endregion

		#region Post-processor

		protected void PostProcess(List<ExecutionNode> nodes)
		{
			Branchify(nodes);
		}

		protected void Branchify(List<ExecutionNode> nodes)
		{
			Stack<ExecutionNode> forNodeStack = new Stack<ExecutionNode>();
			Stack<ExecutionNode> doNodeStack = new Stack<ExecutionNode>();

			foreach (var node in nodes)
			{
				if (node.Type == "statement")
				{
					if (node["name"].Equals("FOR", StringComparison.OrdinalIgnoreCase))
						forNodeStack.Push(node);
					else if (node["name"].Equals("DO", StringComparison.OrdinalIgnoreCase))
						doNodeStack.Push(node);
				}
			}

			foreach (var forNode in forNodeStack)
			{
				int index = nodes.IndexOf(forNode);

				int endIndex = 0;

				for (int i = index; i < nodes.Count; i++)
				{
					var node = nodes[i];
					if (node.Type == "statement" && node["name"].Equals("NEXT", StringComparison.OrdinalIgnoreCase))
					{
						endIndex = i;
						break;
					}
				}

				if (endIndex == 0)
					throw new ParserException("Could not find matching NEXT for FOR statement");

				List<ExecutionNode> subNodes = new List<ExecutionNode>();

				forNode.Type = "for-context";
				subNodes.Add(forNode);

				subNodes.AddRange(nodes.Skip(index + 1).Take(endIndex - index - 1));

				nodes.RemoveRange(index, (endIndex - index) + 1);

				ExecutionNode newNode = new ExecutionNode
				{
					Type = "for",
					SubNodes = subNodes.ToArray()
				};

				nodes.Insert(index, newNode);
			}

			foreach (var doNode in doNodeStack)
			{
				int index = nodes.IndexOf(doNode);

				int endIndex = 0;

				for (int i = index; i < nodes.Count; i++)
				{
					var node = nodes[i];
					if (node.Type == "statement" && node["name"].Equals("LOOP", StringComparison.OrdinalIgnoreCase))
					{
						endIndex = i;
						break;
					}
				}

				if (endIndex == 0)
					throw new ParserException("Could not find matching LOOP for DO statement");

				List<ExecutionNode> subNodes = new List<ExecutionNode>();

				var loopNode = nodes[endIndex];
				loopNode.Type = "loop-context";
				subNodes.Add(loopNode);

				subNodes.AddRange(nodes.Skip(index + 1).Take(endIndex - index - 1));

				nodes.RemoveRange(index, (endIndex - index) + 1);

				ExecutionNode newNode = new ExecutionNode
				{
					Type = "do",
					SubNodes = subNodes.ToArray()
				};

				nodes.Insert(index, newNode);
			}
		}

		#endregion
	}
}