Re: Indirect left recursion in iXML grammars

On Monday 09 February 2026 18:13:20 (+01:00), Steven Pemberton wrote:

> 
> This is what I mean by ixml can handle left-recursion:

To be even clearer:

"Processors must accept and parse any conforming grammar, and produce at least one parse of supplied input that matches the grammar starting at the root symbol. "


A processor is *required* to deal with left recursion.


Steven


> 
> 
> steven@steven-XPS-9320$ cat left.ixml
> ants: antstring.
> antstring: antstring, "ant"; {}.
> steven@steven-XPS-9320$ cat left.inp
> antantant
> 
> steven@steven-XPS-9320$ ixml left
> 
> <ants>
>    <antstring>
>       <antstring>
>          <antstring>
>             <antstring/>ant</antstring>ant</antstring>ant</antstring>
> </ants>
> steven@steven-XPS-9320:~/Common/ixml/tests/misc$ 
> 
> 
> On Monday 09 February 2026 17:14:33 (+01:00), Norm Tovey-Walsh wrote:
> 
> > Steven Pemberton <steven.pemberton@cwi.nl> writes:
> > > It's true that some parsing algorithms can't handle left-recursion, but ixml can, so again, I'm not sure what the use-case is here.
> > 
> > I’m not sure what you mean by “iXML can handle left-recursion”. The grammar can express left-recursive structures, sure, but it isn’t a parsing technology. (Maybe it could be, but I’m not aware of any “native iXML parsers”; all of the implementations I’ve seen implement iXML on top of Early or GLL or some other (combination of) parsers.)
> > 
> > If you want to implement iXML, you have to choose a parsing technology that can support hidden left recursion or you have to remove it somehow. I think the question here is, can it be removed in a way that preserves the structure of the original grammar.
> > 
> >                                         Be seeing you,
> >                                           norm
> > 
> > --
> > Norm Tovey-Walsh
> > Saxonica
> > 
> 
>

Received on Monday, 9 February 2026 17:17:31 UTC