Answers.Body: <p>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.</p>
  
  <p>A bit of creativity and looking around can develop many an idea as long as you get <em>outside the box</em>. The cafeteria might be a good place to look.</p>
  
  <pre><code>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]
  </code></pre>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T06:14:28.867Z
Answers.Text: 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.
Answers.UserDisplayName: progner
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T06:17:44.093Z
Answers.Text: 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" :)
Answers.UserDisplayName: Gypsy Spellweaver
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T06:18:34.200Z
Answers.Text: BTW, welcome to [cseducators.se]. Hope to see more of you around here.
Answers.UserDisplayName: Gypsy Spellweaver
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T12:53:14.387Z
Answers.Text: I'll note here that these examples are all expressible as regular expressions. The actual power of BNF isn't needed for these.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T05:46:58.433Z
Answers.LastActivityDate: 2019-10-08T07:13:31.420Z
Answers.LastEditDate: 2019-10-08T07:13:31.420Z
Answers.UserDisplayName: Gypsy Spellweaver
Answers.Body: <p>Mathematical expressions or natural language are good candidates for these.
  e.g. from <a href="http://matt.might.net/articles/grammars-bnf-ebnf/" rel="nofollow noreferrer">http://matt.might.net/articles/grammars-bnf-ebnf/</a> </p>
  
  <pre><code> &lt;expr&gt; ::= &lt;term&gt; "+" &lt;expr&gt;
           |  &lt;term&gt;
  
   &lt;term&gt; ::= &lt;factor&gt; "*" &lt;term&gt;
           |  &lt;factor&gt;
  
   &lt;factor&gt; ::= "(" &lt;expr&gt; ")"
             |  &lt;const&gt;
  
   &lt;const&gt; ::= integer
  </code></pre>
  
  <p>which I think is a good candidate because it exposes the interesting recursive qualities from expansion.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T19:19:47.210Z
Answers.LastActivityDate: 2019-10-08T19:19:47.210Z
Answers.UserDisplayName: Kevin Wang
Answers.Body: <p>The literary arts are full of structured strings. The main problem there is finding ones which have sufficiently interesting structure. E.g.</p>
  
  <pre><code>play ::= act+
  act ::= scene+
  scene ::= (stage-direction | line)+
  stage-direction ::= "Enter" actor+ | "Exit" actor+
  ...
  </code></pre>
  
  <p><a href="/users/104/gypsy-spellweaver">Gypsy Spellweaver</a> helpfully points out that this can be elaborated to incorporate even more structure as</p>
  
  <pre><code>play ::= act ( act* [intermission act+] )*
  </code></pre>
  
  <p>although you may want to distinguish between <code>play</code> (the text) and <code>play-performance</code> (which may have intermissions) and use that as an illustration of sharing rules between grammars.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T07:23:03.387Z
Answers.Text: `play ::= act ( act* [intermission act+ ] )*` ?
Answers.UserDisplayName: Gypsy Spellweaver
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T12:54:14.870Z
Answers.Text: The examples are all simple forms that can be expressed (and are, actually) as regular expressions. BNF is about structure more than these indicate.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T07:15:05.687Z
Answers.LastActivityDate: 2019-10-08T07:40:54.207Z
Answers.LastEditDate: 2019-10-08T07:40:54.207Z
Answers.UserDisplayName: Peter Taylor
Answers.Body: <p>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 <em>structure</em> of a thing, such as a language. As such, the parts have relationships to one another. So, in computer languages &quot;if&quot; and &quot;while&quot; are tokens (word symbols, keywords), and tokens can be defined by regular expressions, the sequence &quot;if while&quot; isn't legal in Python, since the BNF that defines the structure contains no such form.</p>
  <p>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 <em>non terminals</em> of the BNF.</p>
  <p>And note that I'm trying to generate a description of a car, not a car.</p>
  <blockquote>
  <p>carDescription ::= chassis &quot;containing both&quot; propulsionSystem &quot;and surrounded by&quot; body.</p>
  <p>chassis ::= (&quot;rectangular&quot; | &quot;triangular&quot;) framework &quot;with wheels at vertices&quot;.</p>
  <p>framework ::= &quot;reinforced&quot; ( &quot;steel&quot; | &quot;fiberglass&quot;) &quot;semirigid structure&quot;.</p>
  <p>propulsionSystem ::= fuelPoweredEngine | motor</p>
  <p>propulsionSystem ::= (fuelPoweredEngine | motor) propulsionSystem</p>
  <p>motor ::= &quot;electric motor and battery&quot;</p>
  </blockquote>
  <p>etc.</p>
  <p>Note that propulsion system is the recursive way of saying that a propulsion system is one or more &quot;thingies&quot; that provide power. It is equivalent to the + in regular expressions.</p>
  <p>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.</p>
  <p>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.</p>
  <p>Since BNF and REs were actually created in the service of defining <em>languages</em> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T22:04:00.657Z
