Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Recursive descent algorithm able to parse Python?

Reply
Thread Tools

Recursive descent algorithm able to parse Python?

 
 
seberino@spawar.navy.mil
Guest
Posts: n/a
 
      09-28-2006
I'm a compiler newbie and curious if Python grammar is able to
be parsed by a recursive descent parser or if it requires
a more powerful algorithm.

Chris

 
Reply With Quote
 
 
 
 
Michael
Guest
Posts: n/a
 
      09-28-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> I'm a compiler newbie and curious if Python grammar is able to
> be parsed by a recursive descent parser or if it requires
> a more powerful algorithm.


Python is relatively simple to parse using a recursive descent parser. If
you're rolling your own as a learning exercise, the grammar for python is
included in one of the top level directories of the source distribution for
python.

The one area that is slightly different from usual is the emitting of INDENT
and DEDENT tokens by the lexer due to handling of whitespace. But that's
not really that complex either.

A couple of years ago I decided to see what it would be like to try to parse
a python-like language with no keywords and to see if you could do it test
first (for fun . If you do this, you discover the grammar is very short
but you need terminator tokens to close if..elif...elif...else... like
statements (eg if..elif...elif...else...end,
try...except...except...except...endtry).

I put that code up here: http://cerenity.org/SWP/ if you're curious.
That and the python grammar file should probably help you roll your own
parser. (It emits an AST that assumes everything is a function. I was
pondering giving it a lisp backend or transforming to lisp but never
got a round tuit)

If however you're doing this because you're not aware of the compiler
module, it's worth knowing that compiler.parse is a pretty useful
function


Michael.
 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      09-28-2006
(E-Mail Removed) schrieb:
> I'm a compiler newbie and curious if Python grammar is able to
> be parsed by a recursive descent parser or if it requires
> a more powerful algorithm.


I might be mistaken, but isn't recursive descent one of the more
powerful parsing techniques - for the price of non-linearity and even
potentially non-termination?

Under that assumption: certainly!

Diez
 
Reply With Quote
 
Lawrence D'Oliveiro
Guest
Posts: n/a
 
      09-28-2006
In message <(E-Mail Removed)>, Diez B. Roggisch wrote:

> (E-Mail Removed) schrieb:
>> I'm a compiler newbie and curious if Python grammar is able to
>> be parsed by a recursive descent parser or if it requires
>> a more powerful algorithm.

>
> I might be mistaken, but isn't recursive descent one of the more
> powerful parsing techniques - for the price of non-linearity and even
> potentially non-termination?


No, you're thinking of LR(k) bottom-up parsers. Recursive descent is a
top-down parser--might be the same thing as LL(1), I'm not sure. It's easy
to implement and easy to understand, to the point where there is strong
pressure on programming-language designers to make sure their languages can
be parsed with recursive descent.
 
Reply With Quote
 
Gabriel Genellina
Guest
Posts: n/a
 
      09-29-2006
At Thursday 28/9/2006 17:00, Michael wrote:

>(E-Mail Removed) wrote:
>
> > I'm a compiler newbie and curious if Python grammar is able to
> > be parsed by a recursive descent parser or if it requires
> > a more powerful algorithm.

>
>Python is relatively simple to parse using a recursive descent parser. If
>you're rolling your own as a learning exercise, the grammar for python is
>included in one of the top level directories of the source distribution for
>python.


And it will stay so. From PEP 3099: "The parser won't be more complex
than LL(1). Simple is better than complex. This idea extends to the
parser. Restricting Python's grammar to an LL(1) parser is a
blessing, not a curse. It puts us in handcuffs that prevent us from
going overboard and ending up with funky grammar rules like some
other dynamic languages that will go unnamed, like Perl."



Gabriel Genellina
Softlab SRL





__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya!
http://www.yahoo.com.ar/respuestas

 
Reply With Quote
 
Diez B. Roggisch
Guest
Posts: n/a
 
      09-29-2006
Lawrence D'Oliveiro wrote:

> In message <(E-Mail Removed)>, Diez B. Roggisch wrote:
>
>> (E-Mail Removed) schrieb:
>>> I'm a compiler newbie and curious if Python grammar is able to
>>> be parsed by a recursive descent parser or if it requires
>>> a more powerful algorithm.

>>
>> I might be mistaken, but isn't recursive descent one of the more
>> powerful parsing techniques - for the price of non-linearity and even
>> potentially non-termination?

>
> No, you're thinking of LR(k) bottom-up parsers. Recursive descent is a


No, I'm not.

> top-down parser--might be the same thing as LL(1), I'm not sure. It's easy
> to implement and easy to understand, to the point where there is strong
> pressure on programming-language designers to make sure their languages
> can be parsed with recursive descent.


http://en.wikipedia.org/wiki/Recursive_descent_parser

"""
Recursive descent with backup is a technique that determines which
production to use by trying each production in turn. Recursive descent with
backup is not limited to LL(k) grammars, but is not guaranteed to terminate
unless the grammar is LL(k). Even when they terminate, parsers that use
recursive descent with backup may require exponential time.
"""

I have to admit that I have difficulties to compare LR(k) to recursive
descent, but the fact that the latter contains backtracking makes it at
least more powerful than LL(k)

Diez
 
Reply With Quote
 
Lawrence D'Oliveiro
Guest
Posts: n/a
 
      10-06-2006
In message <(E-Mail Removed)>, Diez B. Roggisch wrote:

> I have to admit that I have difficulties to compare LR(k) to recursive
> descent, but the fact that the latter contains backtracking makes it at
> least more powerful than LL(k)


LR(k) is more powerful than LL(k).
 
Reply With Quote
 
Piet van Oostrum
Guest
Posts: n/a
 
      10-06-2006
>>>>> "Diez B. Roggisch" <(E-Mail Removed)> (DBR) wrote:

>DBR> http://en.wikipedia.org/wiki/Recursive_descent_parser


>DBR> """
>DBR> Recursive descent with backup is a technique that determines which
>DBR> production to use by trying each production in turn. Recursive
>DBR> descent with backup is not limited to LL(k) grammars, but is not
>DBR> guaranteed to terminate unless the grammar is LL(k). Even when they
>DBR> terminate, parsers that use recursive descent with backup may require
>DBR> exponential time.
>DBR> """


This is the first time I see this called `backup'. I have always used and
seen the term `backtracking'.
--
Piet van Oostrum <(E-Mail Removed)>
URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C4]
Private email: (E-Mail Removed)
 
