Reddit reviews Compilers: Principles, Techniques, and Tools (2nd Edition)
We found 59 Reddit comments about Compilers: Principles, Techniques, and Tools (2nd Edition). Here are the top ones, ranked by their Reddit score.
Here's my list of the classics:
General Computing
Computer Science
Software Development
Case Studies
Employment
Language-Specific
C
Python
C#
C++
Java
Linux Shell Scripts
Web Development
Ruby and Rails
Assembly
A program in any language goes through either a compiler or an interpreter, or a mixture of both. A compiler turns the program into a series of machine instructions, low level codes that the processor knows how to "execute". An interpreter executes a program indirectly.
The first step of both compiling and interpreting is called parsing. This step takes the program text and converts it into an internal representation called an AST (Abstract Syntax Tree). For e.g. this converts "if" and its attached test and statement blocks into one kind of object, and "or" and its attached expressions into another kind. The compiler or interpreter knows that these two objects should be handled differently.
Programming languages are often programmed in themselves. However, a bootstrapping process is required to create the first compiler or interpreter, i.e. the first version needs to be written in a different language. For low level languages like C, this bootstrapping language is usually assembler. For other languages, more often than not the bootstrapping language is C. Some compilers or interpreters are written in different languages, e.g. the most popular version of Python (which is a mix of a compiler and an interpreter) is written in C.
Going from "rand()" to a string of bytes has more to do with calling a library than a specific feature of a programming language. From the PL point of view, "rand()" is a function call. This function resides in a library that may or may not be written in the same language, in any case, it contains the logic to generate a random number. There are several ways to do this, google or wikipedia for Pseudo Random Number Generator (PRNG).
The standard reference on compilers and interpreters is the so-called Dragon Book, I'll leave it up to others to suggest more material.
But the Dragon Book has cool dragons on it!
"Introduction to Algorithms"by Cormen et.al. Is for me the most important one.
The "Dragon" book is maybe antoher one I would recommend, although it is a little bit more practical (it's about language and compiler design basically). It will also force you to do some coding, which is good.
Concrete Mathematics by Knuth and Graham (you should know these names) is good for mathematical basics.
Modern Operating Systems by Tennenbaum is a little dated, but I guess anyone should still read it.
SICP(although married to a language) teaches very very good fundamentals.
Be aware that the stuff in the books above is independent of the language you choose (or the book chooses) to outline the material.
Should have gotten her this dragon book so she can get a headstart on writing compilers.
Thank you all for your responses! I have compiled a list of books mentioned by at least three different people below. Since some books have abbreviations (SICP) or colloquial names (Dragon Book), not to mention the occasional omission of a starting "a" or "the" this was done by hand and as a result it may contain errors.
edit: This list is now books mentioned by at least three people (was two) and contains posts up to icepack's.
edit: Updated with links to Amazon.com. These are not affiliate - Amazon was picked because they provide the most uniform way to compare books.
edit: Updated up to redline6561
I'm sort of in the same boat as you, except with an aero and physics background rather than EE. My approach has been pretty similar to yours--I found the textbooks used by my alma mater, compared to texts recommended by MIT OCW and some other universities, looked at a few lists of recommended texts, and looked through similar questions on Reddit. I found most areas have multiple good texts, and also spent some time deciding which ones looked more applicable to me. That said, I'm admittedly someone who rather enjoys and learns well from textbooks compared to lectures, and that's not the case for everyone.
Here's what I gathered. If any more knowledgeable CS guys have suggestions/corrections, please let me know.
Full disclosure: I haven't actually read more than the preface of any of those books. Software engineering topics are more directly applicable to me than CS topics right now, so here are some that I've actually started reading:
The code you posted was generated from a grammar definition, here's a copy of it:
http://www.opensource.apple.com/source/bc/bc-21/bc/bc/bc.y
As such, to answer the question in your title, this is the best code you've ever seen, in the sense that it embodies some very powerful computer science concepts.
It [edit: the Bison parser generator] takes a definition of a language grammar in a high-level, domain-specific language (the link above) and converts it to a custom state machine (the generated code that you linked) that can extremely efficiently parse source code that conforms to the defined grammar.
This is actually a very deep topic, and what you are looking at here is the output of decades of computer science research, which all modern programming language compilers rely on. For more, the classic book on the subject is the so-called Dragon Book, Compilers: Principles, Techniques, and Tools.
You might have some better luck if you go top down. Start out with an abstracted view of reality as provided by the computer, and then peel off the layers of complexity like an onion.
I would recommend a "bare metal" approach to programming to start, so C is a logical choice. I would recommend Zed Shaw's intro to C: http://c.learncodethehardway.org/book/
I would proceed to learning about programming languages, to see how a compiler transforms code to machine instructions. For that, the classical text is the dragon book: http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811
After that, you can proceed to operating systems, to see how many programs and pieces of hardware are managed on a single computer. For that, the classical text is the dinosaur book: http://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/1118063333 Alternatively, Tannenbaum has a good one as well, which uses its own operating system (Minix) as a learning tool: http://www.amazon.com/Modern-Operating-Systems-Andrew-Tanenbaum/dp/0136006639/ref=sr_1_1?s=books&ie=UTF8&qid=1377402221&sr=1-1
Beyond this, you get to go straight to the implementation details of architecture. Hennessy has one of the best books in this area: http://www.amazon.com/Computer-Architecture-Fifth-Quantitative-Approach/dp/012383872X/ref=sr_1_1?s=books&ie=UTF8&qid=1377402371&sr=1-1
Edit: Got the wrong Hennessy/Patterson book...
The Dragon Book by somebody. A bit out of date now, but really helped me with my parser/tree implementation.
For designing programming languages, my favorites are
If you only get one then go with Pierce. But If you want to get serious about semantics, then Winskel is the way to go.
On the implementation side my favorites are
Was expecting this dragon book
Here are some standard textbooks on the subject. When I am looking for a book on a particular subject, I like to look at the class schedules for local universities and see what they are using. A class on programming languages is a standard part of a CS program I believe.
Compilers: Principles, Techniques, and Tools
http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811/ref=sr_1_3?ie=UTF8&qid=1343095509&sr=8-3&keywords=Dragon+Book
Concepts of Programming Languages
http://www.amazon.com/Concepts-Programming-Languages-Robert-Sebesta/dp/0136073476/ref=sr_1_5?s=books&ie=UTF8&qid=1343095607&sr=1-5&keywords=Programming+languages
Programming Language Pragmatics
http://www.amazon.com/Programming-Language-Pragmatics-Second-Michael/dp/0126339511/ref=sr_1_2?s=books&ie=UTF8&qid=1343095647&sr=1-2&keywords=Programming+language+pragmatics
LFTL.
I've peeked at this free online book a few times when implementing things. I think it's a pretty solid reference with more discussion of these sorts of things!
Another option is a "real" textbook.
My programming languages course in university followed Programming Languages: Application and Interpretation (which is available online for free). It's more theory-based, which I enjoyed more than compilers.
But the dragon book is the go-to reference on compilers that is slightly old but still good. Another option is this one, which is a bit more modern. The latter was used in my compilers course.
Outside of that, you can read papers! The older papers are actually pretty accessible because they're fairly fundamental. Modern papers in PL theory can be tricky because they build on so much other material.
If you want to know how interpreters/compilers work:
Bonus: http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/
Edit: have fun!
sipser (I have the first edition which you can get on the cheap, it's very good.)
AIMA
Dragon
Naturally, TAOCP.
Many will also recommend SICP, though I'm not quite sure that's what you're angling at here, it's probably worth browsing online to see.
The object you're interested in is the call graph of the program. As you've observed, this is a DAG iff there is no recursion in the program. If function A calls B and B calls A, this is called mutual recursion and still counts as recursion :)
A related graph is the control flow graph (CFG) of a function. Again, the CFG is a DAG iff the function doesn't contain loops.
An execution trace of a program can certainly be represented as a DAG. In fact, since an execution trace does not have any branching, it is just a straight line! However you are very rarely interested in a single trace through a program -- you usually want to reason about all the traces. This is more difficult because if you have any looping structure in the global CFG, there is no (obvious) upper bound on the size of a trace, and so you can't capture them all with a finite structure that you can map into SMT.
Every program can be put into SSA form. The trick is that when you have joins in the control flow graph (such as at the head of a loop), you need a phi node to fix up the SSA indices. If you don't have it already, the dragon book is pretty much required reading if you're interested in any kind of program analysis.
In general, if you have a loop free control flow graph of any kind (a regular CFG or a call graph), then you can translate that graph directly into SAT or SMT in a fairly obvious way. If you have loops in the graph then you can't do this (because of the halting problem). To reason about programs containing loops, you're going to need some more advanced techniques than just symbolic execution. The big names in verification algorithms are:
A good overview of the field is this survey paper. To give an even briefer idea of the flavour of each of these techniques:
Bounded model checking involves unwinding all the loops in the program a fixed number of times [; k ;]. This gives you a DAG representing all of the traces of length up to [; k ;]. You bitblast this DAG (i.e. convert it to SAT/SMT) and hand off the resulting problem to a SMT solver. If the problem is SAT, you've found a concrete bug in the program. If it's UNSAT, all you know is that there is no bug within the first [; k ;] steps of the program.
Abstract interpretation is about picking an abstract domain to execute your program on, then running the program until you reach a fixed point. This fixed point tells you some invariants of you program (i.e. things which are always true in all runs of the program). The hope is that one of these invariants will be strong enough to prove the property you're interested in.
Predicate abstraction is just a particular type of abstract interpretation where your abstract domain is a bunch of predicates over the variables of the program. The idea is that you get to keep refining your abstraction until it's good enough to prove your property using counterexample guided abstraction refinement.
Interpolation can be viewed as a fancy way of doing predicate refinement. It uses some cool logic tricks to do your refinement lazily. The downside is that we don't have good methods for interpolating bitvector arithmetic, which is pretty crucial for analyzing real programs (otherwise you don't take into account integer overflow, which is a problem).
A final wildcard technique that I'm just going to throw out there is loop acceleration. The idea here is that you can sometimes figure out a closed form for a loop and replace the loop with that. This means that you can sometimes remove a loop altogether from the CFG without losing any information or any program traces. You can't always compute these closed forms, but when you can you're in real good shape.
Drop me a message if you want to know anything else. I'm doing a PhD in this exact area & would be happy to answer any questions you have.
Have you worked through the loop detection in the Dragon Book? There are some slides on it here:
http://www.cs.cmu.edu/afs/cs/academic/class/15745-s03/public/lectures/L7_handouts.pdf
My compilers course in college used the Dragon Book, which is one of the more quintessential books on the subject.
​
But you might also consider Basics of Compiler Design which is a good and freely available resource.
​
I'd also suggest that you have familiarity with formal languages and automata, preferably through a Theory of Computation course (Sipser's Introduction to the Theory of Computation is a good resource). But these texts provide a brief primer.
Start with the Dragon Book.
When it actually comes time to implement the language, I would recommend just writing the frontend and reusing the backend from another compiler. LLVM is a good option (it's becoming popular to use as a backend, it now has frontends for C, C++, Objective C, Java, D, Pure, Hydra, Scheme, Rust, etc). See here for a case study on how to write a compiler using LLVM as the backend.
For compilers:
Types and Programming Languages by Pierce is also a must read for theory people.
Per testare le acque velocemente puoi usare https://rubymonk.com/ (introduce Ruby in modo basico). Anche Coursera, Khan, Udacity e simili hanno corsi introduttivi sulla programmazione.
Mentre se vuoi imparare a programmare, il percorso deve toccare almeno tutte queste tappe, in ordine:
Organization-Design-Fourth-Edition/dp/0123744938)
Da qui puoi partire e specializzarti in quello che ti interessa
When I started getting interested in compilers, the first thing I did was skim issues and PRs in the GitHub repositories of compilers, and read every thread about compiler construction that I came across on reddit and Hacker News. In my opinion, reading the discussions of experienced people is a nice way to get a feel of the subject.
As for 'normal' resources, I've personally found these helpful:
In addition, just reading through the source code of open-source compilers such as Go's or Rust's helped immensely. You don't have to worry about understanding everything - just read, understand what you can, and try to recognize patterns.
For example, here's Rust's parser. And here's Go's parser. These are for different languages, written in different languages. But they are both hand-written recursive descent parsers - basically, this means that you start at the 'top' (a source file) and go 'down', making decisions as to what to parse next as you scan through the tokens that make up the source text.
I've started reading the 'Dragon Book', but so far, I can't say it has been immensely helpful. Your mileage may vary.
You may also find the talk 'Growing a language' interesting, even though it's not exactly about compiler construction.
EDIT: grammar
This is a great question! It's also one that every serious CS person will ask at some point. As others here have noted, to really understand this question you must understand how compilers work. However, it isn't necessary to understand the gory details of compiler internals to see what a compiler does for you. Let's say you have a file called hello.cpp that contains the quintessential C++ program
include <iostream>
The first thing the compiler does is called preprocessing. Part of this process includes expanding the
#includestatements into their proper text. Assuming you are using gcc, you can have it show you the output of this stepgcc -E -o hello.pp hello.cpp
For me, the hello.cpp files explodes from 4 lines to nearly 18000! The important thing to note here is that the contents of the iostream library header occur before the
int mainlines in the output.The next several step for the compiler are what you will learn about in compiler design courses. You can take a peek at gcc-specific representations using some flags as discussed on SO. However, I pray you give heed. For there be dragons!
Now let's take a look at the compiler's output. To do this, I am going to not
#includeanything so the output is very simple. Let's use a file called test.cpp for the rest of the tests.int main() {
int i = 3, j = 5;
float f = 13.6 / i;
long k = i<<j;
}
To see the compiler's output, you can use
g++ -S -masm=intel test.cpp
The
-Sflag asks gcc to just output the generated assembly code and-masm=intelrequests the intel dialect (by default, gcc uses the AT&T dialect, but everyone knows the intel one is superior. :) ) The output on my machine (ignoring setup and teardown code) is outlined below.push rbp
mov rbp, rsp
/ int i = 3, j = 5; /
mov DWORD PTR [rbp-20], 3
mov DWORD PTR [rbp-16], 5
/ float f = 13.6 / i; /
pxor xmm0, xmm0
cvtsi2sd xmm0, DWORD PTR [rbp-20]
movsd xmm1, QWORD PTR .LC0[rip]
divsd xmm1, xmm0
movapd xmm0, xmm1
cvtsd2ss xmm2, xmm0
movss DWORD PTR [rbp-12], xmm2
/ long k = i<<j; /
mov eax, DWORD PTR [rbp-16]
mov edx, DWORD PTR [rbp-20]
mov ecx, eax
sal edx, cl
mov eax, edx
cdqe
mov QWORD PTR [rbp-8], rax
/ implicit return 0; /
mov eax, 0
pop rbp
ret
There are lots of details to learn in here, but you can generally see how each simple C++ statement translates into many assembly instructions. For fun, try compiling that program with the optimizer turned on (with g++, you can use
-O3). What is the output?There is still much to see from the binary that is assembled. You can use
nmandobjdumpto see symbols orlddto see what other libraries were (dynamically) linked into the executable. I will leave that as an exercise for the reader. :)But make sure to get the 2nd edition of the Compiler book. It has been enhanced quite a bit.
> And which coder uses physical books any more?
I do for things beyond actual language references; e.g. maybe everything in The Dragon Book has a good description somewhere, but grabbing that off my desk and having a decent chance of it having what I want (it has some problems and omissions, but it's reasonably good) will save wading through a bunch of crap online until I find something complete and accurate enough.
I don't know what he'd recommend, but I found the Dragon Book and Modern Compiler Design to be decent treatments of the subject. There are lots of interesting texts out there though.
Sorry for the cheeky reply.
There are books specifically on language design, syntax trees, and unambiguous grammars.
The classic books on compiler design are "The Dragon Book", designing a compiler is important because a statement in the language should mean exactly one thing, and a language should be able to be compiled efficiently. This is more difficult than it sounds.
Second, you need to understand language design, variable binding, etc. This is a topic of Programming Language Paradigms. I'll figure out a good book for this and edit to add it. The best book probably covers languages like Ada, Haskell, C, and Java and gives an overview of their design and reasons.
edit: The book for design is Concepts of Programming Languages 9th ed, by Robert W. Sebesta.
Reminds me of a joke:
a: "Alright the book is done, all that is left is to choose a cover".
b: "Dragons"
a: "B-but the book is about..."
b: "DRAGONS I SAID"
Book
Compilers-Principles-Techniques-Tools is considered THE definitive book on the subject. It's old, but in a fine wine kind of way.
If you mean writing an interpreter or compiler, then yes. The iconic book for learning how to build languages is called Compilers, Principles, Techniques and Tools. It's often referred to as 'The Dragon Book'. It's pretty heavy reading but contains everything you need to know about building a language!
If you're looking for something more implementation driven, I recently read a book about building a programming language in Go. The principles are the same, just with a different language. The book was called Writing an Interpreter in Go. It's a much lighter read and details the construction of an interpreter from scratch!
http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0321486811
I ordered these for our company library, based on recommendations for/from other programmers (of all levels).
ISBN | Title
---|---
978-1568814247 | Real-time Rendering
0321486811 | Compilers: Principles, Techniques, and Tools (2nd Edition)
1482250926 or 0123742978 | Essential Mathematics for Games and Interactive Applications, Third Edition 3rd Edition
978-1482264616 | GPU Pro 6: Advanced Rendering Techniques
1466560010 | Game Engine Architecture, Second Edition
978-1482243567 | Multithreading for Visual Effects
978-0123750792 | Physically Based Rendering: From Theory To Implementation
That's a good question, acutally. I picked it up in bits and pieces over years. I probably started to pick up when I tried to implement an object-oriented programming system in C. The dragon book was also a great help in figuring this sort of stuff out.
Another great way to learn is to write simple test programs in C or C++, and see what they compile down to with GCC. Using '-O' I find gives me the most readable "direct" assembly.
http://asm.sourceforge.net/howto/Assembly-HOWTO.html
Also, if you have any specific questions, possibly a tutorial or two... well, it's time that I started putting together a website.
Have you ever seen the Dragon Book?
http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=sr_1_1?ie=UTF8&amp;qid=1292732652&amp;sr=8-1
No THAT'S an ugly cover.
https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=mp_s_a_1_1?keywords=compilers&amp;qid=1573050573&amp;sr=8-1
Regarding sandboxing, at least in lua from what I know you can have minute control over what libs access to, and users can only import other libraries if you allow them to (by including a "library" that imports other libraries :-).
Perhaps you should look into formal languages and parser generators, so you can create more complex languages if you feel like it. Even if you build the parsers yourself having the language specified, factorized and so on, helps a lot. The dragon book is a good choice, although it presupposes you know a bit about specifying a formal language IIRC. If you're a student (I know how it is!) then even the old dragon book is an excellent read and it's very cheap.
For anyone who wants to learn more about compilers and loves reading books, the so called dragon book is highly recommended lecture on this topic: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
Well I think better book is http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811 and in the book use the C language
I read this book when I had to write a compiler in my job :)
Compilers: Principles, Techniques, and Tools,
by Aho, Sethi and Ullman
first ed: http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886
second ed: http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
For what it's worth, I'm in the midst of working through the dragon book and would highly recommend it. Unfortunately I don't know of any online courses you could take for credit.
Senior Level Software Engineer Reading List
Read This First
Fundamentals
Development Theory
Philosophy of Programming
Mentality
Software Engineering Skill Sets
Design
History
Specialist Skills
DevOps Reading List
While being a self taught sys admin is great, learning the internals of how things work can really extend your knowledge beyond what you may have considered possible. This starts to get more into the CS portion of things, but who cares. It's still great stuff to know, and if you know this you will really be set apart. Im not sure if it will help you directly as a sys admin, but may quench your thirst. Im both a programmer and unix admin, so I tend to like both. I own or have owned most of these and enjoy them greatly. You may also consider renting them or just downloading them. I can say that knowing how thing operate internally is great, it fills in a lot of holes.
OS Internals
While you obviously are successful at the running and maintaining of unix like systems. How much do you know about their internal functions? While reading source code is the best method, some great books will save you many hours of time and will be a bit more enjoyable. These books are Amazing
The Design and Implementation of the FreeBSD Operating System
Linux Kernel Development
Advanced Programming in the UNIX Environment
Networking
Learning the actual function of networking at the code level is really interesting. Theres a whole other world below implementation. You likely know a lot of this.
Computer Networks
TCP/IP Illustrated, Vol. 1: The Protocols
Unix Network Programming, Volume 1: The Sockets Networking API
Compilers/Low Level computer Function
Knowing how a computer actually works, from electricity, to EE principles , through assembly to compilers may also interest you.
Code: The Hidden Language of Computer Hardware and Software
Computer Systems: A Programmer's Perspective
Compilers: Principles, Techniques, and Tools
OK, a few things:
It looks like you're trying to build a shift/reduce parser, which is a form of an LR parser, for your language. LR parsers try to reduce symbols into more abstract terms as soon as possible. To do this, an LR parser "remembers" all the possible reductions that it's pursuing, and as soon as it sees the input symbols that correspond to a specific reduction, it will perform that reduction. This is called "handle finding".
> If I am correct, my Automaton is a DFA?
When the parser is pursuing a reduction, it's looking for sequences of symbols that match the right-hand sides of the relevant (to our current parse state) productions in our grammar. Since the right-hand sides of all the productions in a grammar are simple sequences, all the handle finding work can be done by a DFA. Yes, the handle recognizer of your parser is a DFA. But keep in mind that it needs to be combined with other parts to make a full parser, and your actual grammar can't be recognized with just a DFA.
In particular, you've shown the
ACTIONtable for a shift/reduce parser. It determines what to do when you encounter a symbol in the input stream. But a shift/reduce parser typically needs a second table as well - theGOTOtable - that determines what to do after a reduction has taken place.One other thing that's worth mentioning: you've expressed your
ACTIONtable as a plain DFA transition table. That's not necessarily wrong, but it's not commonly done that way. Instead of reducing when you reach a certain state, it's common to instead attach an action - either 'shift' or 'reduce' ('accept') - to each transition itself. So in a shift/reduce parser, your table might look more like this:| [ | ] | < | > | id | / | attr
----+-----+-----+-----+-----+------+-----+--------
0 | S1 | | S4 | | | |
1 | | | | | S2 | | R3 : Reduce Tag -> [ id ]
2 | | R3 | | | | | R7 : Reduce Tag -> < id ??? / >
4 | | | | | S5 | S10 | R9 : Reduce Tag -> < id ??? >
5 | | | | R9 | | S6 | S8 R12 : Reduce Tag -> < / id >
6 | | | | R7 | | |
8 | | | | R9 | | S6 | S8
10 | | | | | S11 | |
11 | | | | R12 | | |
Note that
R7andR9aren't well-formed, since multiple sequences of input tokens might cause you to reach these actions. While it would be possible to construct a shift / reduce parser this way, it's not commonly done. Typically, the DFA to recognize handles is an acyclic graph, but your have a self-transition in state 8.> What would be the best way of implementing this automaton in C++? Do I really have to make a huge array?
In general, yes, you need a big array (or, as suggested before, two big arrays). But you can use any space-saving technique you want. For example, since most entries in the
ACTIONtable are invalid, one could represent that data with a sparse array data structure. Also, both The Dragon Book and Cooper and Torczon briefly cover parser-specific ways to compress those tables. For example, notice that rows 5 and 8 in your example have the same entries. Most real grammars have multiple instances of identical rows, so factoring out this commonality can save enough space that the extra complexity is worth it.---
I'm a little surprised that you're building a parser like this by hand, though. Typically people do one of two things:
You're sort of doing a mix of the two, which means you have the downsides of both approaches. You need to track all the states and transitions by hand, instead of relying on tools to automate that process, yet you don't get the flexibility of a hand-coded recursive descent parser.
If you're doing this for education's sake, then by all means proceed. I'd highly encourage you to pick up a book on parsing; I think Cooper and Torczon is a great source. But if you just want a parser that works, I'd definitely recommend using a tool or using a more direct approach, like recursive-descent.
> It’s hard to consolidate databases theory without writing a good amount of code. CS 186 students add features to Spark, which is a reasonable project, but we suggest just writing a simple relational database management system from scratch. It will not be feature rich, of course, but even writing the most rudimentary version of every aspect of a typical RDBMS will be illuminating.
>
> Finally, data modeling is a neglected and poorly taught aspect of working with databases. Our suggested book on the topic is Data and Reality: A Timeless Perspective on Perceiving and Managing Information in Our Imprecise World.
>
>
>
>
>
> ### Languages and Compilers
>
> Most programmers learn languages, whereas most computer scientists learn about languages. This gives the computer scientist a distinct advantage over the programmer, even in the domain of programming! Their knowledge generalizes; they are able to understand the operation of a new language more deeply and quickly than those who have merely learnt specific languages.
>
> The canonical introductory text is Compilers: Principles, Techniques & Tools, commonly called “the Dragon Book”. Unfortunately, it’s not designed for self-study, but rather for instructors to pick out 1-2 semesters worth of topics for their courses. It’s almost essential then, that you cherrypick the topics, ideally with the help of a mentor.
>
> If you choose to use the Dragon Book for self-study, we recommend following a video lecture series for structure, then dipping into the Dragon Book as needed for more depth. Our recommended online course is Alex Aiken’s, available from Stanford’s MOOC platform Lagunita.
>
> As a potential alternative to the Dragon Book we suggest Language Implementation Patterns by Terence Parr. It is written more directly for the practicing software engineer who intends to work on small language projects like DSLs, which may make it more practical for your purposes. Of course, it sacrifices some valuable theory to do so.
>
> For project work, we suggest writing a compiler either for a simple teaching language like COOL, or for a subset of a language that interests you. Those who find such a project daunting could start with Make a Lisp, which steps you through the project.
>
>
>
> [Compilers: Principles, Techniques & Tools](https://teachyourselfcs.com//dragon.jpg) [Language Implementation Patterns](https://teachyourselfcs.com//parr.jpg)> Don’t be a boilerplate programmer. Instead, build tools for users and other programmers. Take historical note of textile and steel industries: do you want to build machines and tools, or do you want to operate those machines?
>
> — Ras Bodik at the start of his compilers course
>
>
>
>
>
> ### Distributed Systems
>
> As computers have increased in number, they have also spread. Whereas businesses would previously purchase larger and larger mainframes, it’s typical now for even very small applications to run across multiple machines. Distributed systems is the study of how to reason about the tradeoffs involved in doing so, an increasingly important skill.
>
> Our suggested textbook for self-study is Maarten van Steen and Andrew Tanenbaum’s Distributed Systems, 3rd Edition. It’s a great improvement over the previous edition, and is available for free online thanks to the generosity of its authors. Given that the distributed systems is a rapidly changing field, no textbook will serve as a trail guide, but Maarten van Steen’s is the best overview we’ve seen of well-established foundations.
>
> A good course for which some videos are online is MIT’s 6.824 (a graduate course), but unfortunately the audio quality in the recordings is poor, and it’s not clear if the recordings were authorized.
>
> No matter the choice of textbook or other secondary resources, study of distributed systems absolutely mandates reading papers. A good list is here, and we would highly encourage attending your local Papers We Love chapter.
>
>
>
> [Distributed Systems 3rd edition](https://teachyourselfcs.com//distsys.png)
>
>
>
> ## Frequently asked questions
>
> #### What about AI/graphics/pet-topic-X?
>
> We’ve tried to limit our list to computer science topics that we feel every practicing software engineer should know, irrespective of specialty or industry. With this foundation, you’ll be in a much better position to pick up textbooks or papers and learn the core concepts without much guidance. Here are our suggested starting points for a couple of common “electives”:
>
> - For artificial intelligence: do Berkeley’s intro to AI course by watching the videos and completing the excellent Pacman projects. As a textbook, use Russell and Norvig’s Artificial Intelligence: A Modern Approach.
> - For machine learning: do Andrew Ng’s Coursera course. Be patient, and make sure you understand the fundamentals before racing off to shiny new topics like deep learning.
> - For computer graphics: work through Berkeley’s CS 184 material, and use Computer Graphics: Principles and Practice as a textbook.
>
> #### How strict is the suggested sequencing?
>
> Realistically, all of these subjects have a significant amount of overlap, and refer to one another cyclically. Take for instance the relationship between discrete math and algorithms: learning math first would help you analyze and understand your algorithms in greater depth, but learning algorithms first would provide greater motivation and context for discrete math. Ideally, you’d revisit both of these topics many times throughout your career.
>
> As such, our suggested sequencing is mostly there to help you just get started… if you have a compelling reason to prefer a different sequence, then go for it. The most significant “pre-requisites” in our opinion are: computer architecture before operating systems or databases, and networking and operating systems before distributed systems.
>
> #### Who is the target audience for this guide?
>
> We have in mind that you are a self-taught software engineer, bootcamp grad or precocious high school student, or a college student looking to supplement your formal education with some self-study. The question of when to embark upon this journey is an entirely personal one, but most people tend to benefit from having some professional experience before diving too deep into CS theory. For instance, we notice that students love learning about database systems if they have already worked with databases professionally, or about computer networking if they’ve worked on a web project or two.
>
> #### How does this compare to Open Source Society or freeCodeCamp curricula?
>
> The OSS guide has too many subjects, suggests inferior resources for many of them, and provides no rationale or guidance around why or what aspects of particular courses are valuable. We strove to limit our list of courses to those which you really should know as a software engineer, irrespective of your specialty, and to help you understand why each course is included.
>
> freeCodeCamp is focused mostly on programming, not computer science. For why you might want to learn computer science, see above.
>
> #### What about language X?
>
> Learning a particular programming language is on a totally different plane to learning about an area of computer science — learning a language is much easier and much less valuable. If you already know a couple of languages, we strongly suggest simply following our guide and fitting language acquisition in the gaps, or leaving it for afterwards. If you’ve learned programming well (such as through Structure and Interpretation of Computer Programs), and especially if you have learned compilers, it should take you little more than a weekend to learn the essentials of a new language.
>
> #### What about trendy technology X?
>
> (continues in next comment)
> Is this a realistic goal
Yes, quite. The bits you are going to be missing are some of the mathematical underpinnings. Depending on what you're programming, you'll also want to grab books on the particular topic at hand that don't try to teach you programming at the same time.
For example, if you want to learn why C# is object-oriented and what that means and how to use it, grab a copy of this book: http://en.wikipedia.org/wiki/Object-Oriented_Software_Construction
If you want to learn how relational databases work, read this one http://www.amazon.com/Introduction-Database-Systems-8th-Edition/dp/0321197844 (You can easily find online versions, but I didn't investigate whether they were legally released or not.)
You want to write a compiler? Grab the "dragon book": http://www.amazon.com/Compilers-Principles-Techniques-Tools-Edition/dp/0321486811
None of those teach you how to program. They teach you the math and background behind major inventions in programming. Keep up with those, find a local mentor who enjoys talking about this stuff, and you'll do fine.
I suggest you to read the Dragon Book.
No problem. Good luck finding a class, compilers are a really fun subject!
If you are just generally interested (I don't know your experience level) but the dragon book is still highly regarded. And might be a good entry way into the theory of it all.
European dragons have a heritage that stretches back to at least the time of the Greek civilisation; calling them "pale imitations" does them a grave disservice. The oldest known sources for dragon myths are from the Middle East, not the Far East.
If you feel like arguing this point, please don't use the Dresden Files. Just stick with authorative sources instead, ok?
https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
well, the common source out there that i can't avoid recommend is the Dragon's book
http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
I'll throw out some of my favorite books from my book shelf when it comes to Computer Science, User Experience, and Mathematics - all will be essential as you begin your journey into app development:
Universal Principles of Design
Dieter Rams: As Little Design as Possible
Rework by 37signals
Clean Code
The Art of Programming
The Mythical Man-Month
The Pragmatic Programmer
Design Patterns - "Gang of Four"
Programming Language Pragmatics
Compilers - "The Dragon Book"
The Language of Mathematics
A Mathematician's Lament
The Joy of x
Mathematics: Its Content, Methods, and Meaning
Introduction to Algorithms (MIT)
If time isn't a factor, and you're not needing to steamroll into this to make money, then I'd highly encourage you to start by using a lower-level programming language like C first - or, start from the database side of things and begin learning SQL and playing around with database development.
I feel like truly understanding data structures from the lowest level is one of the most important things you can do as a budding developer.
She's trying to hide her disappointment. I'm pretty sure this is the one she wanted .
Compilers: Principles, Techniques, and Tools
> Those are interpreted (JIT - just in time compiled)
You are contradicting yourself.
Plus there are also native compilers for Java and .NET languages.
Just a few examples:
Given that C and C++:
Does that make C and C++ interpreted?
Of course not, because as any compiler design student knows, language != implementation.
Bytecodes are just a form of architecture independent machine instructions, by no means do they require interpretation vs further compilation to native code.
Since the Summer is still not over, here is some reading:
Compilers: Principles, Techniques, and Tools (2nd Edition)
>We are talking about a high-level language compiler, remember?
I still consider C a high level language. Some people don't for various reasons..
>You were complaining that it compiles to C rather than emit instructions.
You simply read/took my post wrong. Nowhere am I complaining. Merely making an observation. It is not an unusual feat for a compiler to generate assembly instructions or machine code. Nor would I call it super difficult to write a compiler, but rather straightforward.
>If you are going to emit instructions, it's up to you to write your own optimizer.
Or buy/obtain a compiler that already is capable of doing this step.
I tried to come up with a simple explanation how a compiler works but I feel unable to provide a wording which is still somehow correct.
I guess there is a reason why this book has 1000 pages: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
The simplest explanation would be that somewone wrote a program which the computer understands, that is able to detect your language and converts it also to something your computer can understand.
No, I'm not getting anything confused!
I started in the 70-ties with asm, worked my way through C, then C++ and lately Java. At some point during that time I've implemented a Pascal compiler and I've read the dragon book cover to back and again.
I think I've got a pretty firm grasp of what call by reference is, and let me tell you: Java DOES NOT have call by reference, ONLY call by value.
If there's anyone who's confused it's you. Sorry.
Things get a LOT easier mentally when you call it a pointer in Java. This is just terminology, even the Java designers knew it was a pointer (hence the name NullPointerException).
In Java, objects are only accessible via pointers. To be more consistent with C++, every variable in Java should actually be written as:
MyObject obj = new MyObject();
But since there's no concept of a stack allocated object in Java, you would always have to put that there, and so they left it out.
And indeed, for pass-by-reference, a reference to whatever you have (a pointer in this case) has to be passed. So that's indeed a double indirection. In C++ you can even express this explicitly, since there's not only call-by-reference semantics, but also the address off operator &. Applying the & operator to a pointer (e.g. foo*) yields a double pointer (foo*). This is what happens behind the scenes when you use call-by-reference in C++ and various other languages.
In Java, everything but primitives is a pointer, and that pointer is passed, BY VALUE. In C++ terminology, there's only foo, foo** does not exist. Hence, you can follow that pointer from within a method and thus modify the object that is being pointed too, but you CAN NOT re-assign the pointer as I showed above.
Pass-by-reference semantics DEMAND that a pointer can be re-assigned.
Modifying that was is being pointed too does not count. You are CONFUSED with modifying a stack allocated object. If you pass that into a method and can modify it, then it's pass by reference, since the object itself is passed (no pointer involved), but in Java there is no stack allocated object, only a pointer to an object and that pointer is passed by value.
If you're still confused, please read the dragon book. Even if not for this argument, it will greatly enhance your understanding of how languages and computers work.