Les 3 en 4 - Grammatica's

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Grammatica's

Beschrijven van taal
met grammatica

Leerdoel

Je kunt een grammatica gebruiken om een taal te beschrijven, deze noteren in Backus-Naurvorm, en vaststellen of bepaalde woorden voldoen aan een gegeven grammatica.

Inleiding

In het Nederlands staat een bijvoeglijk nw. vóór een zelfstandig nw.:

• Goed: ‘de hond’, ‘de grote hond’
• Fout: ‘de hond grote’

Zulke grammaticale regels zijn er
ook voor programmeertalen

Deze regels zijn veel strikter
dan bij menselijke talen

Waarom moet elke zin in een programmeertaal volledig duidelijk zijn?

1. Omdat mensen de code moeten begrijpen.
2. Omdat een computer de code moet kunnen uitvoeren.
3. Omdat programmeertalen geen leestekens gebruiken.
4. Omdat grammaticale fouten in programmeertalen niet hersteld kunnen worden.

De Backus-Naurvorm (BNF)

BNF is een makkelijke manier om grammaticaregels te noteren.

Je kunt ermee beschrijven
welke regels je allemaal kunt
maken.

Voorbeeld BNF: notitieregels voor berekeningen

Voorbeeld voor berekeningen:

• Goed: 2 × 3, 4 – 2 en 8 ÷ 4.
  
• Fout: 2 + ÷ 4

Een BNF hiervoor:          <berekening> ::= <getal> <operator> <getal>

Betekenis: een berekening bestaat uit een getal, dan een operator en dan weer een getal.

Let op de ::=-notitie!

Een adres in Nederland bestaat uit een straatnaam, huisnummer, postcode en stad.

Bekijk de volgende grammatica's in BNF. Welke grammatica beschrijft een Nederlands adres?

1. <adres> ::= <straatnaam> <postcode> <plaatsnaam>
2. <adres> ::= <straatnaam> <getal> <postcode> <plaatsnaam>
3. <adres> ::= <getal> <straatnaam> <postcode> <plaatsnaam>
4. <adres> ::= <postcode> <plaatsnaam> <straatnaam> <getal>

BNF: langere berekeningen 

Bekijk nog eens de BNF: <berekening> ::= <getal> <operator> <getal> 

Hoe krijg je hiermee 2 x 3 + 1?

In dit geval mogelijk, maar niet handig:

 <berekening> ::= <getal> <operator> <getal> <operator> <getal>

Niet handig, want elke volgende uitbreiding, bijv. 2 x 3 + 1 : 2, wordt dan weer een probleem...

BNF: langere berekeningen - een slimmere oplossing

Het laatste stuk is hetzelfde als de eerste BNF:

   <berekening> ::= <getal> <operator> <getal> <operator> <getal>

   <berekening> ::= <getal> <operator> <getal>

Een slimme BNF kan er dus als volgt uitzien:

   <berekening> ::= <getal> <operator> <berekening>

BNF: langere berekeningen - oplossingen combineren

Deze twee BNF’s kun je combineren tot:

   <berekening> ::= <getal> <operator> <getal> |

                               <getal> <operator> <berekening>

Betekenis - een berekening is:

• een getal, dan een operator en dan weer een getal OF
  
• een getal, dan een operator en dan een andere berekening.

Met deze BNF kun je oneindig lange berekeningen maken!

| betekent of

BNF: langere berekeningen - een complete oplossing

Om de oplossing compleet te maken moeten we nog aangeven welke operatoren we gebruiken:

<berekening> ::= <getal> <operator> <getal> |
                            <getal> <operator> <berekening>

<operator>      ::= + | – | × | ÷

BNF: berekeningen - grammatica gebruiken ter controle

Hoe weet je of 2 × 3 en 2 × 3 + 1 correcte berekeningen zijn?

• Begin met <berekening>
  
• Vervang het stapsgewijs door wat volgende BNF mag
  

BNF: berekeningen - grammatica gebruiken ter controle

Vraag – Bewijs dat  5 × 3 + 1 een berekening is.

<getal>

<operator>

x

3

<getal>

Werken met grammatica's

Met de vervangingsstappen hebben we laten zien dat 2 × 3 + 1 inderdaad een berekening is volgens de gekozen grammaticaregels: 

• Deze grammaticaregels noemen we  'een grammatica'. 
• De drie regels die we hebben gebruikt, kunnen we dus 'een   grammatica voor berekeningen' noemen.
  
• Grammatica’s moeten altijd zo kort mogelijk zijn, want zo zijn   ze duidelijk en overzichtelijk.

Uitbreiding: Grammatica voor berekeningen met haakjes

