What should a parser for a programming language do?

I have already written a lexer which returns tokens, and now I'm working on a parser. I have one problem.

Imagine this code example:

print("Hello, world!")

The lexer returns four tokens (print, (, "Hello, world!" and )). The final program should print the string "Hello, world!".

But what s开发者_StackOverflow社区hould the parser do? Should the parser already execute the code, should it return something (and what) that is handled by another object?

The parser should generate an abstract syntax tree, which is an in memory representation of the program. This tree can be traversed after parsing to do the code generation. I'd recommend to read some good book about the subject, maybe one involving dragons.

What should the parser do?

The typical role of a parser is to read the stream of tokens and, from that, build a parse tree or abstract syntax tree.

Should the parser already execute the code

No. That's not parsing.

Typically, a parser does not execute anything. Parsers usually take an input (text or binary) and produce an in-memory representation, nothing more... but that's already much!

If you already have a Lexer, then the second step is normally to perform Semantic Analysis, to produce an Abstract Syntax Tree.

This means, producing something of the form:

(FunctionCall "print" [
    (StringLiteral "Hello, World!")
    ]
)

It should return an abstract syntax tree.

The parser should basically do two things:

1. Produce a form of intermediate text, generally in a tree or reverse-Polish form, that the code generator can consume.
2. Clearly and accurately report any errors encountered, identifying the failing line number, the precise cause for the error (in reasonable non-techspeak), and, to the degree possible, the position within the line or the identity of the element that caused the parser to "choke".