Skip to main content

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).

137 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
429 views

Alternatives to phi nodes in static single assignment

I have read somewhere about an alternative SSA representation that doesn't use phi nodes but instead uses parameterized basic blocks. Something like this in an SSA with phi: ...
oconnor0's user avatar
  • 393
5 votes
0 answers
179 views

SSA Phi to Registers

I'm working on an LLVM-like kit for .Net - because this is something that's lacking in .Net and I really want to learn the more advanced compilation theory. I'm really struggling to find anything ...
Jonathan Dickinson's user avatar
5 votes
0 answers
206 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. ...
Ian Ringrose's user avatar
4 votes
0 answers
330 views

How to select a loop nesting trees for irreducible loops?

I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm ...
Li Haoyi's user avatar
4 votes
0 answers
61 views

Substituting "remaining variables" during partial evaluation?

In "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler" Yoshihiko Futamura wrote: "[Some] portions of a computation process [...] are not evaluated at partial evaluation ...
Higemaru's user avatar
  • 213
3 votes
0 answers
180 views

SSA Copy Folding

When can we fold copies in SSA? We are clearly allowed to fold a copy such as a0 = call foo() b0 = a0 But what about a program such as ...
user135438's user avatar
3 votes
0 answers
131 views

What is a good general-knowledge-level title description of Dr. Aho's and Dr. Ullman's body of work for which they were awarded the 2020 Turing Award?

I recently read in the New York Times that my old "Data Structures and Algorithms" class professor Dr. Ullman had received the Turing Award along with Dr. Aho. The article title was "...
Armand's user avatar
  • 131
3 votes
0 answers
752 views

How to decide between operational, denotational, and axiomatic semantics?

Context I'm designing a language which implements lambda calculus and (first-order) predicate calculus, where lambdas behave as the abstraction encapsulating logic, compositionally forming a ...
Phizo's user avatar
  • 51
3 votes
0 answers
101 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 ...
user1868607's user avatar
  • 2,194
3 votes
0 answers
58 views

Is there research into associative/commutative optimizations?

While playing around with optimization sets in LLVM, it occurs to me that the order in which optimizations are run matters greatly since, in general, A(B(src)) is ...
oconnor0's user avatar
  • 393
3 votes
0 answers
317 views

How to refactor a grammar to be suitable for recursive descent?

I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example: $S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow SA \\ B \rightarrow b \\ B \rightarrow ...
Jon McClung's user avatar
3 votes
0 answers
484 views

Recursive-descent parser for the grammar S -> S(S)S | ε

I'm studying (for self-betterment - I don't go to school) the 2nd edition of Compilers: Principles, Techniques and Tools by Aho et al. I'm not sure how to do Exercise 2.4.1 (b), which is to construct ...
Aky's user avatar
  • 225
2 votes
0 answers
61 views

Compiler that compiles to a Universal Turing Machine (UTM) tape program?

With Universal Turing Machines I mean the Turing Machines with fixed transition functions, proven by Yurii Rogozhin in his paper "Small universal Turing machines" to be capable of universal ...
2080's user avatar
  • 181
2 votes
0 answers
135 views

Optimal reassociations is NP-hard?

Consider signed integers with common addition and multiplication. Reassociation of expression is another equivalent form. Say expressions: ...
Konstantin Vladimirov's user avatar
2 votes
0 answers
33 views

History of the category of effectful computations

