Re: Indirect left recursion in iXML grammars

On Mon, 9 Feb 2026 18:28:08 +0000
Bethan Tovey-Walsh <bytheway@linguacelta.com> wrote:

> 
> No. It doesn't specify exactly which parser to use, but it requires a
> parser that can handle any grammar, and then suggests a number of
> them:
> > 
> When you say "no", are you responding to my assertion that iXML is a
> syntax for notating grammars, and is not a parsing algorithm?
> 
> So left recursion is absolutely required.
> > 
> Well yes, of course it is. I'm not asking whether an iXML processor
> needs to be able to handle left recursion or not. I'm asking about
> methods for rewriting iXML grammars to eliminate left recursion,
> while retaining the original parse structure in the XML output.

Substitution algorithms such as
https://www.geeksforgeeks.org/dsa/removing-direct-and-indirect-left-recursion-in-a-grammar/
can eliminate the left recursion but i’m not sure how to go about
proving whether it can be done without changing the iXML parse.

In practice, probably, but in theory, you might care about the wrapping
of non-leaf productions, and then no.

<word><word><word>boy</word>boy</word>boy</word>
is not the same as
<word>boy<word>boy<word>boy</word></word></word>

in, word ::= word "boy" | word;

vs
    word ::= boy | boy word;

and if this is a vald counterexample it’s enough to show it can’t be
done in all cases, but i’m not sure.

-- 
Liam Quin: Delightful Computing - Training and Consultancy in
XSLT / XML Markup / Typography / CSS / Accessibility / and more...
Outreach for the GNU Image Manipulation Program
Vintage art digital files - fromoldbooks.org

Received on Monday, 9 February 2026 22:37:15 UTC