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

1183

Ää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. Aivosyöpää sairastava Olga Temonen TV:ssä - Viimeinen Perjantai-keskusteluohjelma ulos

      Näyttelijä-yrittäjä Olga Temonen sairastaa neljännen asteen glioomaa eli aivosyöpää, jota ei ole mahdollista leikata. Hä
      Maailman menoa
      91
      2920

    2. Pelotelkaa niin paljon kuin sielu sietää.

      Mutta ei mene perille asti. Miksi Venäjä hyökkäisi Suomeen? No, tottahan se tietenkin on jos Suomi joka ei ole edes soda
      Maailman menoa
      299
      1686

    3. Mikä saa ihmisen tekemään tällaista?

      Onko se huomatuksi tulemisen tarve tosiaan niin iso tarve, että nuoruuttaan ja tietämättömyyttään pilataan loppuelämä?
      Sinkut
      246
      1567

    4. Minkä merkkisellä

      Autolla kaivattusi ajaa? Mies jota kaipaan ajaa Mersulla.
      Ikävä
      87
      1391

    5. IL - VARUSMIEHIÄ lähetetään jatkossa NATO-tehtäviin ulkomaille!

      Suomen puolustuksen uudet linjaukset: Varusmiehiä suunnitellaan Nato-tehtäviin Puolustusministeri Antti Häkkänen esittel
      Maailman menoa
      402
      1384

    6. Nyt kun Pride on ohi 3.0

      Edelliset kaksi ketjua tuli täyteen. Pidetään siis edelleen tämä asia esillä. Raamattu opettaa johdonmukaisesti, että
      Luterilaisuus
      402
      1308

    7. Kiitos nainen

      Kuitenkin. Olet sitten ajanmerkkinä. Tuskin enää sinua näen ja huomasitko, että olit siinä viimeisen kerran samassa paik
      Tunteet
      2
      1089

    8. Esko Eerikäinen tatuoi kasvoihinsa rakkaan nimen - Kärkäs kommentti "Ritvasta" lävähti somessa

      Ohhoh! Esko Eerikäinen on ottanut uuden tatuoinnin. Kyseessä ei ole mikä tahansa kuva minne tahansa, vaan Eerikäisen tat
      Suomalaiset julkkikset
      38
      1047

    9. Hyväksytkö sinä sen että päättäjämme ei rakenna rauhaa Venäjän kanssa?

      Vielä kun sota ehkäpä voitaisiin välttää rauhanponnisteluilla niin millä verukkeella voidaan sanoa että on hyvä asia kun
      Maailman menoa
      329
      874

    10. Miksi Purra-graffiti ei nyt olekkaan naisvihaa?

      "Pohtikaapa reaktiota, jos vastaava graffiti olisi tehty Sanna Marinista", kysyy Tere Sammallahti. Helsingin Suvilahden
      Maailman menoa
      257
      855
    Aihe
    TietosuojaselosteKäyttöehdotEvästeasetuksetSäännöt