On 23 Feb 2017, at 19:53, Paul Isaacs paul@redpineinstruments.org wrote:

On 23/02/17 06:26 AM, Bastiaan Veelo wrote:

...

[…] Maybe, but I can’t see how… But why rewrite at this point? For performance? Best, Bastiaan.

I think that variable-access is left recursive. Therefore, with a recursive descent parser, I have to rewrite.

Ah, understood. Indeed, there are no less than six left-recursive cycles through variable-access:

VariableAccess <- ComponentVariable <- IndexedVariable <- StringVariable VariableAccess <- ComponentVariable <- FieldDesignator <- RecordVariable VariableAccess <- ComponentVariable <- IndexedVariable <- ArrayVariable VariableAccess <- IdentifiedVariable <- PointerVariable VariableAccess <- BufferVariable <- FileVariable VariableAccess <- SubstringVariable <- StringVariable

In addition to the three through funtion-access and four through constant-access:

FunctionAccess <- ComponentFunctionAccess <- IndexedFunctionAccess <- ArrayFunction FunctionAccess <- ComponentFunctionAccess <- RecordFunctionAccess <- RecordFunction FunctionAccess <- SubstringFunctionAccess <- StringFunction ConstantAccess <- ConstantAccessComponent <- IndexedConstant <- ArrayConstant ConstantAccess <- ConstantAccessComponent <- IndexedConstant <- StringConstant ConstantAccess <- ConstantAccessComponent <- FieldDesignatedConstant <- RecordConstant ConstantAccess <- ConstantAccessComponent <- SubstringConstant <- StringConstant

I can’t force my brain to rewrite these rules so that all these left-recursions are eliminated. I’m not sure it can be done, as recursion may pass through different cycles for successive recursions. It is a real nightmare.

There is a technique for preventing infinite recursion in recursive descent parsers due to left-recursive grammars. It is based on memoizing the match for each recursion. After a certain number of recursions the length of the match stops growing (actually starts out short again). The crux is to break out of the recursion when the length of the match has reached its maximum. See the following post on one of the D forums, and the pointers therein (including literature references):

https://forum.dlang.org/post/jmpkcjmremoypbpcxqdu@forum.dlang.org https://forum.dlang.org/post/jmpkcjmremoypbpcxqdu@forum.dlang.org

This, also, is not straight forward, but I think I have managed to implement this successfully in Pegged.

Best, Bastiaan.