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
14 views

Haskell Graph Reduction/Graph Representation

I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to ...
0
votes
1answer
23 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 ...
2
votes
0answers
18 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 ...
1
vote
1answer
38 views

How does Warrens Abstract Machine work?

I've recently learned about Prolog and Logic programming which I find pretty cool, but the compiler is currently like magic to me and I want to know how they work. After a little bit of research I ...
0
votes
1answer
15 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 ...
0
votes
0answers
7 views

Control flow graph for 3 Address Code inquiry

I'm supposed to do a three address code for the following semantic action S-> repeat S1 until E times_in_a_row B holds Which is meant to be: Repeat Statement 'S1' as long as the condition B had not ...
1
vote
1answer
21 views

How many syntax trees can be made by a BNF

An example of this would be: 1+2*3+4 Expression = Expression Arithmetic Expression | number Arithmetic = + | - | * | / Through just breaking down 1+2*3+4, it was easy to find that the answer was 5 ...
1
vote
3answers
33 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
16 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
4answers
4k 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 ...
0
votes
2answers
47 views

Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
-2
votes
1answer
34 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
0answers
7 views

Understanding Register Allocation using Graph Coloring in this Specific Paper

I'm currently reading the paper "Register Allocation Via Coloring" By Gregory J. Chaitin and others (1980). I'm having trouble understanding the way an "interference graph" is constructed as explained ...
0
votes
1answer
22 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 ...
3
votes
1answer
81 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
117 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
38 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
29 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
2answers
30 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
1answer
31 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$ ... $...
0
votes
0answers
11 views

trouble in distinguishing between syntax directed translation and syntax directed definition

I am currently reading the dragon book ,chapter 2 is confusing me a lot according to it the definition of the two terms are: syntax-directed translation syntax-Directed translation is done by ...
1
vote
1answer
31 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
0answers
19 views

Alternative of syntax-directed translation

I'm implementing a toy C compiler. For both type checking and code generation phases, I've used the syntax-directed translation method (which is discussed in detail in the Dragon book); looking around ...
0
votes
1answer
133 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
45 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 ...
1
vote
1answer
32 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 ...
1
vote
1answer
40 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 ...
0
votes
0answers
23 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
25 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 ...
0
votes
0answers
22 views

Find equivalent LL(1) grammar

There is sample question to calculate equivalent LL(1) grammar for below grammar: $S \rightarrow S b$ $S \rightarrow S d$ $S \rightarrow c S$ $S \rightarrow c c a$ At first step, ...
-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
54 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
145 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 \...
1
vote
2answers
76 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 ...
-1
votes
2answers
85 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
45 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
107 views

Is type-checking “syntactic” or “semantic”?

On the wikipedia page on compilers, it says: Semantic analysis adds semantic information to the parse tree and builds the symbol table. This phase performs semantic checks such as type checking (...
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 ...
1
vote
1answer
103 views

How to translate automaton (Turing machine) into the program of high level programming language?

Every program in high level ("industrial") programming language can be expresses as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian ...
0
votes
0answers
41 views

What are the errors in the following program?

Consider the following C code: ...
0
votes
1answer
34 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....
0
votes
1answer
32 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, ...
0
votes
1answer
95 views

LR(1) parsing, problem with look ahead symbols

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution. I'm trying to fill the LR(1) parsing table for the grammar ...
1
vote
2answers
100 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 ...
2
votes
0answers
35 views

Compiler optimization which does an SMT-like optimization in software?

Say I had two functions called one after the other: ...
3
votes
0answers
167 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 ...
0
votes
0answers
147 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
43 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
1answer
88 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 ...
1
vote
0answers
56 views

Does a simple calculator have compilers?

When I input something wrong in my Casio fx-82MS calculator it shows Syntax error on its screen. So does even a simple calculation on a most simple calculator like this goes through compilation ...

1
2 3 4 5
10