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

1126

Ää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
      • hemmoit

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

    Takaisin ylös

    Luetuimmat keskustelut

    1. Tällä kertaa Marinia kadehtii Minäminä Päivärinta

      Kokoomuksen tyhjäntoimittelija itkeä tuhertaa, kun kansainvälinen superstaramme ei leiki hänen kanssaan. Oikean puoluee
      Maailman menoa
      410
      1656

    2. Minua itkettää tämä tilanne

      Meidän pitäisi jutella. Eikö niin? Miehelle.
      Ikävä
      105
      1328

    3. Miksi jollain jää "talvi päälle"

      Huvittaa kastoa ullkona jotain vahempaa äijää joka pukeutuu edelleen kun olisi +5 astetta lämmittä vaikka on helle keli
      Maailman menoa
      173
      1260

    4. Miksi koulut pakottavat

      Lapset uimaan sekaryhmänä? Murrosikäiset tunnetusti häpeilevät vartalossa tapahtuvia muutoksia. Tulee turhia poissaoloja
      Maailman menoa
      117
      1255

    5. Mitkä oli suurimmat

      Syyt mihin hänessä ihastuit alussa ja pikkuhiljaa tunteiden edetessä
      Ikävä
      44
      1007

    6. Minulla oli tunteita

      Tein itsestäni pellen. Sait hyvät naurut ja minä 💔
      Ikävä
      63
      926

    7. Susanne Päivärinta kirjassaan: Sannalla nousi valta päähän, Big Time!

      Päivärinta toteaa ettei ole nähnyt kenenkään muuttuvan niin totaalisesti kuin Marinin, eikä siis todellakaan parempaan s
      Maailman menoa
      92
      861

    8. Suomen Pallolitto: Tasoryhmät lasten jalkapallossa - Erätauko-tilaisuus ma 20.5.2024

      Tasoryhmät lasten ja nuorten jalkapallossa herättävät paljon keskustelua. Mitä tasoryhmät ovat ja mikä on niiden tarkoit
      Suomi24 Blogi ★
      0
      850

    9. Se katse silloin

      Oli hetki, jolloin katseemme kohtasivat. Oli talvi vielä. Kerta toisensa jälkeen palaan tuohon jaettuun katseeseen. Tunt
      Ikävä
      32
      846

    10. Tuhdit oluet kauppoihin. Miksi vastustaa?

      8% oluet kauppoihin mutta mikä siinä on että osa politikoista vstustaa ? Kauppa kuitenkin hinnoittelee vahvan oluen ni
      Maailman menoa
      199
      788
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt