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
1answer
45 views

Tools for modelling compilers

I'm a wannabe mathematician, whose master's thesis is (by the looks of it) going to focus on a certain "compiler", used to produce learning materials from a subset of $\LaTeX$, in the context of ...
1
vote
1answer
189 views

When and how to generate parse tree while top down parsing

I am trying to build a parser that will eventually output a 3 address code. My question is, how do I build the parser to go from parsing in a table driven top down parsing to then give me a parse ...
1
vote
1answer
35 views

Calculating LL(1) grammar

I am trying to calculate the First and Follow of the following grammar S->ABC A->Aa A->aB B->Bb B-> epsilon C-> Cc C-> Epsilon I have ...
1
vote
1answer
33 views

On which stage (lexical analysis, syntax analysys, and so on) is most of the compilation time spent?

I know that during compilation we need to undergo several stages like lexical analysis, syntax analysis and so on. Which of them takes the most time?
1
vote
2answers
5k views

What is the use of First() and Follow() in compiler design?

I am completely aware of how to calculate first and follow, my professor has taught me that well , but he had not explained what is the need of First() and Follow(), so any explanation why we need ...
1
vote
1answer
219 views

Unambiguousness and determinism of CFGs for them to be LR

I came across this statement: Note that there are unambiguous grammars for which every LR parser construction method will produce a parsing action table with parsing action conflicts. I was ...
1
vote
1answer
338 views

context-free grammar for comma-separated list with comments

I'm trying to write a context-free grammar for a comma-separated list of statements with comments. It is trivial if the comma appears at the end of a statement. It is trivial if the comment is ...
1
vote
1answer
406 views

Implementing a symbol table with a hash table and a stack

I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different ...
1
vote
1answer
513 views

LR parsers and ambiguous and non deterministic grammars

