Skip to main content

Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Filter by
Sorted by
Tagged with
76 votes
1 answer
16k views

Language theoretic comparison of LL and LR grammars

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...
Raphael's user avatar
  • 72.6k
40 votes
2 answers
7k views

Are there inherently ambiguous and deterministic context-free languages?

Let us call a context-free language deterministic if and only if it can be accepted by a deterministic push-down automaton, and nondeterministic otherwise. Let us call a context-free language ...
Patrick87's user avatar
  • 12.9k
37 votes
2 answers
5k views

What does "context" in "context-free grammar" refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
CodyBugstein's user avatar
  • 2,967
35 votes
9 answers
5k views

What is the significance of context-sensitive (Type 1) languages?

Seeing that in the Chomsky Hierarchy Type 3 languages can be recognised by a state machine with no external memory (i.e., a finite automaton), Type 2 by a state machine with a single stack (i.e. a ...
bitmask's user avatar
  • 1,755
34 votes
4 answers
32k views

How to prove that a grammar is unambiguous?

My problem is how can I prove that a grammar is unambiguous? I have the following grammar: $$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } ...
user1594's user avatar
  • 541
30 votes
4 answers
3k views

What's really meant by context-free in the term context-free grammar?

I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result. So can anyone help ...
Shady Atef's user avatar
28 votes
2 answers
48k views

How to prove that a language is context-free?

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...
D.W.'s user avatar
  • 162k
27 votes
1 answer
9k views

How to show that L = L(G)?

Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
Raphael's user avatar
  • 72.6k
26 votes
2 answers
31k views

Is the complement of { ww | ... } context-free?

Define the language $L$ as $L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}$. In other words, $L$ contains the words that cannot be expressed as some word repeated twice. Is $L$ context-free or not? I'...
Evgeny Eltishev's user avatar
24 votes
4 answers
19k views

Why is left recursion bad?

In compiler design, why should left recursion be eliminated in grammars? I am reading that it is because it can cause an infinite recursion, but is it not true for a right recursive grammar as well?
user avatar
23 votes
1 answer
421 views

Is there any nongeneral CFG parsing algorithm that recognises EPAL?

EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar: $S \rightarrow a a$ $S \rightarrow b b$ $S \rightarrow a S a$ $S \...
Alex ten Brink's user avatar
22 votes
4 answers
2k views

Are there other ways to describe formal languages other than grammars?

I'm looking for mathematical theories that deal with describing formal languages (set of strings) in general and not just grammar hierarchies.
mtanti's user avatar
  • 323
20 votes
1 answer
37k views

Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
sanjeev mk's user avatar
20 votes
2 answers
3k 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 ...
fuz's user avatar
  • 911
19 votes
2 answers
2k views

Can there be 'dead states' in a context-free grammar?

Can a context-free grammar include "dead states" from an automaton, such as $$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$$ The production rules $B\to C$ and $...
cmtjk's user avatar
  • 293
19 votes
1 answer
2k views

Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. ...
user avatar
19 votes
2 answers
5k views

How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?

According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows ...
Ava Petrofsky's user avatar
18 votes
3 answers
3k views

Decidable non-context-sensitive languages

It is arguable that most languages created to describe everyday problems are context-sensitives. In the other hand, it is possible and not hard to find some languages that are not recursive or even ...
Victor Stafusa's user avatar
17 votes
2 answers
4k views

Removing left-recursion in grammar while maintaining left-association of operator

I have a problem with this exercise: Let G be the following ambiguous grammar for the λ-calculus: E → v | λv.E | EE | (E) where E is the single non-...
Marco DallaG's user avatar
16 votes
3 answers
2k views

What would you get if you add parameters to context free grammars?

I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
Aivar's user avatar
  • 285
16 votes
2 answers
5k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
Andrea Tucci's user avatar
15 votes
4 answers
5k views

Can someone give a simple but non-toy example of a context-sensitive grammar?

I'm trying to understand context-sensitive grammars. I understand why languages like $\{ww \mid w \in A^*\}$ $\{a^n b^n c^n \mid n\in\mathbb{N}\}$ are not context free, but what I'd like ...
BlueBomber's user avatar
  • 1,297
15 votes
2 answers
4k views

How do C compilers distinguish casting from grouping?

In the C language, there's the 2 similar-in-form but distict-in-meaning constructs: (type)value which is a casting, and (value), ...
DannyNiu's user avatar
  • 352
15 votes
5 answers
6k views

How is non-ambuiguity different from determinism?

I am trying to understand what is meant by "deterministic" in expressions such as "deterministic context-free grammar". (There are more deterministic "things" in this field). I would appreciate an ...
wvxvw's user avatar
  • 1,388
15 votes
2 answers
1k views

Are the Before and After sets for context-free grammars always context-free?

Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the ...
Alex ten Brink's user avatar
15 votes
2 answers
849 views

Is the language of words that are unbalanced in the first half context-free?

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...
Or Bairey-Sehayek's user avatar
14 votes
2 answers
3k views

How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?

I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context ...
yoyo_fun's user avatar
  • 818
14 votes
1 answer
16k views

Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
Charu Bansal's user avatar
14 votes
1 answer
270 views

When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (...
templatetypedef's user avatar
13 votes
3 answers
17k views

The importance of normal forms like Chomsky normal form for CFGs

I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't ...
user5507's user avatar
  • 2,191
13 votes
3 answers
39k views

How is this grammar LL(1)?

This is a question from the Dragon Book. This is the grammar: $S \to AaAb \mid BbBa $ $A \to \varepsilon$ $B \to \varepsilon$ The question asks how to show that it is LL(1) but not SLR(1). ...
Vinayak Garg's user avatar
13 votes
2 answers
6k views

Is there any way to distinguish between LL(k) and LR(k) grammar?

I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar. We also know the facts that every LL grammar is LR that is LL ...
Debabratta Jena's user avatar
13 votes
2 answers
4k views

Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
bongubj's user avatar
  • 563
12 votes
2 answers
591 views

What is the closure of context-free languages under finite intersections?

Famously the intersection of context-free languages need not be context-free. On the other hand the intersection of context-sensitive languages is context-sensitive. So this leads to the question: ...
gewo's user avatar
  • 121
12 votes
2 answers
11k views

Finding the language generated by a context-free grammar

This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand): What language is generated by this grammar? $S \rightarrow a S b S \mid b S a ...
dan's user avatar
  • 223
12 votes
1 answer
4k views

Example of unrestricted grammar which produces non-context-sensitive language

I'm talking about Type-0 (Chomsky hierarchy) unrestricted grammar, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$. I can not find any ...
Andrey Lebedev's user avatar
12 votes
3 answers
2k views

Decidable languages and unrestricted grammars?

Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are. We can define the decidable languages with ...
templatetypedef's user avatar
11 votes
2 answers
11k views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
kauray's user avatar
  • 519
11 votes
5 answers
2k views

Is there a known method for constructing a grammar given a finite set of finite strings?

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible ...
Gustav Bertram's user avatar
11 votes
1 answer
88k views

Different between left-most and right-most derivation [duplicate]

I am a beginner started learning theoretical computer science. I just came through context-free grammars. So my question is: what is the different between left-most and right-most derivation? ...
H nagma's user avatar
  • 121
11 votes
4 answers
10k views

Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed ...
meribold's user avatar
  • 143
11 votes
2 answers
6k views

How can I prove this language is not context-free?

I have the following language $\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\}$ I am trying to determine which Chomsky language class it fits into. I can see how it could be made using a context-...
justausr's user avatar
  • 435
10 votes
3 answers
2k views

Representing "but not" in formal grammar

I just came across the following grammar definition: CommentChar ::       SourceCharacter but not LineTerminator But for discussion, I'll present this similar ...
jedwards's user avatar
  • 201
10 votes
1 answer
13k views

Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
Soroush's user avatar
  • 203
10 votes
1 answer
488 views

Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

Let $\Sigma$ be the set of terminal and $N$ the set of non-terminal symbols of some context-free grammar $G$. Say I have a string $a \in (\Sigma \cup N)^+$ such that $x a y \in \mathcal{S}(G)$ where $...
Thomas's user avatar
  • 203
10 votes
1 answer
461 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 ...
Jakub Lédl's user avatar
9 votes
2 answers
2k views

Correct name for a recursive descent parser that uses loops to handle left recursion?

This grammar is left recursive: ...
user71015's user avatar
9 votes
1 answer
20k views

Left recursion and left factoring -- which one goes first?

if I have a grammar having a production that contains both left recursion and left factoring like $\qquad \displaystyle F \to FBa \mid cDS \mid c$ which one has priority, left recursion or left ...
Andrea Tucci's user avatar
9 votes
1 answer
1k views

Arithmetic expressions grammar transformation

In the article Parsing Expressions by Recursive Descent by Theodore Norvell (1999) the author starts with the following grammar for arithmetic expressions: ...
SasQ's user avatar
  • 290
9 votes
2 answers
2k views

Is there a different resolution of the "dangling else" problem other than "match closest"?

The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
Gro-Tsen's user avatar
  • 393

1
2 3 4 5
26