5 ms·

My project https://gitlab.com/giomasce/nbs https://gitlab.com/giomasce/nbs is currently able to more or less bootstrap flex, starting from only tcc and musl (wi

My project https://gitlab.com/giomasce/nbs https://gitlab.com/giomasce/nbs is currently able to more or less bootstrap flex, starting from only tcc and musl (within a running Linux kernel). Terms and conditions may apply: I haven't tested much the generated binary yet, and given the tricks I have to do to get there miscompilations and introduced bugs are everything but impossible. But at least ideally it should be possible to iron them out without changing the whole path. Bison is my next target, but I haven't been able to work much on it lately. It's true that it should be possible to bootstrap it by history, although I really hope that one does not need to many steps to get to the latest release.

bloak 7y ago
That's very interesting! Could you summarise the relevant steps? It appears that you're using "The Heirloom Project", which I hadn't heard of. (Is it related to Illumos?) So the Heirloom lex can be built without lex/yacc, and then you can build which version of flex using that?
- giomasce 7y ago
  The Heirloom project is a collection of utilities coming from open-sourced versions of Caldera and Sun code (https://en.wikipedia.org/wiki/Heirloom_Project https://en.wikipedia.org/wiki/Heirloom_Project). It's nice because it is very easy to bootstrap, even if nowadays it is unmaintained. It also features a lex and yacc that are written in plain C, without depending of themselves (well, lex depends on yacc, but at most one dependency is ok). It is not easy to use it to bootstrap flex, but it can be done. Basically you have to use an old enough version of flex (I am using 2.5.11) and modify its lexer so that it can be parsed by a simple lex that is not flex (plus some additional light patching of the C code). It is a bit tedious, but a rather mechanical task. Flex 2.5.11 is rather old now. When I have time I will also add another stage to compile a more recent version. But I believe that flex 2.5.11 can generate the lexer of the latest flex release. Also, it seems that all flex versions can be compiled with a yacc that is not bison. This is what I recall from my experiments of a few weeks ago, that I still have not consolidated in a working script. Surprises might happen! The other steps of the project are described in the README (where flex is not mentioned yet, but all the rest is). Later steps will be bison, as I said, and then who know. I should aim at Perl, which then would unlock autotools, but Perl itself has a lot of dependencies and I haven't yet begun unravelling them. Also bash and coreutils should be bootstrapped at some point, but for the moment dash and Heirloom can do their job without problems, so it is not a priority (although it might become at some point). Later targets will be binutils, gcc and glibc, but do not hold your breath. Eventually I would like to bootstrap Debian packaging tools and start building Debian packages. That might require that I train my offspring into programming and convince them to continue my mission.
  - bloak 7y ago
    That all sounds good! It is also possible (though tedious) to build GCC and binutils without autotools. Getting from epsilon to Debian seems a bit like following stepping stones across a swamp. It's unclear which route is most likely to work, but whichever way you pick you end up ankle-deep, or waist-deep, in mud. Also, it's not clear what "epsilon" should be. My feeling is that the ideal minimum prerequisites would be something like a C89 native compiler on an operating system that is much simpler than Unix. So you could read and write files and execute a subcommand, perhaps, but no pipes and no fork. So the first major goal would be to build GCC and binutils as a cross-compiler, and the second major goal would be to cross-compile those things plus the Linux kernel and some kind of shell so that you could then move to Linux. The whole thing is a big project, but if you can describe a way of getting from stepping stone A to stepping stone B, where B is a bit closer to Debian than A was, then that may help future explorers, and that use of Heirloom Project's lex to build flex sounds like a good example of that.
    - giomasce 7y ago
      Currently epsilon is a Linux kernel with musl and tcc. Since tcc can be used for scripting, I believe that with a non-trivial amount of work (including patching musl), musl could be built by tcc. Therefore epsilon would become just Linux and a static build of tcc. To further reduce epsilon (or, in somewhat standard terminology, the "binary seed") I am also writing asmc (https://gitlab.com/giomasce/asmc https://gitlab.com/giomasce/asmc), which is a minimal operating system with a minimal compiler, totalling less than 6 KiB binary seed. This compiler is not for C, but for G, which is a C-inspired language that I invented for this purpose (see the project README and links for more details). The target for asmc is to be able to build and boot Linux and a static copy of tcc (the latter is more or less already there; Linux is, of course, the hard part), at which point it can bootstrap nbs. I'm not there yet, though. Also, to be fair, although asmc's seed is 6 KiB, you still need an x86 CPU (I'm not aware of free implementations), a loader and a BIOS to have a functional environment. This is not little thing, but I guess it is a reasonable target so far.

bloak 7y ago

That's very interesting! Could you summarise the relevant steps? It appears that you're using "The Heirloom Project", which I hadn't heard of. (Is it related to Illumos?) So the Heirloom lex can be built without lex/yacc, and then you can build which version of flex using that?

giomasce 7y ago
The Heirloom project is a collection of utilities coming from open-sourced versions of Caldera and Sun code (https://en.wikipedia.org/wiki/Heirloom_Project https://en.wikipedia.org/wiki/Heirloom_Project). It's nice because it is very easy to bootstrap, even if nowadays it is unmaintained. It also features a lex and yacc that are written in plain C, without depending of themselves (well, lex depends on yacc, but at most one dependency is ok). It is not easy to use it to bootstrap flex, but it can be done. Basically you have to use an old enough version of flex (I am using 2.5.11) and modify its lexer so that it can be parsed by a simple lex that is not flex (plus some additional light patching of the C code). It is a bit tedious, but a rather mechanical task. Flex 2.5.11 is rather old now. When I have time I will also add another stage to compile a more recent version. But I believe that flex 2.5.11 can generate the lexer of the latest flex release. Also, it seems that all flex versions can be compiled with a yacc that is not bison. This is what I recall from my experiments of a few weeks ago, that I still have not consolidated in a working script. Surprises might happen! The other steps of the project are described in the README (where flex is not mentioned yet, but all the rest is). Later steps will be bison, as I said, and then who know. I should aim at Perl, which then would unlock autotools, but Perl itself has a lot of dependencies and I haven't yet begun unravelling them. Also bash and coreutils should be bootstrapped at some point, but for the moment dash and Heirloom can do their job without problems, so it is not a priority (although it might become at some point). Later targets will be binutils, gcc and glibc, but do not hold your breath. Eventually I would like to bootstrap Debian packaging tools and start building Debian packages. That might require that I train my offspring into programming and convince them to continue my mission.
- bloak 7y ago
  That all sounds good! It is also possible (though tedious) to build GCC and binutils without autotools. Getting from epsilon to Debian seems a bit like following stepping stones across a swamp. It's unclear which route is most likely to work, but whichever way you pick you end up ankle-deep, or waist-deep, in mud. Also, it's not clear what "epsilon" should be. My feeling is that the ideal minimum prerequisites would be something like a C89 native compiler on an operating system that is much simpler than Unix. So you could read and write files and execute a subcommand, perhaps, but no pipes and no fork. So the first major goal would be to build GCC and binutils as a cross-compiler, and the second major goal would be to cross-compile those things plus the Linux kernel and some kind of shell so that you could then move to Linux. The whole thing is a big project, but if you can describe a way of getting from stepping stone A to stepping stone B, where B is a bit closer to Debian than A was, then that may help future explorers, and that use of Heirloom Project's lex to build flex sounds like a good example of that.
  - giomasce 7y ago
    Currently epsilon is a Linux kernel with musl and tcc. Since tcc can be used for scripting, I believe that with a non-trivial amount of work (including patching musl), musl could be built by tcc. Therefore epsilon would become just Linux and a static build of tcc. To further reduce epsilon (or, in somewhat standard terminology, the "binary seed") I am also writing asmc (https://gitlab.com/giomasce/asmc https://gitlab.com/giomasce/asmc), which is a minimal operating system with a minimal compiler, totalling less than 6 KiB binary seed. This compiler is not for C, but for G, which is a C-inspired language that I invented for this purpose (see the project README and links for more details). The target for asmc is to be able to build and boot Linux and a static copy of tcc (the latter is more or less already there; Linux is, of course, the hard part), at which point it can bootstrap nbs. I'm not there yet, though. Also, to be fair, although asmc's seed is 6 KiB, you still need an x86 CPU (I'm not aware of free implementations), a loader and a BIOS to have a functional environment. This is not little thing, but I guess it is a reasonable target so far.