Recursive descent algorithm able to parse Python?

Discussion in 'Python' started by seberino@spawar.navy.mil, Sep 28, 2006.

  1. Guest

    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
    , Sep 28, 2006
    #1
    1. Advertising

  2. Michael Guest

    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.
    Michael, Sep 28, 2006
    #2
    1. Advertising

  3. 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
    Diez B. Roggisch, Sep 28, 2006
    #3
  4. In message <>, Diez B. Roggisch wrote:

    > 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.
    Lawrence D'Oliveiro, Sep 29, 2006
    #4
  5. At Thursday 28/9/2006 17:00, Michael wrote:

    > 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
    Gabriel Genellina, Sep 29, 2006
    #5
  6. Lawrence D'Oliveiro wrote:

    > In message <>, Diez B. Roggisch wrote:
    >
    >> 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
    Diez B. Roggisch, Sep 29, 2006
    #6
  7. In message <>, 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).
    Lawrence D'Oliveiro, Oct 6, 2006
    #7
  8. >>>>> "Diez B. Roggisch" <> (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 <>
    URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C4]
    Private email:
    Piet van Oostrum, Oct 6, 2006
    #8
  9. Lawrence D'Oliveiro schrieb:
    > In message <>, 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
    Diez B. Roggisch, Oct 6, 2006
    #9
  10. hanumizzle Guest

    On 10/6/06, Diez B. Roggisch <> wrote:
    > Lawrence D'Oliveiro schrieb:
    > > In message <>, 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
    hanumizzle, Oct 7, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Phlip
    Replies:
    0
    Views:
    460
    Phlip
    Aug 2, 2004
  2. Phlip
    Replies:
    6
    Views:
    429
    Phlip
    Aug 5, 2004
  3. Phlip
    Replies:
    0
    Views:
    421
    Phlip
    Aug 2, 2004
  4. Replies:
    4
    Views:
    454
    Ben Sizer
    Oct 2, 2006
  5. Just Another Victim of the Ambient Morality

    Is pyparsing really a recursive descent parser?

    Just Another Victim of the Ambient Morality, Nov 2, 2007, in forum: Python
    Replies:
    39
    Views:
    1,387
    Kay Schluehr
    Nov 9, 2007
Loading...

Share This Page