>> Do you have any idea on the natural resulting data structure? It's not
>> clear how trees should be implemented in TeX.
>
> I would suggest just return a token sequence, into which the TeX commands
> the user specified has been inserted to reflect the aspects of the structure
> that he's interested in. A silly example might be something like
>
> \begin{Sentence}\begin{NounPhrase}My
> \begin{Noun}hovercraft\end{Noun}\end{NounPhrase}
> \begin{VerbPhrase}\begin{Verb}is\end{Verb} full
> \begin{PrepositionalPhrase}of
> \begin{Noun}eels\end{Noun}\end{PrepositionalPhrase}\end{VerbPhrase}.\end{Sentence}
>
> It seems to be a fairly standard extension that something inside braces in
> an PEG means "When passing through here upon matching, then insert this
> piece of material." An awkward point is however that you'd often want to
> insert an opening brace at one point and a closing brace a bit later -- for
> example to make that \Noun{hovercraft} rather than the less flexible
> \begin{Noun}hovercraft\end{Noun} -- which is not obvious how to express.

My main problem was the insertion of { and }. We cannot do that
directly, of course, and need to walk an extra mile. A reasonable but
ugly approach is to insert " { \iffalse } \fi " instead of " { " and "
\iffalse { \fi } " instead of " } ", also putting every other piece of
material within "\unexpanded", then once the token list is built,
\edef the whole thing to get braces right. Of course, there needs to
be a check (before \edef-ing) that the result will be brace balanced.

I will probably implement PEGs at some point, but it is unlikely that
I do it before I finish rewriting l3fp (so count a few months).

> I'd be inclined to consider a grammar with a left recursion loop a
> programming error, just like it is for ordinary TeX macros. There is a
> transformation of PEGs that turn left-recursion into runtime match failures
> rather than infinite loops, but I don't know how complicated it is, and I
> suspect it's mainly interesting when the PEG effectively gets compiled to
> machine code. LaTeX already runs inside the TeX virtual machine, so an
> infinite loop is not that fatal.

Detecting left-recursion should be easy, and then I'll just raise an
error, and possibly try to behave in a sensible way (not loop
eternally). The problem is not that different from epsilon-transitions
in an NFA running in a loop.

> And exchanging the sets of initial and final states. Yes, that's all there
> is to it. (I assume you don't worry about submatch capturing there anyway.)
>
>> but the
>> representation I have makes that non-trivial).
>
> It is often there that the crux lies.

Indeed, I don't need to keep track of submatches. Some more thoughts
about that this weekend.

Regards,
Bruno