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):
This, also, is not straight forward, but I think I have managed to implement this successfully in Pegged.
Bastiaan.