Questions tagged [formal-grammars]

Questions about formal grammars, generative descriptions of formal languages.

Questions about formal grammars, generative descriptions of formal languages. In augmented forms, formal grammars can also be used to specify compilers.

1299 questions
76
votes
1 answer

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 all $k$? So how is the situation really? In…
Raphael
  • 73,461
  • 31
  • 185
  • 415
40
votes
2 answers

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 inherently ambiguous if and only if all context-free…
Patrick87
  • 12,994
  • 1
  • 48
  • 78
37
votes
2 answers

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 sensitive grammar" but I still failed to find what the…
CodyBugstein
  • 3,035
  • 11
  • 34
  • 47
36
votes
4 answers

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 } S$$ and make this to an unambiguous grammar, I…
user1594
  • 561
  • 2
  • 6
  • 9
35
votes
9 answers

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 push-down automaton) and Type 0 by a state machine…
bitmask
  • 1,783
  • 2
  • 16
  • 20
30
votes
4 answers

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 with this ?
Shady Atef
  • 411
  • 5
  • 7
30
votes
2 answers

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 a context-free grammar for the language. Are there…
D.W.
  • 170,893
  • 23
  • 241
  • 528
26
votes
4 answers

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've tried to intersect $L$ with $a^*b^*a^*b^*$, but…
Evgeny Eltishev
  • 771
  • 1
  • 6
  • 8
26
votes
1 answer

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 important that the grammar at hand is correct , that…
Raphael
  • 73,461
  • 31
  • 185
  • 415
24
votes
4 answers

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?
user56833
24
votes
1 answer

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 \rightarrow b S b$ EPAL is the 'bane' of many parsing…
Alex ten Brink
  • 9,226
  • 3
  • 37
  • 63
22
votes
4 answers

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
  • 323
  • 1
  • 6
21
votes
1 answer

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 free but not regular. The language generated by…
sanjeev mk
  • 419
  • 1
  • 3
  • 7
20
votes
2 answers

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 tables. What is an IELR-parser? All relevant articles I…
fuz
  • 915
  • 6
  • 20
19
votes
2 answers

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 $C\to cC$ will loop forever and never generate a…
cmtjk
  • 293
  • 2
  • 5
1
2 3
…
86 87