Questions about programs that read code in one language (source language) and translate it into an equivalent program in another language (target language).
2
votes
1answer
25 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 ...
4
votes
2answers
75 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" ...
0
votes
3answers
93 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
78 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
118 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 ...
3
votes
2answers
201 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
85 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
27 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 ...
3
votes
3answers
96 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
69 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
111 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 ...
6
votes
1answer
129 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
64 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
28 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 ...
2
votes
1answer
107 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 ...
2
votes
0answers
24 views
How to explain rehosting and retargeting with T-diagramms?
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 ...
6
votes
2answers
99 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 ...
3
votes
3answers
245 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 ...
1
vote
1answer
48 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
90 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 ...
2
votes
2answers
209 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\ |\ ...
1
vote
0answers
90 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
69 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 ...
3
votes
1answer
121 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 ...
7
votes
2answers
228 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
124 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 ...
0
votes
1answer
46 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
57 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 ...
5
votes
1answer
93 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:
...
5
votes
3answers
234 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
161 views
2
votes
1answer
76 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, ...
6
votes
1answer
115 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. ...
0
votes
1answer
97 views
What are current approaches to auto-parallelisation?
I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.
5
votes
1answer
68 views
Dataflow framework for global analysis: Why meet, then apply?
In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides). In this framework, an analysis is defined by a set of transfer ...
3
votes
1answer
201 views
Cost in time of constructing and running an NFA vs DFA for a given regex
Repost from Stack Overflow:
I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated.
The ...
3
votes
0answers
152 views
is there a compiler from high level language to Turing machine? [closed]
For many years I have looked for a compiler that converts an arbitrary program written in a high-level/human-readable programming language (binary variables, arrays, strings, subroutines, loops, ...
3
votes
1answer
62 views
How to call something that can be either a terminal or a nonterminal?
I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C.
I came across a terminology problem however that I remember in the past I couldn't ...
1
vote
2answers
232 views
How to implement deep copy?
Is there any scientific work about deep copying? So far I have only found source codes (Java, Python, ...). However, there are various approaches and nobody seems to evaluate them.
Reflection-based ...
10
votes
1answer
188 views
Type inference with product types
I’m working on a compiler for a concatenative language and would like to add type inference support. I understand Hindley–Milner, but I’ve been learning the type theory as I go, so I’m unsure of how ...
1
vote
0answers
60 views
Where should we place action symbols in a grammar?
In the following grammar that is used for math expressions(and other grammars) how do I know where should I place action symbols(@add, @mul, @pushID)? Is there a algorithm for it?
E -> TE`
E'-> +T ...
6
votes
1answer
123 views
Efficient subtype testing
Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to ...
4
votes
3answers
707 views
A faster, leaner JavaScript for scientific computing: what features should I keep?
Here I'm really interested in lowering barriers to mathematical education.
Target:
I'd like to see created for the JavaScript community, an equivalent of the Python-based/linked scientific and ...
5
votes
1answer
136 views
Frame Pointers in Assembler
I am currently learning assembly programming on wombat 4, I am looking at Frame pointers. I understand exactly what a frame pointer is: it is a register and are used to access parameters on a stack. ...
5
votes
3answers
391 views
Cross Compiler's T diagram
I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone ...
3
votes
1answer
207 views
From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?
There is this question I read somewhere but could not answer myself.
Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a ...
6
votes
3answers
399 views
Why is using a lexer/parser on binary data so wrong?
I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
26
votes
8answers
2k views
Can a dynamic language like Ruby/Python reach C/C++ like performance?
I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, ...
7
votes
1answer
251 views
Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?
Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$.
Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where ...
5
votes
3answers
268 views
A DFA for recognizing comments
The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with ...