Bij berekeningen met haakjes geldt dat er na elk openingshaakje ook altijd een keer een sluithaakje volgt. 2 × (3 + 1 is dan dus niet correct.

 De haakjesregel kunnen we als volgt verwerken in de grammatica:

<berekening>  ::=  <getal> <operator> <getal> |

                              <getal> <operator> <berekening> |                                                              <berekening> <operator> <getal> |                                                              (<berekening>) 

<operator>      ::=  + | – | × | ÷

Uitbreiding: Grammatica voor berekeningen met haakjes

Met deze uitbreiding is 2 × (3 + 1) ook een correcte berekening.

Bewijs

<berekening>
<getal> <operator> <berekening>

2 × (<berekening>)

2 × (<getal> <operator> <getal>)

2 × (3 + 1)

Zelf werken met grammatica's

Maak uit Fundament:

•  Vraag 1 en 2 van 3.4
•  Vraag 1 en 2 van 3.5

Ter illustratie doen we de eerste
opgave klassikaal.

Tip: gebruik het interactieve element.

Leerdoel gehaald?

Je kunt een grammatica gebruiken om een taal te beschrijven, deze noteren in Backus-Naurvorm, en vaststellen of bepaalde woorden voldoen aan een gegeven grammatica.

Voor de volgende les

Fundament

• Lees B4 - hoofdstuk
   3.1 t/m 3.5 door.
• Maak vraag 1 en 2
   van hoofdstuk 3.4.
• Maak vraag 1 en 2
  
   van hoofdstuk 3.5.

Grammatica's

Verschillende soorten
grammatica's

Leerdoel

Je kunt de BNF's voor verschillende soorten grammatica's uitleggen en gebruiken. Ook ben in je in staat om een grammatica aan te passen en uit te breiden. Tenslotte kun je uitleggen wanneer je een BNF gebruikt en wanneer een eindige automaat.

Terugblik: Grammatica voor berekeningen met haakjes

Vorige les hebben we een grammatica behandeld voor berekeningen waarin haakjes voor kunnen komen:

<berekening>  ::=  <getal> <operator> <getal> |

                              <getal> <operator> <berekening> |                                                              <berekening> <operator> <getal> |                                                              (<berekening>) 

<operator>      ::=  + | – | × | ÷

Terugblik: Grammatica voor berekeningen met haakjes

Met deze grammatica is bijv. 2 × (3 + 1) ook een correcte berekening.

Bewijs

<berekening>
<getal> <operator> <berekening>

2 × (<berekening>)

2 × (<getal> <operator> <getal>)

2 × (3 + 1)

Soorten grammatica's

We gaan ons blik nu richten op grammatica's voor:

• Getallen
• Programmeertalen
• Variabelenamen
• Toekenningen
  

Grammatica voor getallen

Getallen zijn opgebouwd uit de cijfers 0 t/m 9. Dat kun je zo noteren:
<cijfer> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9                of als volgt:
<cijfer> ::= 0 | 1 | … | 9

Positieve gehele getallen zijn opgebouwd uit een of meer cijfers:

<positief geheel getal> ::= <cijfer> |

                                          <cijfer><positief geheel getal>

<cijfer>                          ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Grammatica voor programmeertalen

Hoe maak je een grammatica
voor deze code?

Je hebt regels nodig voor het noteren van het gebruik van if en elif, de voorwaarde, het inspringen en voor de toekenning.

Grammatica voor programmeertalen

Bijvoorbeeld een grammatica
voor een toekenning

<toekenning>  ::=  <variabele> = <uitdrukking>

• Eerst een grammatica voor variabele
  
• Daarna een grammatica voor uitdrukking
  

Welk codevoorbeeld is er sprake van een toekenning, volgens de grammatica in de tekst:

<toekenning> ::= <variabele> = <uitdrukking>

1. prijs = 5, btw = 1.21
2. som += huidig
3. totaal = prijs * btw
4. return False

Grammatica voor een variabelenaam

Een variabelenaam mag bestaan uit hoofdletters, kleine letters, cijfers en underscores ( _ ). keywords (if, elif en else) zijn niet toegestaan. 

<variabele>  ::=  <teken> |
                           <teken><variabele>        behalve if, elif en else
<teken>       ::=  _ |

                         <letter> |

                         <cijfer>

Ook mag een variabelenaam niet beginnen met een cijfer. Waarom niet?

1. Omdat variabelen altijd met een letter moeten beginnen.
2. Omdat programmeertalen geen cijfers toestaan in variabelen.
3. Omdat dit verwarring kan veroorzaken met numerieke waarden.
4. Omdat het de code moeilijker leesbaar maakt voor mensen.

Begin variabelenaam geen cijfer?

Een variabelenaam mag niet beginnen met een cijfer omdat je dan een variabelenaam kunt maken die helemaal uit cijfers bestaat. En dan kun je niet meer zien of je met een variabele of met een getal te maken hebt.

Een variabelenaam moet dus altijd ten minste een letter of underscore
( _ ) bevatten. Vrijwel alle programmeertalen hebben als regel dat er aan het begin een letter of underscore moet staan. 

Complete grammatica voor een variabelenaam

<variabele>       ::=  <letter> | _ |

                                <letter><tekenreeks> | _<tekenreeks>      
                                behalve if, elif en else

<tekenreeks>    ::= <teken> |

                               <teken><tekenreeks>
<teken>             ::=  _ |

                               <letter> |

                               <cijfer>

Complete grammatica voor een variabelenaam

Welke variabele is geldig volgens deze grammatica? _h4ll0, 32test, the_end? of $tartUp?

<variabele>       ::=  <letter> | _ |

                                <letter><tekenreeks> | _<tekenreeks>      
                                behalve if, elif en else

<tekenreeks>    ::= <teken> |

                               <teken><tekenreeks>
<teken>             ::=  _ |

                               <letter> |

                               <cijfer>

Welke variabele is geldig volgens de grammatica?

1. _h4ll0
2. 32test
3. the_end?
4. $tartUp

Grammatica voor programmeertalen

Onze grammatica:

<toekenning>  ::=  <variabele> = <uitdrukking>

• We hebben al een grammatica voor variabele
  
• Nu nog een grammatica voor uitdrukking

Grammatica voor een uitdrukking

Er zijn heel veel soorten uitdrukkingen, we beperken ons hier tot:

• een losse waarde, bijvoorbeeld
   prijsMetKorting = 4.20
  
• een losse variabele, bijvoorbeeld
   prijsMetKorting = prijs
• een combinatie daarvan, bijvoorbeeld
   prijsMetKorting = prijs * 0.95 – 0.20

Grammatica voor een uitdrukking

Een grammatica voor deze uitdrukking:

<uitdrukking>  ::= <waarde> |
                             <variabele> |
                             <uitdrukking> <operator> <uitdrukking> |                                                     (<uitdrukking>)

<operator>     ::=  + | – | * | /

<waarde>       ::=  <kommagetal> | <geheel getal>

Grammatica voor een toekenning

BNF en eindige automaten

Grammatica voor variabelenaam is best uitgebreid:

<variabele>       ::=  <letter> | _ |

                                <letter><tekenreeks> | _<tekenreeks>      
                                behalve if, elif en else

<tekenreeks>    ::= <teken> |

                               <teken><tekenreeks>
<teken>             ::=  _ |

                               <letter> |

                               <cijfer>

Opdracht: BNF en eindige automaten

Teken een automaat die de grammatica van een variabele zo goed mogelijk beschrijft.

<variabele>       ::=  <letter> | _ |

                                <letter><tekenreeks> | _<tekenreeks>      
                                behalve if, elif en else

<tekenreeks>    ::= <teken> |

                               <teken><tekenreeks>
<teken>             ::=  _ |

                               <letter> |

                               <cijfer>

Hoeveel transities heb je minimaal nodig voor deze automaat?

Antwoord: BNF en eindige automaten

Soms kan het een stuk korter als een eindige automaat. Vergelijk het voortgaande eens met:

Vergelijk tussen BNF en eindige automaat 

<variabele>       ::=  <letter> | _ |

                                <letter><tekenreeks> | _<tekenreeks>      behalve if, elif en else

<tekenreeks>    ::= <teken> |

                               <teken><tekenreeks>
<teken>             ::=  _ |

                               <letter> |

                               <cijfer>

Vergelijk tussen BNF en eindige automaat

• Er moet nog wel bij dat if, elif en else niet mogen
• Op woordniveau zijn automaten soms handiger dan een BNF
• Op zinsniveau is een BNF vrijwel altijd het handigst

Leerdoel gehaald?

Je kunt de BNF's voor verschillende soorten grammatica's uitleggen en gebruiken. Ook ben in je in staat om een grammatica aan te passen en uit te breiden. Tenslotte kun je uitleggen wanneer je een BNF gebruikt en wanneer een eindige automaat.

Voor de volgende les

Fundament

• Lees B4 - hoofdstuk
   3.6 t/m 3.10 door.
• Maak vraag 2 van hoofdstuk 3.8.
• Maak vraag 1 en 2 van
   hoofdstuk 3.9.