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
1 vote
1 answer
61 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
34 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
49 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
54 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
33 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
47 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
44 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
66 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
123 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
82 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
1 vote
1 answer
83 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
28 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,209
1 vote
0 answers
32 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
39 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
51 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,209
2 votes
1 answer
51 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,209
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
57 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
48 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
24 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
81 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
144 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
30 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
63 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
344 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
111 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
36 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 was : $S\rightarrow abABC|DE$ $A\rightarrow a | \varepsilon$ $B\rightarrow bA|\varepsilon$ $C\rightarrow c$ $D\rightarrow d|(E)$ $E\rightarrow e|\varepsilon$ After ...
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
257 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
55 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
84 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
362 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
163 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
63 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
122 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
419 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
  • 261
2 votes
2 answers
576 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
  • 261
1 vote
1 answer
54 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,...
user avatar
1 vote
1 answer
69 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 ...
user avatar
  • 199
3 votes
1 answer
200 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 ...
user avatar
  • 131
0 votes
1 answer
75 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 ...
user avatar
1 vote
0 answers
15 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
user avatar

1
2 3 4 5
12