Re: 10206 productions re-write

> On 23 Feb 2017, at 19:53, Paul Isaacs <[email protected]> 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/[email protected] <https://forum.dlang.org/post/[email protected]>

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

Best,
Bastiaan.

_______________________________________________
Gpc mailing list
[email protected]
https://www.g-n-u.de/mailman/listinfo/gpc