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

How does LALR(1) parser behave compared to LR(1) paser?

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads: "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
0
votes
0answers
16 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 "...
1
vote
1answer
98 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
1
vote
1answer
85 views

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below. The above diagram is very helpful in understanding the correlation among ...
2
votes
1answer
30 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
2
votes
1answer
123 views
0
votes
0answers
43 views

Can you decompile from code that was written in assembly?

I've been reading a little about decompilers, and I think I get the general idea. I understand that I could start with either assembly or machine code, and then I'd have a decompiler which would ...
0
votes
1answer
558 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 (...
2
votes
0answers
15 views

History of the category of effectful computations

The 1971 paper A Catalog of Optimizing Transformations contains this passage: irreducible subprograms require special handling. (An irreducible subprogram is one which maintains a history, performs I/...
0
votes
1answer
53 views

Removing left recursion with terminals only

I have a grammar: $G → id > id$    $| id < id$    $| G and id$ Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?
0
votes
0answers
13 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
0
votes
1answer
23 views

LALR lookahead is wrong, why?

I am studying LALR(1) parser and I have this question: Consider the following Grammar S - > V = E E - > F | E+F F - > V | int | (E) V - > id Construct the LALR(1) parsing table for this ...
0
votes
1answer
104 views

left/right derivations of grammars and parse trees

I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct. $S-> NP$ $V$ $NP$ $NP -&...
20
votes
9answers
4k views

Would it be wrong to say that the processor (and hardware) is the implementation of an interpreter for machine language?

The question is basically in the title. I know that a computers hardware is of course some physical object, where as the interpreter is some abstract thing that does something abstract with the code ...
1
vote
3answers
4k views

Compilation speed dependent on CPU?

Is the speed of compiling software very dependent on the CPU? I know this question is a bit broad, but I'm to find an answer to the case described below. If I download a software project that makes ...
0
votes
0answers
89 views

Why doesn't my compiler think more about optimization?

This happens to me from time to time: I compile my code with the highest optimization level (-Ofast) of the allegedly fastest compiler (GCC) of one of the fastest ...
0
votes
2answers
555 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
0answers
30 views

how ambiguity of following grammar cant be decidable?

SO According to question grammar should be like this (A -> AA ). ->So i learn that if grammar is left and right recursive both then that grammar must be ambiguous but here the answer is deferent....
0
votes
1answer
31 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
55 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 ...
0
votes
0answers
17 views

What's the impact of polyhedral compiler techniques on downstream code-writers?

I've seen a lot of buzz and literature on polyhedral compilers recently. For a SWE or scientific computing person who uses compilers but doesn't care too much for their inner workings, what kinds of ...
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
24 views

Condition of LL(3) grammer

To find out whether a grammar G is LL(1) or not, we test this condition among other conditions, "If whenever A -> alpha | beta are two distinct productions ...
0
votes
2answers
51 views

Why some codes can be executed by creating an object file through compiler while some codes need an interpreter to be executed?

We can execute a c/cpp file by creating an object file through compilatio.But why do we need to pass java bytecodes through an interpreter to execute them?Or why we can execute python/bash files by ...
0
votes
1answer
145 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
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 : ...
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 ...
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
140 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 ...
4
votes
1answer
82 views

Can reading a value of a variable kill the definition of the variable?

I was going through the concept of reaching definitions from the red dragon book. The authors define reaching definitions as follows: Definition: We say a definition $d$ reaches a point $p$ if there ...
1
vote
2answers
99 views

Are parse trees always produced?

When my instructor taught compiler construction he explained all the phases of compiler and their working nicely. But when I read online here, at last line it is written that Parse trees are not ...
0
votes
0answers
16 views

How do I find the associativity or precedence of operators/terminals to create the Operator Precedence Table from an Operator Precedence Grammar?

The initial grammar provided to me was: S->abABC/DE A->a/epsilon B->bA/epsilon C->c D->d/(E) E->e/epsilon After converting this grammar to OPG, I get: S->abaBc/abBc/De/D A->a ...
0
votes
0answers
46 views

Why the grammar is not (LL1)?

Why the grammar is not (LL1)? (e is the epsilon) $$S \to a A \mid b B \mid a C c $$ $$A \to a A \mid a a A \mid e $$ $$B \to c C \mid D \mid e $$ CHOICE 1: The grammar is Left-Recursive (LR) CHOICE 2: ...
1
vote
2answers
192 views

What kind of binary compatibility is present for 2 processors sharing an Instruction Set?

Consider Intel x86 and AMD x86 Processors. As I understand, since they use the same Instruction Set, in theory an application compiled for Intel x86 processor would run without any modification on ...
1
vote
3answers
48 views

Variable name starting with integers

When I started doing programming I wondered that why the variable names can't start with integer. Back then I accepted that , may be this is how the compiler designers have decided to go with. But now ...
0
votes
1answer
65 views

How are lexical tokens produced

I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, ...
2
votes
1answer
38 views

Left recursive grammar to right recursive grammar

I am studying conversion from left recursive grammar to right recursive grammar. The given grammar is $$E \to E + T \mid T $$ It's equivalent right recursive grammar will be $$\begin{align}E &\to ...
2
votes
0answers
47 views

What assigns the physical addresses to variables?

Earlier I was having a technical test when I stumbled across this question: I know that probably in modern systems, the OS and the MMU is responsible for that. But the test was focused on Embedded ...
2
votes
1answer
48 views

How does software prefetching work with in order processors?

From prof. Onut Mutlu's slides on prefetching, this example has been shown as software prefetching: ...
1
vote
3answers
733 views

How is a program stored before compiling?

When we write code, after compilation the code will be converted to machine language and then stored in the hard disk. But before compiling the code, it is still in the high-level language. How and ...
0
votes
0answers
23 views

Calculating ring inequalities with fixed precision

Suppose we are given $n$ $M$-bit (the word size of the computer) integers $x_i$, and wish to calculate a linear or nonlinear inequality involving the numbers (an expression made up from the $x_i$, ...
4
votes
1answer
87 views

How compiler optimizations create irreducible control flow graph?

I've been looking through research papers and the internet and found many claims that "compiler optimizations can cause irreducible control flow". However, I was not able to find a single ...
6
votes
2answers
155 views

Does strong typing contribute to better performance optimization by compiler?

Do guarantees provided by the type systems enable better performance optimizations by the modern compilers? I found a 20+ year article suggesting that it would. Also, intuitively speaking, knowing ...
0
votes
0answers
122 views

How LR parser works with grammar containing epsilon productions

In Dragon book for compiler design there is this example of SDT in Example 5.16 $L\rightarrow En$ $E\rightarrow \{ print (' +') ; \} \space E_1 + T$ $E\rightarrow T$ $T\rightarrow \{ print (' *' ) ; ...
1
vote
2answers
237 views

How is CLR(1) grammar more powerful than LALR(1) grammar

I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
3
votes
1answer
114 views

Representing abstract syntax tree as a graph

Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code? The goal and application ...
1
vote
1answer
42 views

PDA translating $a^{m+n} b^n$ to $x^{2m+2} y^{3n}$

On my compilation theory exam we had the following problem: Construct a PDA translator (just one stack) such that it translates the language $$ a^{m+n}b^n \rightarrow x^{2m+2}y^{3n}, \text{ where } n,...
1
vote
1answer
59 views

virtual machine based programming languages vs low level

I took programming lecture it was about C/java and how to build compilers, so I wanted to know. As far I see, languages like Java/C# are developing their virtual machine CLR/JVM with good base and are ...
0
votes
1answer
69 views

What other implementation styles are there besides compilation, interpretation and transpilation?

Obviously there is JIT but it is basically run-time compilation. There is also implementing things in VHDL or ASIC. But my question is more towards software techniques for program building and ...

1
2 3 4 5
12