Re: Recursive descent algorithm able to parse Python?

seberino@xxxxxxxxxxxxxxx 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.
.

Relevant Pages

  • Re: Recursive descent algorithm able to parse Python?
    ... Python is relatively simple to parse using a recursive descent parser. ... you're rolling your own as a learning exercise, the grammar for python is ... Todo lo que querías saber, y lo que ni imaginabas, ...
    (comp.lang.python)
  • Re: Is pyparsing really a recursive descent parser?
    ... there are grammars it can't parse that my recursive descent parser would ... parse, ... grammar = OneOrMore) + Literal ... Why does pyparsing fail to parse ...
    (comp.lang.python)
  • ANN: cssutils 0.9.4b1
    ... CSS validator (and according the selector spec - I hope;). ... IE and Safari nevertheless seem to parse this rule as ``a b`` so as if a space would be present. ... cssutils now parses this selector as intented by the spec as ``ab``. ... ``css.CSSRuleList`` is still a Python list but setting methods like ``__init__``, ``append``, ``extend`` or ``__setslice__`` are added later on instances of this class if so desired. ...
    (comp.lang.python.announce)
  • Re: Is pyparsing really a recursive descent parser?
    ... sorry unable to test it just now) as the PyParsing solution. ... The error is in the grammar. ... productions of your recursive descent parser so not only did I not follow ... are many ways to parse this correctly and pyparsing chooses none of these! ...
    (comp.lang.python)
  • Re: the annoying, verbose self
    ... Ruby speed will increase, don't worry, as more people will use it. ... correspond to the grammar used by the CPython parser. ... I will use the notations of the Grammar file used by the CPython parser. ... This problem vanishes with Python 3.0 which defines an own ellipsis literal: ...
    (comp.lang.python)