FAQ
Hello all,

I've been spending the last few weeks learning Python, and I've just
started to use it to write a simple BASIC compiler. I'm writing a
mathematical expression parser and wrote a function that would take a
string and split it into high level tokens.

The code can be found at http://pastebin.com/f757252ec (have a look at
the function tokenize).

I was interested to see if the tokenize function could be written in a
better way, so as to make better use of the Python language and
libraries. One thing that sprung to mind was whether it would be a
good idea to perhaps take advantage of regular expressions. I had a
look at a few compiler sites and regexps seem to come into that role
quite a bit. I've only done a little work on regexps and they seem
very powerful, but can easily get out of control!

So, any suggestions as to how to make better use of the language
writing something like this?

Thanks,

--Amr

Search Discussions

  • John Machin at May 7, 2009 at 3:11 am

    On May 7, 9:23?am, Amr wrote:
    Hello all,

    I've been spending the last few weeks learning Python, and I've just
    started to use it to write a simple BASIC compiler. I'm writing a
    mathematical expression parser and wrote a function that would take a
    string and split it into high level tokens.

    The code can be found athttp://pastebin.com/f757252ec(have a look at
    the function tokenize).
    It's always a good idea to describe to yourself what you are actually
    trying to achieve before you get too embrolied in the implementation
    details.

    Adding a few more tests like this:

    if __name__ == '__main__':
    tests = """\
    1 + 2 * 3
    (1 + 2) * 3
    1 + (2 * 3)
    !@#$%^
    foo = bar + zot
    foo=bar+zot
    xyzzy(bar, zot + 2.34)
    """
    for test in tests.splitlines():
    test = test.strip()
    e = Expression(test)
    result = e.tokenize(e.expression)
    print "%r => %r" % (test, result)

    produces this:
    '1 + 2 * 3' => ['1', '+', '2', '*', '3']
    '(1 + 2) * 3' => ['1 + 2', '*', '3']
    '1 + (2 * 3)' => ['1', '+', '2 * 3']
    '!@#$%^' => ['!@#$%^']
    'foo = bar + zot' => ['foo', '=', 'bar', '+', 'zot']
    'foo=bar+zot' => ['foo=bar', '+', 'zot']
    'xyzzy(bar, zot + 2.34)' => ['xyzzy', 'bar, zot + 2.34']
    '' => []

    which indicates that your notions of what a token is and what you
    might use them for must be rather "interesting".

    Most other folks' tokenisers would have no concept of "bracket depth",
    would not throw the parentheses away, and would return not only the
    tokens but a classification as well e.g.

    'xyzzy' ID
    '(' LPAREN
    'bar' ID
    ',' LISTSEP
    'zot' ID
    '+' OPER
    '2.34' FLOAT_CONST
    ')' RPAREN

    I was interested to see if the tokenize function could be written in a
    better way, so as to make better use of the Python language and
    libraries. One thing that sprung to mind was whether it would be a
    good idea to perhaps take advantage of regular expressions. I had a
    look at a few compiler sites and regexps seem to come into that role
    quite a bit. I've only done a little work on regexps and they seem
    very powerful, but can easily get out of control!

    So, any suggestions as to how to make better use of the language
    writing something like this?
    There are various packages like pyparsing, plex, ply, ... which are
    all worth looking at. However if you want to get stuck into the
    details, you can lash up a quick and dirty lexer (tokeniser) using
    regexps in no time flat, e.g.

    an ID is matched by r"[A-Za-z_][A-Za-z0-9_]*"
    an INT_CONST is matched by r"[0-9]+"
    an OPER is matched by r"[-+/*]"
    etc
    so you set up a (longish) re containing all the alternatives
    surrounded by capturing parentheses and separated by "|".

    r"([A-Za-z_][A-Za-z0-9_]*)|([0-9]+)|([-+/*])etc"

    Hint: don't do it manually, use ")|(".join()

    and you just step through your input string:
    1. skip over any leading whitespace
    2. look for a match of your re starting at current offset
    3. matchobj.lastindex gives you 0 if it's an ID, 1 if it's an
    INT_CONST, etc
    4. save the slice that represents the token
    5. adjust offset, loop around until you hit the end of the input

    Hint: the order in which you list the alternatives can matter a lot
    e.g. you better have "<=" before "<" otherwise it would regard "<=" as
    comprising two tokens "<" and "="

    HTH,
    John
  • Amr at May 7, 2009 at 7:04 pm
    Hi John,

    Thanks for the tips, I will check them out.

    --Amr

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedMay 6, '09 at 11:23p
activeMay 7, '09 at 7:04p
posts3
users2
websitepython.org

2 users in discussion

Amr: 2 posts John Machin: 1 post

People

Translate

site design / logo © 2022 Grokbase