Question in Implementing Functional Languages 
Author Message
 Question in Implementing Functional Languages

    As I mentioned quite a while back, I had been trying to write a compiler
based on the book "Implementing Functional Languages" by Peyton-Jones
and Lester.   Since I'm doing this more or less for the fun of it,
and since there aren't people working in the area of functional
languages here, I thought I would post it to the net.   For those
who don't want to read a "novice" post, please hit 'n' now.

    Basically, I have managed to get through the first chapter.
The main problem I have is the section labelled "eliminating
left recursion".   The grammar used to represent the Core
language looks something like

       expr ::==   expr aexpr | ... (various alternatives)

    Now, the book suggest that to eliminate left recursion,
one should use:

       expr ::== (aexpr)*

where * is 0 or more repetitions.   This seems a bit peculiar.
I found a book on compilers (recall this is my first time
trying to write any kind of compiler) which said that one
eliminates left recursion as follows.   If the expression is:

      A ::== B | A R

then it can be replaced by

      A ::== B (A)*

   The only way I can see that the non left recursive
grammar could be reduced to  expr ::== (aexpr)* is if
the original grammar was something like
expr ::== aexpr | (aexpr)* which it is not.

    The other question I have is what this even means.
The other valid expressions in the Core language are
such things as case statements, let statements, letrec
statements, lambda expressions, etc.   These are
reasonably straightforward.   However, the
expr ::== expr aexpr part has me baffled.   Could some-
one enlighten me on what this is supposed to represent.

--
Charles Lin



Sun, 30 Jun 1996 09:26:46 GMT  
 Question in Implementing Functional Languages

:
:     As I mentioned quite a while back, I had been trying to write a compiler
: based on the book "Implementing Functional Languages" by Peyton-Jones
: and Lester.   Since I'm doing this more or less for the fun of it,
: and since there aren't people working in the area of functional
: languages here, I thought I would post it to the net.   For those
: who don't want to read a "novice" post, please hit 'n' now.

Don't be so modest.
:
:     Basically, I have managed to get through the first chapter.
: The main problem I have is the section labelled "eliminating
: left recursion".   The grammar used to represent the Core
: language looks something like
:
:        expr ::==   expr aexpr | ... (various alternatives)
:
:     Now, the book suggest that to eliminate left recursion,
: one should use:
:
:        expr ::== (aexpr)*

This is the way to eliminate left recursion, except that the
" ... (various alternatives)" has been left out.  The correct
way, as you have noticed, is indeed

        expr ::= ... (verious alternatives) (aexpre)*

:
: where * is 0 or more repetitions.   This seems a bit peculiar.
: I found a book on compilers (recall this is my first time

It may be the first time, but your common sense can be trusted.

: trying to write any kind of compiler) which said that one
: eliminates left recursion as follows.   If the expression is:
:
...
...
: --
: Charles Lin

--
-------------------------------------------------------
Try one or more of the following addresses to reply.

at home:        uunet!ozrout!topoi!hendrik



Tue, 02 Jul 1996 21:53:54 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Sigma, an interpreted functional programming language implemented in C++

2. Textbooks on implementing functional languages

3. Implementing Functional Languages

4. implementing functional languages with combinatory logics

5. books/papers on implementing strict functional languages

6. non-functional syntax in a mostly functional language

7. Questions about functional languages

8. A general question about scheme and functional languages

9. Speed of FP languages, prospects (was Re: Benchmarking Lazy Functional Languages)

10. Implementing Functional Compilers/Interpreters

11. Implementing OO languages

12. Which languages implement full laziness?

 

 
Powered by phpBB® Forum Software