[Oberon] How2 calculate First and Follow and check if LL(1)

John R. Strohm strohm at airmail.net
Mon Jul 18 22:45:55 CEST 2016


As I recall, ANTLR generates parsers for LL(1) languages.

yacc generates parsers for LALR(1) languages.

COCO/R generates parsers for LL(k) languages.  There is an old version for Oberon.

Wirth strongly prefers handmade recursive descent parsers, in part because languages that can be parsed easily by a handmade recursive descent parser tend to be quite a bit simpler and cleaner than languages that "requires" a machine-built LR(1) (or higher: JOVIAL was LR(2), if I remember correctly) parser.  PASCAL, Modula-2, and Oberon certainly meet that criteria when compared to C and C++ and their ilk.

--- sinu.nayak2001 at gmail.com wrote:

From: Srinivas Nayak <sinu.nayak2001 at gmail.com>
To: ETH Oberon and related systems <oberon at lists.inf.ethz.ch>
Subject: Re: [Oberon] How2 calculate First and Follow and check if LL(1)
Date: Mon, 18 Jul 2016 22:38:36 +0530

Dear Jorg and John,

You both are correct.

At least I got to know that we have EBNF parsing program.
But we don't have a program to calculate First and Follow.
Otherwise, you already would have mentioned it...

Nicely without mentioning the word LL(1), professor Wirth explained
what should be the characteristics of a language,
so that it can easily be parsed using recursive descent parsing.
He gave 3-4 rules of thumb and manually calculated First and Follow.

No doubt, with Oberon like small/elegant language,
one doesn't need to use machine to calculate First and Follow
and to check LL(1) mechanically. It can be done manually.
Mechanically calculating First and Follow is mostly needed for
table driven parsers. For us not.

I could see, because of unwanted complexity, Wirth intentionally
refrained from detailing those and using the mechanical means,
which is never needed for language implementer, but rather
needed for the language designer, when language is LL(1).

But I was little curious if we already have any
mechanized program; so that, in case I want to play
creating dialects of Oberon, I will have easy means to check my dialect.

Another angle to my query was, if these algorithms can easily be
inter woven with our EBNF parser... Those books present the algorithm
in purest form. But I wanted to know, if using attributed grammar
and our EBNF parser, it is easy to get the job done... If yes,
how should we start about it.

And yes, from another angle, I wanted to know, if someone has ever tried to do so...


With thanks and best regards,

Yours sincerely,
Srinivas Nayak

Home: http://www.mathmeth.com/sn/
Blog: http://srinivas-nayak.blogspot.in/

On 07/18/2016 06:01 PM, John R. Strohm wrote:
> Calculation of First and Follow is covered in the Green Dragon Book.  I'd expect it to be covered in the later books as well.
>
> And, as always, Google is your FRIEND.  "first follow sets"
>
> -----Original Message----- From: Srinivas Nayak
> Sent: Sunday, July 17, 2016 8:52 PM
> To: ETH Oberon and related systems
> Subject: [Oberon] How2 calculate First and Follow and check if LL(1)
>
> Dear All,
>
> Lets say I want to modify Oberon language.
> I would then like to check if my modified language is LL(1).
> Towards that end, I would also like to calculate First and
> Follow set of symbols for each of my non-terminals.
>
> I see a nice program EBNF.Mod
> How can I modify this program to
> 1. calculate First and Follow set of symbols for each of my non-terminals.
> 2. check if my language is LL(1)
>
>
>
> With thanks and best regards,
>
> Yours sincerely,
> Srinivas Nayak
>
> Home: http://www.mathmeth.com/sn/
> Blog: http://srinivas-nayak.blogspot.in/
> --
> Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
> https://lists.inf.ethz.ch/mailman/listinfo/oberon
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
> --
> Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
> https://lists.inf.ethz.ch/mailman/listinfo/oberon
>
--
Oberon at lists.inf.ethz.ch mailing list for ETH Oberon and related systems
https://lists.inf.ethz.ch/mailman/listinfo/oberon




More information about the Oberon mailing list