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).
654
questions
0
votes
0
answers
54
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 ...
0
votes
0
answers
28
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 ...
- 161
1
vote
0
answers
25
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 ...
- 173
2
votes
0
answers
122
views
Optimal reassociations is NP-hard?
Consider signed integers with common addition and multiplication.
Reassociation of expression is another equivalent form.
Say expressions:
...
0
votes
2
answers
78
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 ;
...
- 11
2
votes
2
answers
123
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 ...
- 123
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 ...
0
votes
1
answer
48
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 ...
- 103
1
vote
0
answers
51
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 ...
- 187
0
votes
1
answer
59
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:
...
- 187
-1
votes
1
answer
44
views
Can parser split tokens?
Is it valid to have the token split up, in a parser; as shown in the below grammar:
...
- 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:
...
- 101
0
votes
1
answer
82
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 ...
- 187
0
votes
1
answer
59
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.
...
- 187
1
vote
1
answer
60
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 ...
- 111
0
votes
1
answer
102
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 ...
- 121
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 ...
- 549
1
vote
1
answer
30
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 ...
- 125
0
votes
1
answer
103
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 ...
- 171
0
votes
0
answers
30
views
How to handle parentheis in Operator Precedence Parser?
I wrote this c++ code for a operator precedence parser.
it works perfectly for expressions without parentheis.
Eg: i*i+i is accepted
...
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 ...
- 9,501
0
votes
1
answer
58
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 ...
- 1
0
votes
0
answers
45
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:
...
- 1
0
votes
1
answer
63
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?
- 1
0
votes
1
answer
123
views
Compiler optimization pass joining identical function definitions together (or specializing them)
Consider this program transformation, in any direction, written in ANF:
...
- 711
0
votes
1
answer
41
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....
- 105
1
vote
2
answers
37
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 ...
- 111
0
votes
2
answers
35
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 ...
1
vote
1
answer
36
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:
...
2
votes
1
answer
55
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.
...
- 140
1
vote
1
answer
34
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:
...
- 11
0
votes
0
answers
55
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 ...
1
vote
0
answers
35
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 ...
- 11
0
votes
1
answer
52
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 $\...
0
votes
0
answers
55
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 ...
6
votes
4
answers
3k
views
How does the linker know where to look for a function implementation in C++?
I am currently learning about how the compilation and linking works in C++. I think I kinda get how the compiler works, and that for a file to fully compile you don't need to have function ...
- 163
-1
votes
1
answer
70
views
find the minimization of the dfa
so this is the question , I have to minimize this DFA
this is How I did it
but when I checked for answers , this is what it was,
can someone please explain to me what mistake I made? I have been ...
0
votes
0
answers
36
views
Programming language implementation challenge: is recursion harder than HOFs, or vice versa?
(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)
All other things being equal, which of the following languages would be more challenging to ...
- 179
1
vote
0
answers
41
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 ...
0
votes
0
answers
21
views
Example of L-attributed definition with cycle present in dependency graph
Text from Compilers (Aho, Lam, Sethi, Ullman):
The second class of SDD's is called L-attribute definition The idea behind this class is that, between the attributes associated with a production body, ...
- 108
0
votes
0
answers
25
views
Avoiding Excess Roll Back in engineering a compiler 2nd edition, page 63
I am reading Engineering a Compiler 2nd edition by Keith and can not understand the pseudocode on page 63.
...
- 1
-3
votes
1
answer
69
views
A chatbot's take on dynamic scoping: it is easier to debug - correct?
I asked the chatbot at you.com, "what is an advantage of dynamic scoping?" and it said the following on the pane titled YouChat. (If you click the link, you will probably see a different ...
- 179
0
votes
1
answer
36
views
Is S->E+S|E, E->number|(S) same as S->number|(S+S)?
I'm reading https://ilyasergey.net/CS4212/_static/lectures/PLDI-Week-07-more-parsing.pdf
On page 11, there's the definition of Sum Grammar:
...
- 103
0
votes
0
answers
68
views
In Compilers, are def-use chain and use-def chain inverses of each other?
I'm mostly confused about these definitions. I was reading several texts and it seems that you can derive use-def chains using the data flow analysis, Reaching Analysis. This uses a forward flow ...
- 101
1
vote
1
answer
257
views
How to remove ambiguity from the grammar?
I want to remove ambiguity from the grammar below:
S → ABC
A → abA | ab
B → b | BC
C → c | cC
I have removed left recursion and left factoring and obtained the grammar as follows:
S → ABC
A → abA'
A' →...
0
votes
0
answers
19
views
Reference request: Domain specific language, runtime, virtual machine design and implementation
I'm a working software engineer who is interested in programming language design and I want to try to implement a simple DSL as an exercise and a side project. I want to apply for grad school in this ...
- 101
0
votes
1
answer
729
views
How to handle epsilon production in CLR(1) parsing?
Given the following grammar:
S -> A
A -> AB
A -> ϵ
B -> aB
B -> b
Check whether it is CLR(1) or not.
I have drawn the canonical itemsets as well as the parse table. But I'm not sure ...
- 101
0
votes
1
answer
315
views
Should I lookahead in the lexer or parser?
So I have this Recursive Descent Parser which outputs a Syntax Tree for arithmetic expressions.
While doing some reading, I learned that LL(1) grammars have a lookahead of 1 - I remembered using a ...
- 115
0
votes
0
answers
30
views
Von Neumann Architeture
Recently I came across with a question about Von Newman architecture (which is usually used) and whether the following statement is true or not?
In Von Neumann architecture data are stored in disk and ...
- 1
1
vote
0
answers
22
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 ...
- 1,006