Dragon book says: An ambiguous grammar can never be LR. And then immediately further it says: For example, consider the dangling-else grammar: $\begin{align} stmt \rightarrow & \textbf{...
1
vote
1answer
20 views

Choosing correct action in bottom up parsing

Using grammar: $ S \to aABe \\ A \to bcA \mid c \\ B \to b $ to bottom parse a string $abcccde$, the course of action would be: $ \begin{array}{c|c|c|c} \hline Step & Stack & Input &...
1
vote
1answer
133 views

Can the compiler convert recursive algorithm into a dynamic programming

So I was going through the idea behind dynamic programming (memoization), and thought of this question. Can a compiler convert any recursion into a table filling DP solution, of course given the ...
1
vote
1answer
116 views

Are space allocated to C/C++ variables in secondary storage also in Compiled file?

Are data segments,heap,stack etc also present in secondary memory with compiled code then later mapped by OS to RAM when I open it?
1
vote
1answer
186 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
1
vote
1answer
294 views

High Level Assemblers vs Compilers?

I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful ...
1
vote
1answer
131 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
1
vote
2answers
167 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
1
vote
1answer
43 views

Follow set confusion about inclusion

The book I am learning about compilers from states that $M \to \alpha N \beta$ will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable. This ...
1
vote
1answer
1k views

Lexical analysis and reserved words

My book says lexical analysis detects reserved words. How can lexical analysis detect whether we are using reserved words in incorrect places ? For eg :- while(a>0) and int while = 5. How can ...
1
vote
1answer
512 views

Lexical analysis [closed]

Will the below statement cause any lexical error ? int a123c ; According to me, int would be tokenized as a keyword and there would be a lexical error when "...
1
vote
1answer
91 views

I'm looking for a construct that is to semantic-analysis what NFA/DFA are to scanning and DPDA is to parsing

What maps to Semantic Analysis the way automata like Finite State Machines and Pushdown automatons map to Lexing and Parsing? A couple of years ago I came across a paper that presented such a ...
1
vote
1answer
47 views

Box representation in modern languages

I'm studying value representation in modern languages. The idea is that since in many situations the size of objects can be unknown, one can introduce a box representation of it. This box ...
1
vote
1answer
232 views

how to create tokens from CFG

i have a context free grammar i want to create a tokens from the language is there any techniques to do that ? for example , this CFG from Prof.Alex Aiken notes : ...
1
vote
1answer
78 views

Implementing Do keyword in a compiler

I'm writting a compiler implementation for a language that you can see defined here. I having problems designing how the do keyword should be handled. You can find the code I'm referring to in here. ...
1
vote
1answer
2k views

Converting Regular expression to DFA by building syntax tree

There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition ...
1
vote
1answer
1k views

Computing FIRST and FOLLOW sets

Suppose we have the following grammar: S -> A ( S ) B | ε A -> S | S B | x | ε B -> S B | y where S is the start ...
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 ...
1
vote
1answer
322 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 ...
1
vote
1answer
83 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 ...
1
vote
2answers
686 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
175 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 ?
1
vote
0answers
22 views

Condition of LL(3) grammer

To find out whether a grammar G is LL(1) or not, we test this condition among other conditions, "If whenever A -> alpha | beta are two distinct productions ...
1
vote
0answers
12 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
1
vote
0answers
38 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
1
vote
0answers
37 views

Understanding the concept of "Viable Prefixes"

I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I ...
1
vote
0answers
19 views

Compile XPath Abbreviated Query to Unabbreviated version

The Xpath 3.1 presented by W3C includes the full grammar of the language with both abbreviated and unabbreviated syntax. I am interested in references (if any) for any formal work done to compile/...
1
vote
0answers
74 views

Help me to make sure, that I got defunctionalized continuations right

I am reading this Defunctionalization at work paper. So, in order to ascertain that I got it right, I request a little code review. I'll start with a recursive definition of a factorial function and ...
1
vote
1answer
92 views

How do you create a sentential form in a given grammar?

I am given the following grammar: $$S ::= aBS| abT |a$$ $$T::= d | dT$$$$B ::= da | ϵ | S$$ I need to decide whether $aBaabda$ can be produced in the given grammar. I am unsure how the grammar can ...
1
vote
0answers
24 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
1
vote
0answers
43 views

Is there a way to simplify redundant conditionals?

For example if I've this: if a == false then return true else if a == true and b == false return true else if a == true and b == true then return false can be ...
1
vote
1answer
377 views

Why is the following grammar not LL(1)

Consider the following grammar: S → bAb | bBa A → aS | CB B → b | Bc C → c | cC I have to provide the reasons as to why this grammar is not LL(1). So far ...
1
vote
2answers
59 views

Can Yacc be used to generate three address code for Java 1?

I have read that yacc generates bottom up parser for LALR(1) grammars. I have a grammar for Java 1 that can be used for generating three address code and is strictly LALR(1), but the translation ...
1
vote
0answers
82 views

How to translate boolean expressions to three address code?

There are two uses of a boolean expression in a language like C, one as a condition in flow of control statements and the other as boolean value in assignment and arithmetic expressions. I was ...
1
vote
0answers
23 views

Is Constant Folding a type of Memoization?

I was reading about Constant Folding and it sounds very similar to Memoization so I suspect that it indeed is a type of memoization but I've done some searching and can't find a solid answer (in ...
1
vote
2answers
145 views

Run-Time environments

I was reading about Run-Time Environments. In the Dragon book (2nd ed.) I came across the following presentation: [To implement abstractions, the] compiler ...
1
vote
0answers
153 views

Does a simple calculator have compilers?

When I input something wrong in my Casio fx-82MS calculator it shows Syntax error on its screen. So does even a simple calculation on a most simple calculator like this goes through compilation ...
1
vote
0answers
30 views

Using DPDA instead of LR parsers

If LR parsers handle only DCFLs than why we don't just use dpda to parse these languages? What are advantages of using LR parsers over DPDA? Is it that it is easy to built autonomously or something ...
1
vote
0answers
61 views

Compiler implement power method with syntax graph

We learn how to write compiler. I know that we can use grammar to construct a parser for compiler or otherwise use a syntax graph to represent grammar and generate code when move on it's node. our ...
1
vote
0answers
42 views

Design considerations of datatypes in early programming languages like C

Although type theory originated (e.g. already discussed by Russell in 1910s) much earlier than programming languages, I have this feeling that languages such as C considered type-checking from a very ...
1
vote
0answers
26 views

Are there any algorithms for extracting functions from expressions?

Suppose you have an expression like this: sqrt(x) * 6 + sqrt(x + 1) * 6 + sqrt(x + 2) * 6 Are there any well-known or published algorithms that can find the ...
1
vote
1answer
54 views

Add type checking/inference to my programming language

I am currently creating my own compiled programming language, and I have come to a point where I would like to start working on the type system and introduce some type checking. Ideally I would like ...

1
6 7
8
9 10
12