Однопроходные компиляторы: принципы работы и ограничения

In computer programming, a one pass compiler is a compiler that passes through the parts of each compilation unit only once, immediately translating each part into its final machine code. This is in contrast to a multi pass compiler which converts the program into one or more intermediate representations in steps between source code and machine code, and which reprocesses the entire compilation unit in each sequential pass. This refers to the logical functioning of the compiler, not to the actual reading of the source file once only. For instance, the source file could be read once into temporary storage but that copy could then be scanned many times. The IBM 1130 Fortran compiler stored the source in memory and used many passes; by contrast the assembler, on systems lacking a disc storage unit, required that the source deck of cards be presented twice to the card reader/punch.

One pass compilers are smaller and faster than multi pass compilers. One pass compilers are unable to generate as efficient programs as multi pass compilers due to the limited scope of available information. Many effective compiler optimizations require multiple passes over a basic block, loop (especially nested loops), subroutine, or entire module. Some require passes over an entire program. Some programming languages simply cannot be compiled in a single pass, as a result of their design. For example PL/I allows data declarations to be placed anywhere within a program, specifically, after some references to the not yet declared items, so no code can be generated until the entire program has been scanned. The language definition also includes pre processor statements that generate source code to be compiled: multiple passes are certain. In contrast, many programming languages have been designed specifically to be compiled with one pass compilers, and include special constructs to allow one pass compilation.

The basic problem is of forward references. The correct interpretation of a symbol at some point in the source file may be dependent on the presence or absence of other symbols further on in the source file and until they are encountered, correct code for the current symbol cannot be produced. This is the problem of context dependence, and the span can be anywhere from adjacent symbols to arbitrarily large amounts of source text.

Suppose that the symbol < is recognized as being for a "less than" comparison, as opposed to "greater than" for example. Because of character coding limitations, the glyph ≤ may not be available in a standard encoding, so a compound representation is to be allowed, "<=". Even though this context is determined by the very next symbol, it is unknown when "<" is encountered. Similarly, the symbol "=" does not always mean "=", as when it is a part of a compound symbol. Other compound symbols might include ". lt." for the case when the special character "<" is unavailable. Yet another possibility where a character code for the glyph ¬ ("not") is unavailable is "<>" for "¬=" or "not equal" some systems employ ~ or ! for ¬ as still further variation. One approach is to advance the scan after "<" and on encountering the "=", backtrack. This of course means that there will be two passes over that portion of text, which is to be avoided. For that matter, the source file may come from a device not supporting a go back and reread operation, such as a card reader. Instead of making an early decision that may later have to be undone, the lexical analyser can maintain multiple interpretations rather like the notion of Quantum Superposition, collapsing to a specific choice only on later observing the determining symbol. Notably, COBOL compilers devote a pass to distinguishing between full stops appearing in decimal constants and the full stops that appear at the end of statements. Such a scheme is unavailable to a single pass compiler. Similarly with the names of items. Few languages restrict themselves to single character names, so the character "x" as a single character name is quite different from the character "x" within a name such as "text" now the context extends beyond the immediately adjacent characters. It is the task of the lexical analyser to separate the items of the sequential source stream into the tokens of the language. Not just words, because "<" and "<=" are tokens also. Names typically start with a letter and continue with letters and digits, and perhaps a few additional symbols such as " ". The syntax allowed for specifying numbers is surprisingly complex, for example +3.14159E+0 can be valid. It is usual to allow an arbitrary number of space characters between tokens, and Fortran is unusual in allowing (and ignoring) spaces within apparent tokens also so that "GO TO" and "GOTO" are equivalent as are "<=" and "< =". However, some systems may require spaces to delimit certain tokens, and others, such as Python, use leading spaces to indicate the scope of program blocks that otherwise might be indicated by Begin End or similar markers.

Although the description above has employed the notion that code may be generated with certain fields left to be fixed up later, there was an implicit assumption that the size of such code sequences was stable. This may not be the case. Many computers have provision for operations occupying different amounts of storage, notably relative addressing whereby if the destination is within say 128 or +127 addressing steps then an eight bit address field can be used, otherwise a much larger address field is required to reach. Thus if the code were generated with a hopeful short address field, later it may become necessary to go back and adjust the code to use a longer field, with the consequence that earlier code referencing locations after the change will have to be adjusted as well. Likewise, later references going backwards across the change will have to be fixed, even those that had been to known addresses. And as well, the fixup information will itself have to be fixed, correctly. On the other hand, long addresses could be used for all cases when nearness is not certain, but the resulting code will no longer be ideal.

Already mentioned are some possibilities for optimisation within a single statement. Optimisations across multiple statements would require that the content of such statements be held in some sort of data structure that could be analysed and manipulated before code is emitted. In such a case, producing provisional code, even with fixups allowed for, would be a hindrance. In the limit this means the compiler would generate a data structure representing the entire program in an internal form, but a straw could be clutched and the claim made that there is no actual second pass of the source file from start to end. Possibly in the PR document advertising the compiler. Notably therefore, a compiler cannot generate its code in a single relentlessly forwards sequence, still less immediately as each part of the source is read. The output could still be written sequentially, but only if output of a section is deferred until all pending fixups for that section have been made.

