Compiler-témájú szakdolgozat segítség

Fórumok

Sziasztok!

Olyan embert keresek nagyon sürgősen, aki ért a fordítóprogramokhoz (elméletben és gyakorlatban) és segítene (ingyen/pénzért vagy bármilyen más kompenzációért cserébe) a szakdolgozatomban, ugyanis elakadtam.

Röviden a sztori:
Fordítóprogram részletet írok nyelvhez:
- a fordítás első három alfázisát kell megcsinálnom: lexer, parser, semantic analyzer
- a nyelvet én találtam ki, leírtam viszonylag részletesen. Szándékosan egyszerűre találtam ki.
- Már készen van a Lexer amibe már sikerült beépíteni a Semantic Analyzer néhány feladatát
- Sikerült egy fajta leírási módot és algoritmust találni a Syntax Analyzer-hez, ami implementálva is van; ha minden igaz akkor megfelelő szabályok mellett ez tudna működni.
- Jelenleg a nyelvtan formális leírásán küzködök (BNF-ben, mert azt egy-az-egyben implementációba fordíthatom), de ez nagyon nem megy.

Tehát a segítség az eddigi munka átnézésében és a továbbhaladásban kell.

A munka nagy része itt található:
https://github.com/arphox/BScThesis_PseudocodeRecognizer

Nagyon szépen köszönök minden segítséget!

U.i.: Mivel teljes állásban dolgozok és 6 hetem van befejezni a munkát, nem opció az hogy nekiállok átnézni és értelmezni a témában lévő több tízezer oldal angol nyelvű szakirodalmat. Személyes segítség kell és hamar.

Hozzászólások

Én szeretem a compilereket, még írtam is hobbiból sajátot, de most így más cuccát kibogarászni biztosan nem fogom. Én a helyedben arra rendezkednék be, hogy nem kapsz segítséget, és egyedül kell megcsinálnod.

6 hét rengeteg idő, meg kell csinálni rendesen akár vért izzadva is. Ha nem sikerül, akkor biztos lehet haladékot kérni, manapság már mindenre van pót-pót-pót-beadás is.

Ha nem konkrétan az a lényeg, hogy magad írod a lexert meg a parsert, akkor én az idő rövidségére való tekintettel inkább levennék a polcról egy kész parser megoldást. És azzal valósítanám meg a saját nyelvet. Szinte minden progamozási nyelvhez van többféle parser kererendszer is.

Onnan, hogy van valamid, ami akár működhetne is odáig, hogy _jól_ működik nagyon sok van hátra. Az én parserem például a nyelvtan és az input néhány speciális esetén bugos volt, amit elég melós volt fixálni. Általában is egy programtól, ami még nem volt valódi körülmények között tesztelve ezt lehet várni, hogy lesz benne pár blocker hiba.

Konkrét kérdésre egyébként szívesen válaszolok.

A Coursera compilers kurzusa még talán elérhető, self-learning formában. Ott mondjuk flex és bisonnal lehetett lexert és parsert írni, de ha bisonban megírtad, akkor már végül is kész a nyelvtan leírása. A szemantikai analízishez is volt ott egyfajta formális nyelv (messze ez volt a legnehezebb rész).

Ha leírtad viszonylag részletesen a nyelvet, akkor abból triviális dolog lenne BNF-et, vagy más szintakszisú CFG-t csinálni.
Esetleg csinálhatsz Parsing Expression Grammart, CFG-vel elvileg ekvivalens, de egyszerűbb parsert lehet hozzá készíteni.

Szerintem nem jó irányból közelítetted meg a feladatot.
A nyelvet úgy kell definiálni, hogy (és akkor van kész a definiálás, ha) a BNF formális leírása is megvan. Addig tök értelmetlen lexeren meg parseren gondolkodni, amíg ezt nem csináltad meg.
Ha sikerült olyan nyelvet írni, aminek a BNF leírásával gondok vannak, akkor nem jó nyelvet találtál ki - ilyenkor lehet, hogy inkább a nyelvet kéne megváltoztatni.

+1

Ez már a topik indítónak:
Először definiálni kell egy nyelvtant, utána van értelme elkezdeni a lexert, utána a parsert, utána a szemantikai elemzést.

Egy-két észrevétel:
- Az tömbElemElérés szabályban csak az "azonosító [ ]" kell, a másik levezethető ebből.

- A lexerhez kell a literálok definíciója, azt csak a kódban láttam, a dokumentációban nem. Mondjuk csak átfutottam mindkettőt.

- A kódban nem tekinted a \r karaktert whitespacenek. Van erre beépített c# függvény, char.IsWhitespace().

- Én egy típus szabályt írnék, ahol mind a 8 típus fel van sorolva: egész, egész[], tört, tört[],... Egyszerűbb lesz a nyelvtan mwg a feldolgozás, és mivel úgysem lehet többféle típus, jó eredményt ad így is.

- A ciklus_vége lemaradt a nyelvtanban, csak a dokumentációban van benne.

