1
$\begingroup$

When my instructor taught compiler construction he explained all the phases of compiler and their working nicely. But when I read online here, at last line it is written that

Parse trees are not always produced.

So, what does it mean? I thought parse trees are always produced after lexical analysis part. Is there any example for it?

$\endgroup$
2
$\begingroup$

It's possible to use an attribute grammar to directly compute three-address code or some other Intermediate Representation; there are examples in the Dragon Book (and possibly other texts). This is not usually recommended but it seems like there is always the temptation to ignore the advice.

Parsers which are not actually connected to a compiler often don't bother with a parse tree. For example, a directly executed calculator without loops or stored procedures would have little need for a parse tree, and I think the vast majority of calculator examples are directly executed (so the parser just executes each operator as it discovers the operands). That's unfortunate, in my opinion, because for real compilers building a tree is by far the simplest starting point, and it's not difficult; the calculator examples are misleading and not very good models.

So I suggest you stick with what you were taught. But it would be more realistic (truth in advertising, as they say) to replace "Parse trees are always produced." with "Parse trees should always be produced."

For a real-life example of a simple language which goes directly to Intermediate Representation, tou can take a look at Lua's hand-built parser.

$\endgroup$
2
$\begingroup$

The key feature of explicit parse trees (or, probably more accurately, abstract syntax trees) that makes them useful is that they are as close as it's possible to get the source program, while still following the structure of the source program. This makes them ideal for implementing any programming language feature which is better expressed in terms of the source language.

Perhaps the most obvious example is semantic analysis. Many modern programming languages have semantics which require reading in the whole program first (e.g. languages which don't require forward declarations). Any semantic error (e.g. a type error) should be reported to the user in a way that refers to the source program as closely as possible, so using an abstract syntax tree makes more sense than an intermediate representation.

(As an aside, generating high-quality diagnostic/error messages is an under-appreciated aspect of compiler development. These messages are, in a sense, the primary user interface of a compiler as far as a programmer is concerned.)

Another example is applying optimisations or transformations which are defined in terms of the source language, such as copy elision in C++. For retargetable compilers or compiler frameworks (e.g. GCC, LLVM), these transformations are neither source-language-independent, nor target-architecture-dependent, so implementing them on the ASTs prior to IR generation is usally the best option.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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