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

Which parser has the highest reduce moves?

From what I have learned the number of reducing moves in the parsers are generally in the order LR(0)>= SLR(1) >= LALR(1). But I am unable to understand where should I place CLR(1) in this ...
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 ...
2
votes
1answer
2k views

What is the Purpose of Augmented Grammar in LR parsers?

I was reading the LR() parsers from the Dragon Book where I came across these lines: To construct canonical LR(0) collection for a grammar, we define an augmented grammar and 2 functions, CLOSURE ...
2
votes
1answer
219 views

Computing epsilon-closure. What does $E(n) \leftarrow \{n\};$ and $E(p)$ mean?

I'm currently reading "Engineering a Compiler" book. In the chapter that explanes computing epsilon-closure there is listed the following algorithm: But I couldn't understand what does $E(n)$ and $E(...
8
votes
1answer
539 views

Representation of the concatenation at the type level

I would like to learn more about concatenative programming through the creation of a small simple language, based on the stack and following the concatenative paradigm. Unfortunately, I haven't found ...
0
votes
1answer
834 views

Why is left recursion and left factoring no problem in bottom up parsing?

i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced. But why is this then a problem ...
2
votes
1answer
66 views

Table-driven lexers in Engineering a Compiler 2nd Edition

Recently, I am reading Engineering a Compiler 2nd Edition. But I am struggling to understand the following pseudocode. Can anyone help me to explain the pseudocode in a simple and plain English? ...
5
votes
1answer
51 views

Explain auto continue passing style transformations

Recently I saw 3 cps transformation rules, but no explanations were given. expressions: $e :=x\left|e e^{\prime}\right| \lambda x \cdot e$ rules: $$ \begin{array}{l}{[[x]]=\lambda \kappa \cdot \...
-1
votes
1answer
930 views

What is the time complexity of LR parsers?

Bottom up parsers in worst case take O($n^3$) time, and i believe that LR parser being a bottom up parser should also take O($n^3$) time, but i read on wiki that they are able to solve problems in ...
2
votes
0answers
31 views

What is the logic behind seperating Shift moves/reduce moves and Goto moves in parsing table?

In the parsing tables of SLR(0), LALR(1) and LR(1) I have seen that shift moves and reduce moves have separate columns from Go-to Moves. What is the logic behind this?
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 ...
0
votes
2answers
55 views

Doubt on Token in Compiler Design

Say i have code snippet like --> m -= n; is minus and assignment considered as a single token or they will be considered as different token? So the total token count will be 4 or 5?
1
vote
1answer
643 views

Can CYK Parsing algorithm generate the parsing tree in O(n^3)?

I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
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?
0
votes
1answer
31 views

Is scanner and Lexical analyzer same?

Today I read that The scanner is a subroutine which is frequently called by an application program like a compiler. The primary function of a scanner is to combine characters from the input ...
0
votes
2answers
1k views

Is this a syntax error or a semantic error?

I came across the following question The error in the expression " if x>y x=2; " is detected by a. Syntax analyzer b. Lexical analyzer c. semantic analyzer I know that the parentheses ...
0
votes
0answers
28 views

Is $LR(k) \subset SLR(k+1)$ for $k=1,2,...$? [duplicate]

I know that: Point 1: Set of languages accepted by $LR(0)$ parsers $\subset$ Set of languages accepted by $SLR(1)$ parsers Does this logic hold for higher $k$'s? That is, does following fact hold?...
2
votes
0answers
199 views

Does SLR(0), LALR(0) exists?

I read about LL(1), LR(0), SLR(1) and LALR(1) in many online sources and even in dragon book. However I found that no one talks about LL(0), SLR(0) and LALR(0). So I googled and come up against these ...
0
votes
2answers
448 views

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power. Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),...
0
votes
1answer
177 views

How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?

I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt: When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
1
vote
2answers
58 views

Compiler - Why is the grammar not suitable for shift-reduce

Consider this example: stmt => if (expr) stmt | if (expr) stmt else stmt | other Why can't we use shift-reduce on this? This is a compiler homework and I ...
1
vote
1answer
161 views

Are all compilers Turing Machines?

So the definition of a compiler I got is that: A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No". So does that mean all compilers ...
0
votes
0answers
40 views

Choosing algorithms and/or data structures at runtime based on input characteristics

I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
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
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 ...
31
votes
6answers
8k views

Why are ambiguous grammars bad?

I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
1
vote
1answer
225 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 ...
3
votes
1answer
443 views

Connection between non determinism and LL(1) conflicts

I am trying to understand connection between non determinism of grammar and LL(1) conflicts introduced by it. As per my understanding non deterministic context free grammar is a context free grammar ...
0
votes
0answers
81 views

How to collect free/bound variables in Lambda Calculus?

I am building a simple interpreter for untyped lambda calculus, currently trying to implement alpha-reduction. According to this document on LC: Alpha-reduction is used to modify expressions of ...
3
votes
2answers
125 views

How does a compiler infer a value's type?

From A Swift Tour — The Swift Programming Language (Swift 5): var myVariable = 42 myVariable = 50 let myConstant = 42 A constant or variable must have the same ...
2
votes
1answer
1k views

When will SLR(1) parser fail but CLR(1) will not

Dragon book says following about where SLR(1) parser can fail but CLR(1) wont: Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$...
1
vote
1answer
351 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
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 ...
2
votes
1answer
2k views

In what sense a type of parser is less power than the other?

I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x < y means parser x is less "powerful" that parser y, then, I read, the ...
6
votes
3answers
3k views

Why anyone learn compiler? [closed]

I am learning compiler in my Uni. I have been through all major compiler techniques like top-down parsing, bottom-up parsing, Lexical analyzer, Symbol table, etc. I have a good understanding of them, ...
8
votes
2answers
2k views

Assembly writer vs compiler in VLIW architecture

I read this sentence in a book: In VLIW architecture, the compiler/and or assembly writer chooses instructions that can be executed in parallel. What is the difference between assembly writer and ...
1
vote
1answer
55 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 ...
0
votes
0answers
42 views

Understanding the rules of parsing table construction

I'm studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules. Example grammer is like this S → ( S ) S | $\epsilon$ How can I derive like ...
1
vote
1answer
430 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 ...
2
votes
0answers
24 views

Metrics for measuring and scoring automated “code analysis”?

I am writing various "program analysis" (aka static code analysis) algorithms. I am looking for ideas for metrics to measure how well my algorithms "understand the code". Some ideas i have so far : ...
0
votes
1answer
72 views

Generating intermediate code

I have a problem in backpatching "if-else" statements, for generating 3 address codes. The grammar rule is : S -》 if E then M1 S1 N else M2 S2 The semantic ...
4
votes
1answer
1k views

How to find First in a left recursive grammar?

One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed. If a grammar is left-recursive, then the set of ...
3
votes
1answer
537 views

Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive

I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous. I couldn't make up my mind on this statement. How can a grammar which is both ...
2
votes
2answers
87 views

Error propagation when compiling a compiler

Just for curiosity, I recently heard that many compilers are written in its own language. For example, gcc is partially written in C. And old version of compiler is used to compile the new version of ...
5
votes
1answer
115 views

Why more and more handcraft lex do not use regular expression any more?

Recently I read the source code of Clang, and found that it just do the lex thing by reading characters one by one and manually do the matching. But both my teacher when I'm in college and the book "...
2
votes
1answer
60 views

Is this a proper LL(1) Grammar?

Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) ...
1
vote
1answer
97 views

Can there still be infinite recursion if I remove all left recursion?

I have to transform the following grammar into a non left recursive grammar: S → aSb | bAS A → AaA | bAA | AAa | bAb This is what I came up with: A → bAAA’| bAbA’ A’ → aAA’| AaA’| ε S → aSb | ...
4
votes
1answer
178 views

Why more and more languages do not have link stage when compiling?

As far as I know, only C, C++, and Objective-C (in most used languages) need a linker when compiling, languages like Java and C# don't have one, and it seems more and more modern languages do not have ...
2
votes
1answer
56 views

Why are regular expression used in lexical analysis instead of grammars?

Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?
3
votes
1answer
83 views

SLR parse table and unambiguity

If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous? I think that since we have constructed the parse table ...

1 2 3
4
5
12