Talen en automaten/2011-12/producten/Python

Uit Werkplaats
Ga naar: navigatie, zoeken
Page Break




Algolfrag.jpg

Talen en automaten

Erik Barendsen

 © comments



Python

Tim van Lent, Rik de Kort



Talen en automaten 2011-12



15:25 A






Tim van Lent
 e-mail 

cursuspagina

Bestand:Tim van Lent.jpg

Rik de Kort
 e-mail 

cursuspagina

Bestand:Rik de Kort.jpg
Page Break





Beschrijving

Python is een programmeertaal die gebouwd is in C met het idee dat een programmeertaal leesbaar moet zijn. Waar programmeertalen als C++, Java en Perl dan ook haken, ogen of puntkomma's gebruiken om blokken code en statements van elkaar te onderscheiden, heeft Python in een meer natuurlijke syntax. Voor een duidelijk overzicht van de verschillen tussen Python en andere populaire programmeertalen bekijken we een voorbeeld, hetzelfde programma in C++ als in Python. 

   #include <iostream>
   using namespace std;

   void hello_world()
   /*
      Print de tekst:
      "Hello world!"
   */
   {
       cout << "Hello world!\n"; //Dag wereld.
   }

   int main()
   {
       hello_world();
       return 0;
   }


   def hello_world():
   """
      Print de tekst:
      "Hello world!"
   """
       print "Hello world!" #Dag wereld.

   hello_world()

Het eerste verschil dat opvalt is dat Python geen include-statements aan het begin van het programma heeft. Python vereist alleen include-statements voor speciale functies, zoals reguliere expressies en sinussen. Verder hoeft in Python ook niet duidelijk te zijn welke namespace er gebruikt wordt; dit doet Python zelf. Vervolgens komen we aan bij de functiedefinitie. Python gebruikt hier een sleutelwoord voor, dat hetzelfde is, ongeacht de functie. C++ vereist hier aan te geven wat voor een type waarde de functie terug zal geven. In Python maakt dit niet uit. In Python gebruikt men vervolgens een dubbele punt en een indent om het blok aan te geven (het maakt overigens niet uit of de indent uit spaties of tabs bestaat). Voor C++ gebruikt men accolades rondom het blok. Om een statement te eindigen vereist C++ een puntkomma. In Python is dit simpelweg een nieuwe regel, hoewel een puntkomma niet leidt tot fouten. Ook voegt Python automatisch een newline toe aan ieder print statement, hoewel dit te voorkomen is. Commentaar wordt in Python aangegeven met een hekje, waarin deze taal dus afwijkt van de meeste programmeertalen. Commentaar over meerdere regels wordt aangegeven met drie dubbele quotes, in tegenstelling tot de gebruikelijke slash gevolgd door een asterisk. Vooraf gedefinieerde functies dient men in C++ aan te roepen vanuit de functie main(). In Python is een programma (tenzij dit wordt overreden) altijd bevat in een main()-functie. Het aanroepen van de functie hello_world is vervolgens identiek (op de puntkomma na). In C++ volgt nog een return-statement voor de main() functie. Python vereist dit niet.

Voor ons werkstuk is vooral de eigenschap dat Python blokken code scheidt met behulp van indents belangrijk. Hij is namelijk indent-gevoelig. Dat wil zeggen dat de volgende code niet wordt geaccepteerd: 

   if true:
        if true:
   if true:
   print "Great Succes!"

Een if-statement dient (zoals gebruikelijk bij alle programmeertalen) gevolgd te worden door een voorwaarde (boole), waarna een dubbele punt en een newline volgt. Vervolgens moet de code na de if (die wordt uitgevoerd als aan de voorwaarde voldaan is) inspringen. Hoe dit wordt gedaan is meestal niet van belang, zolang de indents maar van hetzelfde type zijn (dus of alleen tabs, of alleen 4 spaties, of alleen 5 spaties, etc.). Als de code niet wordt ingesprongen zal de code niet compileren.

De volledige grammatica van Python is hier te vinden.

Regulier?

We vatten Python op als de verzameling van alle series symbolen die syntactisch correct in Python zijn.

Stelling: Python is een niet reguliere taal.

Bewijs: Stel, Python is regulier. Dan is er een automaat die deze taal accepteert, met k states. We nemen nu een woord uit Python, en wel het volgende: 

   if true:
       if true:
           if true:
               ...
                   if true:
                       print "Great success!"

Waarbij het aantal if-statements groter is dan k. Volgens het pomplemma voor reguliere talen is het woord pompbaar en zit het pompbare deel binnen de rij if-statements (aangezien de lengte van deze rij groter is dan k). Nu gaan we dit deel pompen. Echter, we krijgen nu aan het eind van het pompbare deel een if-statement gevolgd door een if-statement met een kleinere indent, terwijl volgens Python's grammatica een if-statement altijd moet worden gevolgd door een deel code met een grotere indent. Een voorbeeld van het pompbare woord (als k = 2): 

   if true:
       if true:
        print "Great success!";

Om de theorie hierop toe te passen, kun je de if true: met de newline opvatten als woord a en de indent als element b (indents kun je namelijk wel zien als element van het alfabet wat in python wordt gebruikt). Als dan 'print "Great succes!"' woord c is, dan is het woord van het voorbeeld. abab...abkc. Deze wordt geaccepteerd door Python. Stel Python is een reguliere taal, dan geldt volgens het pomplemma:

  • |y| > 0
  • |xy| ≤ k
  • Voor alle n ≥ 0, xynz behoort tot Python.

Dan zou in xynz tot Python behoren. |abk| > k, dus y geen elementen van c bevatten. y kan dus de volgende vormen hebben

  1. bpabiabi+1...abjabq met 0 ≤ p < i ≤ j en q ≤ j+1 of i = j = 0 met p < q
  2. vbiabi+1...abjw met v een deel van a en w een deel van a (met deel wordt bedoeld dat bijv. a = zvl), waarbij 0 ≤ i ≤ j
  3. bp met 0 < p
  4. bpabq met 0 < p ≤ q of p = 0 < q

Merk op dat |y| > 0, dus y is niet het lege woord.

  • Als y van vorm (1) of vorm (2) me i > 0 is, dan zal er altijd in voorkomen abpabq met p ≥ q ≥ 0 als n > 2. Dit wordt niet geaccepteerd door Python, want Python is indent gevoelig.
  • Als y van vorm (2) en i = 0, dan wordt y2 niet geaccepteerd in Python.
  • Als y van de vorm (3) of (4) dan is er een deel abqa in z, zodat er is een n > 0 zodat yn een bm bevat met m ≥ q > 0 (er is een b in y, dus uit het originele woord volgt q > 0). Dit wordt niet geaccepteerd door Python, want Python is indent gevoelig en |xy| < k.

Voor alle mogelijke y kan het niet. Hieruit volgt dat Python geen reguliere taal is.

Regulier? Alternatief

We vatten Python op als de verzameling van alle series symbolen die syntactisch correct in Python zijn.

Stelling: Python is een niet reguliere taal.

Bewijs: Stel, Python is regulier. Dan is er een automaat die deze taal accepteert, met k states. We nemen nu een woord w uit Python, en wel het woord met een aantal herhaalde haakjes openen, gevolgd door "1+1" en het daarna evenveel haakjes sluiten als haakjes openen:

w = (((...((1+1))...))

We nemen het aantal haakjes openen gelijk aan k. Volgens het pomplemma voor reguliere talen geldt nu:

  • w = xyz, waarbij Lengte(xy) ≤ k en Lengte(y)≥ 1
  • xy iz zit in Python voor alle positieve i.

Omdat we k haakjes openen hebben, volgt dat xy van de vorm (((...((( is en dat y minimaal één haakje openen bevat. Stel, het aantal haakjes openen in x is i en in y is j. Daaruit volgt dat z van de vorm 1+1)))...))) of ((..((1+1)))...))) is. Alle haakjes sluiten zijn dus in z bevat. Stel dat het aantal haakjes openen in z gelijk is aan l. Er geldt voor het woord w dat i+j+l=k.

Volgens het pomplemma geldt nu ook dat xy 2 z in Python zit. Echter, het aantal haakjes openen in dit gepompte woord is j+2i+l = k+i > k, omdat i≥1. Echter, het aantal haakjes sluiten is nog steeds k, omdat er niets met z is gebeurd. Dit woord is dus syntactisch incorrect en dus geen onderdeel van Python. Tegenspraak, dus Python is niet-regulier.

Contextvrij?

Python is een contextvrije taal, omdat de beschrijvende grammatica, die te vinden is op de website en gebruikt wordt voor het parsen van Python-programma's, een contextvrije grammatica is. Het is dan ook geen uitdaging om aan te tonen dat Python zelf contextvrij is. Wij kiezen er dan ook voor Python uit te breiden, en wel met een serie functies en constanten uit de math-module. Een lijst met functies, expressies en constanten hierin kan hier gevonden worden.

Omdat er geen grammatica voor de functies in deze module beschikbaar is, zullen we deze zelf moeten implementeren om te bewijzen dat Python met deze uitbreiding nog steeds contextvrij is.


