OSDev.org

The Place to Start for Operating System Developers
It is currently Sun Apr 21, 2019 12:18 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: How to make a compiler
PostPosted: Thu Mar 28, 2019 5:25 pm 
Offline
Member
Member
User avatar

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 633
It's literally just lots of graph problems; graph coloring, vertex reachability, etc. Prove me wrong.

_________________
Glidix: An x86_64 POSIX-compliant operating system, aiming to be as optimized as possible, especially in graphics.
https://glidix.madd-games.org/


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Thu Mar 28, 2019 5:31 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1445
Location: Athens, GA, USA
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.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Thu Mar 28, 2019 6:50 pm 
Offline
Member
Member

Joined: Tue Mar 04, 2014 5:27 am
Posts: 951
mariuszp wrote:
It's literally just lots of graph problems; graph coloring, vertex reachability, etc.

Only if your compiler is an optimizing one.


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Fri Mar 29, 2019 12:15 am 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 564
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.

_________________
managarm: A microkernel-based OS that is capable of running a Wayland desktop


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Fri Mar 29, 2019 9:08 am 
Offline
Member
Member
User avatar

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 633
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.

_________________
Glidix: An x86_64 POSIX-compliant operating system, aiming to be as optimized as possible, especially in graphics.
https://glidix.madd-games.org/


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Fri Mar 29, 2019 9:48 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1445
Location: Athens, GA, USA
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).

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Fri Mar 29, 2019 12:04 pm 
Offline
Member
Member

Joined: Thu May 17, 2007 1:27 pm
Posts: 564
Doesn't hold when you want to parse C++. (And context-sensitivity gives you a PSPACE-complete problem.)

_________________
managarm: A microkernel-based OS that is capable of running a Wayland desktop


Top
 Profile  
 
 Post subject: Re: How to make a compiler
PostPosted: Fri Mar 29, 2019 4:56 pm 
Offline
Member
Member
User avatar

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 633
There is probably a pretty obvious reason why P is a strict subset of NP, which nobody thought of, because it's "too obvious".

_________________
Glidix: An x86_64 POSIX-compliant operating system, aiming to be as optimized as possible, especially in graphics.
https://glidix.madd-games.org/


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group