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

Filter by
Sorted by
Tagged with
1 vote
1 answer
52 views

Can and does any statically typed programming language safely support in-place type-conversion?

Here's some hypothetical rust-inspired language syntax to show what I mean ...
Hjulle's user avatar
  • 113
0 votes
1 answer
23 views

Discard all ambiguity from given CFG

Here is given CFG : CODE→VDECL CODE | FDECL CODE | ϵ VDECL→vtype id semi | vtype ASSIGN semicolon ASSIGN→id assign RHS RHS→EXPR | lit | char | bool EXPR→EXPR addsub EXPR | EXPR multdiv EXPR EXPR→...
bFur4list's user avatar
  • 103
1 vote
1 answer
55 views

Can code using GOTO be converted GOTO-less algorithmically?

My impression is yes, and probably it is achievable even in polynomial time, but I am not sure. The important thing I can see is that the "structured" control structures can be embedded into ...
peterh's user avatar
  • 428
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
0 votes
2 answers
53 views

(novice to compiler design) how does a recursive descent parser decide which nonterminal to parse if there are multiple

Let's say we have a grammar S -> A | F A -> id = exp F -> id ( arglist ) ...
peterparker's user avatar
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
0 votes
0 answers
15 views

Collapsing loops in a control-flow graph

Let's say we are given some CFG, maybe in SSA-form, and we want to "collapse" each top-level loop into s single node, whose successors would be all exit blocks of the original loop. So we ...
return true's user avatar
0 votes
1 answer
67 views

Table driven parser vs Recursive Descent parser

