current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote -2 down vote favorite

I have read about compiler construction some concepts. What is understood is that

  1. You need a lexer that divides your program statements into tokens.
  2. You need to check and identify tokens into known types.
  3. You have to create a grammar and check if your tokens fit between the grammar defination.
  4. You have to create a AST syntax tree .

I am stuck at the parser and AST step , I am trying to create a simple language compiler.

How can I create a parser and AST for simple statements like var a = 10 * 20; ... etc.

share|improve this question
6  
This is a huge topic, I'd recommend getting a good book on the subject, modern compiler design is a nice one –  jozefg Oct 9 '13 at 14:22
2  
I'm pretty sure none of your 4 points are technically necessary, it is quite easy to write lexerless parsers with something like FParsec. There are certianly languages that have such little syntax a formal grammar is of very little use. –  jk. Oct 9 '13 at 14:33
3  
After the AST you still aren't finished. You need to generate IR code from that. –  luiscubal Oct 9 '13 at 14:41
add comment

closed as too broad by Florian Margaine, GlenH7, Robert Harvey, gbjbaanb, gnat Oct 10 '13 at 3:52

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 1 down vote

Well, the first thing you need to do is decompose the statement into tokens. So in your case, it might look something like type identifier EQUALS number TIMES number SEMICOLON. Now that you know what tokens you are looking for, the parser looks through the list of tokens and tries to match that particular case. If it can, then you need to turn it into a statement of some sort to put into an AST. Perhaps you'd have a variable declaration, which has three arguments: type, identifier, and expression. var would be the type, a would be the identifier, and then there would be a multiplication expression (another element with two operands, left and right).

For doing this in .NET, I strongly recommend you use F# and FsLex and FsYacc. There's a lot more information and an example SQL lexer/parser in this Wikibook: F Sharp Programming: Lexing and Parsing.

share|improve this answer
    
FParsec is another option –  jk. Oct 9 '13 at 14:29
add comment
up vote 0 down vote

Rather than building all of this yourself, you might want to take a look at ANTLR. It generates a lexer and parser based on a grammar that you specify for the language and will generate the AST. It is worth checking out even if you don't end up using because it will give you a working example of how a grammar can be specified and what the AST output will look like.

We needed to rewrite SQL queries for a project and one of the guys on my team was able to get up and running with a SQL parser very quickly.

There is a C# target for ANTLR that you can find here.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.