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
4
votes
1answer
348 views

What data-structure is best suited for escape analysis?

I'm making a compiler using LLVM and LLVM's shadow-stack. I thought I might easy the load of the GC by using escape analysis and allocate some variables on the stack. Can I use my typed AST for this ...
1
vote
3answers
166 views

How are variables accessed in the correct order from the stack?

I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order. So if I had a basic program calculating the sum of some user entered values ...
3
votes
1answer
118 views

Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that ...
4
votes
4answers
2k views

Why translating a program from one high-level programming language directly into another is difficult?

I am looking for a better explanation (research level, papers) to answer: Why translating a program from one high-level programming language directly into another is difficult? Note: When I say ...
0
votes
1answer
326 views

How does a Single Pass Compiler does parsing,analyzing and generating code all at once?

I would like to know how a single pass compiler does parsing,analyzing and generating code all at once as said in P.14 of SIngle Pass Compilers.Is it possible to do all these at once since you can't ...
0
votes
1answer
145 views

What is the name of this code transformation that uses associativity of addition?

I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code. For example, consider the following expression: ...
3
votes
1answer
2k views

Ambiguous Grammar and SLR parsing table : No conflicts?

We have been studying the development of SLR parsers, and that now we have done the arithmetic expression grammar (the unambiguous version), I was curious to see if the same could be done to the if-...
6
votes
1answer
843 views

Backward data-flow: post-order or RPO on reverse CFG?

When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which ...
1
vote
1answer
337 views

What is token-type in Lexical analysis?

I'm currently studying compiler construction book "Compilers Principles, Techniques, and Tools (2nd Edition)" , in page unit 3.1 , page 113 , example 3.2 . i cannot understand what is this kind of ...
4
votes
1answer
146 views

Subgraph of an interprocedural control flow graph

Say I have the interprocedural control flow graph (ICFG) of a program. Now I am only interested in the control flow between two functions f1 and f2. What is the most straight-forward way to remove ...
5
votes
0answers
186 views

How are weak references in a reference counted system implemented?

When reference counting is used for automatic memory management (e.g. Objective C or Swift), it is well know that “loops” give problems. E.g. ...
3
votes
1answer
5k views

Creating arrays of object of abstract class in statically-typed object-oriented languages

In statically-typed object-oriented languages (like Java, C++, C#, ...), suppose I declare an abstract class: public abstract class myclass1 { ................. } ...
3
votes
4answers
146 views

compilers and their inheritance

If compilers have an inheritance of compilers(for example, a compiler needs to be compiled by another compiler, and that compiler needs to be compiled by another compiler, and so on) then if there is ...
1
vote
0answers
24 views

How equality of item (production state) is defined in LR parser?

Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):...
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, ...
2
votes
1answer
76 views

How profiling is done in trace scheduling?

I'm trying to understand how trace scheduling works. The book that I'm reading, Engineering a Compiler by Keith D. Cooper & Linda Torczon, states that this method is using profiling. Profiling ...
6
votes
2answers
209 views

Eliminate non-local references from closure

For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure: ...
2
votes
2answers
323 views

What are transitive successor and transitive predecessor in the graph?

I'm reading a book on compilers, Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon and I came a across two new terms that I can't understand, they are: transitive successor and ...
0
votes
2answers
44 views

Unable to understand a definition of an instruction in a compiler schedule [closed]

Recently I've accepted a job offer to work on compiler design. To be properly prepared I've decided to review the material. The book that is being used for that is Cooper and Torczon's Engineering a ...
0
votes
2answers
1k views

Number of operations performed in increment operators [closed]

How many operations are performed in the following in order to get a running time function of an algorithm: x = x + 1 x += 1 <...
2
votes
1answer
620 views

Parse DAG into task tree

