Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about programs that read code in one language (source language) and translate it into an equivalent program in another language (target language).

-1
votes
0answers
16 views

Can we assume that a UTM is equivalent to a programming language? [duplicate]

I wanna know can we assume that a Universal Turing Machine is equivalent to a programming language like C++? The main question is can the gcc compiler work as a UTM or not? I know we can implement UTM ...
1
vote
1answer
11 views

Choosing correct action in bottom up parsing

Using grammar: $ S \to aABe \\ A \to bcA \mid c \\ B \to b $ to bottom parse a string $abcccde$, the course of action would be: $ \begin{array}{c|c|c|c} \hline Step & Stack & Input &...
3
votes
2answers
450 views

Do “compiler” and “assembler” correspond to frontend and backend phases of a compiler?

In Compilers: Principles, Techniques, and Tools (2nd Edition) 2nd Edition by Alfred V. Aho (Author), Monica S. Lam (Author), Ravi Sethi (Author), Jeffrey D. Ullman (Author) , Figure 1.5 gives a ...
1
vote
1answer
35 views

Can the compiler convert recursive algorithm into a dynamic programming

So I was going through the idea behind dynamic programming (memoization), and thought of this question. Can a compiler convert any recursion into a table filling DP solution, of course given the ...
-1
votes
1answer
29 views

Is it safe to assume that there would be no high level languages without existence of compilers/interpreters?

I am relatively new to computer science. There,s been something that i have been thinking now that i am studying how to make actual compilers. We are past the days of programming with binary and ...
1
vote
1answer
22 views

Are space allocated to C/C++ variables in secondary storage also in Compiled file?

Are data segments,heap,stack etc also present in secondary memory with compiled code then later mapped by OS to RAM when I open it?
3
votes
0answers
33 views

Type system for Query DSL with only simple GADTs: what typing judgments are needed?

Background I have several F# codebases with reasonably high level of complexity of code. In order to convince myself that the code is solid I do whatever I can to write as much of it as possible type-...
1
vote
3answers
86 views

What is a non-ambiguous CFG for generating the set of natural numbers?

I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar: $\mathcal{G}: S \rightarrow 0\ |\ ...
0
votes
0answers
28 views

Alternatives to phi nodes in static single assignment

I have read somewhere about an alternative SSA representation that doesn't use phi nodes but instead uses parameterized basic blocks. Something like this in an SSA with phi: ...
0
votes
0answers
17 views

Counting number of control flow path

I know the answer that it will be 1024(2^10). But iam not able to understand why, I have looked the answer but still don't find it compelling My reason, it says ten if are there in the language and ...
0
votes
1answer
40 views

Counting tokens in compilers, lexical analyser

Let's start with the question. Say I have a C language statements follows it 458cat 2.01 = 96.87abc a.2 ; -my question is how many tokens are there in the above statements. Secondly does white ...
1
vote
1answer
47 views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
4
votes
1answer
156 views

How to generate branch tables from SSA form?

Branch tables are usually described as an efficient way a compiler can implement a switch statement, and that actually seems how GCC and Clang do it (and LLVM even has an opcode just for that). If a ...
1
vote
1answer
83 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
0
votes
0answers
28 views

A problem with understanding handles

This is the definition of a handle: 1.A “handle” of a string is a substring that matches the RHS of a production. And 2.Whose reduction to the non-terminal (on the LHS of the production) represents ...
0
votes
3answers
75 views

Is it 100% OK to say “All software doesn't need to know the system lower than the architecture level”?

Most of you know this diagram. If this diagram is true, all software is free to not know the levels lower than ISA. But it's not true. Softwares like performance-critical programs or system softwares ...
5
votes
1answer
152 views

How to transpile generic functions into language that do not support generics?

Currently, I am developing a transpiler for my own language, however, I find difficulties to transpile generic functions. For example, how would you translate the following Java-like code in to C? <...
0
votes
1answer
59 views

Compilation speed dependent on CPU?

Is the speed of compiling software very dependent on the CPU? I know this question is a bit broad, but I'm to find an answer to the case described below. If I download a software project that makes ...
2
votes
1answer
17 views

Unclear logic notation for PFX program rules

I'm very new to this so please bear with me. I found this document describing the PFX language, a stack-oriented language where the instructions act on a stack and replace the arguments with the ...
1
vote
2answers
1k views

Difference between dynamic loading and dynamic linking in the OS

First of all, I saw many answers of this topic in Quora, Stackoverflow, and this site. But, I couldn't definitely understand the difference between dynamic loading and dynamic linking. What I ...
0
votes
0answers
28 views

Translation from Intermediate Language into 'three-address' machine instructions

I am unsure where to start with this. From what I understand so far, 'VAR(x)' corresponds to Rule 2, ':= VAR(x) ' refers to Rule 5 and '+ NUM (1) refers to link 3. ...
0
votes
0answers
16 views

Do you have any SDD(syntax directed defenition) practice example?

I follow Compilers Principle, Technique and Tools by Alfred V.Aho. I learnt SDD from this book. But, I don't get enough example or practice problem to check how my learning stage is. I also search ...
2
votes
1answer
82 views

