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
0answers
18 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 ...
0
votes
1answer
31 views

Do compilers of high programming languages always compile them directly to machine code?

As an amateur Bash/JavaScript scripter who never wrote one sentence in Assembly, I ask: Do compilers of high programming languages always compile them directly to machine code, or are there cases ...
0
votes
0answers
18 views

question about LL(1) and LR(0)

If grammar is an $LL(1)$ and does not contain any null production (i.e $V \rightarrow \epsilon$) then does that grammar necessarily be an $LR(0)$ grammar? I have tried to find counterexample for ...
0
votes
0answers
21 views

Minimal DFA for “$n$th character from the right is $a$” [duplicate]

I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$: $$ (a|b|c)^*a(a|b|c)^{n-1}. $$ The exercise asks for the number ...
2
votes
2answers
41 views

Does assembly language get translated to binary code? If so, is assembly language portable across machines?

I've tried to find the answer through Google but I've come across conflicting uses of terminology, so I just wanted to be absolutely clear. Here is my understanding: High level code written in a ...
0
votes
0answers
19 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 ...
0
votes
0answers
31 views

Why is empty in this Abstract Syntax Tree?

I given the following code to write as AST: { a = 4; while (a<10) if (a<5) a = a+5; else a = a+3; } ...
0
votes
1answer
21 views

How to determine valid handle for given bottom up parser?

I came across following question: Consider the grammar: $E → E + n\text{ | }E × n\text{ | }n$ For a sentence n + n × n, the handles in the right-sentential form of the reduction are (...
0
votes
1answer
24 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
24 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 ...
0
votes
1answer
44 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
34 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
457 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
33 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
33 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
41 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
70 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
20 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
22 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
38 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
179 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
26 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
19 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
163 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
21 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?...
0
votes
0answers
31 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
1answer
25 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
0answers
22 views

Proving correctness of LR parser facts

I have came across following facts while reading some compilers related text. However I did not find them in any standard reference book (mainly dragon book). Are they correct? If yes, how can we ...
0
votes
1answer
31 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 ...
0
votes
1answer
41 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
75 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
30 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
36 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
128 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 ...
30
votes
6answers
6k 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
39 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 ...
2
votes
1answer
75 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
49 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 ...
0
votes
0answers
77 views

Understanding handle, viable prefix and valid item in the context of LR(0) and LR(1) items

Dragon book gives definition of handle, viable prefix and valid item at various different places. I am trying to understand these definitions in each other's context. Various definitions given are as ...
2
votes
2answers
84 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 ...
1
vote
1answer
119 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
60 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
25 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
73 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 ...
2
votes
3answers
428 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 ...
0
votes
0answers
17 views

Connection of relation between valid item and viable prefix with canonical collection

I was trying to understand connection between different concepts of parsers and how those are followed in actual parsing steps. I came across following statement while reading LR parsers: An item ...
1
vote
1answer
34 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
37 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
55 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 ...