Програмски преводиоци 1/Пројекат

Пројекат на предмету важи за једну од најтежих активности на њему због тога што захтева практичну примену знања стечених у трећем блоку (и понеких из првог и другог блока). Његова израда може захтевати око недељу дана константног рада (у зависности од нивоа за који радите) али се такође велики део тога може искористити из постојећих материјала са вежби и званичних видео водича за пројекат, на које ће се овај водич надаље ослањати.

Основно

Идеја пројекта јесте конструкција преводиоца за Микројаву — поједностављену, школску варијанту језика Јава чија се спецификација помало мења из године у годину (али неке суштинске ствари остају исте). Преводилац из једног фајла са изворним кодом чита Микројава код по спецификацији датој уз текст пројекта (а одвојеној од саме поставке), пролази кроз четири фазе превођења (лексичку анализу, синтаксну анализу, семантичку анализу и генерисање кода) и његов крајњи резултат јесте објектна датотека са Микројава бајткодом. Тај објектни фајл се затим може извршавати преко Микројава виртуелне машине (чија је имплементација већ дата и не може се мењати) и на основу неког уноса произвести неки излаз.

За пројекат је потребно гледати вежбе трећег блока из табеле симбола и Микројава виртуелне машине, и евентуално вежбе првог и другог блока из JFlex и CUP. Такође су доступни видео водичи за пројекат са странице предмета, које је корисно погледати као увод у алате и нека генерална очекивања. Ти водичи су енкодовани неким јако застарелим кодеком, а реенкодовани снимци се могу наћи овде.

Пре него што пређете на даље одељке, препоручује се да прочитате поставку пројекта. Микројава спецификацију не морате читати, јер ће вам она највише значити приликом самог развијања пројекта.

Поставка

Сада када сте прочитали поставку, о њој је потребно рећи пар речи.

• Структура пројекта уопште не мора да буде онаква каква пише у поставци. То значи:
  • Пакет не мора да се зове rs.ac.bg.etf.pp1.
  • Не постоји конкретан директоријум у који морате да сместите спецификације лексера и парсера.
  • Није обавезно коришћење JDK 1.8 (мада је препоручено)
  • Класе не морају да се зову Compiler, SemanticAnalyzer и CodeGenerator.
• На одбрани се мање-више гледа само излаз преведеног Микројава програма за модификацију и за јавни тест одговарајућег нивоа за који радите. Ово у пракси значи:
  • Нико неће проверавати формат грешке лексера.
  • Нико неће проверавати да ли се успешно ради опоравак од грешке.
    • Ипак, препоручује се да пробате овај део да одрадите, али ако на неком месту не ради то није велики проблем.
  • Нико неће проверавати да ли нисте користили precedence (али нико неће ни објаснити како се користи).
  • Нико неће проверавати како су именовани нетерминали нити класе које одговарају гранама тих нетерминала.
  • Нико неће проверавати да ли сте додали акције у спецификацију парсера.
    • Свакако се препоручује да потребне акције обављате кроз одговарајуће посетиоце стабла, јер у спецификацији парсера није доступан IntelliSense.
  • Није много вероватно да ће предметни сарадници погледати да ли користите њихову табелу симбола, да ли сте је распаковали и превели поново или користите неку потпуно другу имплементацију.
    • Ипак, коришћење њихове табеле симбола носи са собом погодност да ћете увежбати рад са њом па нећете много морати да обнављате за такве задатке на испиту.
  • Нико неће проверавати да ли сте имплементирали методу tsdump().
  • Нико неће проверавати да ли исписујете симболе при њиховој детекцији.
  • Слабо ће се проверавати да ли се пријављују семантичке грешке.
    • Ипак, пошто током семантичке обраде свакако мора да се попуни табела симбола, вреди додати ове провере, у крајњем случају зато што ће вама значити уколико будете писали своје тест примере и напишете нешто семантички неисправно.
    • Може да се деси да неке ствари из јавних тестова или тестова за модификације које су закоментарисане морају да пријаве семантичке грешке, и да их предметни сарадници откоментаришу приликом одбране.
  • Нико неће проверавати да ли се путање до улазних и излазних фајлова прослеђују кроз аргументе командне линије.
