Questions about programs that read code in one language (source language) and translate it into an equivalent program in another language (target language).

learn more… | top users | synonyms

2
votes
1answer
33 views

Why would we want a self-hosting compiler?

I understand that a self-hosting compiler is a compiler which can compile the code of the same language that it is written in into different language but I don't understand why we would want to do ...
3
votes
0answers
6 views

Are there any implementations of the spineless tagless G-machine other than in GHC?

From Simon Peyton Jones (recent Royal Society member) we read the paper: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine. Now this paper is part of how they ...
1
vote
0answers
7 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
-2
votes
0answers
31 views

How is YACC compiler different from other compilers? [on hold]

How is YACC compiler different from other compilers? Were YACC compilers default parse generators for earlier OS?
-1
votes
1answer
41 views

How to find FOLLOW for variables which has next value ε

Its very easy to find FIRST in compiler design. Im finding difficult to find follow , suppose if we have one variable(say B) then we need to search the variable in the whole question .If there was a ...
2
votes
1answer
33 views

Can a cross-compiler be self-hosting?

My understanding is that a self-hosting compiler will take as input the language it is written in and a cross-compiler will output a language which runs on a platform which is different to what it ...
3
votes
1answer
70 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 ...
-1
votes
1answer
26 views

Need help removing ambiguity from grammar

$E \rightarrow UV \bracevert EBE \bracevert V \bracevert [E]$ $V \rightarrow a \bracevert b$ $U \rightarrow < \bracevert > $ $B \rightarrow ? \bracevert ! \bracevert @ $ Order of precedence: ...
2
votes
2answers
81 views

What defines a tool as a “compiler”

I've been trying to figure out what technically makes a tool or program a compiler. For example, I know that gcc will compile source code to object files or assembly, hence transforming a ...
0
votes
0answers
28 views

Regular expression for C-style /**/ comments [duplicate]

I am aware that a similar question was already asked here and that the recent question A DFA for recognizing comments is also related but I am not satisfied with the answers. The point is that ...
0
votes
0answers
13 views

why the end marker is part of a follow set of a start symbol?

I can't figure out why the end marker is part of the follow set of the start symbol, in other words if $\$$ is the input-end marker and $S$ is the start symbol then $ \$ \in Follow(S)$. My question is ...
4
votes
1answer
24 views

Incremental compilation over AST

Is incremental compilation ever done based on the AST? That is, the compiler would just regenerate code for the parts of the AST that have changed. I know that many compilers do incremental ...
1
vote
0answers
16 views

Lazy way of comparing ISA on code length

I hope this is not too broad. I need to evaluate about 8 different ISA targets for about 12 specs. The only metric I'm intersted in is size of the output bytecode. Moreover, I'm only interested in ...
0
votes
0answers
19 views

What is the difference between Moore's algorithm and partition refinement algorithm for DFA minimization?

Both the algorithms use the partition method to minimize the DFA. I cannot understand the difference between them. Can someone give an example where we can see the difference between them.
0
votes
0answers
18 views

What are the parts of an object module and how do they work with a linker?

I'm trying to figure out how a linker works (after the compiler and assembler have finished processing a module). In my class notes we are given an example of a target machine that is word addressable ...
0
votes
1answer
18 views

Does preparing min DFA by combining equivalent states always result in min DFA

I know the following fact: If $Ma_N=\{w:n_a (w)=Nk,k≥0\}$, then Number of states in $$Ma_{N1}×Ma_{N2} =Ma_{N1}∪Ma_{N2} =Ma_{N1}∩Ma_{N2} =Ma_{N1}-Ma_{N2} =LCM(N1,N2)$$ where $n_a (w)$ is the ...
1
vote
1answer
26 views

Calculating attributes' values in the semantic analysis stage

I'm reading through the book : "Compiler Construction: Principles and Practice". In chapter 6 : semantic analysis, an example about attribute grammars is given. The example is of a simple integer ...
3
votes
3answers
88 views

Examples of specialized instructions of assembly language not available in compilers?

In my CS computer organization textbook, there's this blurb on the advantage of assembly over a high-level language. Another major advantage of assembly language is the ability to exploit ...
3
votes
0answers
18 views

Detect assigned variables in expression in linear time

Let's say I have the lambda calculus extended with set! for assignment. ...
0
votes
0answers
28 views

Eliminating left recursion and left factoring this grammar

I have a grammar S-> SS* | SS+ | a Really confused on how to remove the left recursion and do left factoring My attempt on removing left recursion : S -> aS' S' -> S+S' | S*S' | epsilon If this is ...
1
vote
1answer
52 views

What are differences between Static Scope and Dynamic Scope?

My teacher has provided the following pseudo-code, and says that the output using static scope is 1 2 3, but the output using dynamic scope is ...
1
vote
1answer
49 views

Program interpretation for static analysis

Are there any implementations, or even academic work, regarding an application capable of looking at code and inferring what the code actually intends to do? For example, we give it a program that ...
1
vote
2answers
40 views

