Infinite loop

[athas]

This CFG makes alpacc -q 1 -k 3 go into an infinite (or just incredibly slow) loop:

string = "[a-zA-Z0-9_\-\s\(\):/@.]*";
num = (|\-)[0-9]+(|.[0-9]+);
ignore = \s|\n|\t|\r;

J = O | A | string | num | "true" | "false" ;

O = "{" FS0 "}";
FS0 = | F FS1;
FS1 = | "," F FS1;
F = string ":" J;

A = "[" EL0 "]";
EL0 = | J EL1;
EL1 = | "," J EL1;

The culprit is the productions for "true" and "false". It's pretty fast without that.

[WilliamDue]

I ran into this problem before and I think it only happens for "longer" concatenations https://github.com/diku-dk/alpacc/issues/12#issue-2174999957 I am quite sure the problem is my composition table generation is very slow. I think an idea could be to use something like a DFS to find all the compositions instead or something.

[WilliamDue]

Fixed https://github.com/diku-dk/alpacc/commit/67cc9daf01fca638a309c891746bccab560e98f1

[athas]

Lovely, this now runs in a few seconds. I hope it will scale to much larger lexical syntaxes, because this one is still pretty simple.

[WilliamDue]

I actually forgot to test this lexical syntax, it is better but I thought it would had been much better.

[WilliamDue]

I have thought about it a bit and it should definitely be possible to optimize my code more.

[WilliamDue]

I have tried optimizing it more and it seems like it still scales badly. I think maybe some alternative method of creating the composition table should be thought of.