Example parsers to learn how to write them [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Guide the asker to update the question so it focuses on a single, specific problem. Narrowing the question will help others answer the question concisely. You may edit the question if you feel you can improve it yourself. If edited, the question will be reviewed and might be reopened.

Closed 8 years ago.

Improve this question

I am looking for source codes of parsers and/or parser generators that could be studied in order to develop further, my skills that I acquired during a school course. Do you know any recommendable parsers of any type?

• Dervall: Parsers or parser generators?
• Nicolas Zozol: I also had pain with that, and I've worked on Masala Parser (github.com/masala-oss/masala-parser) in the purpose of being an easier parser generator than bison/yacc.

Answer 1

You should know how to build recursive descent parsers by hand. Here's an SO link to a quick lesson on how to do this: https://stackoverflow.com/a/2336769/120163

If you want to understand how recursive descent parsers can be constructed automatically, you can read a paper (and see a tutorial) on MetaII at this link: https://stackoverflow.com/a/1142034/120163

• Ira Baxter: @Ankit: Dead link: this is SO shooting themselves in the foot, and making good information that you want unavailable. SO continually complains that "links to offsite resources can go stale", so text should be "here" at SO. This is a link to a stack overflow answer (you can see that in the link name), that SO moderators in their wisdom decided to delete. (It had 17 upvotes and a 100 point bonus awarded by the original question author). If you think this was a bad idea on their part, you can go to Meta and complain. [Those of us with high rep can see deleted answers].
• Ira Baxter: @Odexios: I wrote the answer at the dead link. SO deleted it. I have the rep to include the answer here, but all that will do is bring down the wrath of the deletionists; after all, the already deleted it once. I've been here before with the SO folks, and see no point in subjecting myself to more of the same. It comes from poor policy choices, but I can't control that.
• Ira Baxter: I didn't delete it, so I don't know the actual motivation. Some set of SO guys did. They closed the question of "Please Recommend CS/CI Project books" as "not constructive". This is a "select a deletion reason from a list". Who knows what they actually thought.
• Runium: Alternative link: web.archive.org/web/20100727140855/http://stackoverflow.com/… - Oha! It got deleted after 666 views?
• Matt Joiner: It's not dead now. The people rise!

Answer 2

• Bison is a classical example (C/C++).
• Pyparsing is a great module, and it is very easy to use (Python) .
• Lemon is very easy to use (C++).

Check the examples, and good luck.

Edit:

I guess I should comment. A parser is a program which processes an input and "understands" it. A parser generator is a tool used to write parsers. I guess you mean you want to learn more about generating parsers, in which case, you should refer to the documentation of parser generators (all of the above).

Answer 3

Parsers themselves are usually not that interesting, it's the generators of parsers that are more of a subject of study.

• ANTLR generates LL parsers which are easily readable once generated. (Java)
• Bison generates LALR(1) parsers which are impossible to read. (C)

If LALR(1) interests you, I have a library up on github that tries to do a new number on LALR parsing. Feel free to take a look. It's in C# and I've tried my finest to make the code comprehensible. It's been a learning project for me, but it's smaller than the big tools and a bit easier to penetrate. And definitely feel free to contribute, lots of features to add still.

Otherwise, take a look at the generated code of these tools to see how they build the actual parsers that do the work.

• user1658543: Parser generators cause lots of problems. Write your own parser and you have a) fun and b) full control.
• Ira Baxter: GLR parser generators solve lots of problems, mostly be avoiding the traps of classic parser generators (YACC, Bison, JavaCC, ...). Why write a parser by hand, when you can just hand one a set of context-free rules?

Answer 4

I would suggest you this book: http://www.cs.nott.ac.uk/~gmh/book.html. it's quite good to start Haskell and it has got an entire chapter on parsers.

If you can understand that, creating a parser using Haskell is pretty straight forward. Take also in consideration that Haskell is quite fast and good for multi-core programming, so it may be the future.

Plus.

Here is a parser in Haskell: Happy - http://www.haskell.org/happy/.

Answer 5

I just went through the same battles and finally feel like I have a good handle on your options.

Lots of parsers are build for context-free grammars. You can read the formal definition of context-free but my intuition is that it basically means that syntax tokens / rules cannot change based on some context. I could be wrong about this, but I think it also means that you don't have look-ahead.

For example, markdown is not context-free, and I think pretty much a any language that is indentation based is not context-free without having to do some preprocessing to wrap blocks with start and end tokens. C is a perfect example of a context-free grammar.

If you're dealing with a context-free grammar, BNF is a formal way of specifying the compiler. This was an immensely helpful article explaining how BNF grammars work, how they're performant, and common extensions to BNF grammars.

Some of your options in this category are ANTLR, Bison, Yacc, Jison, and Peg.js.

However, after battling against ANTLR for a while, I found what I think is the best solution: "parser combinators". Its basically regex on steroids and very popular in the functional programming world.

I don't have any good learning resources for you yet, but Google around and you'll find them for pretty much any language. I come from the JavaScript world and peeking through the source code of this very small library really helped me understand what they're all about.