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

120 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10 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 ...
5 votes
0 answers
295 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: ...
  • 373
5 votes
0 answers
150 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 ...
5 votes
0 answers
202 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. ...
4 votes
0 answers
289 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 ...
  • 113
4 votes
0 answers
59 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 ...
  • 213
3 votes
0 answers
66 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 ...
  • 238
3 votes
0 answers
128 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 "...
  • 131
3 votes
0 answers
640 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 ...
  • 51
3 votes
0 answers
89 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 ...
  • 2,230
3 votes
0 answers
57 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 ...
  • 373
3 votes
0 answers
273 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 ...
3 votes
0 answers
362 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 ...
  • 225
2 votes
0 answers
20 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/...
  • 41
2 votes
0 answers
812 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 ...
2 votes
2 answers
90 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
2 votes
0 answers
26 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 ...
  • 1,911
2 votes
0 answers
53 views

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

Say I had two functions called one after the other: ...
2 votes
0 answers
238 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 ...
2 votes
0 answers
37 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?
  • 1,172
2 votes
0 answers
278 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 ...
  • 1,557
2 votes
0 answers
25 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 : ...
  • 21
2 votes
0 answers
73 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 ...
2 votes
0 answers
618 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 ...
  • 21
2 votes
0 answers
167 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 ...
2 votes
0 answers
128 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 ...
2 votes
0 answers
499 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 ? ...
  • 953
2 votes
0 answers
807 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 ...
2 votes
0 answers
51 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 ...
2 votes
0 answers
23 views

Detect assigned variables in expression in linear time

Let's say I have the lambda calculus extended with set! for assignment. ...
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 ...
  • 29.2k
2 votes
0 answers
111 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 ...
  • 751
2 votes
0 answers
31 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 ...
  • 121
2 votes
1 answer
80 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 ...
  • 19
1 vote
0 answers
27 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'|\;\;\...
1 vote
0 answers
43 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 ...
1 vote
0 answers
31 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 ...
1 vote
0 answers
17 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
1 vote
0 answers
68 views

Understanding the concept of "Viable Prefixes"

I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I ...
1 vote
0 answers
21 views

Compile XPath Abbreviated Query to Unabbreviated version

The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax. I am interested in references (if any) for any formal work done to compile/...
1 vote
0 answers
35 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
  • 9,259
1 vote
0 answers
47 views

Is there a way to simplify redundant conditionals?

For example if I've this: if a == false then return true else if a == true and b == false return true else if a == true and b == true then return false can be ...
1 vote
2 answers
82 views

Can Yacc be used to generate three address code for Java 1?

I have read that yacc generates bottom up parser for LALR(1) grammars. I have a grammar for Java 1 that can be used for generating three address code and is strictly LALR(1), but the translation ...
1 vote
0 answers
133 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 ...
1 vote
0 answers
26 views

Is Constant Folding a type of Memoization?

I was reading about Constant Folding and it sounds very similar to Memoization so I suspect that it indeed is a type of memoization but I've done some searching and can't find a solid answer (in ...
  • 111
1 vote
0 answers
212 views

Does a simple calculator have compilers?

When I input something wrong in my Casio fx-82MS calculator it shows Syntax error on its screen. So does even a simple calculation on a most simple calculator like this goes through compilation ...
  • 1,172
1 vote
0 answers
39 views

Using DPDA instead of LR parsers

If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...
1 vote
0 answers
67 views

Compiler implement power method with syntax graph

We learn how to write compiler. I know that we can use grammar to construct a parser for compiler or otherwise use a syntax graph to represent grammar and generate code when move on it's node. our ...
  • 11
1 vote
0 answers
45 views

Design considerations of datatypes in early programming languages like C

Although type theory originated (e.g. already discussed by Russell in 1910s) much earlier than programming languages, I have this feeling that languages such as C considered type-checking from a very ...
  • 259
1 vote
0 answers
27 views

Are there any algorithms for extracting functions from expressions?

Suppose you have an expression like this: sqrt(x) * 6 + sqrt(x + 1) * 6 + sqrt(x + 2) * 6 Are there any well-known or published algorithms that can find the ...