Questions about programs that read code in one language (source language) and translate it into an equivalent program in another language (target language).

learn more… | top users | synonyms

0
votes
2answers
95 views

How does an operating system implement the C library?

I have an idea of how a C program is turned into machine code by the compiler. I also know how the processor processes the instructions (https://www.youtube.com/watch?v=cNN_tTXABUA this video has a ...
1
vote
1answer
34 views

Why does left recursion have to be eliminated? [closed]

For example, Let the Grammar be: S->Sa|B Thus, S->Sa->Saa->...->Saa...aaa->Baa...aaa What's wrong with ...
4
votes
1answer
51 views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
4
votes
2answers
41 views

Does the OS create its own bootstrapped stack frame when running a program?

I've been doing nand2tetris exercises and I'm quite interested in how compilation actually works. In nand2tetris when creating the VM language I had to create a "bootstrap" which called the main ...
32
votes
5answers
2k views

Time complexity of a compiler

I am interested in the time complexity of a compiler. Clearly this is a very complicated question as there are many compilers, compiler options and variables to consider. Specifically, I am interested ...
3
votes
2answers
74 views

Mathematical background for programming languages, compilers and formal methods in software engineering [closed]

Can you tell me what mathematical background (concrete themes) should I have for studying and doing some investigations (in future) in programming languages, compilers and formal methods in software ...
1
vote
1answer
105 views

When do type systems start needing a logic engine?

I've noticed that some languages include a logic engine as part of their type system (e.g. Shen, Typed Clojure). Other languages have a much more direct type checking algorithm (e.g. Haskell / ...
0
votes
3answers
74 views

What data is stored in the symbol table for a number token?

I'm reading the Dragon Book. The following is from the start of Section 3.1.3. When more than one lexeme can match a pattern, the lexical analyzer must provide the subsequent compiler phases ...
0
votes
2answers
48 views

Which Type of Grammar is this?

I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the ...
1
vote
3answers
32 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
60 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 ...
1
vote
1answer
27 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
153 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
92 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 ...
1
vote
1answer
34 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
33 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
47 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
2
votes
1answer
93 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
3answers
51 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
46 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 ...
2
votes
4answers
316 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
41 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 ...
4
votes
1answer
93 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 ...
2
votes
3answers
265 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, ...
3
votes
1answer
42 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 ...
4
votes
2answers
86 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 ...
5
votes
3answers
310 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 ...
1
vote
1answer
105 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
152 views

What is the job of Syntax Analyzer in 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
66 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: ...
6
votes
2answers
909 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
103 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
120 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 ...
1
vote
1answer
54 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 ...
10
votes
1answer
180 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 ...
7
votes
5answers
307 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
37 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 ...
5
votes
2answers
146 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" ...
-1
votes
3answers
166 views

Top Turing machine simulators on the web? [closed]

There are many Turing machine simulators on the web of varying degrees of sophistication and can be highly useful for pedagogical purposes for students of widely varying ages, and they also have ...
7
votes
1answer
154 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 ...
5
votes
3answers
220 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 ...
6
votes
2answers
1k 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?
1
vote
3answers
301 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
43 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 ...
4
votes
4answers
198 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 ...
1
vote
0answers
250 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 ...
5
votes
3answers
250 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 ...
8
votes
2answers
439 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
101 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
57 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 ...