Zkouška 30. 1. 2020

[NeverNotBluu]

Téma: Makroprocesor s parametry

Vstupem je soubor, jehož jméno je jediným parametrem příkazové řádky.
Vstupní soubor se zpracovává po řádkách, ve vstupním pořadí.
Zpracovaný soubor vypisujte na standardní výstup.

Každá řádka je dělena na tokeny těchto druhů:

• slovo = posloupnost písmen (std::isalpha)

• číslo = posloupnost číslic (std::isdigit) tvořící kladné celé číslo v dekadickém zápise

• rovnítko = symbol "="

Tokeny jsou odděleny mezerami apod. (std::isspace), ty mohou být i na začátku a konci řádky.

Řádky jsou dvou druhů:

• definice = řádka začínající tokeny slovo a rovnítko. Počáteční slovo definuje název makra, obsahem makra je posloupnost tokenů za rovnítkem (může být i prázdná). Tato posloupnost může obsahovat slova a čísla - ta představují odkazy na parametry makra (číslovány od 1). Nejvyšší číslo vyskytující se za rovnítkem definuje aritu makra. Ne všechny parametry makra musejí být použity (poslední ale bude použit vždy), některé mohou být použity vícekrát.

• normální řádka = řádka obsahující pouze slova.

Definice jsou průběžne ukládány do paměti makroprocesoru. Opakující se definice se stejným názvem jsou povoleny, konkrétní definice je tedy viditelná při zpracování normálních řádek mezi touto definicí a koncem souboru nebo následující definicí stejnojmenného makra. Při ukládání definice se nijak neřeší výskyt názvů maker v definici.

Zpracování normální řádky probíhá vždy zleva doprava.
Pokud je nalezeno slovo shodné s názvem viditelného makra M, je toto slovo z aktuálního obsahu řádky odebráno společně s n dalšími slovy p1..pn, kde n je arita makra M. Odebraná (n+1)-tice slov je nahrazena obsahem makra M, přičemž každé číslo v obsahu makra je nahrazena příslušným slovem z posloupnosti p1..pn. Výsledkem nahrazení makra je tedy vždy posloupnost slov stejně dlouhá jako obsah makra.

Nahrazování maker se opakuje do té doby, dokud se na řádce vyskytuje název viditelného makra, nahrazuje se vždy první výskyt zleva.

Výsledná posloupnost tokenů je, oddělena mezerami, vypsána jako další řádek do výstupního souboru.

Implementace musí přežít bez pádu, zacyklení nebo vyčerpání paměti všechny vstupy včetně vadných. Diagnostika vadných vstupů není vyžadována - výstup programu pro chybné vstupy není předepsán.

Chybné vstupy zahrnují zejména tyto situace:

• řádky nejsou správně tokenizovány nebo obsahují nepovolené znaky

• rovnítko vyskytující se jinde než na druhé pozici

• číslo vyskytující se jinde než za rovnítkem

• použití makra, za kterým nenásleduje dostatečný počet tokenů pokrývající aritu makra

• nekonvergující rekurzivní aplikace makra

Rekurzi je možno detekovat na základě výskytu některého z těchto jevů:

• řádka se rozvíjením makra příliš prodloužila

• rozvíjení makra na téže pozici se opakuje příliš dlouho

[guest]

Kolik na to bylo času?

[Kwan]

Kolik na to bylo času?

Oficiálně je na zkoušku 4 hodiny, tedy mělo to být od 13:00 do 17:00. Bednárek přišel o asi 5 minut pozdě. Zadávání mu zabralo nějakých 20 minut. Začal jsem na tom pracovat ve 13:30 a odcházel jsem zhruba v 16:45, takže nevím, jestli čas náhodou neprodlužoval.

Přikládám odkaz na moje řešení: https://github.com/Kwantigon/CPP-exam

Komentář od Bednárka: "Uvnitř Macro(size_t p, std::vector<Token> t) chybí move, jinak OK."
(hádám, že jsem měl použít std::move() na std::vector<Token> t)

Ve zkratce:
-načtu řádek ze souboru a zavolám funkci process_line(), která se podívá na první 2 slova (tokeny) a podle toho se rozhodne co udělat
-pokud je druhý token rovnítko, tak jde o definici. Funkce si vyhledá v std::unordered_map<Token, Macro> a přidá nebo modifikuje
-pokud řádek nebyl definice makra, tak se zavolá funkce replace_line()
-tato funkce dostane všechny tokeny na řádku v std::deque (fronta). Vybere první token z fronty a zkusí ho vyhledat.
-pokud ho nenajde, tak přidá token do vector již zpracovaných tokenů, který bude potřeba vypsat.
-pokud najde, tak si z fronty vybere přislušný počet parametrů, které toto makro přijímá a místo toho přidá na vrch fronty tokeny tohoto makra.
-tento postup opakuju dokud nedojde fronta nebo dokud jsem nenahradil už tisíckrát
-na konci zavolám print_tokenized_line() na výstupní vector z funkce replace_line()

Datové struktury:
-k mapování <jméno makra - makro> jsem použil unordered_map, protože potřebuju vyhledat podle stringu a tato mapa nabízí složitost O(1) na vyhledávání (hashuje klíče).
-fronta samozřejmě deque. Hodí se i to, že má náhodný přístup k prvkům v čase O(1).
-výstup z funkce replace_line() je klasický vector, protože nepotřebuju nic speciálního. Jen projít od začátku do konce a vypsat
-třída Macro si jen pamatuje počet parametrů, které přijímá a ve vector si pamatuje, co se má vypsat pokud narazím na to příslušné makro.

Pokud má někdo nejasnosti k mému řešení, tak mi napište zprávu tady na fóru a možná i odpovím. Většinou sem ale chodím jen o zkouškové Nebo mi dejte nějak vědět přes GitHub jestli to jde.