# Questions tagged [compilers]

The tag has no usage guidance.

38 questions
Filter by
Sorted by
Tagged with
129 views

### Commutative operation benefits

With an associative operation I can rewrite a computation tree + / \ + 4 / \ + 3 / \ + 2 / \ 0 1 to be more efficient ...
• 71
103 views

### Origin of simulation relations for compiler correctness

Leroy uses simulation relations as a means of showing compiler correctness; the basic idea is that a simulation relation is an asymmetric binary relation between states in two different small step ...
1 vote
61 views

### Why can a Predictive Parser contain E' -> TE' | ε

I am studying the basics of predictive parsing and I think I have missed a concept that I would like to understand instead of just accepting and memorizing. I am watching this video and I am confused ...
1 vote
59 views

### Is there an unambiguous grammar that has no left recursion or left factors, but is not in $LL(1)$?

I know that, for a grammar $G$ to belong to $LL(1)$, it is necessary that $G$ is not ambiguous; that is, every sentence has a unique parse tree in $G$. $G$ has no left recursion; that is, we can't ...
194 views

### Does Standard ML validate (CBV) eta equivalence?

$\eta$ equality of functions is fundamental in their Category-theoretic semantics but in practice even "functional" languages include "impure" features that violate it. Note that this is not an issue ...
• 1,412
7k views

### Difference between syntax and semantic error in programming languages

When compilers generate errors for a specific programming language, there's distinction between syntax & semantic errors. E.g. ) + f 3 has ill-formed syntax, ...
• 171
1 vote
201 views

### Optimal evaluation of polynomials / rational functions

A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
• 225
467 views

### Can we say that Church encoding is a form of Gödelization?

We see here the following statement about Godelization: Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the ...
• 2,501
1k views

### Computing the DAG of a program given source code or AST

I've seen many papers on scheduling components or tasks once a DAG for the program is known, either by user-input or by domain restriction (i.e. all cross shaped 5-pt stencil codes have a known DAG). ...
1 vote
174 views

• 161
344 views

### Literature on alias analysis

I am writing my master's thesis in CS and I am working with alias analysis. The thing that I am interested in is intraprocedural, flow sensitive must- and may-alias analysis for Java-like languages. ...
• 211
262 views

### Preserving termination when rewriting recursive programs

Powerful program transformations like partial evaluation, deforestation and supercompilation are based on applying three kinds of transformations: Rewrite using axioms, e.g. a+b = b+a. Unfolding/...
• 390
1k views

### Certified compiler and optimizations in Coq/Agda

I am interested in verified compilers formalized in Martin-Löf type theory, i.e. Coq/Agda. At the moment I’ve written a small toy example. Therewith I can prove that my optimizations are correct. For ...
• 443
300 views

### Why do we need PAP (partial aplication) objects in heap?

In the paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon Marlow and Simon Peyton Jones it is told that a PAP heap object may be created in the push/enter model ...
• 557
476 views

### What are possible implementations of Haskell's type classes and what are their (dis)advantages?

As far as I know, a Haskell function with type classes constraints is internally compiled to a function with additional arguments that receive dictionaries with the necessary implementations of each ...
• 2,471
3k views

### machine learning for code and compiler optimization?

I am looking into ML for generating more efficient code (i.e. compile time and run time heuristics). I have a phd (compilers, hpc), but very little ML experience. I would appreciate any references ...
• 81
3k views

### Proof that DFA that accepts string has NFA that accepts reversal of string

I have seen descriptions for an algorithm that can take a regular deterministic finite automata and create a non-deterministic finite automata that is guaranteed to generate the reverse of string ...
• 7
1k views

### Compiler correctness proofs

I am looking for tutorial material that covers compiler correctness proofs, preferably using denotational methods, at the level of a beginning grad student. Alternatively, do you know of some ...
• 4,676
1 vote
204 views

### How is the iteration space of a nested for-loop containing two sequential nested loops represented?

In a general for loop of the form: for (i = 0, i <= n, i++) { for (j = i, j <= n, j++) ... for (k = i, k <= n, k++) ... } What ...
• 127
390 views

### Can any language be modeled as LR(k)

If L(G1) is the language that is produced by grammar G1 and G1 is not LR(k) parsable (specifically speaking for k = 1). Does there exist a grammar Gx that is L(Gx) = L(G1) where Gx is LR(1) parsable ? ...
• 121
1k views

### The Stalin compiler brutally optimizes, but how?

J.M. Siskind's research statement states: Stalin is an optimizing compiler for Scheme that performs whole-program static analysis and uses the results of that analysis to generate extremely efficient ...
• 390
1 vote
149 views

### Optimal inlining algorithm

I seek an algorithm to optimise the process of inlinling. Is there such an algorithm, or set of such algorithms? Is there an efficient functional algorithm? To be specific assume we have an Algol ...
• 111
285 views

### Where can I find an elementary small-step structural operational semantics for closures?

Lexical closures are an implementation technique in languages with first-class functions. I'm interested in a simple operational description of function closures. Does anyone know of such a ...
• 2,637
184 views

### Describing a grammar and associated parser

In the process of writing a Turing machine simulator, I decided on a machine representation in ASCII that closely mirrors Turing's original machine tables. I am interested in the formal categorization ...
869 views

### Equivalence of two basic blocks

My questions: What are other names for this and similar problems and their fields? ("equivalence of varieties in universal algebra", "equivalence of algebraic structures", "rewriting systems for ...
1k views

### Brackets expression incremental parsing algorithm

I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets. Consider the example with expression like "((1)())(2)". Parse tree for that ...
• 151
450 views

### Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?

Defunctionalization is a program transformation that converts higher-order programs into first-order programs. The idea is that given a program, there are only finitely many lambda-abstractions, so ...
• 31.6k