I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (...
Ali Ahmed's user avatar
1 vote
1 answer
27 views

Is a language *engine* the same as a language *implementation*?

(This may just be a terminology clarification question.) Wikipedia says A language usually has at least one implementation in the form of a compiler or interpreter, allowing programs written in the ...
Niels Bom's user avatar
  • 111
1 vote
1 answer
36 views

Creating an executable after code generation - compiler design

I am learning about and building a very basic compiler. My question is about code generation. I have read on a lot of materials about code generation when building a compiler and I get the concept. ...
Ali Ahmed's user avatar
2 votes
1 answer
40 views

What does the language of DFA of LR itemsets represent?

As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production. With this $.$ we keep track ...
Ajit Kumar's user avatar
1 vote
2 answers
97 views

Could a compiler/static analysis infer the best abstract data type?

I initially brought this up on the Swift Forums, and it was suggested that this might be a thing better suited for CS SE. So here goes: I had this thought that the compiler already has enough ...
Manav's user avatar
  • 111
0 votes
0 answers
13 views

Dependency testing and parallel compilers

I currently study well known dependency testing for automatic loop parallization from parallel compilers (ZIV, SIV, MIV, Single Variable Constraint, Multiple Variable Constraint, Acyclic Test, Fourier ...
Athanasios Margaris'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
0 votes
1 answer
74 views

Is bytecode ("virtual machine code") inherently faster to compile and/or interpret, than higher level (above Assembly) languages?

First, this is not an opinion question. I'm interested in if there is some kind of objective answer. If there isn't, then the answer would be "no". Is bytecode ("virtual machine code&...
BipedalJoe's user avatar
0 votes
0 answers
62 views

What is the earliest compiler in chain that was used to create what we nowadays have as a modern C compiler?

My apologies if the title is confusing. First I begin with the statement that may be wrong but what I always thought what happened. "Dennis Ritchie created C compiler which was used to create ...
Clear Sky's user avatar
0 votes
0 answers
44 views

State of the art in register allocation for straight-line programs

TL;DR: I'm looking for the fastest known algorithm to perform optimal register allocation (optimal in the sense of minimizing the number of spills and reloads) for straight-line programs. Context I am ...
swineone's user avatar
  • 161
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
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
0 votes
2 answers
92 views

Can you verify the end of a function declaration through syntax analysis?

In some languages, it is expected that a function declaration be terminated by syntax that includes the function name. For example, in MODULA-2, a function is declared as shown below: PROCEDURE P ; ...
Emma3201's user avatar
2 votes
3 answers
166 views

What are quines (layman friendly)?

I was going through the Wikipedia page on Quines and did not understand this paragraph - A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
DashwoodIce9's user avatar
0 votes
0 answers
19 views

Minimum number of swaps to achieve prefix constraint

(An isogram is a word in which no letters repeat.) I'd like to know if there's a standard name for this problem, and/or any standard algorithms. If not, I'm interested in whether anyone has any ideas ...
SocraticMathTutor's user avatar
0 votes
1 answer
58 views

Could there be a computer or components based on a non-classical logic?

Since circuits and processors are heavily influenced and designed based upon boolean logic, which is itself a subset of propositional logic, could there be different interpretations of hardware or ...
Jonas's user avatar
  • 103
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
0 votes
1 answer
99 views

Correct way to derive parse trees, for a given input, to show ambiguity

Is it correct to state that the below grammar can handle the expression: a - b * c, by the below two different parse trees. Grammar: ...
jiten's user avatar
  • 187
-1 votes
1 answer
50 views

Can parser split tokens?

Is it valid to have the token split up, in a parser; as shown in the below grammar: ...
jiten's user avatar
  • 187
0 votes
1 answer
51 views

Is it possible to automatically detect which variable is not used in future and free those memory?

What I need is similar to garbage collection but a bit different, consider the following code: ...
Peter Wu's user avatar
  • 101
0 votes
1 answer
160 views

Change of associativity for a given right-recursive grammar

In section 3.7.1, of the book titled: Compiler design in C, by Allen I. Holub (made available freely online, by the author here, & the page #19 of errata, here), have on page #176, the mention of ...
jiten's user avatar
  • 187
0 votes
1 answer
61 views

Doubts in backtracking function animation, for call sequence flow

In the slides' based animation given for backtracking, here (with code here, in the web-page ); have few doubts, in the code restated below, and the execution as shown in the call #5. ...
jiten's user avatar
  • 187
3 votes
1 answer
117 views

Dataflow Analysis: Available Expressions, why is OUT[B] initialized to universal set?

In the dragon book, section 9.2.6, why is the $OUT[B]$ initialized to $U$ except for $OUT[ENTRY]$. Wouldn't using the $OUT[B] = \emptyset \quad \forall B$ be a more conservative solution? The book ...
David Yue's user avatar
  • 133
1 vote
1 answer
128 views

Requirements to a CPU architecture to actually allow a C compiler to be built for it

I have this rather weird CPU architecture for which currently only an assembler exists. I won't go into too much details about this architecture as it is not publicly available. However, some quirks ...
GNA's user avatar
  • 141
2 votes
6 answers
1k views

Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?

Edit: Since this post is gaining traction, I feel the need to clarify that the purpose of this is to see if asymptotic and constant factor estimations calculated from high level code implementations ...
wjmccann's user avatar
  • 569
1 vote
1 answer
37 views

Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?

Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch? I am trying to write a program to analyze Java programs and figure out the transitive closure of the ...
Li Haoyi's user avatar
0 votes
1 answer
127 views

What does it take to support a programming language on an OS?

From my understanding, something like Linux is very geared towards C programs, with things like libc. What I'm wondering is, even in Java, you have arguments to ...
user129393192's user avatar
5 votes
6 answers
2k views

Why is backpatching needed during intermediate code generation? For what purposes?

I understand how backpatching works during intermediate code generation, but I do not understand why it is needed. A common argument for using backpatching during intermediate code generation is as ...
hengxin's user avatar
  • 9,571
0 votes
1 answer
73 views

Is it possible for a language to have mixed evaluation strategies?

As far as I am aware, most functional programming languages today use a call-by-value eager evaluation strategy with some exceptions like Haskell. I am curious if it is possible for a language to have ...
wildcat's user avatar
0 votes
1 answer
131 views

How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
whoAsked's user avatar
0 votes
1 answer
75 views

Can all LL(k) grammar can be recognized by LR(1)?

For context free languages, I wonder that if all LL(k) languages can be recognized by a LR(1) grammar?
xie cui's user avatar
0 votes
1 answer
128 views

Compiler optimization pass joining identical function definitions together (or specializing them)

Consider this program transformation, in any direction, written in ANF: ...
paulotorrens's user avatar
0 votes
1 answer
50 views

Loop Invariant Code Motion not tagging an expression correctly

I was reading the LICM section of the book Advanced Compiler Design and Implementation and found me questioning why the expression d = -c wasn't tagged as invariant....
Akari Oozora's user avatar
1 vote
2 answers
38 views

Compile procedural code to pure stack operations

I asked this question specifically about why the JVM has a separate area for local variables: https://stackoverflow.com/q/76086392/1463507 It was answered satisfactorily within the scope of the ...
kqr's user avatar
  • 111
0 votes
2 answers
41 views

Executable linking/loading workflow

I'm having a bad time understanding how multiple concepts work simultaneously for achieving linking/loading correctly an executable. From the very beginning loading/linking is basically the art of ...
ca-hercor's user avatar
1 vote
1 answer
37 views

How do you convert a string representing a finite set of strings into a regulair expression without using lots of vertical bars?

Consider the following string: ...
Toothpick Anemone's user avatar
2 votes
1 answer
82 views

Is order important in Structural Equivalence?

From 6.3.2 of Aho et al. When type expressions are represented by graphs, two types are structurally equivalent if and only if one of the following conditions is true: They are the same basic type. ...
muser's user avatar
  • 150
1 vote
1 answer
56 views

Confusion regarding FLEX(regular expressions)

I am building an analyzer that takes in text and numbers the lines; taking in hello how are you i'm fine thanks as input and using the code: ...
AlexG's user avatar
  • 11
0 votes
0 answers
74 views

How do programs communicate with the kernel?

I am trying to understand how operating systems work because I would like to write my own version of Unix. Anyway, I have some doubts about some mechanisms that allow the applications to communicate ...
Angelo Giannuzzi's user avatar
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
0 votes
1 answer
65 views

How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?

I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules: Consider a robot arm that accepts two commands: $\triangledown$ puts an apple in the bag and $\...
Dean DeRosa's user avatar
0 votes
0 answers
86 views

Is there any way to tell which states are final states in a finite state automata given only its grammar?

Problem In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
Brett Smith's user avatar

1
2 3 4 5
14