Difference between single-pass and multi-pass compilers?

Question

I saw a lot of messages about compilers one pass and multi pass , but I did not seem to understand.

• What are single pass compilers?

• What are multi pass compilers?

• What is the main difference between the two?

• Can someone provide the difference between them in a very simple language?

Answer 1

The origin of the term multi-pass comes from a time when computers had much less memory. Compilers require a lot of memory, and on a small memory machine it's hard to handle.

Thus, the original idea was that the compiler was executed with several passes. The first pass read the source code and performed basic tasks, such as checking syntax, possibly building a symbol table, and then writing its results to a disk file for the second pass. Each subsequent passage N read the previous result of the transfer and changed the presentation of the program in order to move it further and further to the machine code and write its results for passage N + 1 for reading. This process is repeated until the final pass gives the final code. Many compilers can get multiple ("multi") passes; there were well-known compilers with dozens of passes built on really old machines.

(The same concept applies to the so-called "dual-processor assemblers": the first pass reads the assembler source code, checks the syntax, determines which location values ​​should be used for label characters, and the second pass creates object code using the knowledge of the character layout assigned in the first pass )

Now the memory becomes larger, and it is quite practical for reading the source code for all very large programs into memory, so that the compiler does all its work in the memory of one process and writes object code. You still see some similar remnants of this in the concept of linkers; they glue several object modules ("first pass") into a single binary file.

If you look at the compiler inside yourself, they work in stages. Typical phases may be:

* Parse and syntax check * Build symbol tables * Perform semantic sanity check * Determine control flow * Determine data flow * Generate some "intermediate" language (representing abstract instructions) * Optimize the intermediate language * Generate machine code from the optimized language 

What a particular compiler does for phases depends on the compiler and the compiler. Each of these steps pushes the presentation of programs closer to the final machine code. The N-pass compiler will link one or more of these steps in a single pass.

Back to today, we have a lot of memory; it is not necessary for a modern compiler to write intermediate results to a disk file, therefore all these phases occur in the memory of one process. You, the compiler user, do not see them. Thus, you can call modern compilers "one-pass" in the original senses of the word. Since no one cares now, the phrase simply fell into disrepair.

In any case, compilers are still, as a rule, multiphase inside. (There are compilers that perform all these steps in what constitutes one phase; usually they cannot do a lot of optics).

Answer 2

A multi-pass compiler is one that divides the compilation into several passes, where each pass will continue with the result of the previous pass. Such passes may include parsing, type checking, intermediate code generation, various optimization passes, and finally code generation. So, for example, the parser can create a parsing tree, which then checks the type checks for type errors, and the intermediate code generator can translate into some form of intermediate code. Then the optimization passes will take the current intermediate code and turn it into a more optimized form. Finally, the code generation code will receive the optimized intermediate code and output the target code from it.

In a single-pass compiler, all steps are performed in a single pass. Thus, he reads part of the source code, analyzes it, checks it, optimizes and generates code for it, and then proceeds to the next code fragment.

Single-skipped compilers consume less memory (because they do not contain all AST and / or intermediate code in memory) and usually work faster.

Some languages, such as C, are designed to be compiled in one pass, while others are not. For example, functions in C must be declared before their first use, so the compiler already saw the signature of the function type before it reads the function call. He can then use this information for type checking. For example, in more modern languages, such as Java or C #, functions can be called before they are defined (and forward-declarations do not exist). Such languages ​​cannot be compiled in a single pass, because the type checker may not know anything about the signature of the function when it encounters a function call, which makes it impossible to execute the typecheck program without first processing the entire file.

In addition, a multi-pass compiler can use more types of optimization, therefore, even for languages ​​that can be compiled in one pass, modern compilers usually use several passes.

Answer 3

Passing in the compiler is nothing more than passing the entire program once from top to bottom

. Often a pass will consist of several stages. Typically, a single pass is sufficient to complete both lexical and parsing analysis. This means that after going through the entire program once, we can check if the statement is syntactically correct. And then the result of the parsing is an abstract syntax tree, which is nothing more than the source code (compressed) in the form of a tree. The semantic analyzer must go through the AST in order to do its job and there, having successfully completed the entire program again. That is, two passes are required to complete semantic analysis (if explicit AST is required).

Answer 4

• A single-pass compiler is a compiler that only goes through the source code of each compilation unit. A multi-pass compiler is a type of compiler that processes the source code or abstract syntax tree of a program several times.

• Single-pass compilers are faster than multi-pass compilers

• The single-pass compiler has a limited skip area, but the multi-pass compiler has a wide range of passes.

• Multi-pass compilers are sometimes called wide compilers, because they are sometimes referred to as a narrow compiler as a single-pass compiler.

• Many programming languages ​​cannot be represented using single-pass compilers, for example, Pascal can be implemented using a single-pass compiler, where, since languages ​​such as Java require a multi-pass compiler.

Answer 5

The “pass” reads the source program or the output of the previous pass, converts it in accordance with its phases and writes the output to an intermediate file, which can then be read through the next pass.