The 1971 paper A Catalog of Optimizing Transformations contains this passage: irreducible subprograms require special handling. (An irreducible subprogram is one which maintains a history, performs I/...
Theo H's user avatar
  • 321
2 votes
0 answers
2k views

What assigns the physical addresses to variables?

Earlier I was having a technical test when I stumbled across this question: I know that probably in modern systems, the OS and the MMU is responsible for that. But the test was focused on Embedded ...
Amr Mohamed's user avatar
2 votes
0 answers
33 views

Does a new stack get created for each async callback internally?

I am thinking about JavaScript here, or any language that supports async IO or that sort of thing (coroutines? though don't have much experience with those). I have looked at some of the resources ...
Lance's user avatar
  • 2,243
2 votes
0 answers
236 views

How to translate boolean expressions to three address code?

There are two uses of a boolean expression in a language like C, one as a condition in flow of control statements and the other as boolean value in assignment and arithmetic expressions. I was ...
Shashank Kumar's user avatar
2 votes
0 answers
62 views

Compiler optimization which does an SMT-like optimization in software?

Say I had two functions called one after the other: ...
user130558's user avatar
2 votes
0 answers
312 views

Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
Charlie Parker's user avatar
2 votes
0 answers
42 views

What is the logic behind seperating Shift moves/reduce moves and Goto moves in parsing table?

In the parsing tables of SLR(0), LALR(1) and LR(1) I have seen that shift moves and reduce moves have separate columns from Go-to Moves. What is the logic behind this?
Turing101's user avatar
  • 1,200
2 votes
0 answers
459 views

Does SLR(0), LALR(0) exists?

I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
RajS's user avatar
  • 1,677
2 votes
0 answers
26 views

Metrics for measuring and scoring automated “code analysis”?

I am writing various "program analysis" (aka static code analysis) algorithms. I am looking for ideas for metrics to measure how well my algorithms "understand the code". Some ideas i have so far : ...
YAZR's user avatar
  • 21
2 votes
0 answers
109 views

Why irreducibility is an important concept in Flow Graphs?

Here is a definition of reducible flow graphs : A flow graph is reducible if every retreating edge in any DFST for that flow graph is a back edge. And the reasons why we care about ...
Yushan ZHANG's user avatar
2 votes
0 answers
1k views

Calculation of Gen and Kill set for data flow analys

I'm currently preparing for an exam in compiler construction. The course is mainly about optimization in the backend of the compiler. For the optimization we have to do data flow analysis by hand. In ...
mdxg's user avatar
  • 21
2 votes
0 answers
177 views

Novel escape analysis algorithm for Java

Today I read a very interesting article about escape analysis in Java called Escape Analysis for Object Oriented Languages: Application to Java I think I have some grasp on how escape analysis works ...
Gaslight Deceive Subvert's user avatar
2 votes
0 answers
130 views

Trends in size of computer programs

Everyone knows code bloat is a real thing, of course. Everyone knows that programs are getting bigger too (this may be nothing to do with 'bloat' of course - they are more sophisticated, safer or ...
adrianmcmenamin's user avatar
2 votes
0 answers
557 views

SLR vs CLR parser

In SLR we use follow set of a non terminal for determining reduce moves and in CLR we use lookaheads for the same. How does using lookaheads actually help in improving the performance of the parser ? ...
Zephyr's user avatar
  • 993
2 votes
0 answers
899 views

What is the difference between a loop and a natural loop?

Is there a difference between a loop and a natural loop? Natural loops are defined as having a back edge to a head block that dominates it. If you have a natural loop nested inside of another ...
Victor Brunell's user avatar
2 votes
0 answers
56 views

How to lexically list sentences in peano arithmetic?

I am working on building a toy automated theorem prover, What I want to do is to efficiently generate sentences in peano arithmetic, that I can attempt to verify as True/False/requires-more-resources ...
Sidharth Ghoshal's user avatar
2 votes
0 answers
24 views

Detect assigned variables in expression in linear time

Let's say I have the lambda calculus extended with set! for assignment. ...
Leif Andersen's user avatar
2 votes
0 answers
32 views

Where does the term "Amechanicity" for type-error generation come from

I've been looking at these slides about improving type error messages for programming languages. One of the things they describe, starting at Slide 8, is the concept of amechanicity. Anytime the ...
Joey Eremondi's user avatar
2 votes
0 answers
113 views

Constraint solving for scheduling code with complex unspillable register classes?

I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none ...
Extrarius's user avatar
  • 771
2 votes
0 answers
1k views

Where does the Dynamic Link point to on the activation record

I'm a bit confused as to wear exactly the dynamic link points to on the activation record. I understand that it points to the 'top' of the instance of the callers activation record but I am unsure of ...
Nickknack's user avatar
  • 213
2 votes
0 answers
32 views

How does supercompilers relate to macro tree transducers?

Supercompilers can be used as a generalisation of deforestation of a functional program. Macro Tree Transducers composition can be used to the same effect, using a completely different approach. What ...
dokkat's user avatar
  • 121
2 votes
1 answer
157 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
Swordow's user avatar
  • 19
1 vote
0 answers
13 views

Why would a control flow block need access to the labels associated with a higher or lower level nested control flow block?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
Dean DeRosa's user avatar
1 vote
0 answers
11 views

Why must empty rules be inserted in syntax-directed translation of a control-flow grammar?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
Dean DeRosa's user avatar
1 vote
0 answers
25 views

CHK graph dominance algorithm proof

The algorithm developed by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy is widely used in industry for building dominator tree, but I cannot follow the proof in the “Engineering the data ...
rand0m_scr1pt_k1dd1e's user avatar
1 vote
0 answers
28 views

A formula of the major garbage collection threshold

I'm studying the garbage collection code of Alex Aiken's COOL programming language's runtime system. (This is the language used in a relatively famous Stanford Online Compilers course) A major garbage ...
Myk's user avatar
  • 173
1 vote
0 answers
86 views

Correct way to show example of ambiguous grammar

Facing confusion due to two different texts stating different ways to show examples of ambiguous grammar, though the example exists in the first book. The second book gives a different example, as ...
jiten's user avatar
  • 187
1 vote
0 answers
39 views

Why Path-convergence criterion Requirement 6 is necessary?

The path-convergence criterion states that there should be a φ-function for variable a at node z of the flow graph exactly when all of the following are true: There is a block x containing a ...
user157513's user avatar
1 vote
0 answers
65 views

Can compilers improve performance in real workloads by inserting prefetches in their output?

Prefetching is a task that the compiler feels like it should be suited for. Prefetching requires knowing in advance what data the program is about to load, and the compiler has a ton of information at ...
Narrateur du chaos's user avatar
1 vote
0 answers
24 views

Can we extend DDC to three rounds and get more information?

During diverse double-compiling, they say that it is proof that either all the compilers are subverted, or none of them, but they cannot say which one is subverted. In my studies of the technique I ...
Niklas Rosencrantz's user avatar
1 vote
0 answers
231 views

How does ANTLR4 handle optional rules?

Are the following two stat rules equivalant? stat : 'if' expr 'then' stat ('else' stat)? ; ...
hengxin's user avatar
  • 9,571
1 vote
1 answer
62 views

Getting something wrong while building parse table for the grammar

Task Build the Parse Table Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\...
bigstreet's user avatar
1 vote
1 answer
328 views

Calculate post dominator with non exiting control flow

Using the basic algorithm to calculate post dominators I run into trouble when working with a CFG containing an infinite loop (i.e., not terminating). The algorithm: ...
Sim's user avatar
  • 591
1 vote
0 answers
79 views

How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?

I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
Charlie Parker's user avatar
1 vote
1 answer
602 views

How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
hengxin's user avatar
  • 9,571
1 vote
0 answers
54 views

Condition of LL(3) grammer

To find out whether a grammar G is LL(1) or not, we test this condition among other conditions, "If whenever A -> alpha | beta are two distinct productions ...
Sihat Afnan's user avatar