C-kielen parserointi, kummallisuuksia...

C_opiskelija

C-kielen parserointi, kummallisuuksia...

C-kielen parserointi ei valitettavasti ole niitä helpoimpia tehtäviä.

Päätin kuitenkin yrittää.

Tässä on muutamia vastaantulleita C -kielen sellaisia ominaisuuksia, jotka hankaloittavat C -kielen oikein ymmärtävän parserin toteuttamista:

1) eräät symbolit / merkit / merkkiyhdistelmät, joilla on vähintään 2 merkitystä:

* voi olla ainakin:

a) kertolasku
b) osoittimen derererenssi, eli esim:

int a;

int * p;

p = &a;

a = 2;

*p = 6;

// Nyt muuttujan a arvo on 6, eikö ?

& voi olla ainakin:

a) bittitason AND -operaatio, esim:

a = a & 0x3F;

b) AddressOf -toiminto, ks. edeltävä esimerkki.

Eli ainakin näillä voi olla useampia merkityksiä:

* ( 2 tiedettyä merkitystä, onko muita ?)
& ( 2 tiedettyä merkitystä, onko muita ?)

onko muita sellaisia merkkejä, merkkiyhdistelmiä tai avainsanoja, joilla on useampia merkityksiä ?

Vielä 1 tiedossa oleva:

i = i >> 3;

tuohan kääntyy assembleriksi (80386, Pentium & yhteensopivat):

[1] JOKO:

mov eax, [i]
mov cl,3
shr eax,cl
mov [i],eax


[2] TAI:

mov eax, [i]
mov cl,3
sar eax,cl
mov [i],eax


Huomasitko eron?

C-kielinen i = i >> 3;

kääntyy tavalla [1], kun i on esim. tyyppiä unsigned int,

MUTTA

C-kielinen i = i >> 3;

kääntyy tavalla [2], kun i on esim. tyyppiä signed int, tai (useimmissa, ellei peräti kaikissa C -kääntäjissä) pelkkä int.

Mitä muita tällaisia on tiedossa, joissa yjksittäisen symbolin selvittäminen ei riitä oikean tulkinnan tekemiseksi, vaan tarvitaan ohjelmakoodin muuta tutkimista ?

Entä mitkä ovat ne säännöt, joiden perusteella
C -kääntäjä päättelee, mistä merkityksestä monimerkityksisten rakenteiden kohdalla kulloinkin on jyse ?

11

1313

