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

1262

Äänestä

    Vastaukset

    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. Voiko normaali ihminen ryhtyä vasemmistolaiseksi?

      Tätä jäin pohdiskelemaan.
      Maailman menoa
      202
      4248

    2. SDP haluaa 40 000 nettomaahanmuuttajaa

      SDP:n Suunnanmuutos-vaihtoehtobudjetissa, käy ilmi, että demarit itse asiassa vaativat räjähdysmäistä ”työperäisen” maah
      Maailman menoa
      146
      3798

    3. Orpo: Velkajarrua vastustavaa puoluetta vaikea ajatella hallitukseen

      No Minja Koskelan kommunistipuolue jäi ulos tuosta. Kaikki eduskuntapuolueet vasemmistoliittoa lukuun ottamatta sopivat
      Maailman menoa
      136
      3245

    4. Hienoa! Eduskunta luopui käteisen käytöstä

      Nyt tuo sama muutos pitää saada myös muuhun yhteiskuntaan. Käteistähän ei tarvitse tänä päivänä enää kuin rikolliset.
      Maailman menoa
      47
      1629

    5. Ikävä sinua mies

      Vuosia kuluu, mutta tunteet ei ole hävinnyt. Tasoittuneet toki, kun ei olla nähty. Järki palannut päähän kuitenkin. Se i
      Ikävä
      19
      1508

    6. Mikä tämä henkilö mahtaa touhuta Parkanossa

      Kamalaa https://www.ylasatakunta.fi/teksti/pirkanmaan-karajaoikeus-vangitsi-koiran-tappamisesta-epaillyn-6.68.127794.b58
      Parkano
      34
      1450

    7. Sulla on avaimet ja keinot

      Jos haluat jatkaa tutustumista. Itse olen niin jäässä etten pysty tekemään enää mitään. Pidempi keppi johon on helpompi
      Ikävä
      25
      1385

    8. Orpo loukkaantui fasismiin viittaavasta sanavalinnasta

      Mutta miksi loukkaantui? Orpohan on tehnyt yhteistyötä fasistien kanssa jo vuonna 2019, siis jo neljä vuotta ennen loukk
      Maailman menoa
      27
      1351

    9. Kiinnostaa - ei kiinnosta - kiinnostaapas

      Selittäkää hämmentyneelle miksi miehiä ei ikinä kiinnosta silloin, kun sitä olisi itsekin kiinnostunut? Sitten kun siirt
      Sinkut
      116
      1160

    10. Martina haluaa Marbellaan

      Martinan tekisi mieli ottaa lennot Marbellaan, jossa näkisisi kauniita ja hyväntuulisia ihmisiä. No sitten pitää matkust
      Kotimaiset julkkisjuorut
      215
      1063
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt