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 ?
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 ?
Vastaukset 11
Vanhimmat
avoimen lähdekoodin kääntäjistä. hatunnosto sinulle ja piiiitkäää pinnaa valitsemallasi uralla. tuskin on parempaa keinoa oppia c syvällisesti !
"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.
eri opcodet.
fp/signed välillä on tietysti eri kuin fp/unsigned
http://www.thefreecountry.com/sourcecode/grammars.shtml
http://www.lysator.liu.se/c/ANSI-C-grammar-y.html
http://en.wikipedia.org/wiki/Small-C
> 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.
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ä.
Netistä löytyviä C-parsereita (jotka sellaisenaan eivät oimi, ja joita on mahdoton saada toimimaan ilman huomattavan hyvää C -osaamista):
http://www.cs.berkeley.edu/~smcpeak/elkhound/sources/elsa/index.html
sitten on vielä tämä:
http://hal.cs.berkeley.edu/cil/
mutta eipä senkään asentaminen ole helppoa...
http://www.gccxml.org/HTML/Index.html
Opettele BNF-notaatio. Hae C-kielen BNF-kielioppi. Kirjoita ohjelma, joka parsii lähdekoodin em. kieliopin mukaisesti.
BNF-notaatiosta:
http://www.tol.oulu.fi/kurssit/okp/Luennot/OKP_Syntaksi.html
http://www.tuug.utu.fi/~f/pascal/luku08.html
C-kielen BNF-kieliopista:
http://lists.canonical.org/pipermail/kragen-hacks/1999-October/000201.html
http://www.lysator.liu.se/c/ANSI-C-grammar-y.html
http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/mainB/node23.html