Thread: Parsing for the very dummies?

  1. #1
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476

    Parsing for the very dummies?

    Hi all,

    I have always been interested in parsing etc. but I can't figure it out! I know it's not easy, but nothing seems to help. I can moderately use lex & yacc, but I don't want those. Lexer is not a problem, I have written one or two, but I can't understand the concept. Is there any good solution without much theory or mathematics, but with a solid base on practice? One drawback I know is that most of them use Pascal, I can understand some, but I'm not fluent and don't want to learn it.

    I merely know some terms:
    Non-terminals and terminals
    Type x grammars
    BNF-notation
    LL, LALR etc.

    My goal is to write at least a parser for a small language, like 'solution = 6 * 7;' with operator precedence to add later on. I would be happy if I could parse things such as 5 + 6!

  2. #2
    Registered User
    Join Date
    Sep 2008
    Posts
    53
    The Unix Programming Environment - Wikipedia, the free encyclopedia

    in the bottom of this article there is a link to an online version of this book. i have the hardcopy of the original book and there is a chapter on parsing in it as well as some chapters about c programming in the unix environment.

    i did not read the whole online version yet but it is a updated version .

    i know it is not much but it is all i know of right now.
    good luck.

  3. #3
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Sorry, I know that and I don't want to use parser generators if not absolutely necessary.
    Is there any source written in a very clear style implementing a parser? That might help a bit. I simply want to do it straightforwardly.

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    53
    SMALL C Files

    only thing i can think of then is to get the source of one of the small c compilers and see how it is done.

    i have one called small Uc that i got from a Danish book and the book is written in Danish and covers only a small amount of the parsing and compiler construction. not even enough that i can fully understand from the book how one would go about writing a language and compiler that actually works.

    but to study the source of such program is a learning experience in it self. and pretty complicated for beginners like me that only been programming for a very short time.

    i can not help anymore than this.
    hope you figure something out.

  5. #5
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Well, I have given a try. Thank you, but I still need some more material, or tutorial etc. Or maybe a good book. Preferably showing you "why and how" to do things and with exercises. That would really be great!
    Last edited by Brafil; 04-12-2009 at 10:31 AM.

  6. #6
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Bump... Nothing? I started reading some yacc code... But I can't really read it. Well, I'm very tedious. Nevermind. So I would like to know if there is a parser generator with a clear codeing style?

  7. #7
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Recursive descent parser - Wikipedia, the free encyclopedia and follow the references for a simple type of parser which will handle many common types of grammars.

    Parsing simple things is simple. There's lots of examples of a simple 4 operator calculator out there (Shunting-yard algorithm - Wikipedia, the free encyclopedia, http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm).

    Parsing slightly more complicated grammars gets interesting very quickly, so the answer to "Is there any good solution without much theory or mathematics, but with a solid base on practice?" is basically no. If you're looking to do anything more complex than a simple calculator without the help of parser generators, learning a different language to understand the examples is going to be the least of your worries.

    Sorry, wish I had better news. There's a reason that lex and yacc were written... There are simple examples of lex and yacc that you could start from, such as Bison Tutorial.

  8. #8
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Well, I now know what is recursive-descent and LALR. But in the first case, it's difficult to track the predictions back if any goes wrong, and in the second one it's difficult to implement a DFA. Well, Thanks, I'll take a look.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need sth about parsing
    By Masterx in forum C++ Programming
    Replies: 6
    Last Post: 11-07-2008, 12:55 AM
  2. draw tree graph of yacc parsing
    By talz13 in forum C Programming
    Replies: 2
    Last Post: 07-23-2006, 01:33 AM
  3. Parsing for Dummies
    By MisterWonderful in forum C++ Programming
    Replies: 4
    Last Post: 03-08-2004, 05:31 PM
  4. I hate string parsing with a passion
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 03-19-2002, 07:30 PM
  5. for Dummies books
    By Unregistered in forum C Programming
    Replies: 0
    Last Post: 02-26-2002, 12:23 AM