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

How to view Graph Reduction/Graph Representation for a Haskell program?

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 ...
1
vote
1answer
409 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
259 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 ...
2
votes
1answer
93 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
28 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 ...
1
vote
1answer
49 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
231 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
29 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
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 ...
0
votes
2answers
556 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
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
56 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
130 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
672 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
41 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
118 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
62 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 ...
1
vote
0answers
88 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 ...
0
votes
1answer
247 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
226 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 ...
1
vote
1answer
33 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
467 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 ...
1
vote
1answer
38 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
48 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
34 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
53 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
25 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
88 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
792 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
216 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
190 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
73 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- ...
1
vote
3answers
505 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 ...
2
votes
1answer
279 views

How to translate automatons (Turing machines) into programs of high level programming language?

Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the ...
0
votes
1answer
49 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
56 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
285 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
150 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
47 views

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

Say I had two functions called one after the other: ...
2
votes
0answers
220 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
599 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
82 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
198 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
163 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 ...
0
votes
2answers
99 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 ...
0
votes
0answers
26 views

Minimal DFA for "$n$th character from the right is $a$" [duplicate]

I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$: $$ (a|b|c)^*a(a|b|c)^{n-1}. $$ The exercise asks for the number ...
2
votes
2answers
591 views

Does assembly language get translated to binary code? If so, is assembly language portable across machines?

I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear. Here is my understanding: High level code written in a ...
1
vote
0answers
33 views

Using DPDA instead of LR parsers

If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...

1 2
3
4 5
12