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 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).

1
vote
0answers
16 views

Why irreducibility is an important concept in Flow Graphs?

Here is a definition of reducible flow graphs : A flow graph is reducible if every retreating edge in any DFST for that flow graph is a back edge. And the reasons why we care about ...
-1
votes
0answers
25 views

What's the difference between the given parse trees?

Could someone please explain what's the difference between the two parse trees in the given image and which is the right answer for the given question: Consider two binary operators && and || ...
1
vote
0answers
21 views

Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
3
votes
0answers
174 views

How to select a loop nesting trees for irreducible loops?

I am trying to understand the process of analyzing a control flow graph and building a tree of loops, both reducible (single entrypoint) and irreducible (multiple entrypoint), using the algorithm ...
0
votes
0answers
20 views

Three Address Code

At first I am not sure that this question belongs to this domain. If it does not, I am sorry. As you know, structure of a compiler consists of two parts which are analysis phase and synthesis phase. <...
0
votes
1answer
19 views

How to solve the following left recursion?

A common left recursion: A -> Aa | B can be solve by transforming it into: A -> BA' A' -> aA' | E However, I ...
0
votes
1answer
19 views

is conflict possible In accepting state of LR(0)?

Consider the following grammer:- Stmts -> Stmt | Stmts;Stmt Stmt -> Var =E Var ->id[E] | id E-> id | (E) in accepting state we get S' -> stmts . stmts -> stmts . ;stmt isn't it a conflict ?
1
vote
1answer
30 views

finding separating words (Nerode)

i have found the equivalence classes of given $R_L$ and i need to find the separating words between the equivalence classes(which i don't know how to do). would appreciate if you could explain to me ...
0
votes
0answers
12 views

When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis

I've been exploring the differences between Context Sensitive Analysis (CSA) and Context Insensitive Analysis (CIA), members of ...
-2
votes
0answers
12 views

Symbol Table Memory Allocation methods

I wanted to know how symbol table for a compiler are allocated memory.Are they statically allocated memory or dynamically?
0
votes
1answer
26 views

Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$

I found a question. Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$ My attempt: $t_1 = q*r$ $...
0
votes
1answer
21 views

Token Scanner for programming Language(Lexical Analysis)

This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them. The ...
2
votes
1answer
36 views

Parser theory: How to systematically compute FOLLOW sets?

Forgive me for my ignorance as I am self-teaching myself some of this theory... I am having some trouble understanding how to systematically/algorithmically compute FOLLOW sets, given that I have ...
0
votes
2answers
40 views

Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
0
votes
1answer
19 views

Does any parser ever parse non deterministic unambiguous context free grammar?

I have been informed parser parses unambiguous context free grammars of $DCFL$. I was wondering if there could be a parser which could make a parsing table for unambiguous grammars of $NCFL$? Note: ...
0
votes
0answers
12 views

Does parser ever use ambiguous grammars other than operator grammars to make parse trees?

Operator precedence parser is a bottom up parser which employs even ambiguous grammars, although limited, in form of operator grammars to parse a stream of tokens. But is there any parser which ...
-1
votes
0answers
52 views

Why we don't use regular expressions in syntax analysis

In lexical analysis, we use regular expressions. A regular expression is a sequence of characters that defines a search pattern. However, in syntax analysis we use grammars. A grammar is a set of ...
0
votes
1answer
35 views

First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?

Suppose that we have a grammar with the following rules: $$S \to Aa\ |\ b\ |\ \varepsilon\\ A \to Ad\ |\ c$$ From looking at it I already know that $First(S) = \{b, \varepsilon, c\}$. My question is:...
0
votes
1answer
19 views

LL(1) and LR(0) Grammars

The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision. For example, without reading a symbol from the input, we cannot decide in LL(1) ...
0
votes
0answers
18 views

Follow Set of a Grammar

I have a grammar, and I cannot make sure a follow set: A -> ABC B -> b C -> c ...
0
votes
1answer
25 views

Transition diagram for following token number

number -> digits(.digits)?(E[+ -]?digits)? This transition diagram runs the above mentioned token I can not understand this how this is work.what is meaning of "?"Symbol and digits. can anyone ...
0
votes
1answer
36 views

LR parsers and ambiguous and non deterministic grammars

Dragon book says: An ambiguous grammar can never be LR. And then immediately further it says: For example, consider the dangling-else grammar: $\begin{align} stmt \rightarrow & \textbf{...
0
votes
1answer
58 views

First-order vs Higher-order Programs

Can someone explain the difference between first-order programs and higher-order programs in the context of programming languages? My understanding so far is that Functional Languages (most) use ...
1
vote
0answers
15 views

Clear definitions of various terms related to top down parsers and classification of the same

I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am ...
4
votes
0answers
45 views

What is the difference between A-normalization and K-normalization in compilers?

Administrative normal form is a program intermediate representation in which each immediate instruction has a name. It is used in GHC and OCaml. K-normalized form is an intermediate representation in ...
1
vote
1answer
12 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
480 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
39 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
30 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
25 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
37 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
100 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
39 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
18 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
76 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
63 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
161 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
85 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
0
votes
0answers
30 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
77 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
158 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
64 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
19 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
3k 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
35 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
27 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
91 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
49 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
95 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
31 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 ...