Answers.Text: I think you made a typo in the definition of `propulsionSystem`.
Answers.UserDisplayName: Solomon Ucko
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T22:34:45.880Z
Answers.Text: @SolomonUcko, worse than a typo. A logical error. An infinite recursion. Oh my. Fixed now.
Answers.UserDisplayName: Buffy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-08T13:26:02.437Z
Answers.LastActivityDate: 2019-10-08T22:34:05.327Z
Answers.LastEditDate: 2020-06-18T08:36:57.023Z
Answers.UserDisplayName: Buffy
Body: <p>I'm preparing a class on the modified BNF notation that python uses. I.e.,</p>
  
  <blockquote>
    <p>Each rule begins with a name (which is the name defined by the rule) and ::=. A vertical bar (<code>|</code>) is used to separate alternatives; it is the least binding operator in this notation. A star (<code>*</code>) means zero or more repetitions of the preceding item; likewise, a plus (<code>+</code>) means one or more repetitions, and a phrase enclosed in square brackets (<code>[ ]</code>) means zero or one occurrences (in other words, the enclosed phrase is optional). The <code>*</code> and <code>+</code> operators bind as tightly as possible; parentheses are used for grouping. <a href="https://docs.python.org/3/reference/introduction.html#notation" rel="noreferrer">Source</a> </p>
  </blockquote>
  
  <p>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. </p>
  
  <p>In other words, I can't use something like</p>
  
  <p><code>longstringitem ::= longstringchar | stringescapeseq</code>,</p>
  
  <p>I must use something like this instead:</p>
  
  <p><code>digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9</code><br>
  <code>"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"</code></p>
  
  <p>What are some non-CS concepts that can be used to illustrate the <code>*</code> sign (zero or more repetitions of the preceding item,) the <code>+</code> sign (one or more repetitions,) the phrase enclosed in <code>[]</code> (zero or one occurrences) and the <code>()</code> (used for grouping) from the BNF notation?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-08T10:08:44.237Z
Comments.Text: 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).
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-08T10:44:39.763Z
Comments.Text: 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.
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-10-09T08:20:50.933Z
Comments.Text: @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](https://docs.python.org/3/reference/lexical_analysis.html#identifiers): "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 ..."
Comments.UserDisplayName: muru
Tags: <teaching-analogy><introductory-lesson><adult-education><syntax><layperson>
Title: What are some non-CS concepts that can be defined using BNF notation?
ThreadText: # What are some non-CS concepts that can be defined using BNF notation?
  
  (Asked by: username_0 on 2019-10-08)
  
  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](https://docs.python.org/3/reference/introduction.html#notation)
  
  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?
  
  **Tags:** teaching-analogy, introductory-lesson, adult-education, syntax, layperson
  
  > **Comments:**
  > **username_1**: 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).  
  > **username_1**: 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.  
  > **username_2**: @username_1 given the context, it would be better to ask which encoding is assumed. That was an example, they clarify it in [the next chapter](https://docs.python.org/3/reference/lexical_analysis.html#identifiers): "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 ..."  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_3 on 2019-10-08. Score: 10
  
  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.
  
  > **Comments:**
  > **username_0**: Thanks, username_3. 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.  
  > **username_3**: 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" :)  
  > **username_3**: BTW, welcome to [cseducators.se]. Hope to see more of you around here.  
  > **username_1**: I'll note here that these examples are all expressible as regular expressions. The actual power of BNF isn't needed for these.  
  
  ---
  
  ### Answer by username_4 on 2019-10-08. Score: 4
  
  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.
  
  
  ---
  
  ### Answer by username_5 on 2019-10-08. Score: 4
  
  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+
  ...
  
  ```
  
  [username_3](/users/104/username_3) 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.
  
  > **Comments:**
  > **username_3**: `play ::= act ( act* [intermission act+ ] )*` ?  
  > **username_1**: The examples are all simple forms that can be expressed (and are, actually) as regular expressions. BNF is about structure more than these indicate.  
  
  ---
  
  ### Answer by username_1 on 2019-10-08. Score: 2
  
  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.
  
  > **Comments:**
  > **username_6**: I think you made a typo in the definition of `propulsionSystem`.  
  > **username_1**: @username_6, worse than a typo. A logical error. An infinite recursion. Oh my. Fixed now.  
  
  ---
  
  