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
3
votes
2answers
319 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
365 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
92 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
688 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
177 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
138 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
327 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
2k views
2
votes
1answer
3k 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
395 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
120 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
146 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 ...
6
votes
2answers
9k 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
1answer
978 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 ...
2
votes
2answers
1k 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 (...
15
votes
1answer
706 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
1answer
170 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
171 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 ...
9
votes
4answers
10k 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 high-...
5
votes
1answer
356 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. ...
9
votes
3answers
10k 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 ...
4
votes
1answer
457 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 ...
13
votes
3answers
3k 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 ...
68
votes
10answers
12k 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, ...
10
votes
1answer
411 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
4answers
5k 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 ...
8
votes
3answers
5k views

Deriving the regular expression for C-style /**/ comments

I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: ...
3
votes
3answers
2k views

Understanding $\text{handle}$ in parsing problem

Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there The BNF is defined as followed: ...
22
votes
2answers
5k views

How is a JIT compiler different from an ordinary compiler?

There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or ...
20
votes
3answers
1k views

Parsing arbitrary context-free grammars, mostly short snippets

I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, ...

1
8 9 10 11
12