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
2
votes
4answers
90 views

How do compilers assure stability?

Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
1
vote
0answers
42 views

Is there a way to simplify redundant conditionals?

For example if I've this: if a == false then return true else if a == true and b == false return true else if a == true and b == true then return false can be ...
2
votes
1answer
76 views

Is a compiler a kind of Gödel numbering program?

Question: Is a compiler a kind of Gödel numbering program? Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one ...
2
votes
1answer
72 views

Code optimization - syntax tree vs. intermediate representation

I'm working on a compiler for my own custom language. As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been ...
1
vote
1answer
236 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
3
votes
0answers
149 views

Uses of irreducible control flow

What are some applications where irreducible control flow is required*? I'm particularly interested in programming language features that will be tricky to efficiently compile if the compile target ...
0
votes
1answer
26 views

Predicitve Parser LL(1) condition

Lets say we use the predictive parser LL(1). Why is it necessary that $FIRST(\alpha) \cap FIRST(\beta) = \emptyset$, for all $\alpha, \beta$ right side of alternative productions i.e., productions ...
2
votes
1answer
1k views

What is the Purpose of Augmented Grammar in LR parsers?

I was reading the LR() parsers from the Dragon Book where I came across these lines: To construct canonical LR(0) collection for a grammar, we define an augmented grammar and 2 functions, CLOSURE ...
1
vote
3answers
55 views

Why is casting float to double applicable?

This is indeed a Computer Science Question. As far as I am concerned casting down (up) does not require any mathematical operation. It is just shrinking down (leveraging) the significant bits. e.g <...
0
votes
0answers
27 views

Computing Follow sets of Grammar for LL(1) parser

I am trying to compute the Follow set of the following Grammar: E -> E' E A A -> + | * E -> num E' -> num I start by adding the end of string symbol, ...
3
votes
1answer
118 views

Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that ...
3
votes
4answers
5k views

Do you ever “download” a language?

When one "downloads" a language (say, downloading the python file, or doing apt-get ruby or something), is it always the ...
-2
votes
1answer
37 views

Computing FIRST and FOLLOW

Given the following grammar with terminals $VT=\{[,],a,b,c,+,-\}:$ $S \rightarrow [SX]|a$ $X \rightarrow +SY|Yb|\epsilon$ $Y \rightarrow -SXc|\epsilon$ This should be the FIRST function: $first(S) =...
0
votes
1answer
2k views

Computing FOLLOW sets for a LL(1) grammar

I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word. Given the grammar: ...
3
votes
1answer
117 views

Loop-local variable in Cytron's SSA algorithm

I am trying to write a compiler that converts a simple imperative language to SSA form, but I am having trouble with loops. As an example, I have some code that looks like: ...
0
votes
2answers
608 views

How to write suitable three address code for switch-case statements?

I want to translate a java switch-case statement to intermediate representation of the three address code form. Three address code or TAC is a form of intermediate representation where each ...
0
votes
1answer
39 views

Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
2
votes
1answer
96 views

Why is backpatching needed during intermediate code generation?

In compiler design, control-flow statements are translated to sequences of three-address-code (3AC) instructions a lot of which are jump statements. A 3AC instruction of the jumping type could be an ...
1
vote
0answers
58 views

How to translate boolean expressions to three address code?

There are two uses of a boolean expression in a language like C, one as a condition in flow of control statements and the other as boolean value in assignment and arithmetic expressions. I was ...
1
vote
1answer
164 views

Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars. However, I've encountered this statement from my notes: With $\epsilon$ productions in the ...
0
votes
1answer
164 views

How can I determine the start non-terminal of a CFG?

Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (disjoint). $A ::= x|y|z$ $B ::= a|b|c$ ... $...
1
vote
1answer
27 views

Compilation with a witness / certificate

