====== Cvičení 9, Fronta, Stavový automat ======

===== náplň cvičení =====

==== Quick test 1 ====

==== Úloha 1 Fronta ====

  * Přeměňte řešení úlohy 3 Flood fill z cvičení 8 na frontu.
  * Postupnou animací zjistěte jak se změnilo vyplňování prostoru
  * Zjistěte, zda potřebuje více paměti zásobník, nebo fronta

==== Úloha 2 Komentáře - rozšíření ====

  * Upravte program na odstraňování komentářů z přednášky tak:
    * aby program bral v úvahu řetězce začínající a končící znakem '
    * aby správně interpretoval znaky \' a \"
    * aby pokud řádka končí znakem \ dovedl řetězec prodloužit přes více řádek
  * Program otestujte na následujících datech
<code>
a='b\'c#d' #e
i="j\"k'l#m" #n
</code>
  * Program z přednášky:
<code python>
def preskoc_komentare(line):
  # vytiskne obsah souboru 'f' s vynechanymi komentari
  stav=0          # počáteční stav automatu
  for c in line:  # přečti jeden znak
    if stav==0:   # počáteční stav
      if c=="#":  # začátek komentáře
        stav=1
        continue        
      elif c=='\"':
        stav=2    # začátek řetězce
    elif stav==1: # 1="komentar"
      continue
    elif stav==2:
      if c=='\"':
        stav=0
    print(c,end="") # vytiskni znak

i=input()
preskoc_komentare(i)  # nacti radku a preskakuj
</code>
==== Úloha 3 Kontrola reálného čísla ====

  * Reálné číslo v pythonu je zadána touto BNF gramatikou:
<code BNF>
floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit+
fraction      ::=  "." digit+
exponent      ::=  ("e" | "E") ["+" | "-"] digit+
digit         ::=  "0"..."9"
</code>
  * Vymyslete a naprogramujte stavový automat, který bude zjišťovat, zda je řetězec na řádce reálným číslem.
  * 
==== Úloha 4 Obsahy závorek ====
  * Uvažujme řetězec obsahující závorky () a [].
  * Napište program, který bude testovat, zda je výraz správně uzávorkován a zjistí text uvnitř závorek
  * Závorky mohou být do sebe vnořeny a pak text patří do poslední úrovně závorek
  * Program tedy text:
<code>
aa[bb(cc)dd(ee)fff[gggg]]hhh
</code>
  * převede na výstup:
<code>
()cc
()ee
[]gggg
[]bbddfff
</code>
  * písmena 'aa' a 'hhh' se zahodí, nejsou uvnitř žádných závorek

  
===== domácí práce =====

==== Lehká varianta:====
  Proveďte lexikální analýzu jedné řádky vstupu, který může obsahovat pouze následující lexikální termy:
    * Dec: decimální číslo 
<code BNF>
decimalinteger ::=  nonzerodigit digit* | "0"+
nonzerodigit   ::=  "1"..."9"
digit          ::=  "0"..."9"
</code>
    * Oct: octalové číslo (číslo v osmičkové soustavě)
<code BNF>
octinteger     ::=  "0" ("o" | "O") octdigit+
octdigit       ::=  "0"..."7"
</code>
    * Bin: binární číslo
<code BNF>
bininteger     ::=  "0" ("b" | "B") bindigit+
bindigit       ::=  "0" | "1"
</code>
    * Hex: hexadecimální číslo (číslo v šestnáctkové soustavě)
<code BNF>
digit          ::=  "0"..."9"
hexinteger     ::=  "0" ("x" | "X") hexdigit+
hexdigit       ::=  digit | "a"..."f" | "A"..."F"
</code>
    * Rea: Reálné číslo - viz úloha 2
    * Str: Pokud není vstup detekován v žádném předchozím případě

  * Komentáře neuvažujte, předpokládejte, že vstup obsahuje pouze písmena, číslice a znaky '+', '-'.
  * Program **number.py** načte jeden řádek standardního vstupu a vytiskne na výstup o jaký lexikální term
  * Program odevzdejte jako úlohu HW09.  
=== Příklad ===
  * Pokud je vstupní program následující kód:
<code>
1245
</code>
  * pak je výstupem:
