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
0
votes
0answers
2 views

SSA Copy Folding

When can we fold copies in SSA? We are clearly allowed to fold a copy such as a0 = call foo() b0 = a0 But what about a program such as ...
0
votes
1answer
5 views

BNF syntax for a recursive function?

I'm to write a syntax that will allow for a recursive function, i.e. f(x) = if x == 0 then x else f(x+1) Here's one attempt at creating the grammar: But I don't ...
0
votes
0answers
3 views

Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar?

I'm looking at the following grammar rules for the Java language described on the Oracle docs: ...
0
votes
0answers
32 views

What is the future of Language Design?

What is the future design of Programming Languages? I have heard that compilers is going to become more integrated with editors and Browsers? Are we moving to a future with less code in Language ...
0
votes
0answers
38 views

Eliminating ambiguity in $A \to AA \mid (A) \mid a$

I'm trying to solve this complier design problem related to ambiguity in CFG the given grammar is \begin{align} &A → AA \\ &A → (A) \\ &A → a \end{align} I was able to find that this ...
0
votes
1answer
24 views

Using saved registers at the main function with no other function calls [RISC-V]

The convention when a function is going to use a saved register is to save the contents of that register to the stack in case the caller (if there's one? the main function doesn't have one) had been ...
1
vote
0answers
26 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
3
votes
0answers
111 views

What is a good general-knowledge-level title description of Dr. Aho's and Dr. Ullman's body of work for which they were awarded the 2020 Turing Award?

I recently read in the New York Times that my old "Data Structures and Algorithms" class professor Dr. Ullman had received the Turing Award along with Dr. Aho. The article title was "...
0
votes
1answer
34 views

How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$

Below is an excerpt from the Red Dragon book. $$(1) \quad S \rightarrow A_1 \quad A_2 \quad\{ A_1.in : = 1;\quad A_2.in : = 2 ;\}$$ $$(2) \quad A \rightarrow a \quad \{ print(A.in) \}$$ We find that ...
0
votes
1answer
15 views

L-attributed definitions include all syntax-directed definitions based on LL(1) grammars

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following claim: L-attributed definitions include all syntax-directed definitions ...
1
vote
1answer
20 views

In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?

I was going through the text Compilers: Principles,Techniques and Tools by Ullman et. al. where I came across the claim in the question by authors. Below is the definition and following it is the ...
0
votes
1answer
17 views

$\text{“The error entries in the goto table are never consulted”}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across a claim: $\text{"The error entries in the goto table are never consulted"}$ I feel ...
1
vote
0answers
25 views

Understanding the concept of “Viable Prefixes”

I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I ...
0
votes
0answers
43 views

In shift reduce parsing why the handle always eventually appear on top of the stack and never inside?

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the excerpt where the authors try to justify why stack is the best data structure of shift ...
1
vote
2answers
40 views

Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al. where I came across the following excerpt. Example 4.11. Consider the abstract language $L_1 = \text{ { $wcw$...
0
votes
0answers
39 views

Co-relating the direct algo for $\epsilon-NFA$ to $DFA$ with the chain : $\epsilon-NFA \rightarrow NFA \rightarrow DFA$

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following algorithm to convert an $\epsilon\text{-NFA}$ to $\text{DFA}$ ...
0
votes
0answers
14 views

How to help compiler do pipelining?

I don't mean compiler flags for pipelining. I would like to program in a way that helps the compiler do optimizations using pipelining. I mean I want to order instructions in C in such a way that GCC (...
5
votes
2answers
813 views

Break keyword outside a loop is syntax error or semantic error?

I am designing a simple compiler for my university project. In my programming language, the break keyword is allowed. I want to know whether break keyword occurs outside a loop should be a syntax ...
0
votes
0answers
16 views

Why can't I evaluate this L-Attributed SDD with a pre-order traversal?

My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
0
votes
0answers
14 views

Min number of register without spilling

The program below uses six temporary variables a, b, c, d, e, f. a = 1 b = 10 c = 20 d = a+b e = c+d f = c+e b = c+e e = b+f d = 5+e return d+f Assuming that all ...
3
votes
3answers
355 views

Compiler Design Question

$\text{Consider the following ANSI C code:}$ int main(){ Integer x; return 0; } $\text{What will be the type of error?}$ $\text{a) Lexical}$, $\text{b) Syntax}$, ...
-1
votes
1answer
30 views

Compilers: how to find first and follow sets?

I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!
1
vote
1answer
28 views

How to handle L-attributed SDDs with LR parsers

I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points: How to handle L-attributed SDDs in an LR grammar when using a tool ...
0
votes
0answers
14 views

LL(1) Eliminate Ambiguous ε-derivations

I have this grammar I want to convert to LL(1): S -> A B a | A B b A -> A c | B d B -> A a | b I eliminated the left-recursions, I factored out the ...
2
votes
0answers
18 views

Does a new stack get created for each async callback internally?

I am thinking about JavaScript here, or any language that supports async IO or that sort of thing (coroutines? though don't have much experience with those). I have looked at some of the resources ...
0
votes
1answer
16 views

Compilers: How to see “the number of grammars where there exists a string that has at least two different left-most derivations”?

Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
0
votes
1answer
36 views

Removing left recursion with terminals only

I have a grammar: $G → id > id$    $| id < id$    $| G and id$ Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?
1
vote
0answers
19 views

Compile XPath Abbreviated Query to Unabbreviated version

The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax. I am interested in references (if any) for any formal work done to compile/...
0
votes
1answer
42 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
0
votes
3answers
65 views

(Finite Automata) Why the following is a NFA?

The first one seems like a DFA. Could someone explain why this is a NFA?
10
votes
1answer
1k views
1
vote
1answer
78 views

Is my compilers assignment irrational?

In our assignment we are given a grammar (called minipython) and we are asked to implement some phases of compilation (parsing, some semantic analysis). One of the requirements is to be able to check ...
6
votes
2answers
94 views

Does strong typing contribute to better performance optimization by compiler?

Do guarantees provided by the type systems enable better performance optimizations by the modern compilers? I found a 20+ year article suggesting that it would. Also, intuitively speaking, knowing ...
1
vote
0answers
72 views

Help me to make sure, that I got defunctionalized continuations right

I am reading this Defunctionalization at work paper. So, in order to ascertain that I got it right, I request a little code review. I'll start with a recursive definition of a factorial function and ...
2
votes
2answers
101 views

How is code executed in the computer

I started to learn about compilers and interpreters. But I still can't understand how program execution happens under the hood. This is what I have understood so far. Compiler The Compiler does not ...
1
vote
1answer
64 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-...
0
votes
1answer
39 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 ...
1
vote
1answer
662 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
29 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
69 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
72 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
33 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
65 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
47 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
73 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
60 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
22 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
91 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
67 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
26 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 ...

1
2 3 4 5
12