Sometimes, to install a program, you have a choice between compiling it yourself or downloading a precompiled binary. In theory (using a new programming language and a new compiler designed ...
0
votes
1answer
343 views

Table-Driven Lexer and the Classification Table

I'm trying to implement a compiler for a custom language as part of an assignment. I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 ...
1
vote
1answer
48 views

Are these REs equivalent?

I have to implement a compiler for a given language as part of an assignment. The language is kept simple enough such that it can be fully expressed through REs. My question lies with two of the REs ...
0
votes
1answer
68 views

Which parser has the highest reduce moves?

From what I have learned the number of reducing moves in the parsers are generally in the order LR(0)>= SLR(1) >= LALR(1). But I am unable to understand where should I place CLR(1) in this ...
2
votes
4answers
4k views

DFA accepting strings with at least three occurrences of three consecutive 1's

The problem states the following: Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with ...
1
vote
1answer
44 views

Tools for modelling compilers

I'm a wannabe mathematician, whose master's thesis is (by the looks of it) going to focus on a certain "compiler", used to produce learning materials from a subset of $\LaTeX$, in the context of ...
1
vote
1answer
35 views

Passing a non-mutable argument by value or by reference?

A function can generally be defined to receive parameters by value or by reference. If we want to mutate an object inside the function and have those changes reflected outside the function, then it ...
0
votes
0answers
31 views

Compiler design: How are the initialize conditions for data-flow problems set?

Consider a typical data-flow problem, for example, reaching definitions or available expressions. I am struggling to understand how $IN$ and $OUT$ of the basic blocks are initialized. For example, ...
0
votes
0answers
41 views

How to include both precedence and associativity in following grammar?

For the following grammar, how can I include both precedence and associativity of operators: S -> S|S S -> S.S S -> S* S -> (S) S -> a|b Note: In the first rule ...
-1
votes
1answer
24 views

Identify the type of the grammar

I have found the following question from internet. They have even given the answer as option c. But i am confused because the grammar also does not looks like a Regular. Please help me to understand ...
0
votes
2answers
72 views

Is this correct grammar definition of Backus-Naur form?

I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move ...
0
votes
1answer
636 views

Is following grammar LR(0)?

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question. Grammar: $SL \rightarrow SL ; S \space | \space \epsilon$ $S \...
5
votes
2answers
316 views

is the problem of parallelising any program, NP-complete?

Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, ...
0
votes
2answers
92 views

Do compilers of high programming languages always compile them directly to machine code?

As an amateur Bash/JavaScript scripter who never wrote one sentence in Assembly, I ask: Do compilers of high programming languages always compile them directly to machine code, or are there cases ...
1
vote
2answers
163 views

Is call stack compile time or runtime detail?

I'm sorry if the question is quite naive, but I don't understand if a call stack is a language implementation detail or it depends on OS? What I'm trying to understand is what decides how to store ...
5
votes
3answers
16k 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 ...
-1
votes
2answers
154 views

Are there any educational virtual machines?

There is plenty of machine/assembly languages such as LC-3, DLX, etc. designed for educational purposes. I am looking for an educational VM, by VM I mean stack virtual machine that has instructions ...
1
vote
1answer
55 views

does a non-terminated string count as a token in c?

so, I am preparing for an exam which includes lexical analysis from compiler design. I was wondering what is the number of tokens in the following code- ...
0
votes
2answers
390 views

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power. Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),...
1
vote
0answers
23 views

Is Constant Folding a type of Memoization?

I was reading about Constant Folding and it sounds very similar to Memoization so I suspect that it indeed is a type of memoization but I've done some searching and can't find a solid answer (in ...
0
votes
1answer
46 views

Grammar is LL(1) or not?

S -> AS | b A -> SA | a I get FIRST of S = {a,b} for S->AS and FIRST of S = {b} for S->b Hence FIRST(AS) ∩ FIRST (b) is not a disjoint This is not LL(1) But I checked this site http://smlweb.cpsc....
1
vote
2answers
138 views

Run-Time environments

I was reading about Run-Time Environments. In the Dragon book (2nd ed.) I came across the following presentation: [To implement abstractions, the] compiler ...
0
votes
1answer
48 views

What happens with register usage in deeply nested functions calls (in theory)?

I am far from being able to construct a meaningful test for this using godbolt or some C compilation tool. But basically I am wondering what it would look like to have deeply nested function calls, ...
2
votes
0answers
45 views
2
votes
0answers
199 views

Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
90
votes
7answers
21k views

Why are some programming languages “faster” or “slower” than others?

I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I ...
0
votes
0answers
492 views

Syntax Directed Translation Scheme for Postfix to Infix Notation

I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3 We have to construct a syntax-directed translation scheme that translates arithmetic ...
0
votes
0answers
67 views

Converting from cfg to cnf (Chomsky normal form)

I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need ...
1
vote
2answers
58 views

Compiler - Why is the grammar not suitable for shift-reduce

Consider this example: stmt => if (expr) stmt | if (expr) stmt else stmt | other Why can't we use shift-reduce on this? This is a compiler homework and I ...

1 2
3
4 5
12