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
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
82 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
107 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
228 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
246 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
174 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
299 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
696 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
762 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
713 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
5k 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
81 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
959 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
278 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
138 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
289 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
29k 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
306 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
357 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
120 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 ...
13
votes
2answers
5k views

Is there any way to distinguish between LL(k) and LR(k) grammar?

I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar. We also know the facts that every LL grammar is LR that is LL ...
1
vote
2answers
677 views

Can an LL(k) parser parse any grammar without left recursion or common prefixes?

I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can parse)...
1
vote
1answer
173 views

Using Loop Dependence analysis for vectorization

How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?
2
votes
1answer
135 views

Benefit of Backward Pass at compile time

We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform ...
7
votes
3answers
313 views

Are compilers able to detect alternating accesses to arrays and interleave them in memory?

Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this: ...
7
votes
6answers
3k views

Can all languages have semantic and logical errors?

I have been reading about PHP and many authors mention semantic and logical errors separately. As an example of a semantic error, they give a function called with incorrect number of parameters: this ...
2
votes
1answer
1k views
2
votes
1answer
2k views

What is a malformed token?

I am reading Programming Language Pragmatics by Michael Scott. He says that on a first pass, a compiler will break a program into a series of tokens. He says that it will check for malformed tokens, ...
7
votes
1answer
394 views

Can abstract syntax trees be unparsed in subexponential time?

Abstract problem description The way I see it, unparsing means to create a token stream from an AST, which when parsed again produces an equal AST, i.e. ...

1
8 9 10
11
12