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
3answers
146 views

What do assemblers translate macros into during assembling? [closed]

I have dug in simple binaries, such as though like x86 bootloaders, sega video game binaries, etc. I know that these files tend to use assembler macros to define data, etc. What I am having trouble ...
0
votes
1answer
682 views

Is this grammar LL(1)?

Consider following grammar: $$X\to Yc|ZY$$ $$Y\to ab|cX$$ $$Z\to d|\epsilon$$ Can this be converted to LL(1)? Cleary, its not LL(1) because of First/First conflict at first production. Can anyone ...
4
votes
1answer
455 views

Indentation based Grammars

Considering programming languages with significant whitespace for indentation, such as Python or Haskell. How does this whitespace fit into the grand schemes of programming language grammars. I can ...
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] ...
1
vote
1answer
5k views

Is this grammar LR(1)

I am reading parser chapter from dragon book and I found a grammar over there - $ S \rightarrow L=R $ $ S \rightarrow R $ $L \rightarrow *R $ $L \rightarrow id $ $R \rightarrow L $ Now I have ...
0
votes
1answer
429 views

Eliminating $\varepsilon$-productions during elimination of left recursion

I'm following the algorithm for left recursion elimination from a grammar. It says remove the epsilon production if there is any. I have the grammar $\qquad S \to Aa \mid b$ $\qquad A \to Ac \mid Sd ...
1
vote
1answer
46 views

Has there been a lexer that takes in much more than a regular language?

I understand the restrictions, because a regular language is expressive enough to allow all types of tokens. And even if some context is needed in many languages to tokenize properly, they all seem to ...
0
votes
1answer
880 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
3
votes
3answers
1k views

Confusion about compiler and assembler

I have two questions. After compilation of any C program result is assembly language code which should depend on processor. So my question is: how do different computers with different processor ...
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 ...
1
vote
0answers
83 views

what does “Configuration is valid for a viable prefix ” actually means?

I am learning LR(1) parsing from the Dragon Book. I am really confused with this sentence. Formally we say that a configuration $[A \to u•v, a]$ is valid for a viable prefix $α$ if there is a ...
4
votes
4answers
3k views

What information do we get from a compiler's parse tree?

In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars, the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of ...
3
votes
1answer
52 views

Say that a stack frame only contains total functions: could the maximum stack size be statically determined?

Say that you have a program with only total functions, or if that is impossible, consider a subset of the program with only total functions. Is it theoretically possible to statically determine the ...
7
votes
1answer
1k views

Is the Syntax of C Language completely defined by CFGs?

I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions ...
10
votes
2answers
8k views

Compile a programming language with itself

I'm a computer science student. I want to create my own programming language (A basic language with few instructions). I know how to do a syntactic analyser, I already did it in Perl. In an article, ...
4
votes
1answer
108 views

Compiler backend generated from declarative description of the architecture

Is it possible, given a declarative description of an architecture's register layout and instruction semantics and machine code encodings, to autogenerate a compiler back-end? If so, has anyone ever ...
5
votes
2answers
230 views

How are the web based compilers designed? [closed]

