Cvičení 9, Fronta, Stavový automat

• 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

• 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

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

• 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

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.

• 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

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.

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