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
10 views

What other implementation styles are there besides compilation, interpretation and transpilation?

Obviously there is JIT but it is basically run-time compilation. There is also implementing things in VHDL or ASIC. But my question is more towards software techniques for program building and ...
0
votes
0answers
26 views

Structural Equivalence - How exactly is the structural equivalence checked by the compilers?

I wanted to clear my doubts on the structural equivalence type check in the compilers. Consider the following two structs (or records): ...
1
vote
0answers
11 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
3
votes
1answer
79 views

How does a compiler give an immediate compilation error?

I am confused. I know that compilers translate your code one time as a whole into intermediary code, but how come when I type in something improper, the IDE shoots out a compilation error immediately? ...
0
votes
2answers
37 views

A state machine that is either DFA or NFA: is it possible?

I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic ...
2
votes
0answers
18 views

Can reading a value of a variable kill the definition of the variable?

I was going through the concept of reaching definitions from the red dragon book. The authors define reaching definitions as follows: Definition: We say a definition $d$ reaches a point $p$ if there ...
3
votes
0answers
46 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
21 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 ...
3
votes
2answers
665 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
39 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
28 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
118 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
35 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
29 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
23 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
26 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
65 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
41 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
815 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
360 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
31 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
17 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
37 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
48 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
66 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
79 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
98 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 ...
0
votes
1answer
46 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
721 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
30 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
70 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
48 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
75 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
2 3 4 5
12