Need help redefining some of these rules as non-left-recursive

[ethindp]

I hope this isn't an inappropriate place to ask about this, but if it is I apologize. I'm implementing a compiler for the Ada programming language, not a custom one. The language is quite complex and contains a significant number of rules. I've done my best to rewrite them in the Pest grammar format. The syntax summary can be found here, and my rewrite of the grammar is available here. Pest identifies the ExplicitDereference, IndexedComponent, Slice, SelectedComponent, AttributeReference, FunctionCall, GeneralizedReference, GeneralizedIndexing, ImplicitDereference, Name, Prefix, ReductionAttributeReference, ReferenceObjectName, IndexableContainerObjectPrefix, FunctionName, and FunctionPrefix as left-recursive. However, I'm not sure how to rewrite these rules to eliminate that, given that I need to retain the syntax from the original syntax summary. In order, the rules that are left-recursive are below, though it might be helpful to read the full grammar for missing constructs:

ExplicitDereference = { Name ~ "." ~ AllKeyword }
IndexedComponent = { Prefix ~ "(" ~ Expression ~ ("," ~ Expression)* ~ ")" }
Slice = { Prefix ~ "(" ~ DiscreteRange ~ ")" }
SelectedComponent = { Prefix ~ "." ~ SelectorName }
AttributeReference = { (Prefix ~ "'" ~ AttributeDesignator) | ReductionAttributeReference }
FunctionCall = { FunctionName | (FunctionPrefix ~ ActualParameterPart) }
GeneralizedReference = { ReferenceObjectName }
GeneralizedIndexing = { IndexableContainerObjectPrefix ~ ActualParameterPart }
ImplicitDereference = { Name }
Name = { DirectName | ExplicitDereference | IndexedComponent | Slice | SelectedComponent | AttributeReference | TypeConversion | FunctionCall | CharacterLiteral | QualifiedExpression | GeneralizedReference | GeneralizedIndexing | TargetName }
Prefix = { Name | ImplicitDereference }
ReductionAttributeReference = { (ValueSequence | Prefix) ~ "'" ~ ReductionAttributeDesignator }
ReferenceObjectName = { Name }
IndexableContainerObjectPrefix = { Prefix }
FunctionName = { Name }
FunctionPrefix = { Prefix }

I'm not asking for others to remove all the left-recursion for me (though if someone wants to, they can), but instead to provide suggestions (I've only written one other parser and that was in Uni). I've thought about just flattening some of the rules (and for all I know, I've mis-defined some of them because some of them aren't defined in BNF but in narrative descriptions, which is harder to translate), but I'm not sure if that would even work and I feel like I'd be majorly duplicating things all over the place, which would make the grammar harder to maintain. Does anyone have any suggestions?

[tomtau]

I guess there are three general approaches:

1. converting to right recursion (reversing the order of the recursive and non-recursive parts of the rule): e.g. A = {A ~ "b" | "c"} can be rewritten as A = {"c" ~ A' }, where A' = { "b" ~ A' | "" } (The resulting parse tree will be inverted, with the recursive part at the leaves instead of the root, but the overall structure will be preserved.)
2. introducing an auxiliary non-terminal symbol (replacing the left recursive part of the rule with a reference to the auxiliary symbol, and then defining the auxiliary symbol in terms of itself and the original non-terminal): e.g. A = {A ~ "b" | "c"} can be rewritten as A = {B}, where B = {"c" ~ B'} and B' = {"b" ~ B' | ""}. (The resulting parse tree will be similar to the one obtained with the first approach, but the structure will be slightly more complex. One can potentially use silent rules to keep the parse tree simple.)
3. factoring out the common prefixes (identifying the common prefixes shared by the left recursive alternatives, and then extracting them into a separate non-terminal symbol): e.g. A = {B ~ "c" | D ~ "c" | E ~ "c"} can be rewritten as A = {P ~ "c"}, where P = {B | D | E}. (The resulting parse tree will be similar to the original one, but the structure will be simplified.)

[ethindp]

Thanks for those! I've heard of left factoring (or at least I think that's what it's called in reference to your third method) but am unsure what the other two are called. Looking at all the rules that Pest claims have left recursion, the common prefixes are, well, the Prefix and Name rules. I definitely have considered making a significant number of rules silent, E.G. The Name rule, if only because not having them silent complicates the parse tree quite a bit.

Since Prefix is either a Name or ImplicitDereference, and a ImplicitDereference is just a Name, the thing to do, off the top of my head, would be to flatten the rules by replacing all instances of Prefix with Name and eliminating the ImplicitDereference rule entirely.

[ethindp]

Okay so I just resolved it, and it was a lot easier than I thought. I just translated:

Name = { DirectName | ExplicitDereference | IndexedComponent | Slice | SelectedComponent | AttributeReference | TypeConversion | FunctionCall | CharacterLiteral | QualifiedExpression | GeneralizedReference | GeneralizedIndexing | TargetName }

Into:

Name = _{ DirectName ~ NamePrime }
NamePrime = _{ ((ExplicitDereference ~ NamePrime) | (IndexedComponent ~ NamePrime) | (Slice ~ NamePrime) | (SelectedComponent ~ NamePrime) | (AttributeReference ~ NamePrime) | (TypeConversion ~ NamePrime) | (FunctionCall ~ NamePrime) | (CharacterLiteral ~ NamePrime) | (QualifiedExpression ~ NamePrime) | (GeneralizedReference ~ NamePrime) | (GeneralizedIndexing ~ NamePrime) | (TargetName ~ NamePrime))? }

I know that this changes the syntax of the grammar but if I did it right it shouldn't affect the language in any way.