• На одбрани се не тражи да се било шта покреће из командне линије, нити преусмерава стандардни излаз и излаз за грешке.
• Примери Микројава кода из поставке и спецификације могу често бити синтаксно или семантички неисправни. Ово је због тога што предметни сарадници не напишу преводилац за спецификацију Микројаве коју су задали, а пример вероватно ископирају из поставке односно спецификације од претходне године, па не провере да ли је исправан.
• На одбрани нико не погледа извештај са пројекта.
• Нико неће тражити да се покрену студентски тестови пројекта.
• Супротно поставци, дорада пројеката на одбрани је дозвољена.
• У одељку за контекстне услове у оквиру спецификације могу бити описане ствари које се не раде у фази семантичке анализе, већ или описују генерално функционисање тог програмског конструкта, или описују ствари које се морају обезбедити у фази генерисања кода.
• Приликом спецификације синтаксе користи се EBNF нотација.
• Подела функционалности по нивоима може бити јако конфузна. Спецификација Микројаве може посебно напоменути за само пар ствари да се имплементирају само на одређеним нивоима (остављајући утисак да је потребно препознати синтаксу за методе и класе чак и у пројекту А нивоа), док поставка може непотпуно излиставати смене које су потребне да се имплементирају за одређени ниво. Најбољи начин за одређивање шта се имплементира за који ниво јесу одговарајући јавни тестови.

Алати

У овом одељку наведене су све напомене у вези са алатима које ћете користити на пројекту, од којих ће неке имати смисла тек након што погледате видео водиче.

• Неколико ствари из видео водича урађено је на неоптималан начин:
  • Једна од првих ствари поменутих у видео водичима јесте инсталирање Ant. За овиме нема потребе, јер је Ant већ инсталиран у оквиру Eclipse. Такође, Ant правила се доста лакше могу покретати одласком на Window → Show View → Ant, и затим бирањем build.xml фајла из пројекта.
  • Уколико крећете од кода из видео водича, могуће је да ће вам избацивати deprecation упозорења поводом коришћења new Integer() конструктора. Ово можете заменити са Integer.parseInt().
  • Бројање параметара и локалних променљивих коришћењем VarCounter и FormParamCounter није заправо потребно, већ их можете бројати приликом обиласка тих чворова стабла.
  • На неколико места се користи Tab.insert() ради прављења Obj чвора који нема потребе заправо убацивати у табелу симбола. Уместо овога, могу се користити регуларни конструктори за Obj.
• У рачунарским лабораторијама би требало да је доступан и IntelliJ, па можете у њему такође радити пројекат.
• Обавезно преузети библиотеке са странице предмета уместо коришћења оних из шаблона пројекта или видео водича, јер њихове верзије могу бити застареле и проузроковати проблеме.
• Унос са стандардног улаза неће радити уколико се преведени Микројава програм покреће кроз Ant, па је потребно додати директиву <redirector input="input.txt" /> како би се стандардни улаз читао из датотеке input.txt која се налази у кореном директоријуму пројекта.
  • На овај исти начин могу се преусмерити стандардни излаз и излаз за грешке: <redirector input="input.txt" output="output.txt" error="error.txt" />
  • Уколико уместо овога програм покренете кроз командну линију, могуће је да ћете морати да различите податке за унос (преко read и bread инструкција) пишете у истом реду (уместо у новим редовима).
• Није неопходно користити Log4j библиотеку за испис уколико не желите.
• Подразумевано, Log4j библиотека неће исписивати на излаз за грешке већ на стандардни излаз, чак и кад су у питање поруке са грешкама. Ово може да се конфигурише, али свакако нико неће обраћати пажњу на то на одбрани.
• Уколико добијете Cannot invoke "java.net.URL.toString()" because "this.val$url" is null грешку, пробајте да линију DOMConfigurator.configure(Log4JUtils.instance().findLoggerConfigFile()); замените са DOMConfigurator.configure("config/log4j.xml");.
• Грешка за непостојећи log4j.dtd се може игнорисати.
• Не заборавите да на све <java> елементе у build.xml додате fork="true" атрибут, јер ће се иначе те ставке покретати из неког директоријума који није корени директоријум пројекта.

Фазе израде

Лексичка анализа

