Stack Overflow
Stack Overflow

Questions tagged [bnf]

BNF stands for Backus-Naur Form, or Backus Normal Form. It is a form of notation for context-free grammars and is often used for (but is not restricted to) the description of the syntax of programming languages. In addition to programming languages, it is also used to describe communication protocols and document formats.

A BNF specification is a set of derivation rules, written as

<symbol> ::= __expression__

where <symbol> is a nonterminal, and the __expression__ consists of one or more sequences of symbols; more sequences are separated by | indicating a choice, the whole being a possible substitution for the symbol on the left. Symbols that never appear on a left side are terminals. On the other hand, symbols that appear on a left side are non-terminals and are always enclosed between the pair <>. The ::= means that the symbol on the left must be replaced with the expression on the right.

561 questions
108
votes
9 answers

Tool for generating railroad diagram used on json.org

I love the syntax of railroad diagrams on json.org which are a graphical representation of the BNF language. I haven't found any tools that can produce results as eloquently. Can anyone identify the tool used to generate these diagrams?
aleemb
  • 31,265
  • 19
  • 98
  • 114
92
votes
2 answers

What is a regular language?

I'm trying to understand the concept of languages levels (regular, context free, context sensitive, etc.). I can look this up easily, but all explanations I find are a load of symbols and talk about sets. I have two questions: Can you describe in…
FBryant87
  • 4,273
  • 2
  • 44
  • 72
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
45
votes
3 answers

Ruby Grammar

I'm looking for Ruby grammar in BNF form. Is there an official version?
user68109
  • 2,446
  • 6
  • 21
  • 20
43
votes
6 answers

BNF vs EBNF vs ABNF: which to choose?

I want to come up with a language syntax. I have read a bit about these three, and can't really see anything that one can do that another can't. Is there any reason to use one over another? Or is it just a matter of preference?
Jason Baker
  • 192,085
  • 135
  • 376
  • 510
29
votes
3 answers

Regex BNF Grammar

Is there any BNF grammar for regular expression?
Julien Grenier
  • 3,364
  • 2
  • 30
  • 43
27
votes
2 answers

Context-free grammar for C

I'm working on a parser for C. I'm trying to find a list of all of the context-free derivations for C. Ideally it would be in BNF or similar. I'm sure such a thing is out there, but googling around hasn't given me much. Reading the source code for…
limp_chimp
  • 13,475
  • 17
  • 66
  • 105
26
votes
5 answers

Repository of BNF Grammars?

Is there a place I can find Backus–Naur Form or BNF grammars for popular languages? Whenever I do a search I don't turn up much, but I figure they must be published somewhere. I'm most interested in seeing one for Objective-C and maybe MySQL.
Greg
  • 45,306
  • 89
  • 231
  • 297
23
votes
6 answers

Where can I find standard BNF or YACC grammar for C++ language?

I'm trying to work on a kind of code generator to help unit-testing an legacy C/C++ blended project. I don't find any kind of independent tool can generate stub code from declaration. So I decide to build one, it shouldn't be that hard. Please,…
Kevin Yu
  • 1,423
  • 4
  • 15
  • 19
23
votes
7 answers

How to determine whether a language is LL(1) LR(0) SLR(1)

Is there a simple way to determine whether a grammar is LL(1), LR(0), SLR(1)... just from looking on the grammar without doing any complex analysis? For instance: To decide whether a BNF Grammar is LL(1) you have to calculate First and Follow sets -…
Chris
  • 9,209
  • 16
  • 58
  • 74
22
votes
4 answers

EBNF for ECMAScript?

I'm trying to find a good EBNF description of ECMAScript, but so far I've not found anything complete. Any ideas?
Peter Boughton
  • 110,170
  • 32
  • 120
  • 176
22
votes
3 answers

How to implement Backus-Naur Form in Python

I know there are some vaguely similar questions already relating to BNF (Backus-Naur Form) grammars in Python, but none of them help me much in terms of my application. I have multiple BNFs that I need to write code for. The code should be able to…
Jakemmarsh
  • 4,601
  • 12
  • 43
  • 70
18
votes
2 answers

How to represent negation in BNF?

Does BNF or ABNF support negation. That is exclude certain members of the set? I did not see any such negation operator in its syntax. For example, suppose S is the set of all alphanumeric strings that are not equal to "foo" What is the BNF for S?
Jus12
  • 17,824
  • 28
  • 99
  • 157
16
votes
4 answers

Regular expression for a language tag (as defined by BCP47)

I need a regular expression for a language tag as defined by BCP 47. I know that the full BNF syntax is available at http://www.rfc-editor.org/rfc/bcp/bcp47.txt and that I could use it to write my own, but hopefully there is one already out there.…
smartcaveman
  • 41,281
  • 29
  • 127
  • 212
16
votes
4 answers

Is there a formal (ideally BNF) typescript js language grammar (or only typescript subset)?

I'm looking for the Typescript grammar. Not the parser-lexer, but only the formal grammar description. I want to implement ts it's code folding and basic static code analyzing as plugin to one simple linux IDE for GNOME.
Andrey Belyak
  • 685
  • 7
  • 17
1
2 3
…
37 38