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
0answers
21 views

Is there a simple algorithm for generating unit tests given a function's code? [closed]

Given the abstract syntax tree (AST) of each line of a function's code, I am asked to generate code for that function's corresponding unit tests, similar to what Microsoft's IntelliTest tool does here:...
-1
votes
0answers
17 views

Data space progress - Compilers

Consider a programming language that supports (a) nested subroutine statements with static binding and (b) value-by-reference parameterization and by name, with corresponding keywords val, var and ...
0
votes
0answers
34 views

Why the grammar is not (LL1)?

Why the grammar is not (LL1)? (e is the epsilon) S -> a A | b B | a C c ; A -> a A | a a A | e ; B -> c C | D | e ; CHOICE 1: The grammar is Left-Recursive (LR) CHOICE 2: The grammar is Non-...
1
vote
2answers
160 views

What kind of binary compatibility is present for 2 processors sharing an Instruction Set?

Consider Intel x86 and AMD x86 Processors. As I understand, since they use the same Instruction Set, in theory an application compiled for Intel x86 processor would run without any modification on ...
1
vote
3answers
47 views

Variable name starting with integers

When I started doing programming I wondered that why the variable names can't start with integer. Back then I accepted that , may be this is how the compiler designers have decided to go with. But now ...
0
votes
1answer
40 views

How are lexical tokens produced

I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, ...
2
votes
1answer
26 views

Left recursive grammar to right recursive grammar

I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is $$E \to E + T \mid T $$ It's equivalent right recursive grammar will be $$\begin{align}E &\to ...
2
votes
0answers
33 views

What assigns the physical addresses to variables?

Earlier I was having a technical test when I stumbled across this question: I know that probably in modern systems, the OS and the MMU is responsible for that. But the test was focused on Embedded ...
2
votes
1answer
35 views

How does software prefetching work with in order processors?

From prof. Onut Mutlu's slides on prefetching, this example has been shown as software prefetching: ...
0
votes
0answers
17 views

Calculating ring inequalities with fixed precision

Suppose we are given $n$ $M$-bit (the word size of the computer) integers $x_i$, and wish to calculate a linear or nonlinear inequality involving the numbers (an expression made up from the $x_i$, ...
4
votes
1answer
60 views

How compiler optimizations create irreducible control flow graph?

I've been looking through research papers and the internet and found many claims that "compiler optimizations can cause irreducible control flow". However, I was not able to find a single ...
0
votes
0answers
55 views

How LR parser works with grammar containing epsilon productions

In Dragon book for compiler design there is this example of SDT in Example 5.16 $L\rightarrow En$ $E\rightarrow \{ print (' +') ; \} \space E_1 + T$ $E\rightarrow T$ $T\rightarrow \{ print (' *' ) ; ...
1
vote
2answers
84 views

How is CLR(1) grammar more powerful than LALR(1) grammar

I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
1
vote
1answer
34 views

PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

On my compilation theory exam we had the following problem: Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
1
vote
1answer
53 views

virtual machine based programming languages vs low level

I took programming lecture it was about C/java and how to build compilers, so I wanted to know. As far I see, languages like Java/C# are developing their virtual machine CLR/JVM with good base and are ...
3
votes
1answer
33 views

Representing abstract syntax tree as a graph

Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code? The goal and application ...
0
votes
1answer
36 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 ...
1
vote
0answers
12 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
94 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
38 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
21 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
48 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
22 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
670 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
40 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
29 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
30 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
120 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
37 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
36 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
39 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
31 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
167 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
43 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
45 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
15 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
827 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
20 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
385 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
32 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
40 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
15 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
20 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
18 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
45 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
75 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
72 views

(Finite Automata) Why the following is a NFA?

The first one seems like a DFA. Could someone explain why this is a NFA?

1
2 3 4 5
12