Parsing: request for pointers

Discussion in 'Python' started by André, Nov 11, 2008.

  1. André

    André Guest

    Hi everyone,

    I would like to implement a parser for a mini-language
    and would appreciate some pointers. The type of
    text I would like to parse is an extension of:

    http://www.websequencediagrams.com/examples.html

    For those that don't want to go to the link, consider
    the following, *very* simplified, example:
    =======

    programmer Guido
    programmer "Fredrik Lundh" as effbot
    programmer "Alex Martelli" as martellibot
    programmer "Tim Peters" as timbot
    note left of effbot: cutting sense of humor
    note over martellibot:
    Offers detailed note, explaining a problem,
    accompanied by culinary diversion
    to the delight of the reader
    note over timbot: programmer "clever" as fox
    timbot -> Guido: I give you doctest
    Guido --> timbot: Have you checked my time machine?

    =======
    From this, I would like to be able to extract
    ("programmer", "Guido")
    ("programmer as", "Fredrik Lundh", "effbot")
    ....
    ("note left of", "effbot", "cutting sense of humor")
    ("note over", "martellibot", "Offers...")
    ("note over", "timbot", 'programmer "clever" as fox')

    Some observations:
    1. I want to use indentation to identify blocks.
    (the site I referred to uses "end note" which I don't want)
    2. "keywords" (such as "programmer", "note over")
    can appear in text, and should not then be misidentified
    3. I was thinking of using http://effbot.org/zone/simple-top-down-parsing.htm
    as a guide; however, it is not clear to me how it could be
    adapted to handle observations 1 and 2. (If it "easily" could,
    just a few pointers would be enough, and I'll start from there...)
    4. I want to do this only using modules in the standard Python
    library, as I want to use this to learn about the basics
    of parsing. So, please don't *simply* suggest to use a
    third-party module, such as
    [1] plex, [2] yapps, [3] pyparsing
    The learning journey is more important for me than just
    having a canned solution to my (current) parsing problem.

    Cheers,

    André

    [1] http://www.cosc.canterbury.ac.nz/greg.ewing/python/Plex/
    [2] http://theory.stanford.edu/~amitp/yapps/
    [3] http://pyparsing.wikispaces.com/
    André, Nov 11, 2008
    #1
    1. Advertising

  2. On Tue, 11 Nov 2008 11:59:50 -0800, André wrote:

    > 4. I want to do this only using modules in the standard Python
    > library, as I want to use this to learn about the basics of parsing.
    > So, please don't *simply* suggest to use a third-party module, such
    > as
    > [1] plex, [2] yapps, [3] pyparsing
    > The learning journey is more important for me than just having a
    > canned solution to my (current) parsing problem.


    Believe me, there is no canned solution to your current parsing problem.
    Once you have a parser engine (e.g. pyparsing) you still have to build a
    parser, and that's not necessarily trivial.

    Other than that, try this:

    http://docs.python.org/library/shlex.html



    --
    Steven
    Steven D'Aprano, Nov 12, 2008
    #2
    1. Advertising

  3. André

    Paul McGuire Guest

    On Nov 11, 1:59 pm, André <> wrote:
    > Hi everyone,
    >
    > I would like to implement a parser for a mini-language
    > and would appreciate some pointers.  The type of
    > text I would like to parse is an extension of:
    >
    > http://www.websequencediagrams.com/examples.html
    >
    > For those that don't want to go to the link, consider
    > the following, *very* simplified, example:
    > =======
    >
    > programmer Guido
    > programmer "Fredrik Lundh" as effbot
    > programmer "Alex Martelli" as martellibot
    > programmer "Tim Peters" as timbot
    > note left of effbot: cutting sense of humor
    > note over martellibot:
    >     Offers detailed note, explaining a problem,
    >     accompanied by culinary diversion
    >     to the delight of the reader
    > note over timbot: programmer "clever" as fox
    > timbot -> Guido: I give you doctest
    > Guido --> timbot: Have you checked my time machine?
    >
    > =======
    > From this, I would like to be able to extract
    > ("programmer", "Guido")
    > ("programmer as", "Fredrik Lundh", "effbot")
    > ...
    > ("note left of", "effbot", "cutting sense of humor")
    > ("note over", "martellibot", "Offers...")
    > ("note over", "timbot", 'programmer "clever" as fox')
    >


    Even if you choose not to use pyparsing, a pyparsing example might
    give you some insights into your problem. See how the grammar is
    built up from separate pieces. Parse actions in pyparsing implement
    callbacks to do parse-time conversion - in this case, the multiline
    note body is converted from the parsed list of separate strings into a
    single newline-separated string.

    Here is the pyparsing example:

    from pyparsing import Suppress, Combine, LineEnd, Word, alphas,
    alphanums,\
    quotedString, Keyword, Optional, oneOf, restOfLine, indentedBlock,
    \
    removeQuotes,empty,OneOrMore,Group

    # used to manage indentation levels when parsing indented blocks
    indentstack = [1]

    # define some basic punctuation and terminal words
    COLON = Suppress(":")
    ARROW = Combine(Word('-')+'>')
    NL = LineEnd().suppress()
    ident = Word(alphas,alphanums+"-_")
    quotedString.setParseAction(removeQuotes)

    # programmer definition
    progDefn = Keyword("programmer") + Optional(quotedString("alias") + \
    Optional("as")) + ident("name")

    # new pyparsing idiom - embed simple asserts to verify bits of the
    # overall grammar in isolation
    assert "programmer Guido" == progDefn
    assert 'programmer "Tim Peters" as timbot' == progDefn

    # note specification - only complicated part is the indented block
    # form of the note we use a pyparsing parse action to convert the
    # nested token lists into a multiline string
    OF = Optional("of")
    notelocn = oneOf("over under") | "left" + OF | "right" + OF
    notetext = restOfLine.setName("notetext")
    noteblock = indentedBlock(notetext, indentstack).setName("noteblock")
    noteblock.setParseAction(lambda t:'\n'.join(tt[0] for tt in t[0]))
    note = Keyword("note") + notelocn("location") + ident("subject") +
    COLON + \
    (~NL + empty + notetext("note") | noteblock("note") )
    assert 'note over timbot: programmer "clever" as fox ' == note

    # message definition
    msg = ident("from") + ARROW + ident("to") + COLON + empty + notetext
    ("note")
    assert 'Guido --> timbot: Have you checked my time machine?' == msg

    # a seqstatement is one of these 3 types of statements
    seqStatement = progDefn | note | msg

    # parse the sample text
    parsedStatements = OneOrMore(Group(seqStatement)).parseString(seqtext)

    # print out token/field dumps for each statement
    for s in parsedStatements:
    print s.dump()

    Prints:

    ['programmer', 'Guido']
    - name: Guido
    ['programmer', 'Fredrik Lundh', 'as', 'effbot']
    - alias: Fredrik Lundh
    - name: effbot
    ['programmer', 'Alex Martelli', 'as', 'martellibot']
    - alias: Alex Martelli
    - name: martellibot
    ['programmer', 'Tim Peters', 'as', 'timbot']
    - alias: Tim Peters
    - name: timbot
    ['note', 'left', 'of', 'effbot', 'cutting sense of humor ']
    - location: left
    - note: cutting sense of humor
    - subject: effbot
    ['note', 'over', 'martellibot', 'Offers ...']
    - location: over
    - note: Offers detailed note, explaining a problem,
    accompanied by culinary diversion
    to the delight of the reader
    - subject: martellibot
    ['note', 'over', 'timbot', 'programmer "clever" as fox ']
    - location: over
    - note: programmer "clever" as fox
    - subject: timbot
    ['timbot', '->', 'Guido', 'I give you doctest ']
    - from: timbot
    - note: I give you doctest
    - to: Guido
    ['Guido', '-->', 'timbot', 'Have you checked my time machine?']
    - from: Guido
    - note: Have you checked my time machine?
    - to: timbot

    Best of luck in your project,
    -- Paul
    Paul McGuire, Nov 13, 2008
    #3
    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. Brian Birtle
    Replies:
    2
    Views:
    1,981
    John Saunders
    Oct 16, 2003
  2. Phil
    Replies:
    1
    Views:
    634
    llewelly
    Sep 16, 2003
  3. muser
    Replies:
    3
    Views:
    739
    Ron Natalie
    Sep 18, 2003
  4. A
    Replies:
    3
    Views:
    431
    Alan Kelon
    Oct 29, 2003
  5. cerr

    pointers, pointers, pointers...

    cerr, Apr 7, 2011, in forum: C Programming
    Replies:
    12
    Views:
    642
Loading...

Share This Page