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
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 ...
6
votes
5answers
11k views

What is rightmost sentential forms?

I'm solving some past job interview problems. I met an embarrassing question about compilers. The question is : Consider the following grammar, with start symbol $E$: \begin{align*} E &\...
2
votes
1answer
195 views

Full circularity vs strong circularity for attribute grammars

Attributes of an attribute grammar can have a circular dependency. In my compiler construction course I learned, that there are two types of circularity for attribute grammars: full circularity can ...
2
votes
0answers
50 views

How to lexically list sentences in peano arithmetic?

I am working on building a toy automated theorem prover, What I want to do is to efficiently generate sentences in peano arithmetic, that I can attempt to verify as True/False/requires-more-resources ...
5
votes
0answers
130 views

SSA Phi to Registers

I'm working on an LLVM-like kit for .Net - because this is something that's lacking in .Net and I really want to learn the more advanced compilation theory. I'm really struggling to find anything ...
5
votes
2answers
316 views

is the problem of parallelising any program, NP-complete?

Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, ...
-1
votes
2answers
7k views

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

In a bottom-up evaluation of a syntax directed definition, inherited attributes can always be evaluated be evaluated only if the definition is L-attributed be evaluated only if the definition has ...
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
0answers
258 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 ...
1
vote
0answers
24 views

Is there any significant difference in how easily they can be implemented with a recursive descent parser?

What is the distinction between S-attributed definitions and L-attributed definitions? Which one is more expressive? Is there any significant difference in how easily they can be implemented with a ...
0
votes
0answers
20 views

Is XSL-Transformation a type of compiling? [duplicate]

I am currently working on a paper based on the topic of creating a source-to-source compiler from an existing application to C#. The existing application is actually just based on XML files, which ...
10
votes
4answers
2k views

Do we create a programming language by writing a compiler?

Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it? For example, is ...
0
votes
2answers
2k views

what is a compiler intrinsic function?

I'm trying to understand what a compiler intrinsic function is. I did find a wiki article but I'm still kind of fuzzy on what it is exactly. If someone could provide a few concrete examples that would ...
4
votes
2answers
105 views

Is there a fundamental CS problem in ORMs that leads to N+1?

Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it....
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 ...
5
votes
3answers
1k 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 language that it is written in into different language but I don't understand why we would want to do that. ...
7
votes
2answers
686 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
99 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 ...
-1
votes
1answer
70 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
249 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
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 ...
0
votes
1answer
616 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: ...
3
votes
2answers
209 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 ...
2
votes
0answers
65 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 ...
5
votes
1answer
118 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
24 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
267 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
1answer
50 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
214 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 ...
4
votes
3answers
879 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 ...
2
votes
0answers
22 views

Detect assigned variables in expression in linear time

Let's say I have the lambda calculus extended with set! for assignment. ...
0
votes
2answers
3k 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 ...
5
votes
4answers
15k 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
2answers
259 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
307 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
27 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
0answers
101 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
144 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 ...
0
votes
1answer
34 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
34 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 ...
8
votes
0answers
2k 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
1k 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 ...
4
votes
1answer
335 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
74 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
625 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 '(' ...
2
votes
1answer
81 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 ...
1
vote
2answers
2k 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
5
votes
2answers
698 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 ...
5
votes
1answer
306 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 languages,...
32
votes
5answers
8k 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 quarter,...

1
6 7
8
9 10
12