How can I fix recursion problem?

Hello! I’m developing a parser generator and I ran into a problem that I can’t solve. When parser start parsing it matches the root rule step by step (first subrule and then, if success, second rule etc.). It can also match recursively:

x = "(" x ")" | "[0-9]+";
!root = {x};
(1) 23 (456) ((789))

But when grammar is:

exp = unop exp {binop exp};
binop = '+' | '-' | '*' | '/' | '^' | '%' | '..' | '<' | '<=' | '>' | '>=' | '==' | '~=' | 'and' | 'or';
unop = '-' | 'not' | '#';

It recursively do this:
exp → exp → exp
How can I fix this?
Here is the code:

local function match(parser: Parser, rule: Grammar.GrammaticalRule, data: { AST.Element }, offset: number, stack: { [GrammaticalRule]: boolean }): (boolean, { AST.Element }, number)
	if rule.class == "custom" then
		if offset > #data then
			return
		end
		local elements = {}
		for i = offset, #data do
			table.insert(elements, data[i])
		end
		return rule.match(parser, table.freeze(elements))
	elseif rule.class == "pattern" then
		local current = data[offset]
		if current.elementType == "token" and
			current.value:match(`^{rule.pattern}$`) then
			return true, { current }, 1
		end
		return false, { AST.Error.new(current, rule) }, 1
	elseif rule.class == "include" then
		local ruleName = rule.ruleName
		local subrule = parser.grammar.rules[ruleName]
		local success, content, count = match(parser, subrule, data, offset, stack)
		if success then
			if #content > 0 then
				return true, { AST.Structure.new(ruleName, content) }, count
			else
				return true, {}, count
			end
		end
		return false, { AST.Error.new(data[offset], subrule) }, 1
	elseif rule.class == "whitespace" then
		local current = data[offset]
		if current.elementType == "whitespace" and
			(not current.multiline or rule.multiline) then
			return true, { current }, 1
		end
		return true, {}, 0
	elseif rule.class == "eof" then
		local current = data[offset]
		if current.elementType == "eof" then
			return true, { current }, 1
		end
		return false, { AST.Error.new(data[offset], rule) }, 1
	elseif rule.class == "modifier" then
		if rule.modifier == "optional" then
			local success, output, count = match(parser, rule.rule, data, offset, stack)
			if success then
				return success, output, count
			else
				return true, {}, 0
			end
		elseif rule.modifier == "repeation" then
			local output = {}
			local count = 0
			while offset <= #data do
				local success, out, cnt = match(parser, rule.rule, data, offset, stack)
				if success then
					for _, element in out do
						table.insert(output, element)
					end
					offset += cnt
					count += cnt
				else
					break
				end
			end
			return true, output, count
		end
	elseif rule.class == "chain" then
		if rule.operation == "and" then
			local output = {}
			local count = 0
			for _, subrule in rule.rules do
				while data[offset].elementType == "whitespace" do
					offset += 1
					count += 1
				end
				if stack[subrule] then
					stack[subrule] = false
					print("skip", subrule)
					return false, {}, 0
				end
				local substack = table.clone(stack)
				substack[subrule] = true
				local success, out, cnt = match(parser, subrule, data, offset, substack)
				for _, element in out do
					table.insert(output, element)
				end
				offset += cnt
				count += cnt
				if not success then
					return success, output, count
				end
			end
			return true, output, count
		elseif rule.operation == "or" then
			local map = {}
			for _, subrule in rule.rules do
				if stack[subrule] then
					stack[subrule] = false
					continue
				end
				local substack = table.clone(stack)
				substack[subrule] = true
				local success, output, count = match(parser, subrule, data, offset, substack)
				if success then
					map[count] = output
				end
			end
			local max
			local maxn = -1
			for count, output in map do
				if count > maxn then
					max = output
					maxn = count
				end
			end
			if max then
				return true, max or {}, maxn
			end
			return false, { AST.Error.new(data[offset], "variant") }, 1
		end
	end
end

Thank you!

3 Likes