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
1answer
17 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): ...
2
votes
1answer
213 views

How to translate automatons (Turing machines) into programs of high level programming language?

Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the ...
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
1answer
9k views

LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
2
votes
1answer
105 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 ...
0
votes
1answer
206 views

LR(1) parsing, problem with look ahead symbols

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution. I'm trying to fill the LR(1) parsing table for the grammar ...
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 ...
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 ...
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
2answers
666 views
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 ...
1
vote
2answers
130 views

Dynamic list for frame pointers and static list of nested activation frames

I am going through the book Compiler Construction by Niklaus Wirth. The following is what I feel to be stated summarily by his lesson on procedure calls: The compilation of a procedure call is the ...
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 "...
1
vote
1answer
72 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 ...
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 ...
0
votes
1answer
47 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
1answer
75 views
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 ...
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
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 ...
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
1answer
433 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
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
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?
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}$, ...
5
votes
3answers
267 views

Is it possible to go from code to circuit?

I am wondering if it is possible to have a program that interprets programming code and is capable of turning that code into an optimized circuit. Is this possible, and if so, does it exist?
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
15 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 ...
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 ...
1
vote
4answers
83 views

Automatic softcore configuration based on intermediate representation (IR) compiler output

When compiling a piece of software (with LLVM for exmple), you first transform your code into some kind of intermediate representation (IR code). This IR code needs to be converted to your target ...
0
votes
1answer
59 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
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 ...
7
votes
2answers
676 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 ...
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
19 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
2answers
315 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 = ...
1
vote
1answer
34 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
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/...

1
2 3 4 5
12