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
20 votes
1 answer
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 ...
user avatar
  • 519
193 votes
10 answers
54k 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, ...
user avatar
40 votes
8 answers
11k 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? ...
user avatar
69 votes
10 answers
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, ...
user avatar
  • 815
75 votes
9 answers
11k 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 ...
user avatar
8 votes
3 answers
6k 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: ...
user avatar
92 votes
7 answers
22k 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 ...
user avatar
  • 1,352
32 votes
5 answers
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,...
user avatar
  • 421
13 votes
2 answers
6k 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 ...
user avatar
3 votes
2 answers
1k views

Do "compiler" and "assembler" correspond to frontend and backend phases of a compiler?

In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a ...
user avatar
  • 1
4 votes
1 answer
344 views

Can you take classical code and compile it to quantum code?

Is there anyway for example, to take a trivial program from C such as: int main() { int i = 1 + 1; return 0; } And compile this down to some form of Quantum ...
user avatar
3 votes
2 answers
218 views

What defines a tool as a "compiler"

I've been trying to figure out what technically makes a tool or program a compiler. For example, I know that gcc will compile source code to object files or assembly, hence transforming a ...
user avatar
9 votes
3 answers
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 ...
user avatar
2 votes
2 answers
736 views

Existence of one and two state PDAs

I came across following fact in Automata book by Hopcroft, Ullman: Theorem 1: For every PDA accepting by empty stack (PDAeS), there is an equivalent one state PDA accepting by empty stack. I was ...
user avatar
  • 1,557
3 votes
1 answer
310 views

Syntax directed translation , definition and actions

I have trouble understanding Syntax directed translation/definition/actions. I am reading dragon book but it confuses me even more. Having production for simple arithmetic $$ \mathit{expr} \...
user avatar
  • 179
0 votes
1 answer
2k views

Symbol table usage

In which phases of the compiler, is symbol table used and updated ? According to me, In lexical analysis, new entry for each variable is created in symbol table so symbol table is only updated In ...
user avatar
  • 319
65 votes
12 answers
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 ...
user avatar
17 votes
3 answers
25k 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?
user avatar
  • 1,719
13 votes
3 answers
34k 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). ...
user avatar
20 votes
9 answers
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 ...
user avatar
17 votes
6 answers
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 ...
user avatar
5 votes
1 answer
13k views

What are handles in parsing?

I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given. For example, one document said - "the essence of LR parsing is ...
user avatar
  • 125
22 votes
4 answers
18k 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?
user avatar
6 votes
2 answers
10k views

Cost in time of constructing and running an NFA vs DFA for a given regex

Repost from Stack Overflow: I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated. The ...
user avatar
  • 79
3 votes
1 answer
4k views

unambiguous grammar but it's not LR(1)

I have following grammar: $$A \to a A a \mid \varepsilon$$ This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a ...
user avatar
  • 235
7 votes
1 answer
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 ...
user avatar
7 votes
3 answers
195 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 ...
user avatar
  • 205
5 votes
2 answers
598 views

Is it possible to go from code to circuit?

I am wondering if it is possible to have a program that interprets programming code and is capable of turning that code into an optimized circuit. Is this possible, and if so, does it exist?
user avatar
4 votes
2 answers
1k views

How are Signed integers different from unsigned integers once compiled

How are Signed integers different from unsigned integers once compiled? I already know about twos compliment and the like but my question is how can you tell the difference when looking at 8 bit ...
user avatar
4 votes
1 answer
8k views

What is a "sentential form"?

I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" ...
user avatar
  • 201
1 vote
3 answers
1k views

How is a program stored before compiling?

When we write code, after compilation the code will be converted to machine language and then stored in the hard disk. But before compiling the code, it is still in the high-level language. How and ...
user avatar
  • 119
0 votes
1 answer
75 views

What other implementation styles are there besides compilation, interpretation and transpilation?

Obviously there is JIT but it is basically run-time compilation. There is also implementing things in VHDL or ASIC. But my question is more towards software techniques for program building and ...
user avatar
9 votes
1 answer
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 ...
user avatar
8 votes
4 answers
3k 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 ...
user avatar
5 votes
4 answers
6k views

A DFA for recognizing comments

The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with ...
user avatar
  • 2,143
4 votes
1 answer
2k views

How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed. If a grammar is left-recursive, then the set of ...
user avatar
  • 143
3 votes
1 answer
1k views

What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK? is it being used anywhere? ...
user avatar
  • 740
3 votes
3 answers
2k views

Confusion about compiler and assembler

I have two questions. After compilation of any C program result is assembly language code which should depend on processor. So my question is: how do different computers with different processor ...
user avatar
1 vote
1 answer
269 views

Unambiguousness and determinism of CFGs for them to be LR

I came across this statement: Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. I was ...
user avatar
  • 1,557
0 votes
1 answer
6k views

How does lexical analyzer remove white spaces from source file?

In compiler at phase lexical analyzer, how does lexical analyze strip out white spaces from source file?.
user avatar
0 votes
1 answer
10k views

LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
user avatar
3 votes
1 answer
984 views

How to call something that can be either a terminal or a nonterminal?

I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C. I came across a terminology problem however that I remember in the past I couldn't ...
user avatar
  • 153
3 votes
1 answer
67 views

Low-level shift operator implementation

I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int ...
user avatar
  • 2,230
3 votes
0 answers
87 views

Low-level division operator implementation

A few weeks ago, I asked this question on the implementation of the shift operator for an architecture that implements boxing. Reviewing my implementation I found out that the division operator wasn't ...
user avatar
  • 2,230
2 votes
1 answer
153 views

How to pass comma separated values from yacc to cpp file node [closed]

I am writing a compiler in CPP using Flex and Bison and having trouble understanding passing values up the syntax tree in bison. I have grammar like this below, 'exp' would evaluate to any number. <...
user avatar
  • 151
2 votes
1 answer
83 views

finding separating words (Nerode)

i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
user avatar
  • 21
2 votes
1 answer
223 views

Full circularity vs strong circularity for attribute grammars

Attributes of an attribute grammar can have a circular dependency. In my compiler construction course I learned, that there are two types of circularity for attribute grammars: full circularity can ...
user avatar
2 votes
1 answer
424 views

Why is it better to do the data flow analysis in the basic blocks

I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal. Sadly, quoting the exact source, would be slightly hard as it is not in ...
user avatar
  • 157
1 vote
0 answers
86 views

Translation from Intermediate Language into 'three-address' machine instructions

I am unsure where to start with this. From what I understand so far, 'VAR(x)' corresponds to Rule 2, ':= VAR(x) ' refers to Rule 5 and '+ NUM (1) refers to link 3. ...
user avatar
1 vote
0 answers
454 views

Conflicts in LR(0) parser

Why don't we consider conflicts caused due to augmented production? This picture shows the states of a LR(0) parser. In the above picture, why we don't consider shift reduce conflict at state I2 ? ...
user avatar
  • 319