3 ms·

> Single pass compiler with combined parsing and code generation. No separate lexer, no separate parser, no abstract syntax tree. An interesting approach, but

by osrec 7y ago

> Single pass compiler with combined parsing and code generation. No separate lexer, no separate parser, no abstract syntax tree. An interesting approach, but how practical is it for more modern languages?

zeckalpha 7y ago
Some modern languages do the equivalent. Thanks to lazy evaluation, you can have a separate lexer, parser, and code gen, but still have a single pass as long as you have an upper bound on backtracking.
DaiPlusPlus 7y ago
Single-pass compilation requires forward-declarations (or the author to rearrange their definitions), it would also prohibit things like splitting a type definition-up between different source files. That said, a simple two-pass compiler where the first-pass is to simply _index_ each discrete compilation unit would work (and such an index could be written to disk with no need for memory usage) - this would probably enable _most_ of the functionality of a C#-like language - heck, you could probably also add a trivial third-pass to implement generics (albeit as C++-style templates rather than type-safe generics) with compile-time code-generation (again, to-disk). GCs aren't new either - going back to John McCarthy's 1959 implementation in Lisp - which makes me think a non-optimizing AOT C# compiler and stop-the-world GC could probably be implemented with minimal memory usage (actually, isn't this how the .NET Micro Framework worked?) Looking at my current .NET project I'm working on - the actual compilation of about ~800 C# source files to CIL takes less than a couple of seconds - the rest of the build-time is taken-up by asinine build-steps in inherited MSBuild .targets files that I don't have any control over (one step involves copying all of the source files and assets - to a separate pre-build directory twice). Methinks problems with computer efficiency exist in non-obvious places.
- Someone 7y ago
  ”Single-pass compilation requires forward-declarations (or the author to rearrange their definitions), it would also prohibit things like splitting a type definition-up between different source files” You probably know, but for those who don’t: Pascal requires both. It’s not as if Turbo Pascal implemented a subset of the language. Also, multiple passes is less important nowadays. In early times, memory was so tight that each pass wrote its output to disk or tape. Early FORTRAN compilers had many. See for example the ‘sections’ in https://archive.computerhistory.org/resources/text/Fortran/102653992.05.01.acc.pdf https://archive.computerhistory.org/resources/text/Fortran/1.... Depending on how you count, that’s 6 to 9 passes. (Or one. That document says “With one exception, Fortran may be considered as a one pass system. That is, it looks at the source program only once, and it makes a scan of each statement once only. From then on, references are to tables only.” I think that’s bending th truth, though) Nowadays, intermediate results can be kept in RAM. Clang, for example, can runs tens of passes, some of them multiple times. That still slows things down, but less so.
- badsectoracula 7y ago
  Note that you can avoid a second pass by doing 'backpatching' - essentially assuming whatever code you encountered was correct, emitting the relevant bytecode/machinecode with enough reserved space for an address (e.g. for a 'jump to address' instruction, emit zeroes for the address), keep a list of 'unknown stuff' and then resolve them once compilation is finished. Many years ago i wrote a Java-like scripting language (classes, GC, etc) with that approach. Funny enough, at the time it didn't occur me that i could have separate bytecode streams for methods, etc, so the VM was almost like a custom CPU (the only non-CPU-like feature was an instruction to allocate memory) and since it generated bytecode while it was parsing the source code itself (even skipped any separate tokenization, i parsed the character streams directly) while it also allowed code to be placed outside of functions or classes (it was a scripting language after all), every time a class or function was encountered in source code, it'd emit code to jump over it - so the final bytecode would start by a series of jumps over the functions and classes before arriving to the first actual instruction :-P.

by osrec 7y ago

zeckalpha 7y ago

Some modern languages do the equivalent. Thanks to lazy evaluation, you can have a separate lexer, parser, and code gen, but still have a single pass as long as you have an upper bound on backtracking.

DaiPlusPlus 7y ago

Single-pass compilation requires forward-declarations (or the author to rearrange their definitions), it would also prohibit things like splitting a type definition-up between different source files. That said, a simple two-pass compiler where the first-pass is to simply _index_ each discrete compilation unit would work (and such an index could be written to disk with no need for memory usage) - this would probably enable _most_ of the functionality of a C#-like language - heck, you could probably also add a trivial third-pass to implement generics (albeit as C++-style templates rather than type-safe generics) with compile-time code-generation (again, to-disk). GCs aren't new either - going back to John McCarthy's 1959 implementation in Lisp - which makes me think a non-optimizing AOT C# compiler and stop-the-world GC could probably be implemented with minimal memory usage (actually, isn't this how the .NET Micro Framework worked?) Looking at my current .NET project I'm working on - the actual compilation of about ~800 C# source files to CIL takes less than a couple of seconds - the rest of the build-time is taken-up by asinine build-steps in inherited MSBuild .targets files that I don't have any control over (one step involves copying all of the source files and assets - to a separate pre-build directory twice). Methinks problems with computer efficiency exist in non-obvious places.

Someone 7y ago
”Single-pass compilation requires forward-declarations (or the author to rearrange their definitions), it would also prohibit things like splitting a type definition-up between different source files” You probably know, but for those who don’t: Pascal requires both. It’s not as if Turbo Pascal implemented a subset of the language. Also, multiple passes is less important nowadays. In early times, memory was so tight that each pass wrote its output to disk or tape. Early FORTRAN compilers had many. See for example the ‘sections’ in https://archive.computerhistory.org/resources/text/Fortran/102653992.05.01.acc.pdf https://archive.computerhistory.org/resources/text/Fortran/1.... Depending on how you count, that’s 6 to 9 passes. (Or one. That document says “With one exception, Fortran may be considered as a one pass system. That is, it looks at the source program only once, and it makes a scan of each statement once only. From then on, references are to tables only.” I think that’s bending th truth, though) Nowadays, intermediate results can be kept in RAM. Clang, for example, can runs tens of passes, some of them multiple times. That still slows things down, but less so.
badsectoracula 7y ago
Note that you can avoid a second pass by doing 'backpatching' - essentially assuming whatever code you encountered was correct, emitting the relevant bytecode/machinecode with enough reserved space for an address (e.g. for a 'jump to address' instruction, emit zeroes for the address), keep a list of 'unknown stuff' and then resolve them once compilation is finished. Many years ago i wrote a Java-like scripting language (classes, GC, etc) with that approach. Funny enough, at the time it didn't occur me that i could have separate bytecode streams for methods, etc, so the VM was almost like a custom CPU (the only non-CPU-like feature was an instruction to allocate memory) and since it generated bytecode while it was parsing the source code itself (even skipped any separate tokenization, i parsed the character streams directly) while it also allowed code to be placed outside of functions or classes (it was a scripting language after all), every time a class or function was encountered in source code, it'd emit code to jump over it - so the final bytecode would start by a series of jumps over the functions and classes before arriving to the first actual instruction :-P.