6
$\begingroup$

I've read up on Finite State Automata in a lot of different books on compiler construction (two of which are actually called Compiler Construction) and I'm kind of at a loss. I understand the idea of moving from state to state and having a state that is accepted. What I don't understand is why in the world this theory is regurgitated in such an obscenely convoluted way?

If you were to tell me that the point of FSA within a compiler is for Lexical Analysis and that its purpose therein is just to go character by character and determine whether or not a word is an identifier, keyword, or other token, I would be completely confident in my understanding. Problem is that in every chapter of finite state automata I have to go over 50 pages of rigorous notation, differences between non-deterministic and deterministic finite state automata (including separate notation where Epsilon is three different things based on its styling) and a dozen or more of these graphs:

FS Vending Machine

My question is this: Do I need to understand more than this to write a Compiler? Is there something unique about FSA that I'm just completely missing? Or is this just an over complication of a simple concept in regards to creating a compiler?

| cite | improve this question | |
$\endgroup$
  • 11
    $\begingroup$ "why in the world this theory is regurgitated in such an obscenely convoluted way? " -- that, apparently, lies in the eyes of the beholder. Note that finite automata have uses outside of compilers, and are generally a cleaner model than the specific automata that drive lexers. Anyway, your issue seems to be with mathematics as a language. No, you can't really get around it. As a programmer, that should not be weird for you. My recommendation is to dial back the anger and go at introductory resources with an open mind. Chances are you'll learn something that will make you a better programmer! $\endgroup$ – Raphael♦ Jul 24 '17 at 17:40
  • $\begingroup$ Note that there is much more to writing a compiler than a lexer (or even a parser). You could be an expert at FSAs and not know how to write a compiler. $\endgroup$ – Derek Elkins left SE Jul 24 '17 at 22:28
  • 4
    $\begingroup$ @iwannawriteacompiler Have you tried just starting to write code and then seeing where you have difficulty or think "there's gotta be a better way"? Writing a simple compiler for a simple language isn't hard. You'll almost certainly make a mess of it, but you'll probably get something working and will have of where theory can be useful and why it exists. $\endgroup$ – Derek Elkins left SE Jul 24 '17 at 23:02
  • 1
    $\begingroup$ @iwannawriteacompiler Maybe you find my basic introduction to compilers course helpful. I'm explaining FSAs quite informally. All my students write a simple compiler as coursework (at least those who don't cheat). If my students were more mathematically sophisticated I would explain the conversion from REs to FSAs using Brzozowski derivatives (or similar), rather than $\epsilon$-automata. $\endgroup$ – Martin Berger Jul 25 '17 at 9:49
  • 1
    $\begingroup$ Wow. Thanks for the references. They are phenomenal and are much clearer than what I've been digging through. @MartinBerger would you mind if I e-mailed you about your coursework - I had a minor question regarding two examples on the second handout? If not, I understand. I would like to say that they are very thorough and well explained. Thanks so much for linking me. $\endgroup$ – iwannawriteacompiler Jul 25 '17 at 17:25
13
$\begingroup$

What you have asked: "Do I need to understand more than this to write a compiler?" then answer is basically, No - but it does depend on the compiler!

You need to know a lot of theory about a lot of other things, and you could eventually ask about them too. For example, when you get to parsing you might ask "Do I need to know about top-down and bottom-up parsing". Do I need to know the difference between LL, LR, LALR parsing? Do I need to know about Chomsky Level 1 Grammars? Does it matter who Noam Chomsky actually is? Do I need to be able to know how to parse ambiguous languages? Do I need to know about data-flow in optimisation, do I need to know about flow-graphs? Do I need to know about machine architecture? Do I need to know about both register based machine code and stack based machine code?

Just so many things that one could question the need for!

You can write some kind of compiler without knowing any of this, but you wouldn't be fully equipped with all the background knowledge to be able to write any compiler!

If your task was to write a very straightforward compiler for a straight forward language then you can get away without knowing a lot of the background theory. There are some class exercises like that. If your jobs was as a compiler writer then you might be expected to be able to do a bit more.

The next part of your question to address are the textbooks you have used. Most of the textbooks are written for use on undergraduate Computer Science courses. In many/most those courses the background theory behind the practice of writing compilers is included because that is what most course curricula need. This then permits the students to use their wider knowledge to implement compilers for the as-yet-to-be-specified languages to solve the problems of the future. If you could only tackle the simple subset problems from introductory classes that did not require thinking outside the box you knowledge would be rather useless; or rather only useful for class credit, but not much beyond.

I hope that gives the view of a compiler writer and computer scientist. My students sometimes ask the same questions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Apologies, this is my question but I'm not able to accept because I used a guest account and I don't have an alternate e-mail. I appreciate the response. I definitely was not trying to appear dismissive of learning the applications of FA - but I admittedly was frustrated with the out-of-nowhere dump of information when I was getting along fine through my books. I'm self-taught and was never able to get a Higher Education. I've always wanted to build a compiler since I was a kid(really) and it was like I started running through molasses with the chapters on FA. Thanks for your patience. $\endgroup$ – iwannawriteacompiler Jul 24 '17 at 19:15
  • 1
    $\begingroup$ @iwannawriteacompiler Most people don't even know that CS is really a science (worst in other countries because term science is not used to name it!). Of course you can write plenty software without too much knowledge of this kind, but if you want a good level of safety then you must know these scientific tools (I doubt many people would use your DIY plane if you didn't know/use known physicals laws). Too many applications are bad for this sole reason: DIY software. Software need different kind of reasoning and structure to work properly, FSA is one of those tools. $\endgroup$ – Jean-Baptiste Yunès Jul 25 '17 at 7:23
  • 1
    $\begingroup$ In practice, for the decade or so, Chomsky, LL, LR, LALR has almost nothing to do with real world parsers since everyone uses PEGs. You don't need to know the difference between Stevenson's and Walschaerts steam locomotive valve gear to design electric trains. $\endgroup$ – Pete Kirkham Jul 25 '17 at 9:30
  • $\begingroup$ (of course PEGs still relate strongly to non-deterministic automata) $\endgroup$ – Pete Kirkham Jul 25 '17 at 9:32
8
$\begingroup$

You don't need to know FSAs for writing a compiler, provided you use a lexer generator that writes the lexer for you.

In parts the emphasis on FSAs in compiler books is historical: fast lexing used to be a big problem in early computer science and the theory of FSAs is some of the earliest and most developed of computer science. Most textbooks (and lectures) are small variants of earlier textbooks. In the case of compilers the dominant textbook has been the Dragon Book. It is almost half a century old and has quite a lot to say about lexing and FSAs.

Another reason might be that lexing and FSAs are the easiest part of a compiler, and teachers might feel they should explain at least something about compilers with full rigour. BTW, even writing a lexer by hand for a toy language is not simple, because the resulting FSA is quite large (> 1k states). If you 'cheat' and use a regular expression library you'll probably get it wrong -- I know because I teach compilers and writing a lexer / parser for a toy language is one of the assessed exercises they'll have to do. Moreover, regular expression parsers are also implemented 'under the hood' using FSAs.

Finally, FSAs are incredibly useful in computer science, and you do yourself a favour to understand them well. See this answer for some of the uses of FSAs.

In practise understanding lexing / parsing is probably the most important part of a compilers course: almost no student will ever write a type inferencer or code generator in their commercial work, but just about any non-trivial programming task involves reading small (and not so small) formal languages. Almost nothing is as useful as mastery of lexer and parser generators to get this done quickly.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.