I am currently writing a C++ Compiler. I have completed the Lexer portion of my Compiler. I am working on Parser from around a month. I searched a lot on the web, and couldn't found any relevent answer, that can help me in designing and coding the Parser.
I have no idea abt it, and my main problem is those curly braces '{' and '}' that comes a lot of time in the C++ language.
Do anyone knows, how to design and code a Parser..?
How to write a Parser
-
harmanjeet
- Posts: 10
- Joined: Sun Feb 06, 2011 7:03 am
- Location: India
- Contact:
Re: How to write a Parser
You might want to read the dragon book.
-
OSwhatever
- Member
- Posts: 595
- Joined: Mon Jul 05, 2010 4:15 pm
Re: How to write a Parser
I agree if you mean "Compilers Principles, Techniques and Tools" by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. ISBN 0-201-10194-7.DLBuunk wrote:You might want to read the dragon book.
I don't know why there is a dragon on the cover but you will not learn how to tame a dragon reading this book.
Re: How to write a Parser
You should start defining three things, the characters used, the formal grammar and the words.
You need also to define a list of all the good and impossible combinations between words.
C++ is pretty straight so this phase is easy
Than If I were you I'll start writing all the check functions which allows you to know if a string match to a rule. This helps the coder when he has to define all the sub-steps in the parser function. In C++ you will need check functions for maths expressions and for names I guess. These are controls for the "lexical" rules. You will need others to performs "formal" checks on the visibility field of a variable and so on.
Than you have to tokenise the source. In C++ a token could be a single instruction ; ended, or a {} block. You have to write function to analize the blocks...you could translate your source in a sort of bytecode. Than you will need to code an assembler for your specific platform. These are the steps I'd follow in doing it. Good luck
You need also to define a list of all the good and impossible combinations between words.
C++ is pretty straight so this phase is easy
Than If I were you I'll start writing all the check functions which allows you to know if a string match to a rule. This helps the coder when he has to define all the sub-steps in the parser function. In C++ you will need check functions for maths expressions and for names I guess. These are controls for the "lexical" rules. You will need others to performs "formal" checks on the visibility field of a variable and so on.
Than you have to tokenise the source. In C++ a token could be a single instruction ; ended, or a {} block. You have to write function to analize the blocks...you could translate your source in a sort of bytecode. Than you will need to code an assembler for your specific platform. These are the steps I'd follow in doing it. Good luck
-
Combuster
- Member
- Posts: 9301
- Joined: Wed Oct 18, 2006 3:45 am
- Libera.chat IRC: [com]buster
- Location: On the balcony, where I can actually keep 1½m distance
- Contact:
Re: How to write a Parser
There's free college material in case you don't want to buy. I don't have the dragon book so I can't tell if it's worth your pennies.
Re: How to write a Parser
I hand wrote my parser using this technique; http://en.wikipedia.org/wiki/Tail_recursive_parser
But my language's grammar is much simpler than that of C++. Consider using a parser generator.
But my language's grammar is much simpler than that of C++. Consider using a parser generator.
Valix is an experiment in an interpreted userspace with object-oriented and functional design patterns. Developers needed! Join #valix on irc.freenode.net
-
OSwhatever
- Member
- Posts: 595
- Joined: Mon Jul 05, 2010 4:15 pm
Re: How to write a Parser
I usually use flex and bison when parsing more complex texts. If you want to learn how to write a parser, then you could of course write your own. Otherwise flex and bison lets you start more quickly.
Re: How to write a Parser
Hi harmanjeet ,
A parser is only one part of compiler development , in fact you just complete one part of the compiler if you complete parsing. There is lot more to do once parsing in done, the good part is that most of parsing is well understood and well documented at least theoretically. Also I agree with berkus , C++ may not the right language to start if you have not written any parser yet !. Pascal or Basic or even C may be a better choice in the first try. Anyways I am posting some links that might interest you .
.
--Thomas
A parser is only one part of compiler development , in fact you just complete one part of the compiler if you complete parsing. There is lot more to do once parsing in done, the good part is that most of parsing is well understood and well documented at least theoretically. Also I agree with berkus , C++ may not the right language to start if you have not written any parser yet !. Pascal or Basic or even C may be a better choice in the first try. Anyways I am posting some links that might interest you .
- Free Video Lectures on Compiler Development from University of Washington
- Source of of Compiler Blue , it makes use of .Net reflection to generate the final assembly. It makes use of a recursive descent parser
- Compiler Construction by Writh . Note : Direct link to pdf.
- NPTEL compiler development Course from IIT Kanpur
. --Thomas
Re: How to write a Parser
C++ is notorious for being a b*tch to parse correctly. Most importantly, lex / yacc or flex / bison (which are fine tools for other languages like C) won't cut it. You get some of the way, but then you will be utterly stuck.
Bison (and all other parser generators I know) claim to convert a grammar description of a context-free grammar into a parser for that grammer. The catch is that C++ is not context-free.
AFAIK, there is exactly one open-source C++ parser with some claims to completeness, and that is the one used by GCC. They took years and several complete changes in parser architecture to get it right...
Bison (and all other parser generators I know) claim to convert a grammar description of a context-free grammar into a parser for that grammer. The catch is that C++ is not context-free.
AFAIK, there is exactly one open-source C++ parser with some claims to completeness, and that is the one used by GCC. They took years and several complete changes in parser architecture to get it right...
Every good solution is obvious once you've found it.
Re: How to write a Parser
If this is your first parser I would recommend something much simpler, like Lisp or a BASIC then you can use the BASIC as a scripting language.
As for writing a C++ parser you simply can't go past the dragon book, but be ready for some serious theory. I found "Crafting a compiler with C" a very helpful read, I got almost everything I needed from it. Little expensive on Amazon though.
As for writing a C++ parser you simply can't go past the dragon book, but be ready for some serious theory. I found "Crafting a compiler with C" a very helpful read, I got almost everything I needed from it. Little expensive on Amazon though.
Garbage collection is only for programmers that make garbage and can't clean up for themselves.
-
Griwes
- Member
- Posts: 374
- Joined: Sat Jul 30, 2011 10:07 am
- Libera.chat IRC: Griwes
- Location: Wrocław/Racibórz, Poland
- Contact:
Re: How to write a Parser
As others mentioned lex/bison, I think that boost::spirit is also worth mentioning.
Reaver Project :: Repository :: Ohloh project page
<klange> This is a horror story about what happens when you need a hammer and all you have is the skulls of the damned.
<drake1> as long as the lock is read and modified by atomic operations
<klange> This is a horror story about what happens when you need a hammer and all you have is the skulls of the damned.
<drake1> as long as the lock is read and modified by atomic operations
Re: How to write a Parser
...especially since boost::spirit can be (and has been) made to parse C++ correctly.Griwes wrote:As others mentioned lex/bison, I think that boost::spirit is also worth mentioning.
Every good solution is obvious once you've found it.