Page 211 - DCAP507_SYSTEM_SOFTWARE

Unit 13: Formal Systems

In unextended BNF, one would get approximately the similar effect by offering a separate group Notes
for arbitrary-length series of the repeatable component and examining it therefore:
<procedure-call> ::= ( <expression> <expression-sequence> )
<expression-sequence> ::= <empty>
| <expression> <expression-sequence>
This is much like the recursive definition of a list as either null or a pair comprising one element
(the car) and a list (the cdr).

Notes The syntax trees constructed as per the unextended BNF rule appear different from
those constructed as per the star rule-none of the expression nodes for the operands will be
children of the procedure-call node if the unextended BNF rule is utilized.
The star notation permits for the possibility that the repeatable constituent does not occur at all.
(In our example, a procedure call may enclose no operands.) If we wish to state a repeatable
component that must happen at least once, we'll use a plus sign on behalf of the star.

Example: We show example from the Icon programming language:
<program> ::= {<declaration>}+
Alternatively, an Icon program includes one or more declarations. Again, we could obtain a
similar effect in unextended BNF:
<program> ::= <declaration-sequence>
<declaration-sequence> ::= <declaration>
| <declaration> <declaration-sequence>
Lastly, it frequently happens that a creation can comprise any number of consecutive occurrences
of some component, apart from that if there are two or more of them, any two that are contiguous
must be separated by some fixed symbol.

Example: The compound statement in Algol 60 usually comprises numerous statements
separated by semicolons:
begin
temp := first;
first := second;
second := temp
end

Observe that the semicolon is a separator, not a terminator. It would be an error to put a
semicolon among the second occurrence of temp and the keyword end. A compound statement
in Algol 60 can enclose just one statement in its body:
begin
temp := first
end
And it may enclose none at all:
begin
end

LOVELY PROFESSIONAL UNIVERSITY 205