Warning
This page is located in archive.

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

a='b\'c#d' #e
i="j\"k'l#m" #n

  • Program z přednášky:

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

Úloha 3 Kontrola reálného čísla

  • Reálné číslo v pythonu je zadána touto BNF gramatikou:

floatnumber   ::=  pointfloat | exponentfloat
pointfloat    ::=  [intpart] fraction | intpart "."
exponentfloat ::=  (intpart | pointfloat) exponent
intpart       ::=  digit+
fraction      ::=  "." digit+
exponent      ::=  ("e" | "E") ["+" | "-"] digit+
digit         ::=  "0"..."9"

  • 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:

aa[bb(cc)dd(ee)fff[gggg]]hhh

  • převede na výstup:

()cc
()ee
[]gggg
[]bbddfff

  • 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 

decimalinteger ::=  nonzerodigit digit* | "0"+
nonzerodigit   ::=  "1"..."9"
digit          ::=  "0"..."9"

  • Oct: octalové číslo (číslo v osmičkové soustavě)

octinteger     ::=  "0" ("o" | "O") octdigit+
octdigit       ::=  "0"..."7"

  • Bin: binární číslo

bininteger     ::=  "0" ("b" | "B") bindigit+
bindigit       ::=  "0" | "1"

  • Hex: hexadecimální číslo (číslo v šestnáctkové soustavě)

digit          ::=  "0"..."9"
hexinteger     ::=  "0" ("x" | "X") hexdigit+
hexdigit       ::=  digit | "a"..."f" | "A"..."F"

  • 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:

1245

  • pak je výstupem:

Dec

  • Pokud je vstupní program následující kód:

0x12FF

  • pak je výstupem:

Hex

  • Pokud je vstupní program následující kód:

0o123

  • pak je výstupem:

Oct

  • Pokud je vstupní program následující kód:

0B0101

  • pak je výstupem:

Bin

  • Pokud je vstupní program následující kód:

1e-25

  • pak je výstupem:

Rea

  • Pokud je vstupní program následující kód:

0o999

  • pak je výstupem:

Str

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

',",''',""" 
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:

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"

  • 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:

+       -       *       **      /       //      % 
<<      >>      &       |       ^       ~
<       >       <=      >=      ==      !=

  • Sep: Oddělovače:

(       )       [       ]       {       }
,       :       .       ;       @       =       ->
+=      -=      *=      /=      //=     %=      @=
&=      |=      ^=      >>=     <<=     **=

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:

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)

  • pak je výstupem Vašeho programu:

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: )

courses/b3b33alp/cviceni/t09.txt · Last modified: 2018/11/26 00:01 by stepan