• Да бисте почели са развојем ове фазе не морате куцати свој sym.java фајл, већ се он може генерисати из CUP спецификације чим покренете parserGen правило у Ant, уколико сте све своје терминале написали у CUP спецификацији (terminal).
• Ова фаза је најлакша и могуће ју је урадити за само пар сати, али је битно урадити је како треба. Грешке у лексеру могу изазвати проблеме приликом парсирања, само што лексер у том тренутку може бити место на којем ћете најмање посумњати да се налази грешка. Постоји неколико ствари на које треба обратити пажњу:
  • Генералнија правила иду на дно. На пример, уколико се правило за if налази испод правила за детекцију идентификатора, лексер ће if препознати као идентификатор и зато ће парсер избацити грешку приликом парсирања if наредбе.
  • На само дно убацити једно match-all правило (као што је урађено у видео водичу). Уколико то не урадите, лексер ће избацити Error: could not match input грешку уколико се наиђе на карактер који није у спецификацији Микројаве, што само по себи није проблем, али вам ваша сопствена грешка може дати више информација о томе где је тачно проблем.
  • Уколико радите на оперативном систему Linux или macOS, потребно је одвојити правило за \r\n на правила за \r и \n како би их правилно игнорисао.
  • У видео водичу се за препознавање идентификатора користи ([a-z]|[A-Z])[a-z|A-Z|0-9|_]* регуларни израз, где је карактер | грешком дозвољен у оквиру идентификатора, док је правилно [a-zA-Z][a-zA-Z0-9_]*. Ово је мала грешка, али може направити проблем приликом конструката попут a||b, који ће бити препознати као један идентификатор уместо два идентификатора са оператором између њих.

Синтаксна анализа

• Најважније правило током развоја ове фазе јесте да сва правила пишете корак по корак и са тестирањем између. Током развоја алати могу пријавити грешке које вам ни на који начин не сугеришу где је заправо проблем, и такве грешке је далеко лакше пронаћи уколико знате који део синтаксе је тестиран и ради, а који је новододат. Ово значи да када преузмете пројекат из видео водича обришете све смене из њега (осим једне, попут Program ::= PROG;, како би генерисање парсера уопште радило) и кренете са додавањем смена редом по спецификацији. Кад видите да сте додали неку мању али потпуну целину, тестирајте да ли то што сте додали ради. Ако не ради, уклањањем и враћањем делова које сте додали можете лоцирати где је тачно изазвана грешка. Овакав начин развоја помоћи ће и вама и људима које питате за помоћ око евентуалних грешки.
• Када кренете са развојом ове фазе, најбоље је да уопште не постављате називе класа на нетерминалима. Ови називи класа се много лакше постављају након што сте већ развили целу граматику (пре следеће фазе) и имате цео контекст, а њихово додавање током развоја граматике може изазвати неке од честих грешки. Исто тако, нема потребе додељивати типове терминалима и нетерминалима док не стигнете до следеће фазе, већ је довољно само декларисати их.
  • Уколико сте ово покушали да радите и наишли на грешке, њихова решења ће бити објашњавана у следећем одељку.
• Како се у оквиру ове фазе такође ради и опоравак од грешке, вредно је напоменути да је сврха тог опоравка да се пријаве све постојеће синтаксне грешке у програму (уместо да се пријави само једна и изађе), али да се при детекцији било какве грешке не наставља на следећу фазу, чак иако се од свих синтаксних грешки парсер успешно опоравио.
• Уколико се уместо реда за место синтаксне грешке од које се опоравља исписује колона, то је баг у алату и ангажовани на предмету неће то замерати. Ово се такође може десити у следећој фази.
• Грешка java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "X" is null обично значи да је негде заборављена тачка-зарез, али пошто је ово суштински грешка у имплементацији AST-CUP она не даје никаквих додатних информација о томе где би та грешка могла да буде.
• Грешка Syntax error X(Y) означава грешку у синтакси CUP фајла и може се десити из више разлога. Битно је напоменути да се број X односи на линију у аутогенерисаној CUP спецификацији која се налази у фајлу са суфиском _astbuild.cup, а не у оригиналној CUP спецификацији, док се број Y односи на колону (карактер) у том реду где је пријављена синтаксна грешка (који није од велике користи). Разлози из којих се ова грешка дешава могу бити:
  • заборављена тачка-зарез на крају смене,
  • недостатак размака након зареза у декларацији терминала или нетерминала,
  • коришћење := уместо ::=,
  • и тако даље.
• Уколико добијате конфликте приликом имплементације if-else, поставка обично помене која тачно precedence директива сме да се користи за то (и само то).
• Грешка која гласи java.lang.NullPointerException: Cannot invoke "java_cup.astext.AstSymInfo.getType()" because "this.lhInfo" is null значи да неки нетерминал који се користи са леве стране неке смене није претходно декларисан. За нетерминале који се користе са десне стране а нису декларисани се дешава другачија грешка која јасније каже да се ради о томе.
• Од користи може бити следећа скрипта за генерисање листе нетерминала које је потребно декларисати током ове фазе (која престаје да буде корисна у тренутку када нетерминалима треба додељивати типове), коју је потребно покренути Python интерпретером из кореног директоријума пројекта:

  from re import compile
  
  NTERM_REGEX = compile(r'^(\w+)\s*::=')
  
  nterms = []
  
  with open('spec/mjparser.cup') as file:
      for line in file:
          match = NTERM_REGEX.match(line)
          if match:
              nterms.append(match.group(1))
  
  print(f'nonterminal {", ".join(nterms)};')
  

Семантичка анализа

Техничке напомене

• Пре почетка ове фазе не заборавите да свим терминалима који са собом носе неке смислене вредности (идентификатори, константе...) доделите тип (преко terminal Tip naziv;). Уколико ово не урадите, у нетерминалима који садрже те терминале неће се изгенерисати поља са вредностима ових терминала.
• Такође пре почетка ове фазе потребно је свим нетерминалима доделити називе класа (уколико их не доделите, називи класа биће аутогенерисани па су као такви генерално непогодни за рад са њима). Када додељујете ове називе, битно је да се водите са два правила:
  1. Уколико нетерминал има само једну грану, поставите да њен назив класе буде исти као и назив самог нетерминала. Ово ће генерисати једну конкретну класу за тај нетерминал.
  2. Уколико нетерминал има више од једне гране, ниједна његова грана не сме да се зове исто као и сам нетерминал. Назив нетерминала користи се као назив апстрактне класе, а називи класа његових грана користе се за конкретне класе које су изведене из те апстрактне класе. Уколико нетерминал има више грана, и једна грана се зове исто као нетерминал, AST-CUP ће се збунити и неће знати да ли та класа треба да буде апстрактна и конкретна и ово ће испољити као грешка са конструкторима.
     • Важно је напоменути да се левој и десној страни не смеју додељивати називи класа са различитом капитализацијом (AssignOp и Assignop), јер се на фајл системима који се обично користе под Windows ови називи класа мапирају у исту Java датотеку. Ово је посебно опасно на оперативним системима Linux и macOS, где до грешки овог типа неће доћи (већ ће се оне десити тек у лабораторији).
• Уколико сте дошли до овог дела а потребно вам је да регенеришете парсер, не заборавите да након регенерисања парсера освежите пројекат десним кликом на пројекат и опцијом Refresh. Овај корак је потребан због тога што генерисање парсера позива спољашњи програм који без знања Eclipse мења фајлове унутар пројекта, и како би Eclipse знао да су се ти фајлови променили потребно је освежити их. Уколико ово не урадите, IntelliSense може пријављивати грешке које немају смисла и Eclipse може спречавати покретање компајлера због тога.
  • Ово се у Eclipse-у може заобићи тако што се намести аутоматско освежавање након покретања спољашње Ant скрипте. То се ради тако што се у Project Explorer-у кликне десни клик на build.xml скрипту, онда Run as -> External Tools Configuration, онда се у искачућем прозору изабере таб Refresh и чекира се опција Refresh resources upon completion и The entire workspace у подменију.
• Compiler класа је заправо скоро неизмењена MJParserTest класа из видео водича, тако да можете само њу да преименујете/преместите.

Табела симбола

