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
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 ...
189
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, ...
38
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? ...
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, ...
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: ...
90
votes
7answers
20k 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 ...
74
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 ...
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,...
12
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 ...
3
votes
2answers
980 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 ...
4
votes
1answer
335 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 ...
3
votes
2answers
209 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 ...
9
votes
3answers
9k 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 ...
3
votes
1answer
265 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} \...
1
vote
2answers
554 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 ...
0
votes
1answer
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 ...
17
votes
3answers
23k 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?
12
votes
3answers
29k 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). ...
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 ...
5
votes
1answer
12k 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 ...
22
votes
4answers
16k 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?
6
votes
2answers
9k 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 ...
3
votes
1answer
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 ...
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
182 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 ...
5
votes
3answers
270 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?
4
votes
2answers
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 ...
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 ...
5
votes
4answers
5k 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 ...
4
votes
3answers
1k 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 ...
4
votes
1answer
975 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 ...
4
votes
1answer
6k 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" ...
2
votes
1answer
913 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? ...
0
votes
1answer
5k 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?.
0
votes
1answer
9k 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 : ...
3
votes
1answer
974 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 ...
3
votes
0answers
76 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 ...
3
votes
1answer
65 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 ...
2
votes
1answer
98 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. <...
2
votes
1answer
66 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 ...
2
votes
1answer
325 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 ...
1
vote
1answer
172 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 ...
1
vote
0answers
418 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 ? ...
1
vote
0answers
82 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. ...
0
votes
1answer
119 views

How does make/scons manage dependency graph and figure out which file need to be recompiled?

what I understand is that, the file dependency is organized as a graph. Make/scons check the timestamp of each file, when a source file's timestamp is newer than the output, it re-compile everything ...
0
votes
1answer
587 views

Is following grammar LR(0)?

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question. Grammar: $SL \rightarrow SL ; S \space | \space \epsilon$ $S \...