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
2answers
14k views

Drawing Annotated Parse Tree for Syntax Directed Definition [closed]

Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following: [Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308] ...
0
votes
2answers
94 views

How are image files, sounds, data, etc. compiled/linked in to a single file?

I'm both asking for me & future readers as to how pictures, sounds, textures, assets, and such are compiled and linked in to one binary/program, and how that process works. I have seen this in ...
0
votes
1answer
119 views

What are current approaches to auto-parallelisation?

I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.
0
votes
2answers
53 views

A state machine that is either DFA or NFA: is it possible?

I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic ...
0
votes
1answer
19 views

Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"?

Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
0
votes
1answer
33 views

Are colored graphs and red-black trees related?

I've come across the concepts of colored graphs (register allocation) and red-black trees. They both seem to have this notion of "coloring", but I've never seen them being connected ...
0
votes
1answer
337 views

What is the difference between a simulator, emulator, and cross compiler?

As far as I understand, cross compilers, emulators, and simulators are all ways that one computer system to be able to behave like or run another computer system. What is the difference between these ...
0
votes
1answer
741 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 \...
0
votes
1answer
53 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
807 views

Why is left recursion and left factoring no problem in bottom up parsing?

i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced. But why is this then a problem ...
0
votes
1answer
29 views

Is scanner and Lexical analyzer same?

Today I read that The scanner is a subroutine which is frequently called by an application program like a compiler. The primary function of a scanner is to combine characters from the input ...
0
votes
2answers
437 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),...
0
votes
1answer
164 views

How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?

I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt: When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
0
votes
1answer
564 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$ $...
0
votes
2answers
124 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 ...
0
votes
1answer
183 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
924 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 ...
0
votes
1answer
111 views

Register Allocation and Definition of Interference

In my textbook on compiler design [1], it describes interference between two variables (the property that they cannot be in the same register at once) as follows: Definition 9.2: A variable $x$ ...
0
votes
1answer
49 views

How does literals in compiled languages differ from literals in interpreted languages?

A literal is a piece of data which gets its value at compile time. Means: Becomes set at compile time and afterward the value is fixed incorporated into the machine code as a code consisting out of ...
0
votes
1answer
61 views

Forward must problem explanation in compiler design

While studying, I came across the following statements: A join point is a program point where two branches meet. Available expressions is a forward, must problem. Forward = Data Flow from in to out....
0
votes
1answer
77 views

LL(k) Prediction Techniques (and Insight on method applied)

I'm requesting references for LL(k) in situations where k > 1 for reasons described below. I'm looking for research/notes/...
0
votes
1answer
883 views

compiler interaction with OS [closed]

I want know if compiler interacts with operating system during compilation process.And if yes then which part of compiler interacts with which part of operating system
0
votes
1answer
25 views

Why does bottom-up parsing of right-recursive grammars require unbounded O(n) stack space?

I keep reading that while bottom-up parsing of a left-recursive grammar can be done in constant O(1) stack space, for a right-recursive grammar, we have to push the entire input stream onto the stack ...
0
votes
1answer
76 views

Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition: A grammar G is ambiguous if some sentence in L(G) has more than one ...
0
votes
1answer
24 views

BNF syntax for a recursive function?

I'm to write a syntax that will allow for a recursive function, i.e. f(x) = if x == 0 then x else f(x+1) Here's one attempt at creating the grammar: But I don't ...
0
votes
1answer
40 views

Using saved registers at the main function with no other function calls [RISC-V]

The convention when a function is going to use a saved register is to save the contents of that register to the stack in case the caller (if there's one? the main function doesn't have one) had been ...
0
votes
1answer
38 views

How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$

Below is an excerpt from the Red Dragon book. $$(1) \quad S \rightarrow A_1 \quad A_2 \quad\{ A_1.in : = 1;\quad A_2.in : = 2 ;\}$$ $$(2) \quad A \rightarrow a \quad \{ print(A.in) \}$$ We find that ...
0
votes
1answer
41 views

L-attributed definitions include all syntax-directed definitions based on LL(1) grammars

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following claim: L-attributed definitions include all syntax-directed definitions ...
0
votes
1answer
17 views

$\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across a claim: $\text{"The error entries in the goto table are never consulted"}$ I feel ...
0
votes
1answer
110 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...
0
votes
1answer
66 views

Calculating worklist with live variable analysis

I am struggling with the calculation of the worklist algorithm, I do not want to implement the iterative algorithm as so many redundant steps it takes. The algorithm I am following to calculate the ...
0
votes
1answer
70 views

Is there any compiler IR paradigms other than Three Address Code and Static Single Assignment (SSA) Form?

Specifically, I have tried boiling down the operations of a VM into the smallest possible standardized units and arrived at this: ...
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 ...
0
votes
2answers
509 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 = ...
0
votes
1answer
48 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
73 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 ...
0
votes
2answers
53 views

Doubt on Token in Compiler Design

Say i have code snippet like --> m -= n; is minus and assignment considered as a single token or they will be considered as different token? So the total token count will be 4 or 5?
0
votes
1answer
72 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 ...
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
137 views

Token Scanner for programming Language(Lexical Analysis)

This DFA is a token scanner for a programming language.I would like to add keywords of the programming language(if,else,end ... etc) in the DFA so the lexical analyzer can recognize them. The ...
0
votes
1answer
42 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:...
0
votes
1answer
387 views

Counting tokens in compilers, lexical analyser

Let's start with the question. Say I have a C language statements follows it 458cat 2.01 = 96.87abc a.2 ; -my question is how many tokens are there in the above statements. Secondly does white ...
0
votes
1answer
60 views

Can we use Operator precedence parsing with this grammar?

This Grammar: A-->Bbab|aa B-->b I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this ...
0
votes
1answer
3k views

CFG With unambiguous if-else statement

I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'. The non-ambiguous if-else statement I took ...
0
votes
1answer
35 views

Saving information from reaching definition

I am learning about compilers at the moment and in my textbook it is briefly mentioned that UD/DU (Use-Def, Def-Use Chains) a way of saving information from the reaching definition is. It is just said ...
0
votes
1answer
596 views

Big-O complexity of finding exception handler for zero-cost exceptions

I am wondering what the time complexity of finding the most appropriate exception handler for dispatching zero-cost exceptions is. For zero-cost (this refers to execution under the assumption that no ...
0
votes
1answer
164 views

Understanding Wirth's symbol table entry

N.Wirth's book on compiler introduces the concept of symbol table and states that every declaration statement results in a new entry in symbol table. Then after showing how an entry in symbol table ...
0
votes
1answer
203 views

How does make/scons manage dependency graph and figure out which file need to be recompiled?

what I understand is that, the file dependency is organized as a graph. Make/scons check the timestamp of each file, when a source file's timestamp is newer than the output, it re-compile everything ...
0
votes
2answers
43 views

What does the $^*$ operator do in the theory of parsing?

I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^*$). The ...
0
votes
1answer
246 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 ...

1
8 9
10
11 12