8
$\begingroup$

I'm preparing a class on the modified BNF notation that python uses. I.e.,

Each rule begins with a name (which is the name defined by the rule) and ::=. A vertical bar (|) is used to separate alternatives; it is the least binding operator in this notation. A star (*) means zero or more repetitions of the preceding item; likewise, a plus (+) means one or more repetitions, and a phrase enclosed in square brackets ([ ]) means zero or one occurrences (in other words, the enclosed phrase is optional). The * and + operators bind as tightly as possible; parentheses are used for grouping. Source

For this class, I'm not allowed to assume the students have prior knowledge in CS. Thus I must rely on concepts from general knowledge to provide examples in the use of BNF.

In other words, I can't use something like

longstringitem ::= longstringchar | stringescapeseq,

I must use something like this instead:

digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
"a digit is defined as either 0 or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9"

What are some non-CS concepts that can be used to illustrate the * sign (zero or more repetitions of the preceding item,) the + sign (one or more repetitions,) the phrase enclosed in [] (zero or one occurrences) and the () (used for grouping) from the BNF notation?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Let me note for the record that the form you are using is actually a merging of BNF (which doesn't include * or +) and regular expressions, which do. Regular expressions normally define scanners and BNF describes parsers. BNF is strictly more powerful than regular expressions, but uses recursive forms rather than repetition. I hope you aren't confused about that. Most language definitions use both, but for very different things (scanners v parsers). $\endgroup$
    – Buffy
    Commented Oct 8, 2019 at 10:08
  • $\begingroup$ Let me also note that the source you point to is ambiguous. In particular "a" ... "z" is only a hint about the meaning, not the definition. Which language alphabet is implied or assumed? English, French?? I suggest that you use a more formal definition of RE and BNF than you see at that link. Otherwise you risk confusing your students if they come across the proper definitions, which many will eventually, though perhaps not for adult ed. But the instructor needs a firmer grounding in any case. $\endgroup$
    – Buffy
    Commented Oct 8, 2019 at 10:44
  • $\begingroup$ @Buffy given the context, it would be better to ask which encoding is assumed. That was an example, they clarify it in the next chapter: "Within the ASCII range (U+0001..U+007F), the valid characters for identifiers are the same as in Python 2.x: the uppercase and lowercase letters A through Z ..." $\endgroup$
    – muru
    Commented Oct 9, 2019 at 8:20

4 Answers 4

Reset to default
10
$\begingroup$

Going with real-world things which they should be familiar with are best, even if it is completely outside of education. As you have applied the tag for adult education, I'm going to presume it is outside of normal university/college courses.

A bit of creativity and looking around can develop many an idea as long as you get outside the box. The cafeteria might be a good place to look.

entree ::= pizza | hamburger | steak
side_dish ::= corn | coleslaw | fries
beverage ::= coffee | tea | milk | soda
dessert ::= (apple|pumpkin) pie | (peach|cherry) cobbler | ice cream
meal ::= water beverage* entree side_dish+ [dessert]

The water is mandatory (already on the table perhaps), it's possible to have as many drinks, and refills, as you wish. There is always an entree, one side dish is included, but you may have more. Finally, if you choose, you may have a desert.

If the situation is at a regular educational institution you can experiment with using degree requirement courses, and electives. There's enough there to allow the students to create their own versions as practice as well.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, Gypsy. Always appreciate your content. I guess my writer's block came about because I was looking for rigorous definitions, when they definitely don't have to be. $\endgroup$
    – progner
    Commented Oct 8, 2019 at 6:14
  • 2
    $\begingroup$ You could even have an exercise where they reduce pizza into a definition. Crust required other stuff maybe not. And, as a twist, there are places which serve "desert pizza" :) $\endgroup$
    – Gypsy Spellweaver
    Commented Oct 8, 2019 at 6:17
  • 1
    $\begingroup$ BTW, welcome to Computer Science Educators. Hope to see more of you around here. $\endgroup$
    – Gypsy Spellweaver
    Commented Oct 8, 2019 at 6:18
  • 3
    $\begingroup$ I'll note here that these examples are all expressible as regular expressions. The actual power of BNF isn't needed for these. $\endgroup$
    – Buffy
    Commented Oct 8, 2019 at 12:53
