# Questions tagged [parsers]

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

354 questions
Filter by
Sorted by
Tagged with
551 views

### Is the given grammar LL(2)?

http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$ The example is $S -> a^kb/a^ka$ The ...
610 views

### Eliminate left recursion from grammar

Consider the following grammar: $$A\to Ba|Aa|c \\ B\to Bb|Ab|d$$ How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion? I have tried applying the ...
6k views

### LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
552 views

76 views

### Is there any precedence for symbols for constructing parse trees? [duplicate]

I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees. For example, the sentence: p ∧ q → r, ...
675 views

### What would a formal grammar for a binary file format look like?

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive. What would ...
33 views

### Unsure about parse tree of PCFG

I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa. My solution would look like ...
44 views

### Why is particular token missing in LALR lookahead set?

I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin: S' ::= S S ::= L = R | R L ::= * R | id R ::= L The items associated ...
87 views

### How do merged lookahead sets help LALR parse more grammars than SLR? [closed]

From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-...
123 views

### What's the step for build a SLR table for the following CFG? [closed]

(r1) E → E+T (r2) E → T (r3) T → T F (r4)T →F (r5) F → F∗ (r6) F → a (r7) F → b I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. ...
51 views

### operator precendence grammar

According to this post https://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
91 views

### Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
96 views

### How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
2k views

I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them? Any help is appreciated.
427 views

### Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
523 views

### How does this left-associative recursive descent parser work?

For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application. The BNF grammar that describes the ...
2k views

### Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
736 views

### I'm having trouble with Parse Trees

I am doing homework and I have the following problem: Consider the grammar: ...
449 views

### Is the given grammar LALR

We are given the following grammar. S-->AS/b A-->SA/a We have to tell if its LALR or not. As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using ...
2k views

### Need to remove indirect left recursion from CFG

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$ In the ...
259 views

902 views

### How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
747 views

### Basic idea behind error recovery in recursive-descent parsers

I see that modern SW basically dominated by recursive descent parsers. These parsers try grammar production and back track to an alternative one in case of failure. Suppose BNF is ...
194 views

### How to treat ϵ-productions in table-driven predictive parsing?

Here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html in chapter Driver Procedure, it's shown how table-drive predictive parsing works. The predict table however can ...
### Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?
Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL? The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence ...