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!