We weten dat de functies etc. uit de module gebruikt moeten kunnen worden in een blok code, waarvoor in de grammatica de nonterminal 'suite' wordt gebruikt. Dit geeft aanleiding tot het bekijken van de volgende regels: 

   suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT
   simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE   
   stmt: simple_stmt | compound_stmt
   small_stmt: (expr_stmt | print_stmt  | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | exec_stmt | assert_stmt)
   expr_stmt: testlist (augassign (yield_expr|testlist) | ('=' (yield_expr|testlist))*)
   augassign: ('+=' | '-=' | '*=' | '/=' | '%=' | '&=' | '|=' | '^=' | '<<=' | '>>=' | '**=' | '//=' )
   testlist: test (',' test)* [',']
   test: or_test ['if' or_test 'else' test] | lambdef
   or_test: and_test ('or' and_test)*
   and_test: not_test ('and' not_test)*
   not_test: 'not' not_test | comparison
   comparison: expr (comp_op expr)*
   expr: xor_expr ('|' xor_expr)*
   xor_expr: and_expr ('^' and_expr)*
   and_expr: shift_expr ('&' shift_expr)*
   shift_expr: arith_expr (('<<'|'>>') arith_expr)*
   arith_expr: term (('+'|'-') term)*
   term: factor (('*'|'/'|'%'|'//') factor)*
   factor: ('+'|'-'|'~') factor | power
   power: atom trailer* ['**' factor]
   atom: ('(' [yield_expr|testlist_comp] ')' | '[' [listmaker] ']' | '{' [dictorsetmaker] '}' | '`' testlist1 '`' | NAME | NUMBER | STRING+)

De meest logische nonterminal om aan te passen is 'atom'. De redenering is als volgt: Een suite bestaat uit één simple statement (simple_stmt), of een block code dat bestaat uit één of meer statements (stmt). Er zijn twee typen statements: simple (simple_stmt) en compound (compound_stmt). De tweede is niet relevant, want deze dekt if-, while-, for-, try- en with-statments, alsmede class- en functiedefinities en decorators, welke allemaal niet van toepassing zijn op de functies en constanten in de module. We bekijken dus simple_stmt. Dit bestaat uit een serie van small statements (small_stmt), gescheiden door puntkomma's en eindigend met een newline. Bij small_stmt is enkel expr_stmt belangrijk, omdat de andere statements corresponderen met Python's ingebouwde functies. expr_stmt begint altijd met een testlist (daar komen we zo op terug), gevolgd door een van de volgende:

  • Een augmented assignment operator (augassign: '+=', '/=', etc.) gevolgd door testlist of een yield-expressie (de laatste is niet relevant)
  • Een reeks gewone assignment operators ('=') die gevolgd worden door een testlist of een yield-expressie

We komen nu aan bij de nonterminal testlist, wat een lijst van nonterminals test is, gescheiden door komma's. Een test stelt veel verschillende dingen voor en is in principe de rest-nonterminal, waarin alles wat nog niet aan de orde is gekomen wordt afgevangen. De nonterminal lambdef is niet relevant voor onze vraag, dus we gaan het rijtje or_test, and_test, not_test, etc. af. We komen vervolgens uit bij comparison: een vergelijking. Deze bestaat uit een expressie (expr) gevolgd door eventueel een aantal comparison operators met expressies (dus van de vorm 'f == o <= o >= bar' of 'f').

We gaan dus het rijtje expr, xor_expr, and_expr, shift_expr, arith_expr, term, factor, power af. Dit correspondeert met steeds kleinere stukjes van eerst logische expressies en daarna arithmetische expressies. Power is een nonterminal om expressies als math.pi() toe te staan, waarbij een naam wordt gevolgd door een punt, door nog een naam om subklassen aan te duiden.

We komen nu dus bij atom uit. Dit kan enkele dingen zijn: een tupel, een lijst, een dictionary (Python's versie van een hashtable), een lijst, een printbare representant van een object, een naam, een getal of een string.

We zullen nu de grammatica zo uitbreiden dat de functies in de math-module ook hierin terugkomen. We beginnen bij de nonterminal atom: 

   atom: ('(' [yield_expr|testlist_comp] ')' | '[' [listmaker] ']' | '{' [dictorsetmaker] '}' | '`' testlist1 '`' | NAME | NUMBER | STRING+ | math_stmt)

We hebben nu een nonterminal math_stmt voor alle math-functies, expressies en constanten. Deze roept men aan door, afhankelijk van de manier van importeren van de module math.f() te gebruiken, of simpelweg f(). We nemen voorlopig aan dat math.f() wordt gebruikt. 

   math_stmt: 'math.' ( math_func | math_cnst )
   math_func: ( 'ceil(' test ')' ) | ( 'copysign(' test ',' test ')' ) | ( 'fabs(' test ')' ) | ( 'factorial(' test ')' ) |
       ( 'floor(' test ')' ) | ( 'fmod(' test ',' test ')' ) | ( 'frexp(' test ')' ) | ( 'fsum(' (comp_iter | list_iter) ')' ) |
       ( 'isinf(' test ')' ) | ( 'isnan(' test ')' ) | ( 'ldexp(' test ',' test ')' ) | ( 'modf(' test ')' ) | ( 'trunc(' test ')' ) |
       #Maak maar af.
   math_cnst: 'pi' | 'e'

Omdat we zojuist een contextvrije grammatica voor Python uitgebreid met de math-module hebben gecreëerd, kunnen we concluderen dat deze taal contextvrij is.

Overgenomen van "https://lab.cs.ru.nl/algemeen/index.php?title=Talen_en_automaten/2011-12/producten/Python&oldid=177234"