Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2404 > unrolled thread

Re: How change grammar to equivalent LL(1) ?

Back to article view | Back to comp.compilers

Contents

  Re: How change grammar to equivalent LL(1) ? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-12-23 05:57 -0500
    Re: How change grammar to equivalent LL(1) ? Lasse Hillerøe Petersen <lhp+news@toft-hp.dk> - 2020-04-24 16:21 +0000
      Re: How change grammar to equivalent LL(1) ? Kaz Kylheku <773-297-7223@kylheku.com> - 2020-04-24 18:13 +0000
        Re: How change grammar to equivalent LL(1) ? silas poulson <Silas8642@hotmail.co.uk> - 2020-11-11 08:27 -0800

#2404 — Re: How change grammar to equivalent LL(1) ?

Just a slight comment on what
Lasse =?iso-8859-1?q?Hiller=F8e?= Petersen <lhp+news@toft-hp.dk> wrote:

The technique of changing:
Expr: num | num plus Expr;
to
Expr: num ExprTailOpt;  ExprTailOpt: plus Expr | /* empty */;
is called left-factoring.

By the way, "Opt" is the usual suffix for Ety.

--
******************************************************************************
Chris Clark                  email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc.  Web Site: http://world.std.com/~compres
23 Bailey Rd                 voice: (508) 435-5016
Berlin, MA  01503 USA      twitter: @intel_chris
------------------------------------------------------------------------------

[toc] | [next] | [standalone]

#2512

I know this is a very late reply, however, I sometimes forget to read
Usenet news for a while, I hope the moderator is forgiving.

On Mon, 23 Dec 2019 05:57:50 -0500, Christopher F Clark wrote:

> Just a slight comment on what Lasse Hiller�e Petersen
> <lhp+news@toft-hp.dk> wrote:

> is called left-factoring.

I am aware, however the point was having the refactored action return a
function to adjust the direction of the parse tree. I am sure LISPers and
Schemers wouldn't consider this anything special (so ordinary perhaps
even, that I hadn't been able to find any written mention of it, until
today), but when I wrote it back in 2017 I looked at my code and thought
"hey, that's actually neat and general."

Only today did I actually manage to find a paper, which, although I am
very rusty in the matter of formal proofs and theory, being just an
amateur hacker, to me reads like the theory behind "my" method:

Thielecke, Hayo. (2012). Functional semantics of parsing actions, and
left recursion elimination as continuation passing. PPDP'12 - Proceedings
of the 2012 ACM SIGPLAN Principles and Practice of Declarative
Programming. 91-102. 10.1145/2370776.2370789.


> By the way, "Opt" is the usual suffix for Ety.

Not in the Algol68 Reports IIRC. ;-)

/Lasse
[Your moderator tends to draw the line at replies to messages
posted 15 or 20 years ago, generally via Google Groups. -John]

[toc] | [prev] | [next] | [standalone]

#2513

On 2020-04-24, Lasse Hiller�e Petersen <lhp+news@toft-hp.dk> wrote:
> I know this is a very late reply, however, I sometimes forget to read
> Usenet news for a while, I hope the moderator is forgiving.
>
> On Mon, 23 Dec 2019 05:57:50 -0500, Christopher F Clark wrote:
>
>> Just a slight comment on what Lasse Hiller�e Petersen
>> <lhp+news@toft-hp.dk> wrote:
>
>> is called left-factoring.
>
> I am aware, however the point was having the refactored action return a
> function to adjust the direction of the parse tree. I am sure LISPers and
> Schemers wouldn't consider this anything special (so ordinary perhaps
> even, that I hadn't been able to find any written mention of it, until
> today), but when I wrote it back in 2017 I looked at my code and thought
> "hey, that's actually neat and general."
>
> Only today did I actually manage to find a paper, which, although I am
> very rusty in the matter of formal proofs and theory, being just an
> amateur hacker, to me reads like the theory behind "my" method:
>
> Thielecke, Hayo. (2012). Functional semantics of parsing actions, and
> left recursion elimination as continuation passing. PPDP'12 - Proceedings
> of the 2012 ACM SIGPLAN Principles and Practice of Declarative
> Programming. 91-102. 10.1145/2370776.2370789.

Both left and right recursion elimination are related to tail
optimization and continuation passing.

In a shift-reduce LALR(1) parser, right recursion consumes parser stack
space. If you can refactor it to left recursion, it becomes stackless.

There is also a strong connection to the "reduce" or "fold" function in
functional programming. We can linguistically identify the "reduce" in a
LALR(1) parser with "reduce", the function.

"reduce" takes an accumulator, initialized to some value, and then
decimates a sequence by repeatedly passing the accumulator as
the left argument to a function, and the successive items of the
sequence as the right argument. For each successive call, the return
value of the previous call is used as the accumulator.

If we write a left-recursive calculator using a parser generator, say
with addition as the binary op:

   expr : expr '+' expr  { $$ = $1 + $3; }
        | expr           { $$ = $1; }
        ;

  expr : initial_value { $$ = $1 }
       ;

this behaves like an iterative reduce over an input like '1 + 2 + 3 ...'.

The accumulator is seeded with 1, and then threaded through the
successive reductions without consuming parser stack space.

Fold/reduce, grammar reductions, continuations and (tail-)recursion
are all closely related.

If a compiler's target run-time is continuation-based, then stackless
tail calls are trivial to implement. All functions return by invoking
their continuation already, and so to make a tail call to a function,
you just call it, and give it your *own* continuation as the
continuation argument. If that function invokes that continuationm, it
will "return" to wherever you would have returned.
To generate a regular non-tail call which will return back to the
caller, the caller captures a local continuation and gives the callee
that one.

The accumulator object in a reduce is a kind of continuation: it
summarizes everything that has been done so far, so the calculation can
continue withut having to regress anywhere. Old values of the
accumulator are never revisited, so the reduce job can be done
iteratively: by assigning the new accumulator value over the old one.
That is easily achieved without assignment by tail recursion.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]

#2618

An even later response, but thought quote from course notes (§5.6.5
available here <http://cs.rhul.ac.uk/courses/CS3470/>) I'm currently
pursuing might be useful.

*LL(1) grammars*
Grammars which admit non-back-tracking top down LL(1) parsers are
 precisely the ones which are left factored, follow determined and have
 no left recursion.

Thus we have the following definition: A context-free grammar is LL(1) if
for all non-terminals A and productions A ::= α|β we have
1. first(α) ∩ first(β) = ∅
2. If A ∗⇒ ε then first(A) ∩ follow(A) =∅.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web