patternModerate
Finite State Automata Within A Compiler
Viewed 0 times
finiteautomatawithinstatecompiler
Problem
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:
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?
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:
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#79284, answer score: 13
Revisions (0)
No revisions yet.