2
$\begingroup$

Today I heard of BNF which is a language for languages. Also heard that it specifies the entire syntax of C in four pages. So I thought of checking it out. After reading through this page, I got a fair idea about how to read the syntax.

But I don't understand what the first two lines mean:

%token int_const char_const float_const id string enumeration_const
%%

Also I am reading BNF just because I am just curious. How should I proceed to understand the formal syntax by reading BNF?

Here is the BNF syntax of C.

$\endgroup$
  • 1
    $\begingroup$ Search for "%token" on the first link you gave, and you'll find an explanation that appears to answer your own question. Is there something about that which wasn't satisfactory? We expect you to do a significant amount of research before asking, and to show us in the question what research you've done. Questions about the syntax of specific tools are likely off-topic here but might be appropriate for Stack Overflow. $\endgroup$ – D.W. Jul 31 '15 at 6:02
  • $\begingroup$ I was wondering somewhat why you do not seem interested in my answer. I realize it contradicts your second link to the web. Thus I added a note in my answer. In my informed opinion, the document posted by Pete Jinks is too informal to serve as a reference document and does not make much sense from a terminology point of view, since any formalism rich enough to describe the CF syntax of a programming language will be what he calls a variant of BNF. $\endgroup$ – babou Jul 31 '15 at 14:24
4
$\begingroup$

Backus Normal Form does not define special syntax for %token. So that would be a special syntax custom-added by a particular person or web page or tool. Tool support is off-topic here, but if search for "%token" on the first link you gave, you'll find a brief explanation that appears to describe what %token means in the context of that particular example.

In other words: if you only want to understand BNF at a conceptual level, ignore it. That's something that's not part of BNF, but is an add-on that was added for some special purpose. If you want to understand that the specific syntax used by some specific tool (e.g., YACC), your best source is probably the reference manual for that tool.

$\endgroup$
1
$\begingroup$

The document you are using is not BNF (Backus-Naur Form)

BNF is a language used to specify CF grammars. Like most languages it has a reference syntax. It always possible to define another syntax for the same language.

For example you could use another syntax for Python where all the English keywords are replaced by German keyword, and the semi-colon is replaced by the keyword semi-colon. It would work as well, but it would not be considered standard Python. You could even make more drastic syntactic changes without really changing the way it works, including use of begin and end in place of indentation.

Similarly BNF has a reference syntax which is described in various documents, including this wikipedia page. Their are variants, like EBNF (extended BNF) that allow for the use of regular expressions as the right hand-side of rules.

But basically, BNF is just a standard syntax to write context-free (CF) grammars.

The document you refer to does contain a CF grammar. But the syntax is not BNF (and since BNF is just a standard syntax for CF grammars, the use of the name BNF is abusive).

NOTE
I realize (belatedly) that your second link (which I missed) points to a document where the author Pete Jinks takes a different point of view. It only shows that you should always be careful with information found on the web (including from myself), and double check it. He calls it a variant of BNF, but it is as much a variant as my caricature of Python (and I could have made it worse) is a variant of Python. Just try to use it to exchange Python programs with other people. Or double check what he and I are saying with other reference information on the web.

Reading a specification

You are supposed to know how to read a CF grammar.

The real BNF syntax may look strange sometimes, because it is a meta-syntax (the syntax of a language for describing the syntax of other languages), and thus it requires various forcing devices, like those needed to include in a string the symbols used as string delimiters, for example with a backslash, or to include a "*" as symbol in a regex that already uses the same symbol as an operator.

Another aspect is that the syntax of a programming language is usually decomposed in two levels:

  • lexical specification usually done with finite stete technology, or regular expressions. It specifies the spelling of terminals of the CF syntax, i.e. what is sometimes called tokens.

  • context free syntax, which is often expressed in BNF since the langage Algol 60.

Terminals are usually infinite in number, which does not do well for a finite specification of CF syntax (a formal requirement for CF grammars). Hence most of them are grouped in a finite number of families, called in your exanple: - id for identifiers such as foobar - int_const for integer literals such as 23 - etc...

The syntax of these potentially infinite families is not usually included in the BNF, and use of any such terminal is replaced by the name of the family.

It is the list of names of these families of terminals (tokens) that is listed in the lines you worry about.

In standard BNF, they may not be described at all, and left to a complementary specification. Then they can be identified by the fact they they are not the left-hand side of any rule.

Alternatively they can be associated with rules of a regular grammar defining them, also written in BNF. But this may be confusing. One major reason is that the separation between lexical and CF syntax usually plays a role in the interpretation of program layout, especially spaces, tabs and other "invisible" characters.

The most common principle (though not fully used in a language like Python) is that invisible characters can be used arbitrarily as separators of lexical elements, but are ignored at the CF syntactic level. This implies that ther are not to be used in lexical elements unless explicitly permitted by the specification of the lexical family.

Note that all other terminals such as reserved words (if, else, while, ...), operators (+, ==, ...) or punctuation symbols (;, ,, ...) appear directly in the BNF as strings within double quotes.

Of course, as you can see from your own example, people never quite respect standards. Hence it is always wise to read the tool specific documentation. But it is useful to have the standard as reference to understand what it means and what it is for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.