Subject: Recursive Descent-Friendly Languages

From: Shlomi Fish <[email-masked]>
Date: Mon, 13 May 2002 12:57:25 +0300 (IDT)

I had a talk with my SICP lecturer. He said that finite automata is a form
of programming which has proven to be very useful, and that formal
languages are an extension of them, that's only proved to be good for
CS-purposes. I told him that Yacc is an LALR parser generator and was
based on theory of formal languages.

What he said was this:
"Does Scheme needs Yacc?"
I said: "No."
"Does Pascal?"
I said: "No."
"Right, it is Recursive Descent. So maybe the problem is people design
languages which require the use of Yacc and friends."

This made me thinking. I know not all languages are RecDescent-friendly.
But I know that I like many languages that are not. Should we restrict
ourselves to designing languages that are easy to parse?

I started reading the Dragon Book, and read part of the chapter about
syntax analysis. (I stopped in the middle of the LR parsers, because it
became quite boring and I lost interest, so I skipped to the next chapter)
From what I remember RecDescent works like that: you keep a stack of the
syntax tree nodes, and you can tell what the next node would be right from
the next symbol you encounter. (it's an over-simplification, but I don't
remember the exact details now).

It is well known that Pascal's use of semi-colons is confusing: sometimes
you need them and sometimes the compiler will barf on you for putting
them. Does the fact that the last statement does not have a semicolon has
to do with keeping the language RecDescent-friendly?

Also, are perl's single-statement conditionals and loops, E.g:

print "Hello, $_!\n" for (1 .. 10);

compatible with RecDescent?

In any case, IMO, refraining from designing sexy languages, that people find
appealing, just because they require an LALR parser, is bad human
engineering. This touches a broader issue: should man adapt itself to the
machine, or should we adapt the machine to what the man expects?

I believe there should be a balance between the two. And from what I
understand the limitations of RecDescent, sticking to it, is not a good
balance. You necessarily refrain from designing a language that people
would have fun to work with, just so the computer will have less trouble
compiling it.

BTW, is RecDescent the reason Turbo Pascal (and its successors - Delphi
and Kylix) are so fast? When I worked with Delphi 1.0, I was amazed by the
computing speed, which made working with it much more fun. (almost like Perl
where I don't need to compile at all).

Regards,

	Shlomi Fish

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"

---

From: Tzafrir Cohen <[email-masked]>
Date: Mon, 13 May 2002 13:45:35 +0300 (IDT)

> based on theory of formal languages.

I believe that C is an example of such language. IIRC one of its design
goals was easy compilation, which also means easy parsing.

One of the first things you learn is a general Polynomial algorythm to
parse any context-free language (parse:=output a tree. yacc allows you to
run callbacks when you process some nodes of this tree to do something
useful other than producing a nifty tree).

This is, of course a good example for a case where "polynomail" simply
isn't good enough, as this algorith runs in O(n^3). parsing a "word" (say,
a C program) of 1000 "tokens" in around 1,000,000,000 time units is simply
not efficient enough. There neds to be a more efficient algorithm.
Preferebly something that works in one run.

LALR and recursive decent are actually two examples of subclasses of the
class of context-free grammers that can guarantee that. Therefore is a
language is either recursive decent or LALR you are guaranteed that it is
relatively easy to write a parser for this language.

IIRC recursive-descent languages are actually a subclass of LALR
languages.

> ourselves to designing languages that are easy to parse?

Is C hard to parse?

-- 
Tzafrir Cohen
mailto:[email-masked]
http://www.technion.ac.il/~tzafrir

---

From: Shlomi Fish <[email-masked]>
Date: Mon, 13 May 2002 13:54:08 +0300 (IDT)

> IIRC recursive-descent languages are actually a subclass of LALR

Of course that was the whole point. What my lecturer said was that
languages need to be designed so their grammar is RD-able. And that LALR
languages that are not RD-friendly, should be avoided at all cost.

> > ourselves to designing languages that are easy to parse?

Quite hard I assume. C statements can become very complex. AFAIK, C cannot
be parsed in a RecDescent fashion, and neither can Perl be. I believe Perl
5 has a LALR grammar defined for it somewhere (and it was actualy smaller
than Perl 4's), but IIRC, its parser uses Yacc. (but then again, I did not
delve too much into the Perl 5 internals).

Regards,

	Shlomi Fish

> To unsubscribe from this group, send an email to:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

---

From: "Nadav Har'El" <[email-masked]>
Date: Mon, 13 May 2002 16:35:31 +0300

On Mon, May 13, 2002, Shlomi Fish wrote about "[hackers-il] Recursive Descent-Friendly Languages":
>...
>...

Am I missing something? YACC was written in 1975 (!!), and was not the first
compiler-compiler tool (which is why it was named Yet Another Compiler
Compiler). So there is no almost no excuse to limiting computers languages to
more restrictive language families in 2002, when using YACC or many of its
alternatives is so easy and common.

"I didn't finish the LR chapter in the dragon book" or "yacc is complicated"
are really stupid excuses to limit your language's syntax. "the parser is
slow" is also usually silly (in most compilers, the slowest stages come after
the parse tree is already done). When efficiency is of utmost importance,
you usually limit your syntax even further - see for example postfix notation
("reverse polish notation") in Postscript or Forth [1].

So if there is no reason to put artificial limitations on your language's
syntax, why do it?

[1] http://www-2.cs.cmu.edu/~koopman/forth/hopl.html

P.S. Frankly, I didn't understand why you claim C's and Pascal's syntax
to be different as far as the parser-power needed. Can you give an example
of a C statement that shows this problem, and explain how Pascal doesn't
have that problem?

-- 
Nadav Har'El                        |        Monday, May 13 2002, 2 Sivan 5762
[email-masked]             |-----------------------------------------
Phone: +972-53-245868, ICQ 13349191 |I work for money. If you want loyalty,
http://nadav.harel.org.il           |buy yourself a dog.