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

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
user avatar
0 votes
0 answers
16 views

What is an example of some production rules which would allow parentheses, curly braces, and square-brackets to be interchangeable?

In computer programming, there are many different ways to write a for-loop. Some examples are shown below: ...
user avatar
1 vote
0 answers
27 views

Getting something wrong while building parse table for the grammar

Task Build the Parse Table Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\...
user avatar
0 votes
0 answers
14 views

Canonicalizing Arbitrary EBNF Expressions

From what I understand, LL and LR parsing require a grammar to be in "canonical form", i.e. only productions of the form A -> b1 b2 ... bn, where ...
user avatar
0 votes
5 answers
1k views

Could a compiler automatically insert memory deallocations if it were to simulate every conditional statement?

I have read this question on compile time gc and what I understand from it is that the compiler wouldn't know if a variable is referenced or not by some other object due to conditional statements (...
user avatar
0 votes
0 answers
22 views

Good resources on polyhedral compilation

I'm looking for good introductory resources (books, articles, notes, websites, videos, e.t.c.) on polyhedral compilation. I'm especially interested in applications related to deep learning / GPU ...
user avatar
1 vote
1 answer
72 views

How is the lookahead for an LR(1) automaton computed?

I'm reading Douglas Thain's book called "Introduction to Compilers and Language Design" and I've come across the following grammar: , with the following LR(1) automaton: , and I am not ...
user avatar
-1 votes
1 answer
42 views

What is the time complexity of SLR and LALR parsers?

What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)? How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) ...
user avatar
0 votes
1 answer
51 views

find LR(1) items of the first state

I need to calculate the LR(1) items of the following grammar: S -> E E -> E + T E -> T T -> ID T -> ( E ) I can not even calculate the first group {[...
user avatar
  • 3
1 vote
2 answers
55 views

Questions about compilers and machine code

When it is said that machine code is specific to a machine, is it specific to an architecture, or is it specific to a machine? Do two identical processors require different machine code? My guess is ...
user avatar
1 vote
1 answer
36 views

How does JIT compilation and hot-swapping work at the level of individual procedures?

I am trying to understand the lifetime of a procedure, from source code through to being compiled to machine code and being called. I am specifically interested in the context of "live" ...
user avatar
0 votes
1 answer
57 views

How would my parsing functions look for this grammar?

Suppose we have the grammar $$S \to aA | BA $$ $$A \to a | bB | \epsilon $$ $$ B \to cB | d$$ I know that I need to write four different functions in order to parse this grammar. They are ...
user avatar
  • 3
-1 votes
1 answer
30 views

Lexical analysis on a series of tokens given regexes

I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct. ...
user avatar
  • 1
3 votes
1 answer
40 views

What is a program analysis technique for tracing assignments (mutations)?

I am looking to write a program analysis for Java programs that tracks assignments and is able to discern: whether a class field (static or not) is read and where the read originated whether a class ...
user avatar
0 votes
1 answer
50 views

Calculate post dominator with non exiting control flow

Using the basic algorithm to calculate post dominators I run into trouble when working with a CFG containing an infinite loop (i.e., not terminating). The algorithm: ...
user avatar
  • 561
0 votes
1 answer
17 views

Computing Earley Parsing Steps

I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$: \begin{align*} Z & \to S\\ S & \to a\,|\,b\,|\,c\,|\...
user avatar
  • 163
1 vote
1 answer
73 views

If Interpreters are used to run code and are written in another language, won't interpreters need interpreters?

As I was going through my online lectures, it is stated that python is interpreted with Cpython, a software written in C. Similarly, they have Jython (written in Java) and PyPy (written in Python). My ...
user avatar
0 votes
1 answer
140 views

Remove left recursion from a grammar without necessarily removing epsilon production

Consider the grammar $$S →Aa∣b$$ $$A →Ac∣Sd∣ϵ$$ Construct an equivalent grammar with no left recursion and with minimum number of production rules. $\tag {GATE-CS-1998}$ While solving this question, ...
user avatar
0 votes
1 answer
92 views

Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true. Given a grammar $G$, If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$. ...
user avatar
2 votes
1 answer
89 views

Why can't a LR(0) parser have GOTO and Reduce Items in the same canonical set?

I am talking in reference to this question from this compiler test. I think it is actually true that a GOTO and REDUCE can't be present in the same set, but am having a hard time coming up with an ...
user avatar
0 votes
1 answer
31 views

Questions about the Param and Call instructions of three-address code

Section 6.2.1 of the book "Compilers: Principles, Techniques, and Tools" describes three-address code. Specifically, Procedure calls and returns are implemented using the following ...
user avatar
  • 9,219
1 vote
0 answers
39 views

How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?

I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
user avatar
0 votes
1 answer
44 views

Merging states in LALR parser

I was learning LALR parsers from the dragon book (Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman) and I came across the example on page ...
user avatar
0 votes
0 answers
60 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 "...
user avatar
  • 9,219
2 votes
1 answer
53 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)), .... ...
user avatar
  • 9,219
0 votes
0 answers
20 views

Is arithmetic/constants code optimization a function of the Language/Compiler/CPU/ALU/OS and what languages implement such features in itself?

Take the following case ...
user avatar
2 votes
1 answer
60 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 ...
user avatar
  • 19
0 votes
0 answers
49 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 ...
user avatar
  • 113
2 votes
0 answers
19 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/...
user avatar
  • 41
0 votes
0 answers
25 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 ...
user avatar
0 votes
1 answer
32 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 ...
user avatar
0 votes
0 answers
31 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....
user avatar
0 votes
1 answer
87 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 ...
user avatar
  • 147
20 votes
9 answers
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 ...
user avatar
1 vote
1 answer
149 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 ...
user avatar
0 votes
0 answers
19 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 ...
user avatar
1 vote
0 answers
31 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 ...
user avatar
0 votes
2 answers
64 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 ...
user avatar
0 votes
1 answer
365 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 ...
user avatar
1 vote
2 answers
115 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 ...
user avatar
0 votes
0 answers
48 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: ...
user avatar
1 vote
2 answers
267 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 ...
user avatar
1 vote
3 answers
56 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 ...
user avatar
0 votes
1 answer
89 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, ...
user avatar
2 votes
1 answer
439 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 ...
user avatar
2 votes
0 answers
532 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 ...
user avatar
2 votes
1 answer
66 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: ...
user avatar
4 votes
1 answer
135 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 ...
user avatar
  • 41
0 votes
0 answers
476 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 (' *' ) ; ...
user avatar
  • 271
2 votes
2 answers
611 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 ...
user avatar
  • 271

1
2 3 4 5
13