Stack Overflow
Stack Overflow

Questions tagged [grammar]

A formal grammar is a set of production rules that describe how to form strings of valid syntax. Formal Grammars are most often used to specify the syntax of a programming language.

A formal grammar is a set of production rules that describe how to form strings of valid syntax. Formal Grammars are most often used to specify the syntax of a programming language.

A grammar is formally defined as a 4-tuple, consisting of a series of production rules, terminal symbols, nonterminal symbols, and a start symbol, which itself is a nonterminal. Any terminal cannot be a nonterminal and vice-versa.

Grammars prove very useful in parsers for programming languages. A grammar can be used to determine the syntactical correctness of a given string.

Parser generators such as JavaCC or ANTLR use a given grammar (usually one of a particular form, and free of ambiguities) to generate the parser.

3251 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
361
votes
21 answers

int a[] = {1,2,}; Why is a trailing comma in an initializer-list allowed?

Maybe I am not from this planet, but it would seem to me that the following should be a syntax error: int a[] = {1,2,}; //extra comma in the end But it's not. I was surprised when this code compiled on Visual Studio, but I have learnt not to trust…
Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
160
votes
6 answers

Why can't C++ be parsed with a LR(1) parser?

I was reading about parsers and parser generators and found this statement in wikipedia's LR parsing -page: Many programming languages can be parsed using some variation of an LR parser. One notable exception is C++. Why is it so? What particular…
Cheery
  • 24,645
  • 16
  • 59
  • 83
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
110
votes
9 answers

What is the difference between LR, SLR, and LALR parsers?

What is the actual difference between LR, SLR, and LALR parsers? I know that SLR and LALR are types of LR parsers, but what is the actual difference as far as their parsing tables are concerned? And how to show whether a grammar is LR, SLR, or LALR?…
Prasoon Saurav
  • 91,295
  • 49
  • 239
  • 345
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
90
votes
1 answer

What makes Java easier to parse than C?

I'm acquainted with the fact that the grammars of C and C++ are context-sensitive, and in particular you need a "lexer hack" in C. On the other hand, I'm under the impression that you can parse Java with only 2 tokens of look-ahead, despite…
Daniel Shapero
  • 1,869
  • 17
  • 30
80
votes
5 answers

How to identify whether a grammar is LL(1), LR(0) or SLR(1)?

How do you identify whether a grammar is LL(1), LR(0), or SLR(1)? Can anyone please explain it using this example, or any other example? X → Yz | a Y → bZ | ε Z → ε
Prashant Bhardwaj
  • 1,203
  • 2
  • 18
  • 26
78
votes
1 answer

Why is 019 not a JavaScript syntax error? Or why is 019 > 020

If I type 019 > 020 in the JavaScript console (tested in both Chrome and Firefox), I get the answer true. This is due to 020 being interpreted as an OctalIntegerLiteral (equals 16) whereas 019 is apparently being interpreted as DecimalLiteral (and…
lexicore
  • 42,748
  • 17
  • 132
  • 221
78
votes
2 answers

Why is the separator in a TypeScript TypeMemberList semicolon as opposed to comma?

This is a typescript interface: interface A { l: { x: string; y:number } } But this (similar thing) produces an error: interface A { l: { x: string, y:number } } // => Error: ';' expected. On p.37 of the…
Harold
  • 1,584
  • 1
  • 12
  • 20
75
votes
8 answers

English grammar for parsing in NLTK

Is there a ready-to-use English grammar that I can just load it and use in NLTK? I've searched around examples of parsing with NLTK, but it seems like that I have to manually specify grammar before parsing a sentence. Thanks a lot!
roboren
  • 891
  • 1
  • 7
  • 5
66
votes
6 answers

How to check whether a sentence is correct (simple grammar check in Python)?

How to check whether a sentence is valid in Python? Examples: I love Stackoverflow - Correct I Stackoverflow love - Incorrect
ChamingaD
  • 2,908
  • 8
  • 35
  • 58
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
61
votes
4 answers

Examples of LL(1), LR(1), LR(0), LALR(1) grammars?

Is there a good resource online with a collection of grammars for some of the major parsing algorithms (LL(1), LR(1), LR(0), LALR(1))? I've found many individual grammars that fall into these families, but I know of no good resource where someone…
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
1
2 3
…
99 100