OSDev.org https://forum.osdev.org/ |
|
How to make a compiler https://forum.osdev.org/viewtopic.php?f=13&t=33611 |
Page 1 of 1 |
Author: | Schol-R-LEA [ Thu Mar 28, 2019 5:31 pm ] |
Post subject: | Re: How to make a compiler |
Actually, in terms of the time spent, the dominant part of most compilers is the lexical analyzer - which in most cases, amounts to a Deterministic Finite State Automaton, whether formally constructed or as an ad-hoc equivalent. Either way, I would have a lot of trouble seeing that as a graph coloring problem. |
Author: | alexfru [ Thu Mar 28, 2019 6:50 pm ] |
Post subject: | Re: How to make a compiler |
mariuszp wrote: It's literally just lots of graph problems; graph coloring, vertex reachability, etc. Only if your compiler is an optimizing one. |
Author: | Korona [ Fri Mar 29, 2019 12:15 am ] |
Post subject: | Re: How to make a compiler |
Schol-R-LEA wrote: Actually, in terms of the time spent, the dominant part of most compilers is the lexical analyzer - which in most cases, amounts to a Deterministic Finite State Automaton, whether formally constructed or as an ad-hoc equivalent. Either way, I would have a lot of trouble seeing that as a graph coloring problem. That's only true if you either use an existing backend or don't care about optimization. Lexical analysis is solved and there are so many algorithms to do it easily: recursive descend, PEG, LR parsers generators, or even Earley parsers that can handle any CFG. mariuszp wrote: It's literally just lots of graph problems; graph coloring, vertex reachability, etc. Prove me wrong. A LLVM-style Greedy RA is superior to graph coloring RAs in practice, prove me wrong. Graph coloring just cannot easily handle non-homogeneuos register files (and of course, it's also quite expensive). When I wrote an implementation (only a bit over 1k SLOC, can do live range splitting but not register spilling right now) inspired by the LLVM one, I was surprised (i) how natural it is, and (ii) how good the results are if you tune it a bit (for smallish functions with only a few basic blocks/variables, the result is often optimal). It's incredibly easy to tune -- when you see a missed optimization, it's usually straightforward to see how to extend the RA to handle it. |
Author: | Schol-R-LEA [ Fri Mar 29, 2019 9:48 am ] |
Post subject: | Re: How to make a compiler |
mariuszp wrote: Schol-R-LEA wrote: Actually, in terms of the time spent, the dominant part of most compilers is the lexical analyzer - which in most cases, amounts to a Deterministic Finite State Automaton, whether formally constructed or as an ad-hoc equivalent. Either way, I would have a lot of trouble seeing that as a graph coloring problem. All problems in NP have a polynomial-time reduction to graph coloring. facepalm I can't believe I fell for that. Yeah, that can describe more or less any practical algorithm, can't it (as P is a subset of NP). |
Author: | Korona [ Fri Mar 29, 2019 12:04 pm ] |
Post subject: | Re: How to make a compiler |
Doesn't hold when you want to parse C++. (And context-sensitivity gives you a PSPACE-complete problem.) |
Author: | Qbyte [ Sat Jun 01, 2019 8:16 am ] |
Post subject: | Re: How to make a compiler |
Schol-R-LEA wrote: Actually, in terms of the time spent, the dominant part of most compilers is the lexical analyzer - which in most cases, amounts to a Deterministic Finite State Automaton, whether formally constructed or as an ad-hoc equivalent. Either way, I would have a lot of trouble seeing that as a graph coloring problem. The lexer is actually the simplest and least time consuming part of writing a compiler. There's also pretty much only two ways to design a lexer; one which transforms the entire source file into a token array in a single step which is then handed off to the parser, or one which generates tokens for the parser on the fly. I personally prefer the former design for reasons of performance and code simplicity. |
Author: | Schol-R-LEA [ Sat Jun 01, 2019 4:54 pm ] |
Post subject: | Re: How to make a compiler |
Qbyte wrote: Schol-R-LEA wrote: Actually, in terms of the time spent, the dominant part of most compilers is the lexical analyzer - which in most cases, amounts to a Deterministic Finite State Automaton, whether formally constructed or as an ad-hoc equivalent. Either way, I would have a lot of trouble seeing that as a graph coloring problem. The lexer is actually the simplest and least time consuming part of writing a compiler. There's also pretty much only two ways to design a lexer; one which transforms the entire source file into a token array in a single step which is then handed off to the parser, or one which generates tokens for the parser on the fly. I personally prefer the former design for reasons of performance and code simplicity. Sorry if I wasn't clear; I wasn't referring to the implementation time, but the running time during a compile. Depending on the number of potential transitions, and the amount of optimization the compiler performs, lexical analysis can consume up to 80% of the running time (the textbook Modern Compiler Design by Grune, et. al., explains why in detail). Writing a lexical analyzer is pretty easy, comparatively. Writing an efficient one is another story, though as you said, it still is usually simpler and faster to implement than the other components. |
Author: | Thomas [ Sun Jun 02, 2019 11:21 pm ] |
Post subject: | Re: How to make a compiler |
Hi mariuszp, With availability of lot of video courses online, you can do anything you set your mind to. You will need to invest some time and energy for it. With a combination of a book ( a good free one suggested already by others ) and online resources, you should be able to get it done. The classic text by Aho et el is another good reference. Hopefully you can find a low priced used copy online. I think, these videos are very instructional. https://courses.cs.washington.edu/cours ... index.html --Thomas |
Author: | Thomas [ Sun Jun 02, 2019 11:31 pm ] |
Post subject: | Re: How to make a compiler |
I remember enjoying reading this too. https://holub.com/compiler/. The author has released the book and sources in public domain. Read this if you want to learn how to write a lex and yacc clone. However i did not like the design of the final compiler he came up with. There are far more modern and more modular ways to do it. But a good read for sure. --Thomas |
Author: | Solar [ Mon Jun 03, 2019 1:44 am ] |
Post subject: | Re: How to make a compiler |
Boost.Spirit is (IMHO) a strong C++ alternative to the C (lex/flex, yacc/bison) way of going about things. Upsides:
Downsides:
If you're willing to really tackle the learning curve, Boost.Spirit can be very rewarding, for both quick off-the-cuff oneliners or complex parse trees. But you have to dig deep to familiarize yourself with its intricacies. As with many other of my favourite tools (Vim, LaTeX, C++ in general), you won't see a payoff if you're only scratching the surface. The benefits are to be found at the deep end. Additionally, let me mention Crafting Interpreters by Bob Nystrom as an introduction on how to make an interpreter (which isn't that different from making a compiler, really). I found that piece to be more enlightening than many more theoretical approaches, especially if you're a beginner in the art and can't wrap your head around all the related lingo yet. |
Author: | alexfru [ Mon Jun 03, 2019 3:19 am ] |
Post subject: | Re: How to make a compiler |
Schol-R-LEA wrote: Depending on the number of potential transitions, and the amount of optimization the compiler performs, lexical analysis can consume up to 80% of the running time (the textbook Modern Compiler Design by Grune, et. al., explains why in detail). I presume, that figure of 80% corresponds to non- or nearly non-optimizing compilers. The languages that allow writing code with exponential compile times (where the compiler needs to try this or that in order to resolve ambiguity, potentially many times nested) are probably a separate category of their own. |
Author: | nyc [ Thu Jan 23, 2020 6:52 pm ] |
Post subject: | Re: How to make a compiler |
Korona wrote: A LLVM-style Greedy RA is superior to graph coloring RAs in practice, prove me wrong. Graph coloring just cannot easily handle non-homogeneuos register files (and of course, it's also quite expensive). When I wrote an implementation (only a bit over 1k SLOC, can do live range splitting but not register spilling right now) inspired by the LLVM one, I was surprised (i) how natural it is, and (ii) how good the results are if you tune it a bit (for smallish functions with only a few basic blocks/variables, the result is often optimal). It's incredibly easy to tune -- when you see a missed optimization, it's usually straightforward to see how to extend the RA to handle it. I like things like http://people.cs.pitt.edu/~soffa/research/Comp/gurr.ps as ways to make graph colouring or analysis go through, though I'm admittedly coming from the point of view of someone not really interested enough in compilers to code up an implementation of it or a more recent algorithm in the same vein. |
Page 1 of 1 | All times are UTC - 6 hours |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |