Talk:Extended Backus–Naur Form

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Philosophy (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Computer science  
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

In the article it says the http://www.cl.cam.ac.uk/~mgk25/ site has a draft version. However, as I came there, there was a link the final version. The final PDF (ISO/IEC 14977:1996) is also available via official site: http://www.iso.org/iso/en/CatalogueDetailPage.CatalogueDetail?CSNUMBER=26153

I found the pdf on the ISO site after having visited this page so am guessing it would be helpful to correct the article to point to the newly available electronic version and thus have done so. Nagoff

Who created BNF?[edit]

BNF stands for Backus-Naur form. The article states it was created by Nicklaus Wirth. I always thought it was created by two guys named Backus and Naur. —Preceding unsigned comment added by 149.32.192.33 (talk) 17:29, 8 June 2009 (UTC)

Restructure needed[edit]

The table of contents needs restructuring: the lead section is half the article! Most of the section should be moved down into the body of the article and slightly rewritten to fit its new location. Web-Crawling Stickler 19:24, 30 December 2006 (UTC)

No restructure needed anymore[edit]

I just revised the article and I think that the "This article or section may require restructuring to meet Wikipedia's quality standards."-tag can be removed. I don't know how to do this, maybe somebody else could do this. —Preceding unsigned comment added by Klaus trainer (talkcontribs) 00:18, 7 January 2007

All you had to do was remove the line that said {{Cleanup-restructure|December 2006}} ... I did it for you ... also, please sign your posts. —72.75.85.159 (talk · contribs) 01:59, 7 January 2007 (UTC)

Power[edit]

As a layman, I found something missing: I understand EBNF is as powerful as BNF, but can (E)BNF represent most or all programming languages' syntax? If not, why not? --Gwern (contribs) 01:19 22 January 2007 (GMT)

- EBNF is in itself not more powerful than BNF for one simple reason: all EBNF can be translated into equivalent BNF. EBNF is however easier to use because it contains convenience functionality for optional parts, loops, ... . Regarding the other question ("EBNF for most or all programming languages"): EBNF (and therefore BNF) can be used to define any "context free grammar" (chomsky 2). If a programming language is formed by a context free grammar, then you can write down the EBNF for it. --Ray 84.252.12.234 (talk) 12:07, 4 January 2013 (UTC)

I didn't find that a useful explanation. I appreciate that there is a separate article on context free grammar, but what would be useful in this article is something a little less academic and more useful, eg some example languages that are capable of having their grammars expressed in EBNF, some that are not (if any) and why, and some that are mostly able to be expressed in EBNF but where some parts are best excluded (at least for brevity) eg comments (otherwise every EBNF expression would need to contain optional comments at every point). 82.71.24.65 (talk) 20:07, 15 September 2013 (UTC)

Respect the syntax, damnit![edit]

It's just infuriating! It's an article about a syntax description language, and it's very syntax was not respected...

Nearly all examples lacked the concatenation operator, presented as an extension, whereas the only extensions proposed in ISO 14977 are the special sequence and the use of function-like syntax, as parentheses aren't allowed to follow a meta-identifier in plain EBNF...

Also, the program code given as an example of the program grammar was just plain wrong. Even if we forget just a moment that the program grammar was wrong also, at least because it lacked concatenation operators, there is no specification in it where whitespace can take place. So the valid version of the programm would probably have been:

  PROGRAMDEMO1BEGINA0:=3;B:=45;H:=-100023;C:=A;D123:=B34A;BABOON:=GIRAFFE;TEXT:="Hello world!";END.

Well, no, as the grammar badly specified here didn't allow for single-char identifiers... (nor single-digit numbers, for that matters)

I think all these observations have been corrected now. Note that digit { digit } does allow single digits, as {} means zero or more.
The original was therefore correct, I have removed unnecessary [ ] from the example. Bobcousins 11:25, 14 November 2007 (UTC)

Syntax correction?[edit]

It looks to me like the first example in the section "Motivation to extend the BNF" is incorrectly constructed.

Should the code reading:

signed number = [ sign , ] number ;

actually be:

signed number = [ sign ] , number ;

210.15.196.66 04:17, 2 December 2007 (UTC)


Defining a production should be:

production ::= terminal | nonterminal | ... —Preceding unsigned comment added by Dncarley (talkcontribs) 14:14, 25 April 2008 (UTC)

Incorrect BNF reduction?[edit]

I do believe that the repetition is not correctly reduced to BNF:

Repetition:

number = { digit } ;

can be defined in BNF-style as:

number = digit | number digit;

I think this should rather read

number = ε | number digit;

since { digit } also includes the empty word.

141.3.27.53 (talk) 09:43, 9 January 2008 (UTC)

Using ISO EBNF consistantly[edit]

There is currently a mix of notation being used here that seem jolting, in particular a mix of ISO Extended BNF's defining symbol (=) and the notation used in earler BNF and XML's definition (::=). ISO EBNF, resolved the ambiguity between a syntactitic ('=') and meta-syntactic (=) equals-sign by requireing quotes for the former, so the double-colon notation is no longer needed. I'd like to update the article to consistently use the ISO notation, and describe the other language as "the XML specification's BNF", perhaps even moving the topic to a seperate article.

Burt Harris (talk) 17:35, 23 May 2008 (UTC)

"Another example"[edit]

The "Another example" section is huge, and in my opinion totally unnecessary. Defining a programming language (and its semantics, given partially in the table below) is quite beside the point. EBNF is for defining grammars in general, not for defining programming languages. I think this is distracting, and ought to be removed.

Perhaps an example which is self-contained enough that it need not go into excessive background definition would be more useful. Something like a grammar describing ISO paper sizes (A4, B5, etc), perhaps.

Kate (talk) 22:25, 27 June 2008 (UTC)

Clarification needed when to use = and when to use ::=[edit]

The page doesn't explicitly state when to use "=" and when to use "::=" Maybe the distinction is obvious if you know EBNF, but it's not clear to me. I can't see a correlation between statements that use one or the other. Can someone add that?

Thanks.

dj_segfault (talk) 13:34, 2 July 2008 (UTC) David Kramer 07/02/2008

Clarification needed: ISO EBNF syntax described[edit]

This article doesn't really describe EBNF in general at all, but rather the syntax used by ISO EBNF, which for all its virtues doesn't seem to be that common yet. Is there even one other EBNF variant that uses a comma instead of a space for concatentation? (166.70.56.235 (talk) 07:23, 25 January 2009 (UTC))

I kind of agree, but think the current article is good, since it concentrates on one EBNF. Maybe this article should be Extended Backus–Naur Form (ISO/IEC 14977), and an overview article on BNF extensions be produced. ... said: Rursus (mbork³) 10:22, 10 November 2009 (UTC)
No, a better suggestion: since BNF/EBNF variants by Pete Jinks simply presents a table, meaning that EBNF are just homomorphic variation on the same theme, it is better to keep this article as Extended Backus–Naur Form, and clearly state that EBNF(ISO) is just the example EBNF used to illustrate the general structure of all EBNF:s/ABNF:s/XBNF:s. Then the variations are treated by the article. Having one article for each xBNF would be duplicate work. ... said: Rursus (mbork³) 12:38, 10 November 2009 (UTC)

Comma in EBNF, not in BNF[edit]

The article provides incorrect BNF rules: BNF doesn't use comma for concatenation operator, while EBNF (ISO) does. ... said: Rursus (mbork³) 10:22, 10 November 2009 (UTC)

I updated accordingly. I may also add some explanation to the missing commas in BNF. ... said: Rursus (mbork³) 13:21, 10 November 2009 (UTC)

Alternatives[edit]

Would it be useful to include links, or even a quick mention, of alternative forms of defining syntax apart from the BNF/EBNF/Syntax Diagrams? The convention I have read most does not have a name as far as I am aware, but uses Black (heavy) brackets of differing types: [] means optional, {} means one of the enclosed must be present, <> encloses a token, and () could be used to indicate repetition. Interestingly these are slightly different (but seem more sensible) than those proposed to ISO. 82.71.24.65 (talk) 20:16, 15 September 2013 (UTC)

in the german language part on the wp-servers are pictures visualizing the idea behind the grammar.[edit]

ebnf and these kind of syntaxdiagramms are vica-versa transforable. in other word can represent the same grammar.

--> link.

79.234.217.118 (talk) 17:43, 27 October 2013 (UTC)

EBNF does not accurately describe itself[edit]

In the first example, where it says "Even EBNF can be described using EBNF", the provided grammar contains many whitespace characters. One such example is the rule:

"lhs = identifier ;"

The grammar itself, however, does contain any whitespace terminals! In other words, the whitespace to either side of the "=" character is illegal according to the provided grammar!

Two options are: 1. Edit the "sketched" grammar to make newlines and whitespaces legal 2. Make a note that the grammar is actually inaccurate — Preceding unsigned comment added by Walterwalterman (talkcontribs) 23:14, 22 February 2014 (UTC)

{}+?[edit]

I was under the impression that if you superscript a + after a {} then you are saying repetion with at least one, is that the case? Rlk89 (talk) 05:23, 2 March 2015 (UTC)

How is this a productionn grammar?[edit]

A production grammar generates valid strings of a language. The algorithm is well documented.

Production rules are of the general form:

<pattern> \to <string>

Where <pattern> is string of terminals and nonterminals. And <string> is a replacement string of terminals and nonterminals.

The <pattern> of a context free grammar is a single non-terminal symbol.

The <string> is made up of a symbol or symbols that may be terminal or non-terminal.

The production grammar algorithm is a loop:

1) Output string initially containing the start symbol.

2) A rule whose <pattern> matches some sequence of string is chosen. If no pattern can be found the process stops. This is akin to a search and replace in a text editor.

3) The matched <pattern> in the output string is replaced by the production rule <string>.

4) steps 2 and 3 repeated until no pattern can be matched to any part of the string.


The problem here is that these rules are the opposite of production rules. The <string> is not the pattern in a production rule.


In the BNF gramars we have a named language construct rule having a language formation pattern.

rule = construct_name "::=" construct_pattern;
construct_name .. '<' let $(let|dgt|'_'|' ') '>';
construct_pattern = formation $('|' formation);
formation = element $element;
element = symbol | construct_name;
symbol .. character $character;

The above rules are in a metalanguage. The = is a syntax rule. The .. is a token rule. Token rules do not allow white space between matches once the first character is matched.

The confusion I think comes from the misinterpretation of the word formation in the original description of BNF.


Formation:

1. the action of forming or process of being formed.
2. a structure or arrangement of something.


A BNF rule describes the formation of a language construct. In this case the rules are describing the structure. The structure or arrangement definition of formation.

<if structure> ::= if <boolean expression> then <expression>

Here the language construct <if structure> is being defined using the <boolean expression> language construct structure and the <expression> language construct structure. It describes the formation, structure or arrangement, of a named language construct formation (structure or arrangement).

This is a reductive grammar.

A set of syntactic rules for the analysis of strings to determine whether the strings exist in a language.

These meta language rules define language construct formations. The rule specifies a language construct name that can have a semantic meaining. Steamerandy (talk) 18:37, 25 March 2015 (UTC)