8
$\begingroup$

What is the most traditional or meaningful order for learning formal languages, automata, compilers and parsing, if there's one at all?

Would students benefit from a parallel course in formal languages/automata, so as to highlight the connections?

$\endgroup$

2 Answers 2

11
$\begingroup$

I'm happy to stand corrected if someone else comes in with a more experienced answer, but automata and formal languages are typically taught together as two aspects of computational theory, since different sorts of automata represent different sorts of languages. Among other reasons, it's hard to have a discussion about the computing power of modified automata without having the languages to refer to.

As for compilers and parsers, if the goal of a compilers course is to show a student how written code can be translated into machine code, how could you approach one without the other? "This compiler takes a... tree... and turns it into machine code." The topics are significantly enough interrelated that I would have trouble imagining a sequence where they don't get mixed in together.

I believe (though I have not done a thorough search of course sequences to back this up) that compilers is typically taught sometime after computational theory, since it helps to be at least nominally familiar with the notion of a grammar before you begin.

$\endgroup$
1
  • $\begingroup$ Indeed, i believe automata/formal languages course was a pre-req for compilers; nevertheless, we covered the necessary elements of CFGs at the beginning of compilers. $\endgroup$ Jan 1, 2020 at 15:28
3
$\begingroup$

From my experience: compilers is basically the crown jewel subject where all the others come together.

First year you start out with regular languages and finite state automata, and you see how that relates to your basic programming class. In two other classes, you see how propositional logic relates to basic circuit design.

Second year, you get into context-free grammars and in a class that only somewhat feels related to it, concepts of programming languages. Meanwhile you get computer architecture making a bridge from hardware to assembly language.

Third year, compiler construction brings them all together.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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