Skip to main content

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
1 answer
52 views

Can and does any statically typed programming language safely support in-place type-conversion?

Here's some hypothetical rust-inspired language syntax to show what I mean ...
1 vote
1 answer
328 views

Calculate post dominator with non exiting control flow

Using the basic algorithm to calculate post dominators I run into trouble when working with a CFG containing an infinite loop (i.e., not terminating). The algorithm: ...
2 votes
0 answers
1k views

Where does the Dynamic Link point to on the activation record

I'm a bit confused as to wear exactly the dynamic link points to on the activation record. I understand that it points to the 'top' of the instance of the callers activation record but I am unsure of ...
0 votes
1 answer
23 views

Discard all ambiguity from given CFG

Here is given CFG : CODE→VDECL CODE | FDECL CODE | ϵ VDECL→vtype id semi | vtype ASSIGN semicolon ASSIGN→id assign RHS RHS→EXPR | lit | char | bool EXPR→EXPR addsub EXPR | EXPR multdiv EXPR EXPR→...
-1 votes
3 answers
7k views

Eliminating left recursion and left factoring this grammar

I have a grammar S-> SS* | SS+ | a Really confused on how to remove the left recursion and do left factoring My attempt on removing left recursion : S -> aS' S' -> S+S' | S*S' | epsilon If this is ...
0 votes
1 answer
73 views

Is it possible for a language to have mixed evaluation strategies?

As far as I am aware, most functional programming languages today use a call-by-value eager evaluation strategy with some exceptions like Haskell. I am curious if it is possible for a language to have ...
1 vote
1 answer
55 views

Can code using GOTO be converted GOTO-less algorithmically?

My impression is yes, and probably it is achievable even in polynomial time, but I am not sure. The important thing I can see is that the "structured" control structures can be embedded into ...
1 vote
0 answers
13 views

Why would a control flow block need access to the labels associated with a higher or lower level nested control flow block?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
1 vote
0 answers
11 views

Why must empty rules be inserted in syntax-directed translation of a control-flow grammar?

In Engineering a Compiler (Cooper, Torczon) 3rd Edition, Chapter 5 Syntax-Driven Translation, Section 5.3.3 Translating Control-Flow Statements, the following nested control-flow grammar is presented, ...
1 vote
3 answers
419 views

Attribute grammars: How are attributes implemented?

I've read about attribute grammars, but I haven't found out, how are the attributes often implemented? To me they scream objects (of classes), but they could be also variables. But are there any ...
2 votes
3 answers
166 views

What are quines (layman friendly)?

I was going through the Wikipedia page on Quines and did not understand this paragraph - A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
0 votes
1 answer
99 views

Correct way to derive parse trees, for a given input, to show ambiguity

Is it correct to state that the below grammar can handle the expression: a - b * c, by the below two different parse trees. Grammar: ...
0 votes
2 answers
53 views

(novice to compiler design) how does a recursive descent parser decide which nonterminal to parse if there are multiple

Let's say we have a grammar S -> A | F A -> id = exp F -> id ( arglist ) ...
1 vote
2 answers
138 views

Can Yacc be used to generate three address code for Java 1?

I have read that yacc generates bottom up parser for LALR(1) grammars. I have a grammar for Java 1 that can be used for generating three address code and is strictly LALR(1), but the translation ...
0 votes
2 answers
92 views

Can you verify the end of a function declaration through syntax analysis?

In some languages, it is expected that a function declaration be terminated by syntax that includes the function name. For example, in MODULA-2, a function is declared as shown below: PROCEDURE P ; ...
2 votes
0 answers
61 views

Compiler that compiles to a Universal Turing Machine (UTM) tape program?

With Universal Turing Machines I mean the Turing Machines with fixed transition functions, proven by Yurii Rogozhin in his paper "Small universal Turing machines" to be capable of universal ...
1 vote
1 answer
292 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 ...
3 votes
1 answer
117 views

Dataflow Analysis: Available Expressions, why is OUT[B] initialized to universal set?

In the dragon book, section 9.2.6, why is the $OUT[B]$ initialized to $U$ except for $OUT[ENTRY]$. Wouldn't using the $OUT[B] = \emptyset \quad \forall B$ be a more conservative solution? The book ...
0 votes
1 answer
10k views

LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
10 votes
6 answers
2k views

Do we create a programming language by writing a compiler?

Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it? For example, is ...
1 vote
2 answers
194 views

Dynamic list for frame pointers and static list of nested activation frames

I am going through the book Compiler Construction by Niklaus Wirth. The following is what I feel to be stated summarily by his lesson on procedure calls: The compilation of a procedure call is the ...
1 vote
1 answer
62 views

Getting something wrong while building parse table for the grammar

Task Build the Parse Table Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\...
1 vote
1 answer
602 views

How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
0 votes
1 answer
127 views

What does it take to support a programming language on an OS?

From my understanding, something like Linux is very geared towards C programs, with things like libc. What I'm wondering is, even in Java, you have arguments to ...
0 votes
0 answers
15 views

Collapsing loops in a control-flow graph