Attribute grammars: How are attributes implemented?

I've read about attribute grammars, but I haven't found out, how are the attributes often implemented? To me they scream objects (of classes), but they could be also variables. But are there any ...
2
votes
0answers
18 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 ...
2
votes
1answer
47 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ ...
2
votes
0answers
38 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 ...
-1
votes
1answer
32 views

Does checking for correctness belong predominantly to “semantic analysis”?

Does checking for correctness belong predominantly to "semantic analysis"? Or is it reasonable to be done in earlier phases (in a compiler like construction) as well? Mainly in syntax analysis. Or is ...
0
votes
1answer
29 views

Is it “valid” for semantic functions to query outside of the grammar in attribute grammars?

Is it valid (in the sense of formal grammars or formal language theory) to refer to outside of the grammar in attribute grammars? What I mean is that since attribute grammars can contain semantic ...
0
votes
0answers
24 views

What semantical is there in attribute grammars?

I've been reading about attribute grammars since I'm trying to extend CFGs to semantics. What I'm finding difficult to grasp is the use of the word "semantics" in the context of attribute grammars. ...
4
votes
0answers
57 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 ...
1
vote
0answers
38 views

Where does the Dynamic Link point to on the activation record

I'm a bit confused as to wear exactly the dynamic link points to on the activation record. I understand that it points to the 'top' of the instance of the callers activation record but I am unsure of ...
3
votes
1answer
92 views

Can you take classical code and compile it to quantum code?

Is there anyway for example, to take a trivial program from C such as: int main() { int i = 1 + 1; return 0; } And compile this down to some form of Quantum ...
0
votes
0answers
13 views

How to get 2-LOOKAHEAD results in this grammar?

G: S -> bRS | RcSa | @(epsilon) R -> acR | b .... 2-LOOKAHEAD(S->@) = {$,a,aa} 2-LOOKAHEAD(R->b) = {b,ba,bb,bc} I don't understand a result of these ...
0
votes
1answer
56 views

Construct SLR Parse table problems

Consider the augmented grammar G is: S` -> S S -> a S -> (T) T -> T,S T -> S I have tried to construct parse table. But, when I read '(' ...
1
vote
1answer
33 views

Confusion about data types, compilers, hardware data representation and static vs dynamic typing

I am trying to understand static vs dynamic typing, but am really struggling to see how everything fits together. It all starts with data types. As far as I understand, data types are quite abstract ...
0
votes
2answers
54 views

Macro expansion is done in which phase of a compiler?

This is question raised by my teacher in the class room. I don't have enough knowledge about phases of compiler and macro expansion. Could someone help me in finding out proper solution to this
4
votes
2answers
79 views

Interpretation in scripting languages

Why is pure interpretation more common for scripting languages compared to programming languages? I mean, why are programs written in a scripting language not converted to machine language and then ...
2
votes
0answers
67 views

Proof Carrying LLVM?

I am intrigued by and understand the very basics of Proof Carrying Code (PCC) and I recognize that LLVM is a machine-independent intermediate language. LLVM is the intermediate form of many ...
26
votes
5answers
6k views

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the ...
2
votes
0answers
24 views

What data-structure is best suited for escape analysis?

I'm making a compiler using LLVM and LLVM's shadow-stack. I thought I might easy the load of the GC by using escape analysis and allocate some variables on the stack. Can I use my typed AST for this ...
1
vote
3answers
64 views

How are variables accessed in the correct order from the stack?

I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order. So if I had a basic program calculating the sum of some user entered values ...
2
votes
1answer
34 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
4answers
106 views

Why translating a program from one high-level programming language directly into another is difficult?

I am looking for a better explanation (research level, papers) to answer: Why translating a program from one high-level programming language directly into another is difficult? Note: When I say ...
0
votes
1answer
64 views

How does a Single Pass Compiler does parsing,analyzing and generating code all at once?

I would like to know how a single pass compiler does parsing,analyzing and generating code all at once as said in P.14 of SIngle Pass Compilers.Is it possible to do all these at once since you can't ...
0
votes
1answer
85 views

What is the name of this code transformation that uses associativity of addition?

I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code. For example, consider the following expression: ...
2
votes
1answer
167 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 ...
2
votes
0answers
77 views

Backward data-flow: post-order or RPO on reverse CFG?

When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which ...
1
vote
1answer
40 views

What is token-type in Lexical analysis?

I'm currently studying compiler construction book "Compilers Principles, Techniques, and Tools (2nd Edition)" , in page unit 3.1 , page 113 , example 3.2 . i cannot understand what is this kind of ...
3
votes
1answer
37 views

Subgraph of an interprocedural control flow graph

Say I have the interprocedural control flow graph (ICFG) of a program. Now I am only interested in the control flow between two functions f1 and f2. What is the most straight-forward way to remove ...
4
votes
0answers
50 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. ...