Questions tagged [compilers]

Questions about programs that read code in one language (source language) and translate it into an equivalent program in another language (target language).

Filter by
Sorted by
Tagged with
193
votes
10answers
53k views

How can a language whose compiler is written in C ever be faster than C?

Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler originally written in C, ...
92
votes
7answers
21k views

Why are some programming languages "faster" or "slower" than others?

I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I ...
75
votes
9answers
10k views

What properties of a programming language make compilation impossible?

Question: "Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine ...
68
votes
10answers
12k views

Can a dynamic language like Ruby/Python reach C/C++ like performance?

I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, ...
65
votes
12answers
12k views

Why don't compilers automatically insert deallocations?

In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically? Humans do it in a reasonable amount of time(ignoring bugs), so it is not ...
57
votes
4answers
7k views

Time complexity of a compiler

I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested ...
39
votes
8answers
10k views

What determines the "speed" of a programming language?

Suppose a program was written in two distinct languages, let them be language X and language Y, if their compilers generate the same byte code, why I should use language X instead of the language Y? ...
33
votes
5answers
11k views

How do computers remember where they store things?

When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?
32
votes
5answers
8k views

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter,...
31
votes
6answers
8k views

Why are ambiguous grammars bad?

I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
29
votes
2answers
5k views

What is a batch compiler?

I have the following quotation from my compiler's course (in the context of graph coloring): Because it is slow, graph coloring tends to be used in batch compilers, while linear scan tends to be ...
28
votes
6answers
9k views

Are there programs that can 'translate' source code between any two languages?

Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)? If there are, how do they work (techniques used, ...
22
votes
4answers
17k views

Why is left recursion bad?

In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?
22
votes
2answers
5k views

How is a JIT compiler different from an ordinary compiler?

There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or ...
20
votes
9answers
4k views

Would it be wrong to say that the processor (and hardware) is the implementation of an interpreter for machine language?

The question is basically in the title. I know that a computers hardware is of course some physical object, where as the interpreter is some abstract thing that does something abstract with the code ...
20
votes
3answers
1k views

Parsing arbitrary context-free grammars, mostly short snippets

I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, ...
20
votes
1answer
1k views

Do fully optimizing compilers for terminating programs exist?

In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and ...
19
votes
6answers
10k views

Why do compilers produce assembly code?

Assembly language is converted in to machine language by assembler. Why would a compiler convert high-level language to assembly? Can't it directly convert from the high-level language to machine code?...
19
votes
2answers
4k views

Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects ...
17
votes
3answers
24k views

Is there any real difference between a compiler and an assembler?

Is there any difference between the two? As per Ullman's book, compilers convert one language to another (usually low level) language, and so does an assembler. How are the two different?
17
votes
6answers
2k views

Does an abstract syntax tree have to be a tree?

Does the output of a parser have to be a tree or could it also be general graph? Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees ...
16
votes
5answers
3k views

Proof of the undecidability of compiler code optimization

While reading Compilers by Alfred Aho, I came across this statement: The problem of generating the optimal target code from a source program is undecidable in general. The Wikipedia entry on ...
16
votes
1answer
5k views

Why separate lexing and parsing?

It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test ...
15
votes
2answers
900 views

What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
15
votes
2answers
3k views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single non-...
15
votes
1answer
706 views

Type inference with product types

I’m working on a compiler for a concatenative language and would like to add type inference support. I understand Hindley–Milner, but I’ve been learning the type theory as I go, so I’m unsure of how ...
13
votes
3answers
1k views

How does 'deforestation' remove 'trees' from a program?

I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the ...
13
votes
3answers
3k views

Why is using a lexer/parser on binary data so wrong?

I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
13
votes
2answers
5k views

Is there any way to distinguish between LL(k) and LR(k) grammar?

I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar. We also know the facts that every LL grammar is LR that is LL ...
12
votes
3answers
32k views

How is this grammar LL(1)?

This is a question from the Dragon Book. This is the grammar: $S \to AaAb \mid BbBa $ $A \to \varepsilon$ $B \to \varepsilon$ The question asks how to show that it is LL(1) but not SLR(1). ...
11
votes
2answers
2k views

Theoretical minimum number of registers for a modern computer?

I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an ...
11
votes
4answers
8k views

Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
11
votes
3answers
820 views

Getting started with Program Analysis

I'm looking for resources on getting started with program analysis. The only book I've found on the topic is the Nielson & Nielson book. Other than that, it seems like there are only "compiler" ...
11
votes
1answer
727 views

The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the "CPS" approach has done great harm to ...
10
votes
1answer
1k views
10
votes
2answers
9k views

Compile a programming language with itself

I'm a computer science student. I want to create my own programming language (A basic language with few instructions). I know how to do a syntactic analyser, I already did it in Perl. In an article, ...
10
votes
4answers
2k views

Do we create a programming language by writing a compiler?

Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it? For example, is ...
10
votes
1answer
411 views

Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$. Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
9
votes
4answers
10k views

A faster, leaner JavaScript for scientific computing: what features should I keep?

Here I'm really interested in lowering barriers to mathematical education. Target: I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and high-...
9
votes
3answers
10k views

Cross Compiler's T diagram

I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone ...
9
votes
4answers
2k views

Why multiple return values is not a common thing?

I would like to ask a question about multiple return values, why this construct is not preferrable in programming languages (conceptual and/or technical difficulties). I've heard something about stack ...
9
votes
3answers
872 views

Equivalence of data-flow analysis, abstract interpretation and type inference?

@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of ...
9
votes
1answer
335 views

What is a non-contrived example of static type-checking being too conservative?

In Concepts in Programming Languages, John Mitchell writes that static type checking is necessarily conservative (overly strict) because of the Halting Problem. He gives as an example: ...
8
votes
2answers
2k views

Assembly writer vs compiler in VLIW architecture

I read this sentence in a book: In VLIW architecture, the compiler/and or assembly writer chooses instructions that can be executed in parallel. What is the difference between assembly writer and ...
8
votes
3answers
5k views

Deriving the regular expression for C-style /**/ comments

I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: ...
8
votes
1answer
539 views

Representation of the concatenation at the type level

I would like to learn more about concatenative programming through the creation of a small simple language, based on the stack and following the concatenative paradigm. Unfortunately, I haven't found ...
8
votes
1answer
6k views

Quality LISP/Scheme compilers to compete with C/C++

Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin? In my testing, I've found that the ...
8
votes
0answers
2k views

Compiler that compiles to a Turing machine?

I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for ...
7
votes
1answer
1k views

Is the Syntax of C Language completely defined by CFGs?

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions ...
7
votes
3answers
184 views

Is there a technique for statically checking that a function is only called at a particular rate?

I was reading this article about types, and started wondering how static type checkers could enforce other properties in programs. For example, say I wanted to create a language which would allow ...

1
2 3 4 5
12