# Questions tagged [parsers]

Questions about algorithms that decide whether a given string belongs to a fixed formal language.

406 questions
Filter by
Sorted by
Tagged with
23 views

### Disposition: Parsing

I have to prepare 30 minutes of oral examen about the subject called parsing. Where I have to talk about it. And then I shall hand in like 30 pages (including code and figures etc). I don't know how ...
27 views

### Computing Follow sets of Grammar for LL(1) parser

I am trying to compute the Follow set of the following Grammar: E -> E' E A A -> + | * E -> num E' -> num I start by adding the end of string symbol, ...
317 views

### Is this an LL(1) grammar? How to solve First - Follow conflict?

im trying to check if this grammar is LL(1). S -> L = R L -> * L | id R -> L | R + R | num As you can see there is a Left recursion on R production. So i remove that and what i get is: S -> L = ...
76 views

### What is the time complexity of finding the FIRST and FOLLOW sets?

Given how important these are for parsing, I'm surprised I wasn't able to find anything about their complexity. I'm interested in all combinations of: What is the (edit: best known) time complexity ...
43 views

### Abstract syntax tree: expression->operation->lhs|rhs vs expression->lhs|operation|rhs - what should I take into account in decision?

I am trying to build class hierarchy for the abstract syntax tree of First Order Logic as specified in the grammar https://github.com/antlr/grammars-v4/blob/master/fol/fol.g4 (ANTLR parser generator). ...
39 views

### Grammars and Parsing: Ambiguity in Sequences

BACKGROUND I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches. Given terminals: "a": KEYWORD "b": ...
20 views

### Why shift means push terminal symbol and state into the stack? Why not push only state?

Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal ...
75 views

### Build LL(1) parsing table for grammar S -> iSeS | iS | a

Task Bulid parsing table for grammar S -> iSeS | iS | a Resolve conflicts in this table and simulate parser work for word ...
596 views

### Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
209 views

### LR(1) parsing, problem with look ahead symbols

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution. I'm trying to fill the LR(1) parsing table for the grammar ...
326 views

### Syntax Directed Translation Scheme for Postfix to Infix Notation

I'm reading Compilers Principles, Techniques and Tools textbook and I encountered a problem from exercise 2.3 We have to construct a syntax-directed translation scheme that translates arithmetic ...
62 views

### Converting from cfg to cnf (Chomsky normal form)

I am trying to convert this grammar from context free grammar with kleene star productions into the Chomsky normal form equivalent. I am having a hard time trying to understand how to do this, I need ...
433 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 (...
26 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?...
67 views

### CYK result de-transformation

Suppose we have a rules derived from a treebank. And in order to get a syntax tree of a given sentence we use the cyk algorithm. In order to use the cyk we should convert the rules into chomsky normal ...
56 views

### Creating a grammar for a a language for instructions, with repititions

I have a language that consists of instructions for movement on a 2D-plane. You start at coordinate [0,0] The instructions DOWN 1 UP 10 LEFT 5 RIGHT 1 means you ...
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 ...
205 views

### The rightmost derivation is possible with the same rule of leftmost derivation

Can someone please help me in understanding the statement. What does it exactly mean? What I think it means is that: the derivation produces by the leftmost derivation is also possible with rightmost ...
50 views

### Get grammar from his LALR(1) parsing table

I have a problem with this exercise. This is the LALR(1) parsing table for the grammar G. How can i get the productions of G? Thanks :)
476 views

### Handling epsilon productions in recursive descent parsing

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions: ...
160 views

### Is this a correct grammar for untyped lambda calculus?

I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this: ...
41 views

75 views

### Linear time parsing from star of context free language

I was wondering if there are cases in which the star closure of a language can make the resulting language easier to parse. In particular, if I have this grammar: ...
239 views

126 views

### What is a preterm parser?

I am working with HOL-Light parser and keeping seeing references to preterm parser. What is a preterm parser? The most informative statement I find is from the HOL-Light reference for the ...
107 views

### Which Type of Grammar is this?

I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the ...
624 views

### Construct SLR Parse table problems

Consider the augmented grammar G is: S` -> S S -> a S -> (T) T -> T,S T -> S I have tried to construct parse table. But, when I read '(' ...
30 views

### Grammar Recursive Descent

I have this Grammar below: ...
772 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 ...
30 views

### Compilers: how to find first and follow sets?

I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!
24 views

### Parsing table confusion [closed]

I've been researching the different answers I've been given to this, would somebody just be able to give me a clear answer of the difference between Shift, reduce and go-to. - In a parsing table. Of ...
506 views

### How should I show that a grammar is not LL(1) and convert grammar to LL(1)

I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y ...
841 views

### I'm having trouble with Parse Trees

I am doing homework and I have the following problem: Consider the grammar: ...
### Is this $LL(1)$ grammar valid?
Is the following a valid $LL(1)$ grammar: \begin{align} S &\rightarrow L \ \\ L &\rightarrow M L_2 \\ L_2 &\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M &\...