People who code: we want your input. Take the Survey

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

Understanding the rules of parsing table construction

I'm studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules. Example grammer is like this S → ( S ) S | $\epsilon$ How can I derive like ...
1
vote
1answer
346 views

Implementing a symbol table with a hash table and a stack

I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different ...
2
votes
0answers
24 views

Metrics for measuring and scoring automated “code analysis”?

I am writing various "program analysis" (aka static code analysis) algorithms. I am looking for ideas for metrics to measure how well my algorithms "understand the code". Some ideas i have so far : ...
0
votes
1answer
71 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 ...
14
votes
2answers
845 views

What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
4
votes
1answer
1k 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 ...
2
votes
1answer
396 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
78 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
106 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 "...
2
votes
1answer
57 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) ...
2
votes
1answer
607 views

Tokenization Problem

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult. My Regular ...
1
vote
1answer
91 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 | ...
4
votes
1answer
138 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 ...
0
votes
1answer
5k views

How does lexical analyzer remove white spaces from source file?

In compiler at phase lexical analyzer, how does lexical analyze strip out white spaces from source file?.
3
votes
1answer
2k views

How to generate an LL(2) parse table?

The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that: ...
2
votes
2answers
61 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
1answer
50 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?
3
votes
1answer
79 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
34 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 ...
-1
votes
1answer
43 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 ...
2
votes
1answer
66 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 ...
11
votes
3answers
761 views

Getting started with Program Analysis

I'm looking for resources on getting started with program analysis. The only book I've found on the topic is the Nielson & Nielson book. Other than that, it seems like there are only "compiler" ...
2
votes
0answers
56 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
39 views

Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
0
votes
2answers
119 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 ...
3
votes
0answers
270 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
1answer
41 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:...
4
votes
2answers
105 views

Is there a fundamental CS problem in ORMs that leads to N+1?

Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it....
0
votes
1answer
35 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
489 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$ $...
3
votes
2answers
209 views

What defines a tool as a “compiler”

I've been trying to figure out what technically makes a tool or program a compiler. For example, I know that gcc will compile source code to object files or assembly, hence transforming a ...
5
votes
2answers
4k views

Bottom-Up Evaluation of Inherited Attributes

I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows : Using a top-down translation scheme, we can implement any $L$-attributed definition ...
4
votes
1answer
151 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 ...
1
vote
1answer
194 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: ...
5
votes
2answers
2k views

The difference between compiler and interpreter

I am reading dis, It reads: The dis module supports the analysis of CPython bytecode by disassembling it. The CPython bytecode which this module takes as an input is defined in the file Include/...
0
votes
1answer
173 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
159 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 ...
1
vote
1answer
459 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
810 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
23 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 ...
33
votes
5answers
10k views

How do computers remember where they store things?

When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?
0
votes
1answer
227 views

The origin and the meaning of “Abstract Syntax Tree”

This question is closely related to Does an abstract syntax tree have to be a tree? and is partially answered there, but I would like to be more precise and to have more concise answers. What is the ...
17
votes
6answers
2k views

Does an abstract syntax tree have to be a tree?

Does the output of a parser have to be a tree or could it also be general graph? Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees ...
3
votes
3answers
3k views

Why not use Right Recursion to avoid Left Recursion?

I am reading about Representative Grammars from book, where I encountered the following grammar: $$ E \rightarrow E + T \ | \ T $$ $$ T \rightarrow T * F \ | \ F $$ $$ F \rightarrow (E) \ | \ id$$ ...
1
vote
1answer
20 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 &...
1
vote
1answer
116 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
vote
1answer
93 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?
6
votes
2answers
520 views

What's the advantage of typed assembly?

I've seen scattered references to typed assembly in high assurance literature, but I don't really understand the advantage. If the compiler/runtime are capable of passing the types down to the CPU, ...
1
vote
3answers
539 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\ |\ ...
3
votes
0answers
213 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: ...

1
3 4
5
6 7
12