<code>
Dec
</code>

  * Pokud je vstupní program následující kód:
<code>
0x12FF
</code>
  * pak je výstupem:
<code>
Hex
</code>

  * Pokud je vstupní program následující kód:
<code>
0o123
</code>
  * pak je výstupem:
<code>
Oct
</code>

  * Pokud je vstupní program následující kód:
<code>
0B0101
</code>
  * pak je výstupem:
<code>
Bin
</code>

  * Pokud je vstupní program následující kód:
<code>
1e-25
</code>
  * pak je výstupem:
<code>
Rea
</code>

  * Pokud je vstupní program následující kód:
<code>
0o999
</code>
  * pak je výstupem:
<code>
Str
</code>
==== Těžší varianta:====
Proveďte lexikální analýzu Pythonovského programu, který může obsahovat pouze následující lexikální termy:
  * Str: Řetězec - začíná znaky 
<code>
',",''',""" 
</code> a může obsahovat sekvenci se znakem \.
Pokud obsahuje řetězec sekvenci se znakem \X (X reprezentuje nějaký znak z množiny \,',",+,-), pak se do řetězce vloží pouze znak X. 
    * Int: Celé číslo - integer:
<code BNF>
integer        ::=  decimalinteger | octinteger | hexinteger | bininteger
decimalinteger ::=  nonzerodigit digit* | "0"+
nonzerodigit   ::=  "1"..."9"
digit          ::=  "0"..."9"
octinteger     ::=  "0" ("o" | "O") octdigit+
hexinteger     ::=  "0" ("x" | "X") hexdigit+
bininteger     ::=  "0" ("b" | "B") bindigit+
octdigit       ::=  "0"..."7"
hexdigit       ::=  digit | "a"..."f" | "A"..."F"
bindigit       ::=  "0" | "1"
</code>
    * Rea: Reálné číslo - viz úloha 2
    * Key: Klíčová slova Pythonu
    * Var:Proměnné - začíná písmenem a pak může obsahovat písmena, čísla a znak _
    * Ope: Operátory:
<code>
+       -       *       **      /       //      % 
<<      >>      &       |       ^       ~
<       >       <=      >=      ==      !=
</code>
    * Sep: Oddělovače:
<code>
(       )       [       ]       {       }
,       :       .       ;       @       =       ->
+=      -=      *=      /=      //=     %=      @=
&=      |=      ^=      >>=     <<=     **=
</code>

Zadání úlohy
  * Předpokládejte, že je program syntakticky správně.
  * Komentáře neuvažujte, předpokládejte, že program je bez komentářů.
  * Progam **lexical.py** načte soubor zadaný jako vstupní parametr a vytiskne na výstup jednotlivé lexikální termy
  * Program odevzdejte jako úlohu HW09.
  
=== Příklad ===
  * Pokud je zadaný vstupní soubor následující program:
<code>
def funkce(a,b):
    c=''
    a**=b
    if a<b:
        print('ahoj\'ky',a)
    else:
        print(0xff,0b11101,0o777,.90e-10,123E+5,c)
        print('''To je dlouhy
        retezec pres mnoho
        radku''')
funkce(-256+356,.85**.33)
</code>
  * pak je výstupem Vašeho programu:
<code>
Key: def
Var: funkce
Sep: (
Var: a
Sep: ,
Var: b
Sep: )
Sep: :
Var: c
Sep: =
Str: 
Var: a
Sep: **=
Var: b
Key: if
Var: a
Ope: <
Var: b
Sep: :
Var: print
Sep: (
Str: ahoj'ky
Sep: ,
Var: a
Sep: )
Key: else
Sep: :
Var: print
Sep: (
Int: 0xff
Sep: ,
Int: 0b11101
Sep: ,
Int: 0o777
Sep: ,
Rea: .90e-10
Sep: ,
Rea: 123E+5
Sep: ,
Var: c
Sep: )
Var: print
Sep: (
Str: To je dlouhy
        retezec pres mnoho
        radku
Sep: )
Var: funkce
Sep: (
Ope: -
Int: 256
Ope: +
Int: 356
Sep: ,
Rea: .85
Ope: **
Rea: .33
Sep: )
</code>