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
1answer
35 views

Second chance binpacking register allocator

I'm atempting to implement the following linear scan register allocator called "second chance binpacking": Omri Traub, Glenn H. Holloway, and Michael D. Smith. Quality andspeed in linear-...
-2
votes
0answers
70 views

Why Left Recursive Elimination is badly needed in Compiler Design? Explain it

Why Left Recursive Elimination is badly needed in Compiler Design? Explain it. I haven't understand this question please describe me someone. please explain me with figure.
-4
votes
0answers
50 views

LL(1) parsing problem

Grammar: X  X < Y | c Z b | X > Y | c Z a Y  q |  | p Z  = | <= | >= | X A: Show that the given grammar is not suitable for LL(1) parsing: B: Now modify the grammar, so that ...
-1
votes
0answers
12 views

What does the number in the brackets represent in parsing techniques, such as LL(1), LR(0), etc.?

I am studying language compilers and grammars, and I can't seem to tell what the numbers represent in the brackets of the different parsing techniques. And as a side question (no need to answer): what ...
0
votes
0answers
12 views

Calculating worklist with live variable analysis

I am struggling with the calculation of the worklist algorithm, I do not want to implement the iterative algorithm as so many redundant steps it takes. The algorithm I am following to calculate the ...
-2
votes
0answers
17 views

can you help me to eliminating of left recursion and left factoring

According to grammar G(S):        S→(L)|a S|a       L→L,S|S Q1. Modify the grammar by eliminating of left recursion and left factoring
1
vote
1answer
536 views

What does it mean for a grammar to be LR(0)?

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0). For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
0
votes
0answers
24 views

Futamura Projection source code?

Where can I find working code in 2020 that implements the Futamura projections? I can find lots of stuff explaining the theory but no actual implementations.
2
votes
1answer
53 views

What are the most used statements in programming (ranked)?

I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
1
vote
2answers
66 views

What's the accurate definition of a compiler?

Wikipedia: In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language). This ...
0
votes
1answer
32 views

Are colored graphs and red-black trees related?

I've come across the concepts of colored graphs (register allocation) and red-black trees. They both seem to have this notion of "coloring", but I've never seen them being connected ...
1
vote
1answer
38 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
3
votes
1answer
46 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 ...
2
votes
1answer
55 views

How does the undecidability of Extensional Martin-Löf Type Theory apply to real type-checking compilers?

It is claimed in many sources (for example, here) that adding a rule like "if Id(X,Y) then X really equals ...
2
votes
1answer
50 views

Is there a name for a compiler that runs once at runtime right before a program is executed?

I wrote a tiny compiler that is used to execute user-defined plugin code. The compiler is shipped as part of the application. When the user loads a plugin, the compiler runs first (once) and then the ...
1
vote
0answers
20 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
2
votes
1answer
61 views

How to pass comma separated values from yacc to cpp file node [closed]

I am writing a compiler in CPP using Flex and Bison and having trouble understanding passing values up the syntax tree in bison. I have grammar like this below, 'exp' would evaluate to any number. <...
0
votes
0answers
31 views

How to go from an unstructured disassembler to a control flow graph based decompiler?

I have a project which includes a disassembler which makes old virtual machine formats playable online. It's a very simple disassembler; it basically processes the instructions outputting a code ...
0
votes
0answers
24 views

Loop Dependencies

Say I have loop like this, for(1 to 10) { A[i][j]=A[i][j]; } What kind of dependency is this? RAW or WAR? According to me it is none, since there is no problem ...
0
votes
1answer
26 views

left/right derivations of grammars and parse trees

I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct. $S-> NP$ $V$ $NP$ $NP -&...
1
vote
1answer
41 views

Multiple correct answers for compilation

When you are asked to hand compile into assembly language, are there multiple correct answers? For example, in https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-...
0
votes
0answers
31 views

Converting a regular expression to a grammar and regular grammar

I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have ...
1
vote
1answer
54 views

For every imperative function, is there a functional counterpart with identical performance or even instructions?

Currently, I haven't learned about a functional language that can achieve the same performance as C/C++. And I have learned that some languages that favor functional programming to imperative ...
1
vote
1answer
27 views

What are cases where we cannot perform LR parsing without augmented grammar?

Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing. The reason frequently is It is required in cases where start symbol comes on right hand of any ...
0
votes
1answer
36 views

What is a dominator node and a dominator tree?

I tried reading the wikipedia about Dominator (graph theory), which gives the following definition of a dominator node: a node d dominates a node n if every path from the entry node to n must go ...
0
votes
1answer
33 views

Is there any compiler IR paradigms other than Three Address Code and Static Single Assignment (SSA) Form?

Specifically, I have tried boiling down the operations of a VM into the smallest possible standardized units and arrived at this: ...
0
votes
0answers
26 views

ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
0
votes
1answer
116 views

What is the difference between a simulator, emulator, and cross compiler?

As far as I understand, cross compilers, emulators, and simulators are all ways that one computer system to be able to behave like or run another computer system. What is the difference between these ...
0
votes
0answers
23 views

Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
2
votes
2answers
59 views

optimizing for loops

Disclaimer: I'm not a compiler expert. I'm simply curious and come seeking enlightenment. I've seen people claim that -- for efficiency -- for loops should ...
0
votes
0answers
24 views

Referential Transparency and Interchangeability

Being had spent hours trying to grasp referential transparency, I am finally inclined to regard this concept as confusing one rather than helpful. But maybe the problem is me... Usually referential ...
0
votes
0answers
54 views

Why can't a compiler just “think more” about optimization?

This happens to me from time to time: I compile my code with the highest optimization level (-Ofast) of the allegedly fastest compiler (GCC) of one of the fastest ...
16
votes
5answers
3k views

Proof of the undecidability of compiler code optimization

While reading Compilers by Alfred Aho, I came across this statement: The problem of generating the optimal target code from a source program is undecidable in general. The Wikipedia entry on ...
1
vote
0answers
40 views

Is there a way to simplify redundant conditionals?

For example if I've this: if a == false then return true else if a == true and b == false return true else if a == true and b == true then return false can be ...
1
vote
1answer
50 views

Is a compiler a kind of Gödel numbering program?

Question: Is a compiler a kind of Gödel numbering program? Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one ...
2
votes
4answers
78 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
45 views

Code optimization - syntax tree vs. intermediate representation

I'm working on a compiler for my own custom language. As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been ...
2
votes
1answer
52 views

How to view Graph Reduction/Graph Representation for a Haskell program?

I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to ...
1
vote
1answer
32 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
2
votes
0answers
32 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 ...
2
votes
1answer
74 views

How does Warrens Abstract Machine work?

I've recently learned about Prolog and Logic programming which I find pretty cool, but the compiler is currently like magic to me and I want to know how they work. After a little bit of research I ...
0
votes
1answer
20 views

Predicitve Parser LL(1) condition

Lets say we use the predictive parser LL(1). Why is it necessary that $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$, for all $\alpha, \beta$ right side of alternative productions i.e., productions ...
0
votes
0answers
9 views

Control flow graph for 3 Address Code inquiry

I'm supposed to do a three address code for the following semantic action S-> repeat S1 until E times_in_a_row B holds Which is meant to be: Repeat Statement 'S1' as long as the condition B had not ...
1
vote
1answer
24 views

How many syntax trees can be made by a BNF

An example of this would be: 1+2*3+4 Expression = Expression Arithmetic Expression | number Arithmetic = + | - | * | / Through just breaking down 1+2*3+4, it was easy to find that the answer was 5 ...
1
vote
3answers
36 views

Why is casting float to double applicable?

This is indeed a Computer Science Question. As far as I am concerned casting down (up) does not require any mathematical operation. It is just shrinking down (leveraging) the significant bits. e.g <...
0
votes
0answers
19 views

Computing Follow sets of Grammar for LL(1) parser

I am trying to compute the Follow set of the following Grammar: E -> E' E A A -> + | * E -> num E' -> num I start by adding the end of string symbol, ...
3
votes
4answers
5k views

Do you ever “download” a language?

When one "downloads" a language (say, downloading the python file, or doing apt-get ruby or something), is it always the ...
0
votes
2answers
91 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
-2
votes
1answer
35 views

Computing FIRST and FOLLOW

Given the following grammar with terminals $VT=\{[,],a,b,c,+,-\}:$ $S \rightarrow [SX]|a$ $X \rightarrow +SY|Yb|\epsilon$ $Y \rightarrow -SXc|\epsilon$ This should be the FIRST function: $first(S) =...
0
votes
0answers
9 views

Understanding Register Allocation using Graph Coloring in this Specific Paper

I'm currently reading the paper "Register Allocation Via Coloring" By Gregory J. Chaitin and others (1980). I'm having trouble understanding the way an "interference graph" is constructed as explained ...

1
2 3 4 5
11