Reply With Quote
 
Diez B. Roggisch
Guest
Posts: n/a
 
      10-06-2006
Lawrence D'Oliveiro schrieb:
> In message <(E-Mail Removed)>, Diez B. Roggisch wrote:
>
>> I have to admit that I have difficulties to compare LR(k) to recursive
>> descent, but the fact that the latter contains backtracking makes it at
>> least more powerful than LL(k)

>
> LR(k) is more powerful than LL(k).


I know _that_, the point was that recursive descent is more power full
than LL(k)

Diez
 
Reply With Quote
 
hanumizzle
Guest
Posts: n/a
 
      10-07-2006
On 10/6/06, Diez B. Roggisch <(E-Mail Removed)> wrote:
> Lawrence D'Oliveiro schrieb:
> > In message <(E-Mail Removed)>, Diez B. Roggisch wrote:
> >
> >> I have to admit that I have difficulties to compare LR(k) to recursive
> >> descent, but the fact that the latter contains backtracking makes it at
> >> least more powerful than LL(k)

> >
> > LR(k) is more powerful than LL(k).

>
> I know _that_, the point was that recursive descent is more power full
> than LL(k)


Correct me if I'm wrong, but recursive descent parsers are top-down, yes?

Parse::RecDescent in Perl is a top-down parser. It can even do some
context-sensitive grammars and can almost certainly handle Python.

Is Python context-free? Not sure. Does left parenthesis opening either
a function call (x) or an empty tuple () count as context-sensitive,
for instance? Or can () be considered a terminal symbol unto itself?

I am new to most of this

-- Theerasak
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is pyparsing really a recursive descent parser? Just Another Victim of the Ambient Morality Python 39 11-09-2007 04:19 AM
Can recursive descent parser handle Python grammar? seberino@spawar.navy.mil Python 4 10-02-2006 08:58 AM
[Snippet] a Recursive Descent Parser via TDD - recursiveDescentParser.h Phlip C++ 6 08-05-2004 03:12 AM
[Snippet] a Recursive Descent Parser via TDD - test.h Phlip C++ 0 08-02-2004 07:59 PM
[Snippet] a Recursive Descent Parser via TDD - recursiveDescentParser.cpp Phlip C++ 0 08-02-2004 07:48 PM



Advertisments