Stack Exchange Network

Stack Exchange network consists of 175 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).

0
votes
1answer
33 views

Generating intermediate code

I have a problem in backpatching "if-else" statements, for generating 3 address codes. The grammar rule is : S -》 if E then M1 S1 N else M2 S2 The semantic ...
0
votes
0answers
24 views

How does Computer Understand post fix notation? [closed]

for example we just put A B C * + D + and we have to do post fix notation than how does the computer understand to do it in a correct way. Thanks
1
vote
1answer
28 views

How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed. If a grammar is left-recursive, then the set of ...
1
vote
1answer
27 views

Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...
2
votes
2answers
59 views

Error propagation when compiling a compiler

Just for curiosity, I recently heard that many compilers are written in its own language. For example, gcc is partially written in C. And old version of compiler is used to compile the new version of ...
5
votes
1answer
79 views

Why more and more handcraft lex do not use regular expression any more?

Recently I read the source code of Clang, and found that it just do the lex thing by reading characters one by one and manually do the matching. But both my teacher when I'm in college and the book "...
1
vote
1answer
31 views

Is this a proper LL(1) Grammar?

Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) ...
1
vote
1answer
37 views

Can there still be infinite recursion if I remove all left recursion?

I have to transform the following grammar into a non left recursive grammar: S → aSb | bAS A → AaA | bAA | AAa | bAb This is what I came up with: A → bAAA’| bAbA’ A’ → aAA’| AaA’| ε S → aSb | ...
3
votes
1answer
71 views

Why more and more languages do not have link stage when compiling?

As far as I know, only C, C++, and Objective-C (in most used languages) need a linker when compiling, languages like Java and C# don't have one, and it seems more and more modern languages do not have ...
2
votes
1answer
21 views

Why are regular expression used in lexical analysis instead of grammars?

Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?
2
votes
1answer
26 views

SLR parse table and unambiguity

If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous? I think that since we have constructed the parse table ...
1
vote
0answers
20 views

Maximizing cache utilization when scheduling a computation graph

So I’m making a program where I generate a computation graph that will be executed on an external device, where the goal is to order the computations in the graph so that the whole computation is done ...
0
votes
0answers
10 views

Number of look aheads in $LR(1)$ items?

I found the following question Let G be a grammar with the following productions: $E→E+T∣T$ $T→T∗F∣F$ $T→(E)∣T−F$ $F→id$ If $LR(1)$ parser is used to construct the $DFA$ using the ...
0
votes
0answers
23 views

Sufficient conditions for an analysis using a monotone framework to converge

We define a monotone framework as follows: $\begin{align*} in(\ell) &=\begin{cases} \mathrm{Initial} & \text{when $\ell\in$ Entry Labels}\\\\ \bigoplus \{out(\ell') \mid (\ell',\ell) \in \...
2
votes
0answers
19 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
vote
0answers
28 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
181 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
24 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
20 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
34 views

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

Consider the following grammar: Stmts -> Stmt | Stmts;Stmt Stmt -> Var =E Var ->id[E] | id E-> id | (E) in accepting state we get ...
2
votes
1answer
43 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 ...
2
votes
2answers
30 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 ...
0
votes
1answer
29 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
27 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
43 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
42 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
26 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 ...
0
votes
1answer
39 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
21 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
1answer
26 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
57 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
102 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
60 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
13 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
509 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
43 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
40 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
26 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
41 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
119 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
56 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
161 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
105 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
166 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
87 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
84 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 ...