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
3
votes
1answer
96 views

How does a compiler give an immediate compilation error?

I am confused. I know that compilers translate your code one time as a whole into intermediary code, but how come when I type in something improper, the IDE shoots out a compilation error immediately? ...
3
votes
3answers
441 views

Compiler Design Question

$\text{Consider the following ANSI C code:}$ int main(){ Integer x; return 0; } $\text{What will be the type of error?}$ $\text{a) Lexical}$, $\text{b) Syntax}$, ...
3
votes
1answer
2k views

Backward vs Forward Data-flow Analysis

I understand how both forward and backward data-flow analysis work but in what situations would we use them? Why do we need to be able to do it in both ways? Do compilers of certain types perform one ...
3
votes
1answer
302 views

When do type systems start needing a logic engine?

I've noticed that some languages include a logic engine as part of their type system (e.g. Shen, Typed Clojure). Other languages have a much more direct type checking algorithm (e.g. Haskell / ...
3
votes
1answer
186 views

Assertion of Type Inference Rules/Type Checking

I have a problem in a book I am trying to accomplish. I understand the overall type of the expression is boolean and how it derives. (y * x) will be rule 4 (counting from top right). (y * x) + x when ...
3
votes
1answer
6k 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
2answers
636 views

Lexing and parsing a language with juxtaposition as an operator

Normal human math notation treats juxtaposition as implied multiplication, e.g., $2x$ means $2$ multiplied by $x$. This does not seem to be a common feature of computer languages, although it was, for ...
3
votes
2answers
125 views

How does a compiler infer a value's type?

From A Swift Tour — The Swift Programming Language (Swift 5): var myVariable = 42 myVariable = 50 let myConstant = 42 A constant or variable must have the same ...
3
votes
2answers
128 views

Is it possible to tell if two sequences of assembly instructions are semantically equivalent?

In a modern instruction set like x86-64 there are many many many ways to accomplish the same task using a series of old simple instructions all the way up to the complex SIMD instructions. If one ...
3
votes
1answer
126 views

Why doesn't the C/C++ compilers create different tokens for different types of numbers?

Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc. However if we ...
3
votes
1answer
239 views

interference graph: assigning variable to itself

I'm studying the theory behind compiler design, and was assigned with building an Interference graph for a certain code 3-address code. We were taught to first divide the code into blocks (according ...
3
votes
1answer
288 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} \...
3
votes
1answer
2k views

JIT, AOT, Interpretation: What are differences between them?

I'm a beginner in Compilation. My understanding is that Interpretation means Interpreter takes source program as input and produce the result of this program.(source -> Interpreter -> run on the ...
3
votes
1answer
257 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, ...
3
votes
1answer
113 views

Representing abstract syntax tree as a graph

Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code? The goal and application ...
3
votes
1answer
130 views

Loop-local variable in Cytron's SSA algorithm

I am trying to write a compiler that converts a simple imperative language to SSA form, but I am having trouble with loops. As an example, I have some code that looks like: ...
3
votes
1answer
443 views

Connection between non determinism and LL(1) conflicts

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it. As per my understanding non deterministic context free grammar is a context free grammar ...
3
votes
1answer
538 views

Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...
3
votes
1answer
1k views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
3
votes
1answer
387 views

In describing the tokens of a programming language using RE, it is not necessary to have the $\epsilon$ or t. Why is this?

In describing the tokens of a programming language using regular expressions, it is not necessary to have the $\epsilon$, (for the empty set) or t (for the empty string). Why is this? Please tell me ...
3
votes
1answer
2k views

Why using finite automata in implementing lexical analyzers

I studied the subject of building a lexical analyzer using finite automata, through the classical way: Regular Expression -> NDA -> DFA. And I found it elegant, and a more solid approach for building ...
3
votes
1answer
855 views

Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$

In the grammar for S production two bodies have same starting symbol $ S \to Aa \mid b A c \mid Bc \mid bBa $ So i removed the left factoring from those two productions $ S \to bC$ $ C \to Ac ...
3
votes
1answer
131 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 ...
3
votes
1answer
2k views

Algorithm to find Dominance Frontiers

The algorithm that is used by gcc and llvm is that of Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (page 9). We start with the immediate dominators of each control-flow graph node ...
3
votes
1answer
53 views

Say that a stack frame only contains total functions: could the maximum stack size be statically determined?

Say that you have a program with only total functions, or if that is impossible, consider a subset of the program with only total functions. Is it theoretically possible to statically determine the ...
3
votes
2answers
2k views

Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

I am having difficulty with one of the exercises in the Dragon Book: Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars: $$S \rightarrow 0S1\ |\ 01$$...
3
votes
1answer
157 views

Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
3
votes
1answer
558 views

Where does LL parser belong in the top-down parsers classification

There are four types of top-down parsers according to this answer: recursive descent backtracking recursive descent predictive table-driven with backtracking table-driven predictive. Also the author ...
3
votes
1answer
2k views

How to generate an LL(2) parse table?

The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that: ...
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-...
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
1answer
83 views

SLR parse table and unambiguity

If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous? I think that since we have constructed the parse table ...
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 ...
3
votes
1answer
280 views

If a grammar is SLR(1) then are the LALR and SLR tables the same?

I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all ...
3
votes
2answers
1k views

Is Terra the only system programming language able to compile code at runtime? [closed]

I stumbled across Terra last year, and the most similar language I can think of is Julia. Terra is inspired by and uses Lua for templating/metaprogramming instead of being derived from e.g. the Lisp ...
3
votes
1answer
370 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 ...
3
votes
2answers
2k views

How to explain rehosting and retargeting with T-diagrams?

I'm currently learning for an exam about compilers and found the following question: (3 p.) Bootstrapping: Explain the concepts of rehosting and retargeting. Use T-diagrams. As far as I understand,...
3
votes
0answers
53 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 ...
3
votes
0answers
123 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 "...
3
votes
1answer
50 views

Annotated type system problem about conditional branch

I am reading the book "Principle of Program Analysis" by Flemming Nielson for annotated type systems. In the first chapter, section 1.6 they mentioned the simple type system for various ...
3
votes
0answers
250 views

Uses of irreducible control flow

What are some applications where irreducible control flow is required*? I'm particularly interested in programming language features that will be tricky to efficiently compile if the compile target ...
3
votes
0answers
586 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 ...
3
votes
0answers
80 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
0answers
55 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 ...
3
votes
0answers
265 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
0answers
342 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 ...
3
votes
2answers
319 views

How to modify semantic actions when removing left-recursion from a grammer

Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions: $ S \...
2
votes
4answers
96 views

How do compilers assure stability?

Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
2
votes
1answer
48 views

How does software prefetching work with in order processors?

From prof. Onut Mutlu's slides on prefetching, this example has been shown as software prefetching: ...
2
votes
2answers
591 views

Does assembly language get translated to binary code? If so, is assembly language portable across machines?

I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear. Here is my understanding: High level code written in a ...

1 2 3
4
5
12