Hoa\Compiler Not Enough Memory

support
1

I have the following PP grammar:

%skip		space		\s

%token		lparan		\(
%token		rparan		\)
%token		period		\.

%token		identifier	[A-Za-z][A-Za-z0-9_]*

#expression:
	primaryExpression() |
	expression() ::period:: <identifier>
	
#primaryExpression:
	<identifier> |
	::lparan:: expression() ::rparan::

I would like to parse expressions like the following:

Favourite.Food.Cake
(Favourite.Food.Cake)
(Favourite.Food).Cake
(Favourite).Food.Cake

There’s no problem with the first two expressions, but the last two produce the following error:

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 65536 bytes) ... Llk\Parser.php on line 389

which I assume is due to infinite recursion. What’s the best way to solve this problem?

2

I think I solved the problem. What I didn’t mention in my initial post was I’d tried to solve the problem by introducing an intermediate nonterminal like so:

#expression:
	primaryExpression() identifierExpression()
	
#primaryExpression:
	<identifier> |
	::lparan:: expression() ::rparan::

#identifierExpression:
	::period:: <id> identifierExpression() |
	EPSILON

I was stuck because I didn’t know how to specify an empty sequence (EPSILON), but I just realized all I had to do was change #identifierExpression to:

#identifierExpression:
	(::period:: <id> identifierExpression())?
3

Hello :slight_smile:,

Your grammar is left-recursive, which must be avoided in a LL parser. What does it mean? You have written:

#expression:
	primaryExpression() |
	expression() ::period:: <identifier>

So, it includes:

expression:
	expression() ::period:: <identifier>

expression is defined as expression followed by ::period:: and <identifier>. It is recursive. A grammar can be recursive, but not left-recursive. It must consume at least one token before starting a new recursion. This Wikipedia articles provide all the information you need: Left recursion.

5

Thanks for the response.

I believe ANTLR4 automatically resolves left-recursion. Will a similar feature be introduced to Hoa\Compiler in the future by any chance?

6

ANTLR4 has time to apply algorithms to resolve left-recursion. In the context of Hoa\Compiler, we don’t, because it is executed directly. Since recent changes, we are able to “save” the compiler into a file (kind of serialisation). This is a good opportunity to apply more algorithms to simplify the grammar, remove left-recursion etc. probably.