Let's say we are given some CFG, maybe in SSA-form, and we want to "collapse" each top-level loop into s single node, whose successors would be all exit blocks of the original loop. So we ...
0 votes
1 answer
67 views

Table driven parser vs Recursive Descent parser

I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (...
0 votes
1 answer
75 views

Can all LL(k) grammar can be recognized by LR(1)?

For context free languages, I wonder that if all LL(k) languages can be recognized by a LR(1) grammar?
0 votes
1 answer
793 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
1 vote
1 answer
27 views

Is a language *engine* the same as a language *implementation*?

(This may just be a terminology clarification question.) Wikipedia says A language usually has at least one implementation in the form of a compiler or interpreter, allowing programs written in the ...
1 vote
1 answer
36 views

Creating an executable after code generation - compiler design

I am learning about and building a very basic compiler. My question is about code generation. I have read on a lot of materials about code generation when building a compiler and I get the concept. ...
0 votes
1 answer
131 views

How to Remove Left Recursion from this Grammar?

How to remove left recursion in the following Grammar: S→Bb/a B→Bc/Sd/e Im new to this, below is the way I'm doing it: ...
2 votes
1 answer
40 views

What does the language of DFA of LR itemsets represent?

As we know, if we want to make a $LR(0)$ (say) parsing table for a context free grammar (CFG), we prepare the $LR(0)$ itemsets with $.$ (dot) in RHS of the CFG production. With this $.$ we keep track ...
2 votes
1 answer
106 views

Inference and Unification algorithm provided to a Unification graph of two expressions

I am trying to unify two expressions given a unification algorithm $unify$ applied to the unification graph of the two expressions. However, I struggle a lot in understanding how exactly the steps of ...
1 vote
2 answers
97 views

Could a compiler/static analysis infer the best abstract data type?

I initially brought this up on the Swift Forums, and it was suggested that this might be a thing better suited for CS SE. So here goes: I had this thought that the compiler already has enough ...
4 votes
1 answer
171 views

Tail call optimization via translating to CPS

I am struggling to wrap my head around this compiler technique, so let's say here's my factorial function ...
0 votes
0 answers
13 views

Dependency testing and parallel compilers

I currently study well known dependency testing for automatic loop parallization from parallel compilers (ZIV, SIV, MIV, Single Variable Constraint, Multiple Variable Constraint, Acyclic Test, Fourier ...
1 vote
0 answers
25 views

CHK graph dominance algorithm proof

The algorithm developed by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy is widely used in industry for building dominator tree, but I cannot follow the proof in the “Engineering the data ...
2 votes
2 answers
180 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 \...
0 votes
1 answer
74 views

Is bytecode ("virtual machine code") inherently faster to compile and/or interpret, than higher level (above Assembly) languages?

First, this is not an opinion question. I'm interested in if there is some kind of objective answer. If there isn't, then the answer would be "no". Is bytecode ("virtual machine code&...
0 votes
0 answers
62 views

What is the earliest compiler in chain that was used to create what we nowadays have as a modern C compiler?

My apologies if the title is confusing. First I begin with the statement that may be wrong but what I always thought what happened. "Dennis Ritchie created C compiler which was used to create ...
7 votes
3 answers
1k views

Is it possible to go from code to circuit?

I am wondering if it is possible to have a program that interprets programming code and is capable of turning that code into an optimized circuit. Is this possible, and if so, does it exist?
1 vote
0 answers
86 views

Correct way to show example of ambiguous grammar

Facing confusion due to two different texts stating different ways to show examples of ambiguous grammar, though the example exists in the first book. The second book gives a different example, as ...
0 votes
0 answers
44 views

State of the art in register allocation for straight-line programs

TL;DR: I'm looking for the fastest known algorithm to perform optimal register allocation (optimal in the sense of minimizing the number of spills and reloads) for straight-line programs. Context I am ...
1 vote
0 answers
28 views

A formula of the major garbage collection threshold

I'm studying the garbage collection code of Alex Aiken's COOL programming language's runtime system. (This is the language used in a relatively famous Stanford Online Compilers course) A major garbage ...
1 vote
1 answer
315 views

When and how to generate parse tree while top down parsing

I am trying to build a parser that will eventually output a 3 address code. My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse ...
2 votes
0 answers
135 views

Optimal reassociations is NP-hard?

Consider signed integers with common addition and multiplication. Reassociation of expression is another equivalent form. Say expressions: ...
17 votes
2 answers
3k views

Compiler that compiles to a Turing machine?

I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for ...
0 votes
1 answer
51 views

Is it possible to automatically detect which variable is not used in future and free those memory?

What I need is similar to garbage collection but a bit different, consider the following code: ...
0 votes
1 answer
1k views

How to handle epsilon production in CLR(1) parsing?

Given the following grammar: S -> A A -> AB A -> ϵ B -> aB B -> b Check whether it is CLR(1) or not. I have drawn the canonical itemsets as well as the parse table. But I'm not sure ...
-1 votes
1 answer
50 views

Can parser split tokens?

Is it valid to have the token split up, in a parser; as shown in the below grammar: ...

1
2 3 4 5
14