4
$\begingroup$

The literary arts are full of structured strings. The main problem there is finding ones which have sufficiently interesting structure. E.g.

play ::= act+
act ::= scene+
scene ::= (stage-direction | line)+
stage-direction ::= "Enter" actor+ | "Exit" actor+
...

Gypsy Spellweaver helpfully points out that this can be elaborated to incorporate even more structure as

play ::= act ( act* [intermission act+] )*

although you may want to distinguish between play (the text) and play-performance (which may have intermissions) and use that as an illustration of sharing rules between grammars.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ play ::= act ( act* [intermission act+ ] )* ? $\endgroup$
    – Gypsy Spellweaver
    Commented Oct 8, 2019 at 7:23
  • 3
    $\begingroup$ The examples are all simple forms that can be expressed (and are, actually) as regular expressions. BNF is about structure more than these indicate. $\endgroup$
    – Buffy
    Commented Oct 8, 2019 at 12:54
4
$\begingroup$

Mathematical expressions or natural language are good candidates for these. e.g. from http://matt.might.net/articles/grammars-bnf-ebnf/ 

 <expr> ::= <term> "+" <expr>
         |  <term>

 <term> ::= <factor> "*" <term>
         |  <factor>

 <factor> ::= "(" <expr> ")"
           |  <const>

 <const> ::= integer

which I think is a good candidate because it exposes the interesting recursive qualities from expansion.

Improve this answer
$\endgroup$
2
$\begingroup$

Let me try to give a more interesting example, that can't be expressed as a set of simple regular expressions. BNF, properly speaking, is about the structure of a thing, such as a language. As such, the parts have relationships to one another. So, in computer languages "if" and "while" are tokens (word symbols, keywords), and tokens can be defined by regular expressions, the sequence "if while" isn't legal in Python, since the BNF that defines the structure contains no such form.

The following won't be perfect, and I'll need to leave out a lot for want of time to complete it. Take ellipsis (...) as meaning that I'm leaving things out, not as any formal symbol. Literals are quoted. Unquoted words are defined with other BNF productions in the same language (the non terminals of the BNF.

And note that I'm trying to generate a description of a car, not a car.

carDescription ::= chassis "containing both" propulsionSystem "and surrounded by" body.

chassis ::= ("rectangular" | "triangular") framework "with wheels at vertices".

framework ::= "reinforced" ( "steel" | "fiberglass") "semirigid structure".

propulsionSystem ::= fuelPoweredEngine | motor

propulsionSystem ::= (fuelPoweredEngine | motor) propulsionSystem

motor ::= "electric motor and battery"

etc.

Note that propulsion system is the recursive way of saying that a propulsion system is one or more "thingies" that provide power. It is equivalent to the + in regular expressions.

But the intent isn't to define individual, unrelated things, but the overall structure of a complex things that is made of parts, some of which are other complex things. Regular Expressions don't have that power, but BNF does.

And please note that my intention here isn't to be completely accurate (pedantic) but simply to try to demonstrate the essence of BNF as opposed to RE. It is one of the fundamental ideas of the Chomsky Language Hierarchy.

Since BNF and REs were actually created in the service of defining languages such as Python, it is difficult to divorce the idea from language. Hence my example is for a description of a car (which is language) not for a car itself, which is too complicated to express as BNF since the actual form of the connections between things in an actual car are critical. I left out the drive train, for example, which connect the propulsion system to the wheels and the control system that regulates the propulsion system. I don't have a theorem for you but am pretty sure that it would be beyond BNF to do this. Even if it were, the complete description would need the complexity of an engineering diagram and even then would leave out physical principles of combustion or conversion of electrical to mechanical energy.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think you made a typo in the definition of propulsionSystem. $\endgroup$
    – Solomon Ucko
    Commented Oct 8, 2019 at 22:04
  • $\begingroup$ @SolomonUcko, worse than a typo. A logical error. An infinite recursion. Oh my. Fixed now. $\endgroup$
    – Buffy
    Commented Oct 8, 2019 at 22:34

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.