# Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

942 questions
Filter by
Sorted by
Tagged with
2k views

### What is an IELR(1)-parser?

I try to teach myself the usage of bison. The manpage bison(1) says about bison: Generate a deterministic LR or generalized LR (GLR) parser employing LALR(1), IELR(1), or canonical LR(1) parser ...
15 views

### Is this grammar LL(1) grammar?

Is this grammar LL(1)? Would it be a problem that S can be both E/S and E? S -> E / S S -> E E -> letter E -> ‘ S ’ Can it derive ‘a / e / ‘g / s’ ’...
322 views

### Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
55 views

### I´m having problems with this Context Free Grammar

I am not able to convert the following language to a Context Free Grammar. The major problem is how to pump both "sides" of the word to obtain same number of 0s and 1s, but, without creating a series ...
19 views

### Textbook for understanding formal grammars

I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
305 views

### Proof that the grammar is LL(2)

I am given the following grammar: $S \rightarrow AabAba \\ A \rightarrow a | \epsilon$ and I have to prove it is LL(2). I know what LL(k) means - one can choose a production based on k characters ...
42 views

### How to convert the left recursive grammar into right recursive grammar

I have a grammar: $A\rightarrow Aa|bB|c$ The above is the left recursive grammar. I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to ...
466 views

### Context-free grammar for binary words

I am supposed to create CFG for this languague: $L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$ where $|w_b|$ is count of terminals $b$ in $w$. For example: aa - OK, no 'b' abb - wrong, only ...
214 views

### Negative lookahead in LR parsing algorithm

Consider such a rule in grammar for an LR-family parsing generator (e.g YACC, BISON, etc.): Nonterminal : [ lookahead not in {Terminal1, ..., TerminalN} ] Rule ; ...
58 views

### Why LL(1) grammar generate all regular languages?

I came across following: Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages. I tried to get that. Definition: Right linear ...
28 views

### Adding constraints in grammar for Grammatical Evolution

I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p ...
112 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 ...
13 views

51 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 ...
27 views

### Deciding whether CFG generates the empty word

Give an algorithm to decide the following problem: given a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it generate the empty word? How can I make sure my algorithm is ...
140 views

### Is there any other computation theory besides the one in automata theory?

I'm a bit confused at a fundamental level. In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
48 views

### Grammar for language L on {a, b} where L = {w|na(w)mod 3 = 0} [duplicate]

I am able to form the regular expression but I am not confident with the grammar. I have tried the following: S-->aaaS|bS|b|lambda Regular expression is given by: ...
181 views

22 views

### Confused about substitution in grammar in certain cases

To illustrate my confusion let's say I'm given this unambiguous grammar in BNF: ...
45 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 (...
30 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 ...
39 views

### Making a CFG for a^i b^j c^k such that i+k < 3j

I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG. I have thought about solving this for a long time but but this still hasn't gotten me ...
78 views

### Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...
45 views

### What is the computational power of Parsing Expression Grammars?

Parsing Expression Grammars were introduced by Bryan Ford in Parsing Expression Grammars: A Recognition Based Syntactic Foundation.. Wikipedia says that it is an open problem to provide a Context Free ...
29 views

### Are these two things parsing a sentence and solving a problem in a turing machine equivalent?

I'm an undergrad currently studying Advanced Topics in Algorithms, Compiler Techniques, and Natural Language Processing. I'm wondering whether these two things are equivalent. Given a sentence and a ...
55 views

### Does every regular language have a linear grammar?

Some definitions and facts (from Wikipedia): A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions. the left-linear or left ...
56 views

### Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$

Prove that grammar $G$ with productions: $S \to aSc|\epsilon | bBc$ $B\to bBc | \epsilon$ Generates language $L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \}$ Step 1. Prove $L(G) \subseteq L$ . ...
19 views

### Variable derives itself

In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim. Consider the grammar:  \begin{align*} &R \to XRX \mid S \\ &S \to aTb \mid bTa \\ &T \...
20 views

### Use the pumping lemma for context free languages to prove L = {w#w | w \in {a,b}*} is not context free

I know the basics of using the pumping lemma for CFG to prove a language L is not context-free, however, the # symbol seems to be throwing me off or my understanding is not complete.
6k views

### Ambiguous Grammar to Unambiguous Grammar

I'm wondering if somebody can please help me to understand how I go about converting this grammar to an unambiguous grammar. If you can point me in the right direction, I would greatly appreciate it. ...
22 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 ...
259 views

383 views

### Prefix/suffix property of language containing only empty word

Does language $L ={\varepsilon}$, where $\varepsilon$ - empty word has suffix/prefix property? The definition says that language has prefix/suffix property requires that there is no code word in the ...
101 views

### Grammar and Real-numbers

I am curious about following question. I've read other threads but the problem is slightly different: Is the set of real numbers a language? So my question is: If I have a grammar, as defined in ...
136 views

### How do I calculate the Nth result of a context-free grammar?

Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences? Take as an example the following grammar: (from ...
29 views

### How to intuitively come up with an example for an ambiguous grammar and how to make that grammar unambiguous?

I don't get how to intuitively come up with an example for an ambiguous grammar. Let's take as an example this grammar: ...