Assertion of Type Inference Rules/Type Checking

I have a problem in a book I am trying to accomplish. I understand the overall type of the expression is boolean and how it derives. (y * x) will be rule 4 (counting from top right). (y * x) + x when ...
0
votes
0answers
42 views

High Level Assemblers vs Compilers?

I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful ...
4
votes
2answers
91 views

Why can't a compiler create universal N-bit code (e.g. 32-bit, 64-bit, etc.)

It is my understanding from what I have read that you need to compile separate executables for 32 bit and 64 bit machines. So if I compile a C program for example I need to compile 2 different ...
0
votes
1answer
29 views

Can we use Operator precedence parsing with this grammar?

This Grammar: A-->Bbab|aa B-->b I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this ...
1
vote
1answer
122 views

Why use a CFG instead of a DFG

I just realized a Control-Flow Graph (CFG) is composed of basic blocks, which is a set of instructions. It is mentioned that you can still do stuff like dead code elimination and whatnot, with the CFG,...
0
votes
0answers
66 views

What token does a “peek” operation refer to in Lexical analysis?

Given a grammar for a space delimited list of words: S -> word { space word } word -> [a-zA-Z]+ space -> [ \t]+ And given the input "Hello World", ...
2
votes
1answer
28 views

Extended grammar form (backus-naur) and simple grammar forms equivalence

Square braces around a grammar symbol or symbols denote that these constructs are optional. Thus, production A -> X[Y]Z has the same effect as the two productions A -> XYZ and A -> XZ. Curly braces ...
0
votes
1answer
439 views

CFG With unambiguous if-else statement

I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'. The non-ambiguous if-else statement I took ...
1
vote
1answer
148 views

What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK? is it being used anywhere? ...
0
votes
2answers
42 views

Definition of InLeft and InRight

So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it. I have found it used in the specification for COQ, and in some notes on ...
3
votes
1answer
102 views

Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
1
vote
0answers
113 views

Can a YACC parse an ambiguous grammar

I found a question while studying compilers :- Given a grammar E->E+E/E×E/number The above grammar is fed to a YACC with semantic rules for parsing. What will be the action of the YACC. 1) it ...
0
votes
0answers
16 views

When is local and when global register allocation used

I am reading about register allocation performed by the compiler and I cannot understand what are the benefits/necessities of one over the other? In terms of local register allocation algorithms, I ...
0
votes
0answers
72 views

Calculation of Gen and Kill set for data flow analys

I'm currently preparing for an exam in compiler construction. The course is mainly about optimization in the backend of the compiler. For the optimization we have to do data flow analysis by hand. In ...
3
votes
2answers
83 views

Is it possible to tell if two sequences of assembly instructions are semantically equivalent?

In a modern instruction set like x86-64 there are many many many ways to accomplish the same task using a series of old simple instructions all the way up to the complex SIMD instructions. If one ...
2
votes
1answer
87 views

Why doesn't the C/C++ compilers create different tokens for different types of numbers?

Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc. However if we ...
0
votes
0answers
24 views

Difference between local and global instruction scheduling

I am still unaware why would I use global scheduling for the instructions over the local one. From what I know, the difference between the two is, that the local scheduling is performed in the basic ...
2
votes
1answer
86 views

Why is it better to do the data flow analysis in the basic blocks

I have been reading about compilers and it is said that doing the data flow analysis in the basic blocks is more optimal. Sadly, quoting the exact source, would be slightly hard as it is not in ...
4
votes
1answer
78 views

SAT Solver Front-End: Strategy to order Quantifiers

I am working on a small project. The goal is to implement a compiler from a quite simple, custom syntax of logical formulae (including variables over finite domains) to conjunctive normal form (CNF). ...
2
votes
3answers
38 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
25 views

Saving information from reaching definition

I am learning about compilers at the moment and in my textbook it is briefly mentioned that UD/DU (Use-Def, Def-Use Chains) a way of saving information from the reaching definition is. It is just said ...
1
vote
1answer
68 views

Coalescing by register allocation

I have a rough idea of what coalescing in terms of memory access by threads is, but now, when learning about compilers, the term coalescing also appears when talking about register allocation. In my ...
1
vote
1answer
31 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
1
vote
1answer
79 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
0
votes
1answer
76 views

Big-O complexity of finding exception handler for zero-cost exceptions

I am wondering what the time complexity of finding the most appropriate exception handler for dispatching zero-cost exceptions is. For zero-cost (this refers to execution under the assumption that no ...
1
vote
3answers
453 views

Dangling else problem

I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the else with the last <...
0
votes
0answers
38 views

Can inherited attibutes be evaluated in bottom up parsing?

I have come across the following question in an exam: Can inherited attributes be evaluated in bottom-up parsing? My approach went like this: Inherited attributes can never be evaluated in ...
3
votes
1answer
97 views

interference graph: assigning variable to itself

I'm studying the theory behind compiler design, and was assigned with building an Interference graph for a certain code 3-address code. We were taught to first divide the code into blocks (according ...