- A nyelvtan szerint a "ha", "ciklus", stb. törzsében csak 1 parancs fordulhat elő, nem <állítások> akar lenni az a ?

- Én a változó deklarációt csak a program elején engedném meg, rengeteg szívástól kíméled meg magad, ha nem kell láthatóságot meg ilyesmiket kezelni. Ha ez nem számít a szakdogához akkor persze mindegy.

- Én az "és" és "vagy" kifejezéshez használatos szabályokat összevonnám, egyszerűbb nyelvtan és kb mindegy. Ugyan ez a relációkkal.

- Parsereknél gyakoriak az LL(k) elemzők, sok szakirodalom van hozzájuk. Viszonylag egyszerű a megértése meg az implementációja is. Nem lehet a nyelv bal rekurzív, de ez relative egyszerű átalakítással kiküszöbölhető. Főleg ha te definiálod a nyelvet :)

Azóta jócskán átdolgoztam az egészet; jelenleg úgy érzem hogy habár egyszerűen de minden megfogalmazható a jelenlegi változtban (simple_grammar.txt, 2017.10.21. 13:50-kor felrakott commit verziója, remélhetőleg nem változik már)

"- A kódban nem tekinted a \r karaktert whitespacenek. Van erre beépített c# függvény, char.IsWhitespace()."
Ezért:

Code = input.Replace("\r\n", "\n"); // Windows <=> Linux crlf changes;

Önmagában \r-ekkel meg nem foglalkozom, az már elég elavult tudtommal.

Én egy típus szabályt írnék
Jelenleg hasznos hogy van alap és tömbtípus is, használom.

Köszönöm a segítséget, kb. Te vagy az egyetlen aki tényleg bele is nézett a nyelvtanba szerintem. :)
Örök hála!

Mobilrol nem vettem eszre, de egy csomo <xyz>-t eltuntetett a drupal motor, ugyhogy kicsit ertelmetlen lett az eredmeny.

A simple_grammar.txt-hez: az "ujsor"-t en kicserelnem "\n"-re, hiszen nem az "ujsor" tokent varod ott, hanem egy ujsor karaktert.
Meg az nem tudom neked szamit-e, de a simple_grammar.txt-ben kicsit keverednek a lexer es a parser szabalyok, ami nem feltetlen problema, de az egyikre a lexerben, a masikra a parserben lesz csak szukseged.
Lexer szabaly az ami valid tokent (terminalist) eredmenyez, mint pl az "azonosito", "literal", "program_kezd", "vagy", ..., parser szabaly meg az ami nem-terminalist, pl. <Program> := ...
Az ujsor karakterhez hasonloan az "azonosito"-t is lecserelnem, de azt <azonosito>-ra, a "literal"-t ugyanigy, hiszen nem az "azonosito" tokent varod, hanem egy azonositot ami barmi lehet ami passzol a LexicalElementIdentifier.IdentifierPattern-re. Igy latszolag kicsit jobban keverednek a lexer-parser szabalyok, de teljes lesz a leirasod.

Az <azonosito> szerintem kb igy nezne ki BNF-ben:


<azonosito>           := <azonositoElsoBetu> <azonositoTobbiBetuk> 
                      | <azonositoElsoBetu>
<azonositoElsoBetu>   := "a" | "b" | "c" ...
<azonositoTobbiBetuk> := <azonositoTobbiBetu> <azonositoTobbiBetuk> 
                      | <azonositoTobbiBetu>
<azonositoTobbiBetu>  := <azonositoElsoBetu> | "0" | "1" | ...

A <literal>-t ehhez hasonloan, ezek az egyszeru regularis kifejezesek kb egy az egyben alakithatoak BNF formatumra.

Ugyan a topicnyitó a forráskód alapján Csharpban dolgozott, de néhány adalék, ha pl. Java is opció:

- ahogy fentebb írták előbb meg kell csinálni a nyelvtant ami környezetfüggetlen (context-free). Ha viszont a nyelvtant rögtön a parser generátorhoz készíted, akkor gyorsan kiderül, ha olyan nyelvtant találtál ki, amit nehéz megvalósítani.
- ha nem az a célod, hogy kézzel írj lexert és parsert, akkor valamilyen parser generátort javasolt használni.
- nyilván van flex és bison, de ezek már ~15 éve sem a technológia csúcsát jelentették
- már ekkor létezett pl. SableCC (http://www.sablecc.org/), ami szépen AST-t épített a nyelvtanból kész visitorokkal
- ha ma nekem egy diplomamunka céljára nyelvet kellene gyártanom, és hozzá fordítót, akkor elővenném az Eclipse Xtext-et (https://www.eclipse.org/Xtext/), mert ezzel nem csak parsert kapok rögtön, hanem okos szerkesztőt Eclipse-hez, IDEA-hoz és Webhez
- ha ezután még egy gyors interpreter és JIT kellene nekem ehhez, akkor megnézném az Oracle Truffle-t és a GraalVM-et

Köszönöm szépen a segítséget mindenkinek!