Stack Overflow
Stack Overflow

Questions tagged [context-free-grammar]

In formal language theory, a context-free grammar (CFG) is a grammar subject to a special constraint: that the left-hand side (LHS) consist of a single non-terminal symbol. CFGs are capable of representing the set of context-free languages (CFLs).

1364 questions
442
votes
20 answers

Is C++ context-free or context-sensitive?

I often hear claims that C++ is a context-sensitive language. Take the following example: a b(c); Is this a variable definition or a function declaration? That depends on the meaning of the symbol c. If c is a variable, then a b(c); defines a…
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
122
votes
2 answers

What is a Context Free Grammar?

Can someone explain to me what a context free grammar is? After looking at the Wikipedia entry and then the Wikipedia entry on formal grammar, I am left utterly and totally befuddled. Would someone be so kind as to explain what these things are? I…
Ell
  • 4,238
  • 6
  • 34
  • 60
116
votes
8 answers

Regular vs Context Free Grammars

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around. I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for…
Jason Baker
  • 192,085
  • 135
  • 376
  • 510
93
votes
1 answer

Difference between an LL and Recursive Descent parser?

I've recently being trying to teach myself how parsers (for languages/context-free grammars) work, and most of it seems to be making sense, except for one thing. I'm focusing my attention in particular on LL(k) grammars, for which the two main…
Noldorin
  • 144,213
  • 56
  • 264
  • 302
89
votes
9 answers

What programming languages are context-free?

Or, to be a little more precise: which programming languages are defined by a context-free grammar? From what I gather C++ is not context-free due to things like macros and templates. My gut tells me that functional languages might be context free,…
n3rd
  • 5,989
  • 4
  • 39
  • 56
83
votes
1 answer

The recognizing power of "modern" regexes

What class of languages do real modern regexes actually recognise? Whenever there is an unbounded length capturing group with a back-reference (e.g. (.*)_\1) a regex is now matching a non-regular language. But this, on its own, isn't enough to match…
tobyodavies
  • 27,347
  • 5
  • 42
  • 57
64
votes
7 answers

Is D's grammar really context-free?

I've posted this on the D newsgroup some months ago, but for some reason, the answer never really convinced me, so I thought I'd ask it here. The grammar of D is apparently context-free. The grammar of C++, however, isn't (even without macros).…
user541686
  • 205,094
  • 128
  • 528
  • 886
63
votes
1 answer

Can this language be described by a non-ambiguous BNF grammar?

I'm getting back into language design/specification (via BNF/EBNF grammars) after 20+ years of leaving the topic alone (since my CS undergrad degree). I only vaguely recall the various related terms in this space, like LR(1), LALR, etc. I've been…
Kyle Simpson
  • 15,725
  • 2
  • 33
  • 55
49
votes
3 answers

Context-free grammars versus context-sensitive grammars?

Can someone explain to me why grammars [context-free grammar and context-sensitive grammar] of this kind accepts a String? What I know is Context-free grammar is a formal grammar in which every production(rewrite) rule is a form of V→w Where V is…
user1004413
  • 2,509
  • 6
  • 23
  • 33
42
votes
3 answers

What is the difference between LALR and LR parsing?

I understand both LR and LALR are bottom-up parsing algorithms, but what's the difference between the two? What's the difference between LR(0), LALR(1), and LR(1) parsing? How can I tell if a grammar is LR(0), LALR(1), or LR(1)?
AAB
  • 1,594
  • 2
  • 25
  • 40
40
votes
3 answers

What are the differences between PEGs and CFGs?

From this wikipedia page: The fundamental difference between context-free grammars and parsing expression grammars is that the PEG's choice operator is ordered. If the first alternative succeeds, the second alternative is ignored. Thus…
Frankie Ribery
  • 11,933
  • 14
  • 50
  • 64
36
votes
5 answers

Is there a standard C++ grammar?

Does the standard specify the official C++ grammar? I searched, but did not find it anywhere. Also, I wish to read a bit about C++ grammar in detail, like which category of grammars it falls in, etc. Any links pointing me in the right direction…
Lazer
  • 90,700
  • 113
  • 281
  • 364
34
votes
3 answers

chomsky hierarchy in plain english

I'm trying to find a plain (i.e. non-formal) explanation of the 4 levels of formal grammars (unrestricted, context-sensitive, context-free, regular) as set out by Chomsky. It's been an age since I studied formal grammars, and the various definitions…
tylerl
  • 30,197
  • 13
  • 80
  • 113
31
votes
6 answers

Why is bottom-up parsing more common than top-down parsing?

It seems that recursive-descent parsers are not only the simplest to explain, but also the simplest to design and maintain. They aren't limited to LALR(1) grammars, and the code itself can be understood by mere mortals. In contrast, bottom up…
Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
30
votes
3 answers

How can I determine if a language is context free or not?

How can I know whether the languages are context free or not?
user423733
  • 315
  • 1
  • 3
  • 4
1
2 3
…
90 91