Suppose we have a DAG of tasks: Arrows represent flow (reversed dependencies: 8 must be run after 7). Some of the tasks (like 4, 5, 6) can be run in parallel (Par block). Dependent tasks (like 7, 8, ...
-2
votes
3answers
728 views

Is badly written code derogatory to the compiler?

I was having a heated debate with a friend of mine (who considers me an idiot, mind you) and we were arguing about whether a compiler has an index, or coefficient, that judges how poorly code is ...
6
votes
2answers
109 views

Program transformations for numeric stability

There's tons of research on program transformations for optimization. Is there any research on transformations that improve numeric stability? Examples of such transformations might include: ...
1
vote
1answer
2k views

Converting Regular expression to DFA by building syntax tree

There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition ...
3
votes
1answer
1k views

Help in understanding the implementation/application of scope trees

I’m learning (self-taught) about language implementation and compiler design, and I’m implementing a toy language to cement the concepts in my mind. However, I’m having trouble understanding how scope ...
3
votes
3answers
983 views

What techniques can I use to hand-write a parser for an ambiguous grammar?

I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a ...
1
vote
1answer
1k views

Computing FIRST and FOLLOW sets

Suppose we have the following grammar: S -> A ( S ) B | ε A -> S | S B | x | ε B -> S B | y where S is the start ...
1
vote
1answer
330 views

Why the given lexical specification will not process the following strings?

I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question. Here ...
3
votes
1answer
239 views

Top-down typing strategy - is there a name for this?

In most statically typed languages, each expression has an intrinsic type. E.g. in Java, 3 is an int, 3.0 is a double, ...
14
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-...
0
votes
2answers
269 views

Why doesn't my object code/machine code contain 1's and 0's

I know when I compile my C program to machine code it gets compiled into something that specific computer can understand But I thought computers can only understand 1's and 0's (high/low) so why ...
1
vote
1answer
3k views

What are GEN and KILL statements in dataflow analysis?

In data flow analysis, is GEN statement where a variable is used and KILL statement is where variable is redefined?
1
vote
1answer
110 views

Assigning one variable to another in 3 address code?

3 address code is a very common topic in many of the CS theories. I encountered it while studying Compiler Design. According to the Wikipedia article, it says - Each TAC instruction has at most ...
-1
votes
1answer
4k views

Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset construction ...
3
votes
2answers
836 views

Automatic translation between formal languages

There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar. Would it be possible to make a ...
3
votes
1answer
366 views

How to build a label flow graph for static analysis

I'm new to world of static analysis and am trying to build a new analysis of C programs for llvm compiler. I've started with the build of the graph of the constraints of the program: The edges ...
0
votes
0answers
355 views

How to generate intermediate code in more than 1 pass in compiler design?

I'm taking a compiler-design class where we have to implement our own compiler (using flex and bison). In dragon book by V.Aho et al. They have mentioned backpatching to backpatch forward references ...
4
votes
3answers
143 views

What does it mean to be “closed” under beta reduction?

I am reading the paper Compiling with Continuations, Continued, and in section 2.4, Comparison with ANF, the author draws attention to the fact that ANF is not closed under beta reduction. The snippet ...
0
votes
1answer
73 views

New Assembler in compiler [closed]

I'm currently developing my degree thesis, and the lab's idea is to design a new micro architecture, and then, be able to compile stuff for this architecture. So the question is, how do you instruct a ...
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? ...
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 ...
0
votes
1answer
76 views

LL(k) Prediction Techniques (and Insight on method applied)

I'm requesting references for LL(k) in situations where k > 1 for reasons described below. I'm looking for research/notes/...
2
votes
1answer
178 views

Monotone Frameworks: Transfer functions for flow edges instead of labels

So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$. The goal ...
9
votes
1answer
324 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: ...
2
votes
1answer
162 views

Three-address code versus JSON, XML, etc

I'm working on a compiler. The textbooks I have say to output a 3-address intermediate code. This can be translated into the target language of choice. I don't have a problem with the bulk of the ...
2
votes
1answer
2k views

Why we use context-free grammar for parsing?

Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?
0
votes
2answers
3k views

Computing FOLLOW sets for LL(1) grammar. Stuck on question

Calculate the FOLLOW sets for all the non terminals: $S \rightarrow bEx \mid Db \mid b \mid F$ $D \rightarrow EDc \mid Y$ $E \rightarrow dED \mid dDY$ $Y \rightarrow ab \mid aDx \...
2
votes
2answers
1k views

What do I need to study in order to understand and design a programming language? [closed]

What do I need to read in in order to : understand the specs of an already made programming language Design a programming language Design a compiler and assembler for that language make an ...
1
vote
2answers
137 views

Min-Max number of shifts and reductions in bottom-up parser [closed]

Given the Grammar has no unit or ɛ-productions, What is minimum & maximum number of shifts and reduce needed by bottom-up parser?
1
vote
2answers
97 views

How can this grammar parse such an input?

I've an example which I simply don't get at all. Implement an attributed grammar that checks that either the word ends in $b$ or each prefix of the word contains at least as many $b$s ...