Is it possible to design a compiler that can safely compile and run untrusted code? As a practical example, I want to know how the online compilers are designed/programmed?(Like the one on codepad....
19
votes
6answers
10k views

Why do compilers produce assembly code?

Assembly language is converted in to machine language by assembler. Why would a compiler convert high-level language to assembly? Can't it directly convert from the high-level language to machine code?...
1
vote
1answer
313 views

Pros and cons of representing strings as lists of characters

I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma". Maybe some more experienced compiler programmer ...
3
votes
2answers
6k views

What is the job of Syntax Analyzer in a compiler?

What exactly is the job of a syntax analyzer? Suppose I have a mathematical expression. Is it true that the order of execution of the operations is found with the help of syntax analyzer? Any ...
1
vote
2answers
103 views

Trying to understand a token file for lexical analysis

I am reading this article about compiler. I am facing some problem in understanding the content of the token file. Specifically, what is the meaning of the following lines: ...
17
votes
3answers
24k views

Is there any real difference between a compiler and an assembler?

Is there any difference between the two? As per Ullman's book, compilers convert one language to another (usually low level) language, and so does an assembler. How are the two different?
5
votes
2answers
177 views

In general terms, how could the Thompson Hack be implemented in Microcode?

In his lecture Reflections on Trusting Trust, Ken Thompson describes a virus that infects a compiler; the infected compiler installs backdoors into programs, but the key part is that the infected ...
1
vote
1answer
302 views

Getting started with Compiler Design [closed]

This is the first time I will be studying compilers in depth. Can someone point me to best online resources (courses, articles, tutorials, video etc ) and books? My main aim will be to do some ...
2
votes
1answer
700 views

Difference between symbolic execution and reachability analysis

Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find ...
20
votes
1answer
1k views

Do fully optimizing compilers for terminating programs exist?

In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and ...
17
votes
6answers
2k views

Does an abstract syntax tree have to be a tree?

Does the output of a parser have to be a tree or could it also be general graph? Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees ...
2
votes
1answer
55 views

What is the name of the optimization that removes self eliminating multiplication-division statements?

I have a compiler optimization which should be quite common, but I can not find a name for it, nor a reference that describes it. Given an integer x, not known at optimization time, a known constant ...
11
votes
3answers
787 views

Getting started with Program Analysis

I'm looking for resources on getting started with program analysis. The only book I've found on the topic is the Nielson & Nielson book. Other than that, it seems like there are only "compiler" ...
11
votes
1answer
718 views

The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

In a comment to Learning F#: What books using other programming languages can be translated to F# to learn functional concepts? Makarius stated: Note that the "CPS" approach has done great harm to ...
13
votes
3answers
1k views

How does 'deforestation' remove 'trees' from a program?

I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the ...
22
votes
4answers
17k views

Why is left recursion bad?

In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?
3
votes
2answers
6k views

How does interpreting a script work?

Suppose I have a script (.vbs, for example) that is stored in a file. How does the code in the file get converted into machine instructions? What is between the ...
1
vote
1answer
82 views

Time complexity for modular arithmatic

I read about the time complexity for modular arithmetic in many books. There is one thing that I don't understand. I read in some books the following: For any $a \mod N$, $a$ has a multiplicative ...
7
votes
4answers
1k views

Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
8
votes
1answer
6k views

Quality LISP/Scheme compilers to compete with C/C++

Theoretically speaking, is it possible to have a Lisp/Scheme compiler that can produce code that can compete with compiled C, let's say within 15-25% margin? In my testing, I've found that the ...
4
votes
3answers
962 views

How can SML infer types like this?

Wikipedia says: fun factorial n = if n = 0 then 1 else n * factorial (n-1) A Standard ML compiler is required to infer the static type int -> int of this ...
11
votes
2answers
2k views

Theoretical minimum number of registers for a modern computer?

I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an ...
4
votes
1answer
281 views

Type inference in compiler is context sensitive?

Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler ...
0
votes
1answer
139 views

How Does Dynamic Heap Storage Have Something to Do with Heap?

There are three typical ways to allocate memory for programs: static, stack and dynamic heap. However, when I look at the implementation of dynamic heap memory allocation from wikipedia , what I found ...
5
votes
1answer
13k views

What are handles in parsing?

I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given. For example, one document said - "the essence of LR parsing is ...
3
votes
2answers
2k views

How to explain rehosting and retargeting with T-diagrams?

I'm currently learning for an exam about compilers and found the following question: (3 p.) Bootstrapping: Explain the concepts of rehosting and retargeting. Use T-diagrams. As far as I understand,...
7
votes
2answers
293 views

Are monoids useful in optimization?

Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example). There is ...
12
votes
3answers
31k views

How is this grammar LL(1)?

This is a question from the Dragon Book. This is the grammar: $S \to AaAb \mid BbBa $ $A \to \varepsilon$ $B \to \varepsilon$ The question asks how to show that it is LL(1) but not SLR(1). ...
3
votes
2answers
311 views

How to modify semantic actions when removing left-recursion from a grammer

Is there any algorithm that tells us how to modify semantic actions associated with a left-recursive grammar? For example, we have the following grammar, and its associated semantic actions: $ S \...
1
vote
2answers
364 views

Some questions regarding compilers and assemblers

Lots of basic questions are there in my mind. I need to clear them. Statement 1: A compiler converts a human-readable codes to object codes, and those are converted to a machine code (executable) by ...
3
votes
2answers
2k views

Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

I am having difficulty with one of the exercises in the Dragon Book: Exercise 2.4.1(c): Construct recursive-descent parsers, starting with the following grammars: $$S \rightarrow 0S1\ |\ 01$$...
1
vote
0answers
121 views

Is it possible to analyse computation?

Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation. So you have a ...
4
votes
1answer
91 views

Instruction Translation

Imagine two machines of different architecture which produce output of a standard format. If you have a program for one machine and can observe it's operation and output, what techniques exist to ...
5
votes
1answer
7k views

Program compilation and execution flow

I was studying operating system concepts from Silberschatz, Galvin and Gagne's book (sixth edition) and I have some questions about the flow of execution of a program. A figure explains the processing ...

1
8 9 10
11
12