Declaration before use is likewise an easy requirement to meet for procedures and functions, and this applies also to the nesting of procedures within procedures. As with ALGOL, Pascal, PL/I and many others, MATLAB and (since 1995) Fortran allow a function (or procedure) to contain the definition of another function (or procedure), visible only within the containing function, but these systems require that they be defined after the end of the containing procedure. But when recursion is allowed, a problem arises. Two procedures, each invoking the other, cannot both be declared before usage. One must be first in the source file. This need not matter if, as on the encounter with an unknown variable, sufficient can be deduced from the encounter that the compiler could generate suitable code for the invocation of the unknown procedure, with of course the "fixup" apparatus in place to come back and fill in the correct address for the destination when the procedure's definition is encountered. This would be the case for a procedure with no parameters, for example. The returned result from a function invocation may be of a type discernable from the invocation, but this may not always be correct: a function could return a floating point result but have its value assigned to an integer. Pascal solves this problem by requiring "predeclaration." One of the procedure or function declarations must be given first, but, instead of the body of the procedure or function, the keyword forward is given. Then the other procedure or function can be declared and its body defined. At some point the "forward" procedure or function is redeclared, along with the body of the function. For the invocation of a procedure (or function) with parameters, their type will be known (they being declared before use) but their usage in the procedure invocation may not be. Fortran for example passes all parameters by reference (i. e. by address) so there is no immediate difficulty with generating the code (as always, with actual addresses to be fixed up later), but Pascal and other languages allow parameters to be passed by different methods at the programmer's choice (by reference, or by value, or even perhaps by "name") and this is signified only in the definition of the procedure, which is unknown before the definition has been encountered. Specifically for Pascal, in the specification of parameters a prefix "Var" signifies that it must be received by reference, its absence signifies by value. In the first case the compiler must generate code that passes the address of the parameter, while in the second it must generate different code that passes a copy of the value, usually via a stack. As always, a "fixup" mechanism could be invoked to deal with this, but it would be very messy. Multi pass compilers can of course collate all the required information as they shuttle back and forth, but single pass compilers cannot. Code generation could be paused while the scan advances (and its results be held in internal storage) until such time as the needed entity is encountered, and this might not be regarded as resulting in a second pass through the source because the code generation stage will soon catch up, it was merely halting for a while. But this would be complex. Instead a special construction is introduced, whereby the procedure's definition of parameter usage is declared "forward" of its later full definition so that the compiler may know it before use, as it requires. From First Fortran (1957) onwards, separate compilation of portions of a program has been possible, supporting the creation of libraries of procedures and functions. A procedure in the source file being compiled that invokes a function from such an outside collection must know the type of result returned by the unknown function, if only to generate code that looks in the right place to find the result. Originally, when there were only integers and floating point variables, the choice could be left to the rules for implicit declaration, but with the proliferation of sizes and also types the invoking procedure will need a type declaration for the function. This is not special, having the same form as for a variable declared inside the procedure. The requirement to be met is that at the current point in a single pass compilation, information on an entity is needed so that the correct code for it can be produced now, if with address fixups later. Whether the required information will be encountered later on in the source file or is to be found in some separately compiled code file, the information is provided by some protocol here. Whether or not all invocations of a procedure (or function) are checked for compatibility with each other and their definitions is a separate matter. In languages descended from Algol like inspiration, this checking is usually rigorous, but other systems can be indifferent. Leaving aside systems that allow a procedure to have optional parameters, mistakes in the number and type of parameters will normally cause a program to crash. Systems that allow separate compilation of parts of a complete programme that later are "linked" together should also check for the correct type and number of parameters and results as mistakes are even easier to make, but often do not. Some languages (such as Algol) have a formal notion of "upgrading" or "widening" or "promotion", whereby a procedure that expects say a double precision parameter may be invoked with it as a single precision variable, and in this case the compiler generates code that stores the single precision variable into a temporary double precision variable which becomes the actual parameter. This however changes the parameter passing mechanism to copy in, copy out which may lead to subtle differences in behaviour. Far less subtle are the consequences when a procedure receives the address of a single precision variable when it expects a double precision parameter, or other size variations. When within the procedure the parameter's value is read, more storage will be read than that of its given parameter and the resulting value is unlikely to be an improvement. Far worse is when the procedure changes the value of its parameter: something is sure to be damaged. Much patience can be expended in finding and correcting these oversights.

When declaring complex data aggregates, a possible usage of functions Odd and Even could arise. Perhaps if a data aggregate X has a storage size that is an odd number of bytes, a single byte item might be added to it under the control of a test upon Odd(ByteSize(X)) so as to make an even number. Given the equivalent declarations of Odd and Even as above, a "forward" declaration probably wouldn't be needed because the usage of the parameters is known to the pre processor which is unlikely to present opportunities to choose between by reference and by value. However, there could be no invocations of these functions in the source code (outside their definitions) until after their actual definition, because the result of the invocation is required to be known. Unless of course the pre processor engaged in multiple passes of its source file.

Anyone who has attempted to maintain coherence amongst the declarations and usages of procedures in a large program and its usage of libraries of routines, especially one undergoing changes, will have struggled over the usage of forward or similar added declarations for procedures invoked but not defined in the current compilation. Maintaining synchrony between widely separated locations especially across different source files requires diligence. Those declarations using the reserved word are easy to find, but if the helpful declarations are not distinguished from ordinary declarations, the task becomes troublesome. The gain of supposedly swifter compilation may seem insufficient when simply abandoning the goal of one pass compilation would remove this imposition.