• Пре рада са њиховом табелом симбола, не заборавите да у главној класи позовете Tab.init(). Уколико то не урадите, грешка коју ћете добити може садржати "rs.etf.pp1.symboltable.Tab.currentScope" is null.
• Подразумевано, Tab.dump() неће исписивати bool типове објектних чворова, јер то није имплементирано у DumpSymbolTableVisitor (већ ће то место стајати празно). Пошто свакако нико није гледао испис табеле симбола на одбрани пројекта, ово никоме није ни било битно.
• Такође, Tab.dump() може правити проблем када се као члан неке класе или као локални симбол члана неке класе нађе објекат те класе, јер тада долази до бесконачне рекурзије при испису. Једини случај кад неће доћи до ове бесконачне рекурзије јесте кад само симболи са називом this носе тип те класе (у том случају се њихов тип уопште не исписује). Пошто оваквих тест примера није било, ово никоме није правило проблем.
• Још један проблем са бесконачном рекурзијом у њиховој табели симбола може се десити уколико поредите класне типове са њиховом имплементацијом equals. Ако два класна типа имају исти број поља и метода, и барем једну методу, equals ће прећи на поређење тих метода и упасти у бесконачну рекурзију. Као и претходно, пошто оваквих тест примера генерално нема ово никоме не прави проблем. Са друге стране, пошто се на ову грешку најчешће наиђе приликом провере наткласа, може се специјално за случај када се ради о две класе користити оператор == за поређење референци.
• assignableTo метода у њиховој табели симбола не проверава да ли је једна класа подкласа друге, па је ову проверу потребно имплементирати (видети такође напомену изнад).
• Формат исписа чвора у Tab.dump() јесте <kind> <name>: <type>, <adr>, <level>.
• Приликом постављања type поља објектним чворовима који представљају низове праве се нови Struct чворови, тако да два објектна чвора са истим низовском типом неће показивати на исти објекат у позадини. Ово генерално не прави никакав проблем.
• Када се кроз Tab.insert() убаци један објектни чвор у табелу симбола, његов level се аутоматски поставља на 0 уколико се ради о глобалном досегу и 1 уколико се ради о локалном. Ово је пожељно понашање за променљиве, али за методе, чији level треба да садржи број параметара, је прво потребно вратити level на 0 а затим га приликом обиласка сваког чвора синтаксног стабла за параметре повећавати за 1.
• Уколико је потребно додати нешто у universe досег (а обично јесте), то се може обавити одмах након позивања Tab.init(), и код из Tab.init() се може искористити за то.

Генерисање кода

• Уколико се неке варијанте dup инструкције исписују као ??? приликом дисасемблирања, то је нормално понашање.
• Уколико је негде потребно обилазити низ или из неког другог разлога дохватити дужину низа, то није могуће урадити током превођења, већ је потребно генерисати код који позива arraylength инструкцију, која са стека скине низ а постави дужину тог низа, и затим искористити ту вредност са стека у остатку генерисаног кода.
• Ако су у поставци задатка дате неке глобалне функције, код за њих је потребно генерисати на неком месту (најбоље на почетку) а затим тим функцијама поставити адресу на та места где је изгенерисан код за њих.
• Уколико желите да након генерисања кода тај код покренете тако да се приказује ток извршења програма и стање стека, можете додати ново правило попут:

  <target name="debug" depends="disasm">
      <java classname="rs.etf.pp1.mj.runtime.Run">
          <arg value="test/program.obj" />
          <arg value="-debug" />
          <redirector input="input.txt" />
          <classpath>
              <pathelement location="lib/mj-runtime.jar" />
          </classpath>
      </java>
  </target>
  

  • Ово вам, додуше, неће приказати садржај меморије Микројава виртуелне машине након извршених инструкција. Уколико вас то занима, можете прекопирати Run класу из JAR фајла са извршним окружењем у свој пројекат, променити му пакет, поставити аргументе и breakpoint-ове на одговарајућа места (највероватније у interpret методи) и покренути у дебаг режиму.

Одбрана

• На одбрани, пројекат се подешава тако што се Eclipse пројекат отвори помоћу опције File → Open Projects from File System и затим покрене било кроз Ant прозор било на начин показан на видео водичу.
• У поставци пројекта је изричито речено да су студенти дужни да осигурају да њихово решење ради на лабораторијским рачунарима. Ово генерално није толико неопходно, јер су решења генерално преносива, али уколико желите да се уверите лабораторија П26 је отворена за студентски рад радним данима до 20 часова, када се не одржавају остале лабораторијске вежбе.
• Одбрана пројекта изгледа тако што ангажовани на предмету прво дају модификацију и од тада студенти имају три сата да ураде модификацију и одбране пројекат. Тест примери за модификације су генерално дати на дељеним дисковима (али могу бити погрешни, јер нису били тестирани на правом пројекту). Када студент уради модификацију, позове асистента или демонстратора и они покрену пројекат на тесту за модификацију (евентуално више пута са промењеним параметрима, откоментарисаним линијама које су закоментарисане), испитају студента како је урадио модификацију, покрену јавни тест и опционо питају неко питање о самом пројекту. Уколико нешто не ради, студент може да исправља пројекат док не истекне време.
• Дозвољено је дељење тестова између студената, тако да пре одбране можете поделити са осталима своје тестове како би сви заједно више багова ухватили у својим пројектима.

Референце

• Водич за пројекат 2021/2022. на којем су делови овог водича засновани.