Hello Nicolas,
Thanks for your comments! Some of mine below.
> > IS_NULLABLE(rule) == e in pFIRST(rule)
> > IS_LEFTREC(rule). == rule inf pFIRST(rule)
>
> That first equation looks very shaky to me. It's not enough to have the
> empty string (epsilon) as a potential first expression. The issue is
> sequences. For instance: `X ::= a? b` has epsilon in FIRST, but is not
> nullable, since it has to at least match `b`.
>
The first rule should have been:
IS_NULLABLE(exp) == e in pFIRST(exp)
When applied to rules, exp should be the right hand side, which may be a
sequence.
In your example, `X ::= a? b`, `?a` is nullable, but `a? b` shuld not be as
it can never generate the empty sequence. The FIRST set should be {a, b}.
I'll add this example as a unit test.
> Regarding left-recursion, that does indeed work nicely.
>
> The way I formalize left-recursion in my thesis is that I say there exists
> a relationship `FIRST(A, B)` between the parsing expression `A` and `B` if
> `B` can be **directly** invoked by `A` at the same input position it was
> itself invoked at. This relationship gives you a directed graph and
> left-recursion is a loop in the graph.
>
Ah! I knew this must had been thought about before. In my proposal,
pFIRST(exp) may include non-terminals (which don't interfere with
terminals, and can safely be discarded if working towards LL(1) )
> Regarding your sets, I understand `FIRST` and `FOLLOW`, but what is the
> semantics of `LOOKAHEAD`? Is it like `FIRST`, but within a lookahead
> (positive only, or negative as well)?
>
LOKAHEAD is the k-concatenation of FIRST and FOLLOW in LL(k). It is needed
precisely to deal with rules that are nullable. I can't remember an example
for the need off the top of my head.
My interest in this approach is three-fold:
- The theoretical basis is much clearer because it's
algebraic/graph-based (as you explain above)
- Computation of FIRST/FOLLOW is well understood and there are simple
algorithms for it (like the one in TatSu)
- The above make it easier to implement PEG/leftrec in lower level
languages (like in C, which must be the target in my work to help with
next-generation Python compilation).
Best regards,
On Fri, 14 Jun 2019 at 02:07, Juancarlo Añez <[email protected]> wrote:
>
>> Hello,
>>
>> I tested the theory in the previous message, and it's looking good. The
>> only change required is to add a special token rules named on
>> right-hand-sides to the results returned on FIRST set computations. The
>> bold part after the '|' here:
>>
>> class RuleRef(Model):
>> def _first(self, k, f):
>> return f[self.name] *| {ref(self.name <http://self.name>)}*
>>
>> After that,
>>
>> def is_leftrec(rule):
>> return ref(rule.name) in rule.LL_LOOKAHEAD()
>>
>> Nullabillity is `() in exp.LL_LOOKAHEAD()`, and so on.
>>
>> Would anyone be interested in confirming these results?
>>
>> I'm interested because of the the LL lookahead algorithm is simple
>> enough to implement on my ongoing projects. This is FIRST:
>>
>> def _calc_first_sets(self, k=1):
>> f = defaultdict(set)
>> f1 = None
>> while f1 != f:
>> f1 = copy(f)
>> for rule in self.rules:
>> f[rule.name] |= rule._first(k, f)
>>
>> # cache results
>> for rule in self.rules:
>> rule._firstset = f[rule.name]
>>
>>
>> Regards,
>>
>>
>>
>> On Mon, Jun 10, 2019 at 5:20 PM Juancarlo Añez <[email protected]> wrote:
>>
>>> Hello,
>>>
>>> When looking at the resolutions of PEG/leftre with IS_NULLABLE,
>>> IS_LEFTREC, it occured to me that the same could be solved, perhaps in a
>>> more algebraic way, by using LL FIRST/FOLLOW analysis with the modification
>>> of allowing RHS symbols in the sets.
>>>
>>> IS_NULLABLE(rule) == e in pFIRST(rule)
>>> IS_LEFTREC(rule). == rule inf pFIRST(rule)
>>>
>>> Something like that.
>>>
>>> Has anyone explored this approach.
>>>
>>> TIA, and Cheers,
>>>
>>> --
>>> Juancarlo *Añez*
>>>
>>
>>
>> --
>> Juancarlo *Añez*
>> _______________________________________________
>> PEG mailing list
>> [email protected]
>> https://lists.csail.mit.edu/mailman/listinfo/peg
>>
> _______________________________________________
> PEG mailing list
> [email protected]
> https://lists.csail.mit.edu/mailman/listinfo/peg
>
--
Juancarlo *Añez*
_______________________________________________
PEG mailing list
[email protected]
https://lists.csail.mit.edu/mailman/listinfo/peg
