2
$\begingroup$

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form

What does the asterisk (*) mean?

In the example below, what is the difference between <fun-def*> and <fun-def>?

<program> ::= <fun-def*> int main(void) { <block> }

<block> ::= { <var-def*> <statement*> }

<fun-def> ::= void <var-name> ( <parameters> ) { <block> }
            | <type> <var-name> ( <parameters> ) { <block> }
        
<var-def> ::= <type> <var-name> ;
           | <type> <var-name> { <expression> } ;
           | <type> <var-name> = <expression> ; 
$\endgroup$

1 Answer 1

2
$\begingroup$

I have never seen this syntax before, but most likely, <var-def*> is a typo for (or unusual way of writing) <var-def>*. A common extension of BN is to use the * operator from regular expressions. In other words, <var-def>* represents 0 or more instances of <var-def>.

This does not increase the expressive power of BNF and is just syntactic sugar. Of course we could have created a rule <var-defs> ::= | <var-def> <var-defs> and then used <var-defs> in place of <var-def*>. But sometimes it is convenient to be able to use the more concise syntax, without having to create extra non-terminals and rules to represent repetition.

$\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.