Äänestä

    Vastaukset 11

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • mallia

      avoimen lähdekoodin kääntäjistä. hatunnosto sinulle ja piiiitkäää pinnaa valitsemallasi uralla. tuskin on parempaa keinoa oppia c syvällisesti !

      • gcc_ei_ruleta

        "katso mallia avoimen lähdekoodin kääntäjistä"

        Ikävä kyllä gcc:n lähdekoodi on niin sekavaa, että kaikki sen kehittäjätkään eivät täysin ymmärrä sitä.

        Ja linuxista tuttu gcc on varmasti tunnetuin avoimen koodin kääntäjistä.

        toivoin lähinnä vastausta siihen, mikä olisi yleispätevä tapa tunnistaa, kummasta merkityksestä on kyse, kun törmää C -kielisessä lähdekoodissa moniselitteiseen symboliin.

        Tässä esimerkiksi "ogg_stream.c":stä omatekoisen parserin tuloksesta pätkä:

        (vinkki: lataa sellaiseen editoriin, joka osaa näyttää xml -tagit eri värillä)

        ogg_page_bosogg_page og
        ogheader502


        ogg_page_eosogg_page og
        ogheader504


        ogg_int64_t ogg_page_granuleposogg_page og
        pageogheader
        ogg_int64_t granulepospage13ff
        granulepos granulepos8page12ff
        granulepos granulepos8page11ff
        granulepos granulepos8page10ff

        ... ja lisää ...

        ogg_page_packetsogg_page og
        inogheader26count0
        i0ini
        ogheader27i255count
        count



        0
        /* helper to initialize lookup for direct-table CRC (illustrative; we
        use the static init below) */

        ogg_uint32_t _ogg_crc_entry index
        i
        r

        r index 24
        i0 i8 i
        r 80000000UL
        r r 1 04c11db7 /* The same as the ethernet generator
                     polynomial, although we use an
                     unreflected alg and an init/final
                     of 0, not 0xffffffff */

        r1
        r ffffffffUL

        endif

        ogg_uint32_t crc_lookup256
        0000000004c11db709823b6e0d4326d9
        130476dc17c56b6b1a864db21e475005
        2608edb822c9f00f2f8ad6d62b4bcb61


        .... ja tässä malliksi yksi kokonainen C -funktio: ....

        /* checksum the page */
        /* Direct table CRC; note that this will be faster in the future if we
        perform the checksum silmultaneously with other copies */

        ogg_page_checksum_setogg_page og
        og
        ogg_uint32_t crc_reg0
        i

        /* safety; needed for API behavior, but not framing code */
        ogheader220
        ogheader230
        ogheader240
        ogheader250

        i0iogheader_leni
        crc_regcrc_reg8crc_lookupcrc_reg 24ffogheaderi
        i0iogbody_leni
        crc_regcrc_reg8crc_lookupcrc_reg 24ffogbodyi

        ogheader22 crc_regff
        ogheader23 crc_reg8ff
        ogheader24 crc_reg16ff
        ogheader25 crc_reg24ff



        .....

        tuon XML -tyylisen koodauksen idea on kahtalainen:

        1. Siitä on helppo muuntaa ja tulkita edelleen toiseen formaattiin

        ja

        2. Ladattassa editoriin, joka osaa näyttää eri värillä XML -tagit, näkyy selkeästi, mitä vielä jäi näkyvien tagien ulkopuolelle.

        Pitäisi jäädä lähinnä esim. ns. identifierit, vakioiden arvot jne.

    • poikkeaa

      eri opcodet.

      • tyyppikonversiot

        fp/signed välillä on tietysti eri kuin fp/unsigned

    • dx2

      > C-kielinen i = i >> 3;
      >
      > kääntyy tavalla [2], kun i on esim. tyyppiä
      > signed int, tai (useimmissa, ellei peräti
      > kaikissa C -kääntäjissä) pelkkä int.

      Tämä sama juttu on kaikissa lausekkeissa ja operaattoreissa - assembler-koodi riippuu muuttujien tyypistä. Eikä se ole C-kielen spesifinen juttu vaan kaikissa staattisesti tyypitetyissä kielissä on sama juttu. Dynaamisesti tyypitetyissä tilanne on huomattavasti monimutkaisempi.

      > Mitä muita tällaisia on tiedossa, joissa
      > yksittäisen symbolin selvittäminen ei riitä
      > oikean tulkinnan tekemiseksi, vaan tarvitaan
      > ohjelmakoodin muuta tutkimista ?

      Itse asiassa jos toteutat kääntäjän, niin huomaat, että nuo mainitsemasi ongelmat eivät olekaan ongelmallisia ollenkaan, vaan ongelmat tulevat ihan muualta. Klassinen esimerkki lienee ns. dangling-else. Muissa kielissä kuten Fortranissa on kyllä ihan oikeasti tuollaisia mainitsemasi kaltaisia tulkintaongelmia.

      > Entä mitkä ovat ne säännöt, joiden perusteella
      > C -kääntäjä päättelee, mistä merkityksestä
      > monimerkityksisten rakenteiden kohdalla
      > kulloinkin on jyse ?

      Syntaksin ja kieliopin säännöt, presedenssisäännöt, C-kielin speksi. Ne rakenteet eivät oikeasti ole monimerkityksellisiä vaan ihan yksikäsitteisiä.

      Jos omaa kääntäjää meinaa tehdä vaikka harjoitustyötyyppisesti, voi olla hyvä hankkia joku kirja aiheesta. Esimerkiksi Aho/Sethi/Ullmanin "Dragon Book". Ja työkaluiksi klassinen valinta ovat bison ja flex, joilla tokenit voi kirjoitella säännöllisinä lausekkeina ja kieliopin suoraan BNF-muodossa.

      • C_opiskelija

        bison ja flex ?!

        huh !

        Eikös nuo ole Lexx / Yaccin perillisiä ?

        Joskus vuosia sitten törmäsin turbo Pascalilla koodattuun Lexx / Yacc -yhdistelmään.

        Sen *piti* osata parseroida pascal -koodia.

        Kun ohjelman suoritus tuntui kestävän ikuisesti, pysäytin ohjelman ja kokeilin uudelleen debuggerin alaisuudessa...

        Nyt alkoi selvitä: Lexx / Yacc -koodi luki lähdekoodia merkki kerrallaan, kunnes jumittui yhteen kohtaan siten, että ohjelma pysyi ikuisessa silmukassa eikä lähdekoodin lukeminen edistynyt tavuakaan enää, vaan ilmeisesti koodi pyrki hyväksymään seuraavaksi merkiksi vain johonkin tiettyyn joukkoon kuuluvan merkin, ja kun lähdekooditiedostossa seuraavana luettavana ollut merkki ei sitten kuulunutkaan tuohon joukkoon, seurauksena oli ikuinen silmukka !

        En tiedä, oliko tuossa Lexx / Yacc -toteutuksessa vikaa vai oliko sille syötetty väärät syntaksisäännöt, mutta joka tapauksessa käyttökelvoton lopputulos.

        Parseri kun ei saa missään olosuhteissa jäädä ikuiseen silmukkaan, ei vaikka sille syöttäisi syötteenä satunnaisluvuilla täytetyn "lähdekoodi"-tiedoston (joka nyt tietenkään ei tosiasiassa ole lähdekoodia jo9s on kerran satunnaista...).

        Onko tuo noiden lexx/Yacc -tyyppisten ohjelmien perusvika, että jos toteutukselle annetut kielioppisäännöt kuvaavat jotain sellaista, jotga tutkittava lähdekoodi ei täysin vastaakaan, niin seurauksena on ikuinen silmukka ?

        Tuolla kun olisi tarkoitus parseroida myös C -lähdekooditiedostoja, jotak eivät mene kääntäjästä läpi.

        Netistä joskus löytyi parikin C -parseria, molemmaty kirjoitettu C:llä, ja kumpikaan ei mennyt gcc:llä käännöksestä läpi, vaan tuloksena oli kasa virheilmoituksia.

        Tiesipä joku keskusteluketju netissä, että joku olisi joskus koodannut C -kääntäjän pascalilla.

        Ikävä kyllä tuollaisen kääntäjän nimeä tai URLia ei mainittu.

        Jos koodi on vähänkään järkevästi kirjoitettu, niin pascalilla kirjoitetun C -kääntäjän ehkä saattaisin osata jopa korjata, mutta C onkin huomattavasti vaikeampi kieli, niin ihmisen kuin koneenkin tulkattavaksi.

        Arvatkaapa 2 kertaa, miksi esim. Delphi kääntää huomattavasti nopeammin kuin
        saman valmistajan C Builder.

      • dx2
        C_opiskelija kirjoitti:

        bison ja flex ?!

        huh !

        Eikös nuo ole Lexx / Yaccin perillisiä ?

        Joskus vuosia sitten törmäsin turbo Pascalilla koodattuun Lexx / Yacc -yhdistelmään.

        Sen *piti* osata parseroida pascal -koodia.

        Kun ohjelman suoritus tuntui kestävän ikuisesti, pysäytin ohjelman ja kokeilin uudelleen debuggerin alaisuudessa...

        Nyt alkoi selvitä: Lexx / Yacc -koodi luki lähdekoodia merkki kerrallaan, kunnes jumittui yhteen kohtaan siten, että ohjelma pysyi ikuisessa silmukassa eikä lähdekoodin lukeminen edistynyt tavuakaan enää, vaan ilmeisesti koodi pyrki hyväksymään seuraavaksi merkiksi vain johonkin tiettyyn joukkoon kuuluvan merkin, ja kun lähdekooditiedostossa seuraavana luettavana ollut merkki ei sitten kuulunutkaan tuohon joukkoon, seurauksena oli ikuinen silmukka !

        En tiedä, oliko tuossa Lexx / Yacc -toteutuksessa vikaa vai oliko sille syötetty väärät syntaksisäännöt, mutta joka tapauksessa käyttökelvoton lopputulos.

        Parseri kun ei saa missään olosuhteissa jäädä ikuiseen silmukkaan, ei vaikka sille syöttäisi syötteenä satunnaisluvuilla täytetyn "lähdekoodi"-tiedoston (joka nyt tietenkään ei tosiasiassa ole lähdekoodia jo9s on kerran satunnaista...).

        Onko tuo noiden lexx/Yacc -tyyppisten ohjelmien perusvika, että jos toteutukselle annetut kielioppisäännöt kuvaavat jotain sellaista, jotga tutkittava lähdekoodi ei täysin vastaakaan, niin seurauksena on ikuinen silmukka ?

        Tuolla kun olisi tarkoitus parseroida myös C -lähdekooditiedostoja, jotak eivät mene kääntäjästä läpi.

        Netistä joskus löytyi parikin C -parseria, molemmaty kirjoitettu C:llä, ja kumpikaan ei mennyt gcc:llä käännöksestä läpi, vaan tuloksena oli kasa virheilmoituksia.

        Tiesipä joku keskusteluketju netissä, että joku olisi joskus koodannut C -kääntäjän pascalilla.

        Ikävä kyllä tuollaisen kääntäjän nimeä tai URLia ei mainittu.

        Jos koodi on vähänkään järkevästi kirjoitettu, niin pascalilla kirjoitetun C -kääntäjän ehkä saattaisin osata jopa korjata, mutta C onkin huomattavasti vaikeampi kieli, niin ihmisen kuin koneenkin tulkattavaksi.

        Arvatkaapa 2 kertaa, miksi esim. Delphi kääntää huomattavasti nopeammin kuin
        saman valmistajan C Builder.

        Lex/yacc -perillisiähän nuo jollain muotoa ovat. Mutta siis ei ole työkalun vika, että internetistä löytyy jotain huonosti toteutettuja parsereita. Eivät ne työkalut tee mitään mitä ohjelmoija ei käske niitä tekemään (kuten jää jumiin käskemättä). Löytyy niistä myös C -versiot sekä muitakin kieliä tuottavia versioita, jos ei C:stä tai C :sta kääntäjän (tai parserin) toteutuskielenä pidä.

        Eiköhän noilla ole monta niin C- kuin Pascalkin -kääntäjää toteutettu. Ei niitä pakko ole käyttää jos ei halua.

        Mutta joka tapauksessa kannattaisi ennen työkalujen käyttöä tai haukkumista tutustua edes ihan peruskurssitason tietojenkäsittelyteoriaan. Kuten pinokoneet, säännölliset lausekkeet, LL-parserit, LR-parserit jne. Sitten kun ymmärtää miten flex/bison tai lex/yacc toimivat, voi lähteä rauhassa haastamaan niitä.

    • C_Hankalaa

    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Takaisin ylös

    Luetuimmat keskustelut

    1. Mikä on totta mikä ei?

      Onko juoru vai ei että nimeltä mainitsematon henkilö on tehnyt naiselle/naisille jotain joka on väärin?
      Kuhmo
      21
      2124

    2. Päivän aivopieru Trumpilta

      Trump julisti sodan hyttysiä vastaan. Myös punkit ovat Trumpin sodan kohteena. Eikö vieläkään USA:n kansa tajua tuon uko
      Maailman menoa
      71
      1159

    3. Lopetetaanko tämä

      Juttu ja mennään eteenpäin? Pystytkö?
      Ikävä
      132
      938

    4. Just saying

      Mies joka antaa naiselle turvallisen olon, on seksikäs. Ei kieroja kikkoja ja haluaa olla vain sen yhden naisen mies.
      Ikävä
      138
      710

    5. Voisin antaa sulle nyt

      Halin❤️
      Ikävä
      54
      636

    6. Löytyikö syy miksi Martina on Muhiksen kanssa

      Saipa naurut Gekkosen kuvasta, missä ovat ravintola Hookissa Immu fight night ottelun jälkeen, Muhoksella pullottaa hirv
      Kotimaiset julkkisjuorut
      95
      622

    7. Jos selviäisi että kaivattusi

      Olisi savant asperger? Rakastaisitko vielä? Savant-lahjakkuus olisi kapea-alaista neroutta liittyen mekanisiin ja tilan
      Ikävä
      93
      575

    8. Janpen Thai lopettanut, miksiköhän

      Hyvää apetta teki.
      Suomussalmi
      12
      567

    9. Jorma Uotinen läväytti härskin heiton - Paljastus uudesta TTK-romanssista?

      Tuomari Jorma Uotisen linja on välillä hyvinkin rohkea TTK:ssa. Hän näpäytti Jaakko Parkkalille ja Kastanja Rauhalalle v
      Tanssii tähtien kanssa
      11
      563

    10. Tosi kiva on

      Joo. Mitä olisit menettänyt jos olisit paljastanut itsesi?
      Ikävä
      65
      551

    11. Jokin ei täsmää

      Joskus yksi vuosiluku saa katsomaan koko tarinaa uudestaan. Löysin gradun. Matematiikka ei oikein täsmää siihen, mitä mi
      Ikävä
      298
      536

    12. Toivotko vielä viestiä

      Minulta? En rohkene enää ottaa yhteyttä, kun varmasti jo uusia naisia elämässä. Nolaisin vain itseni.
      Ikävä
      44
      529

    13. Tehdään yhdessä itsestämme

      Parhaat versiot❤️ Se vaatii molemmilta hyvää itsetuntoa!
      Ikävä
      42
      525

    14. Oliko Jani Halmeen aika jo tippua TTK:sta?

      Jani Halme ja Claudia Ketonen joutuivat jättämään TTK:n. Halme ja Ketonen saivat viimeiseksi jäänestä tanssista, sambas
      Tanssii tähtien kanssa
      27
      492

    15. Kuka kaipaa T m?

      Kerro nainen kirjaimesi vaan... Haluan miettiä kuka tulee ekana mieleeni.. kuin kurkistus tunteiden meren pinnalle, jota
      Ikävä
      36
      480

    16. Olen ajellut Dieseleillä yli 50 vuotta.

      Enkä ole koskaan kaivannut sähköautoa.
      Hybridi- ja sähköautot
      116
      468

    17. Mitä tunteita

      Sulla vielä on?
      Ikävä
      71
      449

    18. Miksi jotku naiset on niin tyhmiä

      Että elättelevät turhaa toivoa toisen kustannuksella. Onko ne kaikki kaappilesboja vai mikä niitä vaivaa? Sitten itketä
      Ikävä
      51
      447

    19. Vaikea on tämän

      Jälkeen suhtautua sinuun ilman ettei muista kirjoituksiasi.
      Ikävä
      58
      437

    20. Kerro muuten miksi

      Estit somessa?
      Ikävä
      41
      434
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt