2

Consider the following:

A function parameter list is a sequence of zero or more parameters separated by commas and bracketed by parentheses, "(" and ")" .

If I want to give the syntax of "function parameter list" assuming that the syntactic category of "parameter" has been defined, can I write:

  <function parameter list> ::= ( [<parameter> { , <parameter>} ] )

as a BNF? Is the usage of brackets nested in braces acceptable for EBNF?

Initially my impulse was to give the BNF as:

  <function parameter list> ::= ( <parameter> )
                             | ( <parameter> { , <parameter> } )
                             | ( )

I'm unsure how else I would write this BNF without braces.

I'm trying to get info from my text or online about using brackets/braces in regular BNF and some sources imply that you can, but my text doesn't specify exactly. It seems like the BNF needs some type of brace for this case. I thought BNF couldn't use bracket or braces and now I'm unsure.

Mars01
  • 79
  • 2
  • 10
  • Which dialect of BNF are you using? There are many, and they have different sets of rules. Is a parenthesis a metacharacter or a literal character? Maybe you should use LPAREN and RPAREN as token names for left parenthesis and right parenthesis. You casually mention EBNF one place; the rules for [EBNF](http://stackoverflow.com/questions/14922242/how-to-convert-bnf-to-ebnf) are very different from most other BNF-related systems (which is one reason why EBNF is not used very much). And your syntax bears no relation to EBNF. – Jonathan Leffler Mar 11 '15 at 04:17
  • What are {} trying to say? How is different from `[ [ , ] ]` ? – TZHX Mar 11 '15 at 04:17
  • @JonathanLeffler I assume the dialect of BNF is the most basic, academic dialect of BNF, since my text only covers BNF and EBNF and doesn't specify any particular dialect of BNF. This is why I assumed braces/brackets can't be used in "BNF" in this context. I believe the parenthesis is a literal, it isn't explicitly stated though. – Mars01 Mar 11 '15 at 04:31
  • @TZHX {} is saying that the terminals and non-terminals within the {} can be continually repeated. In your example, I believe the brackets denote the content within it as optional, but not continuously repeatable. – Mars01 Mar 11 '15 at 04:33
  • That "most basic form" helps me not the slightest; I've no idea which rules your basic form uses. There are as many BNF forms as there are universities and standards using BNF. There are virtually no two that follow the same rules. Witness: your variant seems to use `->` to indicate that the LHS is derived from the RHS. I don't know whose BNF uses that notation; I've not seen it before. It is understandable; it is not standard (because there is no standard — or because there are many standards; take your pick). How do you embed a literal `{` or `}` or `|` in your BNF, for example? – Jonathan Leffler Mar 11 '15 at 04:35
  • @JonathanLeffler as far as my text is concerned, the BNF they refer to is the one introduced by Peter Naur for the description of ALGOL 60. Unfortunately your question about embedded literals goes beyond the scope of the text it seems, this is part of my problem here. – Mars01 Mar 11 '15 at 04:51
  • @JonathanLeffler In case this was unclear The {} and | symbols are not literals. Neither is []. {} denotes the inner content of the braces can be ommited or repeated indefinitely, [] denotes the content within can be optional but not repeated, and the | symbol is simply denoting "or", as in "function parameter is defined as this OR that". These definitions are taken as a precondition in the text. – Mars01 Mar 11 '15 at 05:04
  • Three examples of BNF — illustrating the differences. [Algol 60 Grammar](http://www.cs.unc.edu/~plaisted/comp455/Algol60.pdf) (pdf); Wikipedia on [Backus-Naur Form](http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form), and [About BNF notation](http://cui.unige.ch/db-research/Enseignement/analyseinfo/AboutBNF.html). Not one of these uses or mentions `->` (they use `::=` instead). – Jonathan Leffler Mar 11 '15 at 05:13
  • Your simplest solution is to introduce `` and `` and use those in the main part of the grammar. Somewhere, you'll define the terminal for those, perhaps as ` ::= '('`. You might be OK without that. You might be able to use `(` and `)` in the grammar directly, without quotes, and it 'works' as a literal parenthesis (leading to ` ::= (` as the definition). It depends on the rules that are defined by whoever is defining the dialect of BNF that you are working with. – Jonathan Leffler Mar 11 '15 at 05:15
  • @JonathanLeffler What about this? Assuming we are OK without defining left/right parenthesis. ::= ( ) | () ::= | , – Mars01 Mar 11 '15 at 05:22
  • That would work. I might use ` ::= ( )` and ` ::= /* Nothing */ | ` and ` ::= | , ` but it ends up as essentially the same. So, if we agree that neither comma nor left-parenthesis nor right-parenthesis is a metacharacter, what you've got is fine (and I'm happy to agree; I just needed the rules spelled out). The `/* Nothing */` notation means 'no symbols', of course — but I'd better spell it out, just in case of confusion. – Jonathan Leffler Mar 11 '15 at 05:28
  • And if your slightly extended BNF uses `[` and `]` to enclose optional material (zero or one appearances), and `{` and `}` to enclose optionally repeating material (zero or more appearances), and commas and parentheses are not metacharacters, your original outline is OK too. But it depends on the rules that you're working under. – Jonathan Leffler Mar 11 '15 at 05:32
  • @JonathanLeffler I appreciate the thoroughness. Cheers. – Mars01 Mar 11 '15 at 05:37

1 Answers1

3

Braces and brackets are EBNF constructs -- the E stands for extended. Simple BNF is just a context-free grammar with no extra syntactic sugar for recursive things, so you have to write it out with a nested recursive rule:

<function parameter list> ::= ( <param-list> ) | ( )
<param-list> ::= <param> | <param-list> , <param>
Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
  • I agree, the question as it was posed in my study material seemed to imply that no additional definition of param-list was needed, which is why I posed my initial question. Cheers. – Mars01 Mar 11 '15 at 05:35