• Osoite. Toimiva laite, joka muuntaa virtuaaliosoitteen (eng. Virtual address) todelliseksi osoitteeksi.
• Dialogi. Tarjoaa ohjelmointikielen käytön aikajakotilassa.
• multipass. Luo objektimoduulin useille lähdeohjelman näkymille.
• Takaisin. Sama kuin rele. Katso myös: purkaja, purkaja.
• yksittäinen passi. Luo objektimoduulin yhdessä lähdeohjelman peräkkäisessä tarkistuksessa.
• Optimointi. Suorittaa koodin optimoinnit luodussa objektimoduulissa.
• Syntaktisesti suuntautunut (syntaksiin perustuva). Se vastaanottaa syötteenä kuvauksen kielen syntaksista ja semantiikasta sekä tekstistä kuvatulla kielellä, joka käännetään määritellyn kuvauksen mukaisesti.
• testata. Joukko kokoonpanokielimakroja, joiden avulla voit määrittää erilaisia ​​virheenkorjaustoimenpiteitä kokoonpanokielellä kirjoitetuissa ohjelmissa.

Lähetyksen tarkoitus- muuntaa tekstiä kielestä toiselle, mikä on tekstin vastaanottajan ymmärrettävää. Käännösohjelmien tapauksessa vastaanottaja on tekninen laite (prosessori) tai tulkkiohjelma.

Prosessorin kieli (konekoodi) on yleensä matalatasoinen. On alustoja, jotka käyttävät konekielinä korkeatasoinen(esimerkiksi iAPX-432), mutta ne ovat poikkeus säännöstä monimutkaisuuden ja korkeiden kustannusten vuoksi. Kutsutaan kääntäjä, joka muuntaa ohjelmat konekielelle, jonka prosessori hyväksyy ja suorittaa suoraan kääntäjä.

Käännösprosessi koostuu yleensä useista vaiheista: leksikaaliset, syntaktiset ja semanttiset analyysit (englanniksi semanttinen analyysi), välikoodin generointi, optimointi ja tuloksena olevan konekoodin generointi. Lisäksi ohjelma on yleensä riippuvainen käyttöjärjestelmän ja kolmannen osapuolen kirjastojen tarjoamista palveluista (esim. tiedosto I/O tai GUI), ja ohjelman alkuperäinen koodi on liitettävä näihin palveluihin. Linkityksen staattisiin kirjastoihin tekee linkittäjä tai linkkeri (joka voi olla itsenäinen ohjelma tai osa kääntäjää), kun taas linkitys käyttöjärjestelmään ja dynaamisiin kirjastoihin tehdään, kun lataaja aloittaa ohjelman suorittamisen.

Kääntäjän etu: ohjelma käännetään kerran, eikä jokaiseen suoritukseen tarvita lisämuunnoksia. Näin ollen kohdekoneessa, jolle ohjelmaa käännetään, ei tarvita kääntäjää. Haitta: Erillinen käännösvaihe hidastaa kirjoittamista ja virheenkorjausta ja vaikeuttaa pienten, yksinkertaisten tai kertakäyttöisten ohjelmien suorittamista.

Toinen toteutustapa on, kun ohjelma suoritetaan tulkki ei käännöstä ollenkaan. Tulkki simuloi ohjelmallisesti konetta, jonka hae-suorita -silmukka toimii korkean tason kielten ohjeilla konekäskyjen sijaan. Sellainen ohjelmistosimulaatio luo virtuaalikone, joka toteuttaa kielen. Tätä lähestymistapaa kutsutaan puhtaaksi tulkinnaksi. Puhdasta tulkintaa käytetään yleensä kielille, joilla on yksinkertainen rakenne (esimerkiksi APL tai Lisp). Tulkit komentorivi käsitellä komentoja komentosarjoissa UNIXissa tai erätiedostoissa (.bat) MS-DOSissa, myös yleensä puhtaassa tulkintatilassa.

Puhtaan tulkin etu: käännösten välitoimien puuttuminen yksinkertaistaa tulkin toteuttamista ja tekee sen käytöstä mukavampaa, myös interaktiivisessa tilassa. Haittapuolena on, että tulkin on oltava käytettävissä kohdekoneessa, jossa ohjelma suoritetaan.

Ohjelmointikielitoteutusten kääntämisen ja puhtaan tulkinnan välillä on kompromisseja, kun tulkki ennen ohjelman suorittamista kääntää sen välikielelle (esimerkiksi tavukoodiksi tai p-koodiksi), joka on tulkinnan kannalta kätevämpi (eli puhumme tulkista, jossa on sisäänrakennettu kääntäjä). Tätä menetelmää kutsutaan sekatoteutukseksi. Perl on esimerkki sekakielisestä toteutuksesta. Tämä lähestymistapa yhdistää sekä kääntäjän että tulkin edut ( suuri nopeus suoritus ja käytettävyys) ja haitat (ohjelman kääntäminen ja tallentaminen välikielelle vaatii lisäresursseja; tulkki tulee järjestää ohjelman suorittamiseksi kohdekoneella). Lisäksi, kuten kääntäjän tapauksessa, sekoitettu toteutus edellyttää, että lähdekoodi ei sisällä virheitä (leksikaalisia, syntaktisia ja semanttisia) ennen suoritusta.

Lähettää Ja tulkinta - erilaisia ​​prosesseja: kääntäminen käsittelee ohjelmien kääntämistä kielestä toiselle, ja tulkkaus vastaa ohjelmien suorittamisesta. Koska kääntämisen tarkoituksena on kuitenkin yleensä valmistella ohjelma tulkkausta varten, näitä prosesseja tarkastellaan yleensä yhdessä. Esimerkiksi ohjelmointikieliä luonnehditaan usein "käännetyiksi" tai "tulkituiksi" riippuen siitä, hallitseeko kielen käyttöä kääntäminen vai tulkinta. Lisäksi lähes kaikki matalan tason ja kolmannen sukupolven ohjelmointikielet, kuten assembler, C tai Modula-2, käännetään ja ylemmän tason kieliä, kuten Python tai SQL, tulkitaan.

Toisaalta käännös- ja tulkkausprosessit tunkeutuvat toisiinsa: tulkit voivat kääntää (myös dynaamisella kääntämisellä), ja kääntäjät voivat vaatia tulkintaa metaohjelmointikonstruktioille (esim. kokoonpanokielen makroille, ehdollinen käännös C-kielellä tai malleille C++:ssa).

Lisäksi samaa ohjelmointikieltä voidaan sekä kääntää että tulkita, ja molemmissa tapauksissa tulee olla yhteiset lähdekielen konstruktien ja direktiivien analysointi- ja tunnistamisvaiheet. Tämä koskee sekä ohjelmisto- että laitteistototeutuksia - esimerkiksi x86-perheen prosessorit purkaa ne ennen konekielisten käskyjen suorittamista, korostaen operandien kentät (rekisterit, muistiosoitteet, välittömät arvot), bittisyvyyttä jne., opkoodeissa, ja sisään Pentium prosessorit NetBurst-arkkitehtuurissa konekoodi käännetään yleensä mikrooperaatioiden sarjaksi ennen kuin se tallennetaan sisäiseen välimuistiin.

OSA 7. Kääntäminen, kokoaminen ja tulkkaus

Ohjelma on käskysarja, joka on suunniteltu tietokoneen suoritettavaksi. Tällä hetkellä ohjelmat kirjoitetaan tekstin muodossa, joka kirjoitetaan tiedostoihin. Tämä teksti on ohjelmoijan toiminnan tulos ja muodollisen kielen erityispiirteistä huolimatta säilyy ohjelma ohjelmoijalle.

Ohjelman luontiprosessi sisältää useita vaiheita. Ohjelman projektin kehitysvaihetta seuraa ohjelmointivaihe. Tässä vaiheessa ohjelma kirjoitetaan. Ohjelmoijat havaitsevat tämän tekstin helpommin kuin binäärikoodin, koska erilaiset muistikirjalyhenteet ja nimet sisältävät lisätietoja.

Ohjelman lähdetiedosto (kutsutaan myös lähdemoduuliksi) käsitellään kääntäjä , joka kääntää ohjelman ohjelmointikielestä koneellisesti ymmärrettäväksi koodisarjaksi.

Kääntäjä - ohjelma tai teknisiä keinoja, esiintymässä ohjelman lähetys. Koneohjelma, joka kääntää kielestä toiseen ja erityisesti ohjelmointikielestä toiseen. Käsittelyohjelma, joka on suunniteltu muuntamaan lähdeohjelma objektimoduuliksi.

Kääntäjä tekee yleensä myös virhediagnostiikkaa, luo tunnistesanakirjoja, tulostaa ohjelmatekstejä jne.

Ohjelman lähetys - jollakin ohjelmointikielellä esitetyn ohjelman muuntaminen toisella kielellä ja tietyssä mielessä ensimmäistä vastaavaksi ohjelmaksi.

Kieltä, jolla syöttöohjelma esitetään, kutsutaan alkuperäinen kieli ja itse ohjelma lähdekoodi. Tulostuskieli on ns Kohdekieli tai objektikoodi.

Kääntäjätyypit

Kääntäjät jaetaan:

· Osoite. Toimiva laite, joka muuntaa virtuaaliosoitteen virtuaalinen osoite) oikeaan osoitteeseen (eng. muistin osoite).

· Dialogi. Tarjoaa ohjelmointikielen käytön aikajakotilassa.

· multipass. Luo objektimoduulin useille lähdeohjelman näkymille.

· Takaisin. Sama kuin rele. Katso myös: purkaja, purkaja.

· yksittäinen passi. Luo objektimoduulin yhdessä lähdeohjelman peräkkäisessä tarkistuksessa.

· Optimointi. Suorittaa koodin optimoinnit luodussa objektimoduulissa.

· Syntaktisesti suuntautunut (syntaktisesti ohjattu). Se vastaanottaa syötteenä kuvauksen kielen syntaksista ja semantiikasta sekä tekstistä kuvatulla kielellä, joka käännetään määritellyn kuvauksen mukaisesti.

· testata. Joukko kokoonpanokielimakroja, joiden avulla voit määrittää erilaisia ​​virheenkorjaustoimenpiteitä kokoonpanokielellä kirjoitetuissa ohjelmissa.

Kääntäjät toteutetaan muodossa kääntäjät tai tulkit . Työnteon kannalta kääntäjä ja tulkki ovat hyvin erilaisia.

Kääntäjä(Englanti) kääntäjä- kääntäjä, kerääjä) - kääntäjä, joka suorittaa käännetyn ohjelman muunnoksen alkuperäinen kieli, objektimoduuliin. Ohjelma, joka kääntää korkean tason kieliohjelman tekstin vastaavaksi konekieliohjelmaksi.

· Ohjelma, joka on suunniteltu kääntämään korkean tason kieli absoluuttiseksi koodiksi tai joskus kokoonpanokieleksi. Kääntäjän syöttötieto (lähdekoodi) on kuvaus algoritmista tai ohjelmasta toimialuekohtaisella kielellä ja kääntäjän tulos on vastaava kuvaus algoritmista konesuuntautuneella kielellä (objektikoodilla).

Kokoaminen- lähdekielellä kirjoitetun ohjelman kääntäminen objektimoduuliksi. Kääntäjän toteuttama.

Kokoa - kääntää koneohjelma ongelmalähtöisestä kielestä konesuuntautuneeksi kieleksi.

Kääntäjä lukee koko ohjelman täysin, kääntää sen ja luo ohjelmasta täydellisen version konekielellä, joka sitten suoritetaan.

Tulkki(Englanti) tulkki- tulkki, tulkki) kääntää ja suorittaa ohjelman rivi riviltä. Tulkki ottaa ohjelmatekstistä seuraavan kielen käskyn, analysoi sen rakenteen ja suorittaa sen sitten välittömästi (yleensä analyysin jälkeen lause käännetään joksikin väliesitykseen tai jopa konekoodiksi tehokkaampaa jatkosuoritusta varten). Vasta sen jälkeen, kun nykyinen käsky on suoritettu onnistuneesti, tulkki siirtyy seuraavaan. Lisäksi, jos sama käsky suoritetaan useita kertoja ohjelmassa, tulkki suorittaa sen ikään kuin se olisi tavannut sen ensimmäistä kertaa. Tämän seurauksena paljon laskentaa vaativat ohjelmat toimivat hitaasti. Lisäksi, jotta voit ajaa ohjelman toisella tietokoneella, siellä on oltava myös tulkki - loppujen lopuksi ilman sitä teksti on vain joukko merkkejä.

Toisella tavalla voidaan sanoa, että tulkki mallintaa jonkin laskennallisen virtuaalikoneen jolle perusohjeet eivät ole perusprosessorikomentoja, vaan ohjelmointikielioperaattoreita.

Erot kokoamisen ja tulkinnan välillä.

1. Kun ohjelma on käännetty, lähdeohjelmaa tai kääntäjää ei enää tarvita. Samalla tulkin käsittelemän ohjelman täytyy uudelleen siirtää konekielelle joka kerta, kun ohjelma ajetaan.

2. Käännetyt ohjelmat toimivat nopeammin, mutta tulkittuja ohjelmia on helpompi korjata ja muuttaa.

3. Jokainen kieli keskittyy joko kokoamiseen tai tulkintaan riippuen tarkoituksesta, jota varten se on luotu. Esimerkiksi, Pascal käytetään yleensä melko monimutkaisten ongelmien ratkaisemiseen, joissa ohjelmien nopeus on tärkeä. Siksi tämä kieli toteutetaan yleensä käyttämällä kääntäjä.

Toisella puolella, PERUS luotiin kieleksi aloitteleville ohjelmoijille, joille ohjelman suorittamisesta rivi riviltä on kiistattomia etuja.

Lähes kaikki matalan tason ja kolmannen sukupolven ohjelmointikielet, kuten assembler, C tai Modula-2, käännetään, kun taas korkeamman tason kielet, kuten Python tai SQL, tulkitaan.

Joskus se on yhdelle kielelle ja kääntäjä, ja tulkki. Tässä tapauksessa voit käyttää tulkkia ohjelman kehittämiseen ja testaamiseen ja sitten kääntää virheenkorjausohjelma sen suorittamisen nopeuttamiseksi. Käännös- ja tulkkausprosessit tunkeutuvat toisiinsa: tulkit voivat olla kääntäjiä (mukaan lukien dynaamisen kääntäjät), ja kääntäjät voivat vaatia tulkintaa metaohjelmointirakenteille (esimerkiksi makrot kokoonpanokielellä, ehdollinen käännös C-kielellä tai mallit C++:ssa).

4. Kääntäminen ja tulkkaus ovat eri prosesseja: kääntäminen käsittelee ohjelmien kääntämistä kielestä toiseen ja tulkkaus vastaa ohjelmien suorittamisesta. Koska kääntämisen tarkoituksena on kuitenkin yleensä valmistella ohjelma tulkkausta varten, näitä prosesseja tarkastellaan yleensä yhdessä.

Johtopäätös: Kääntäjän haittana on ohjelmointikielten kääntämisen työlisyys, jotka ovat tietosuuntautuneita ja monimutkaisia ​​rakenteita, joita usein ei tunneta etukäteen tai jotka muuttuvat dynaamisesti ohjelman toiminnan aikana. Sitten joudut lisäämään konekoodiin paljon lisätarkistuksia, analysoimaan käyttöjärjestelmän resurssien saatavuutta, sieppaamaan ja vapauttamaan ne dynaamisesti, muotoilemaan ja käsittelemään ne tietokoneen muistissa. monimutkaisia ​​esineitä, joka on melko vaikea toteuttaa kovakoodattujen konekäskyjen tasolla ja lähes mahdoton tehtävän kannalta.

Tulkin avulla päinvastoin on sallittua pysäyttää ohjelma milloin tahansa, tutkia muistin sisältöä, järjestää vuoropuhelua käyttäjän kanssa, suorittaa mielivaltaisesti monimutkaisia ​​muunnoksia ja samalla seurata jatkuvasti ohjelman tilaa. ympäröivään ohjelmisto- ja laitteistoympäristöön, jolloin saavutetaan korkea luotettavuus. Jokaista lausetta suoritettaessa tulkki tarkistaa monet käyttöjärjestelmän ominaisuudet ja tarvittaessa tiedottaa kehittäjälle mahdollisimman yksityiskohtaisesti esiin tulevista ongelmista. Lisäksi tulkkia on erittäin kätevä käyttää ohjelmoinnin oppimisen työkaluna, koska sen avulla voit ymmärtää minkä tahansa kielen yksittäisen lausunnon toimintaperiaatteet.

Kokoamisprosessi on jaettu useisiin vaiheisiin:

1. Esiprosessori. Lähdeohjelma käsitellään korvaamalla olemassa olevat makrot ja otsikkotiedostot.

2. Leksinen ja syntaktinen analyysi. Ohjelma muunnetaan merkkijonoksi ja sitten sisäiseksi puuesitykseen.

3. Globaali optimointi. Ohjelman sisäistä esitystapaa muutetaan toistuvasti ohjelman koon ja suoritusajan pienentämiseksi.

4. Koodin luominen. Sisäinen esitys muunnetaan prosessorin käskylohkoiksi, jotka muunnetaan assembler-tekstiksi tai objektikoodiksi.

5. Kokoonpano. Jos kokoonpanoteksti luodaan, se kootaan objektikoodin saamiseksi.

6. Kokoonpano. Assembler yhdistää useita objektitiedostoja suoritettavaksi tiedostoksi tai kirjastoksi.

Vaiheessa leksikaalinen analyysi (LA) syöttöohjelma, joka on merkkivirta, on jaettu lekseemeihin - sanoihin kielen määritelmien mukaisesti. Pääasiallinen formalismi leksikaalisten analysaattoreiden toteutuksen taustalla ovat äärelliset automaatit ja säännölliset lausekkeet. Leksikaalinen analysaattori voi toimia kahdessa päätilassa: joko alirutiinina, jonka jäsentäjä kutsuu seuraavan tunnuksen jälkeen, tai täyden läpimenona, jolloin tuloksena on merkkitiedosto. Poimiessaan merkkejä LA voi itsenäisesti rakentaa nimi- ja vakiotaulukoita ja antaa arvot kullekin tunnukselle seuraavan kerran, kun sitä käytetään. Tässä tapauksessa nimitaulukko rakennetaan myöhemmissä vaiheissa (esimerkiksi jäsentämisen aikana).

LA-vaiheessa havaitaan joitain (yksinkertaisimpia) virheitä (virheelliset merkit, virheellinen numeroiden, tunnisteiden tallennus jne.).

Tarkastellaanpa yksityiskohtaisemmin leksikaalisen analyysin vaihetta.

Leksikaalisen analyysin päätehtävä - murskata sijoita teksti, joka koostuu yksittäisten merkkien sarjasta, sanajonoksi tai lekseemiksi, ts. eristä nämä sanat jatkuvasta merkkijonosta. Tästä näkökulmasta katsottuna kaikki syöttösekvenssin merkit on jaettu merkkeihin, jotka kuuluvat joihinkin lekseemiin ja merkkeihin, jotka erottavat lekseemit (erottimet). Joissakin tapauksissa merkkien välillä ei ehkä ole erottimia. Toisaalta joillakin kielillä merkit voivat sisältää merkityksettömiä merkkejä (esimerkiksi välilyöntiä Fortranissa). C:ssä erotinmerkkien erotusarvo voidaan estää ("\" rivin lopussa "..." sisällä).

Yleensä kaikki lekseemit on jaettu luokkiin. Esimerkkejä tällaisista luokista ovat numerot (kokonaisluku, oktaali, heksadesimaali, reaali jne.), tunnisteet, merkkijonot. Avainsanat ja välimerkit (joita joskus kutsutaan erotinsymboleiksi) korostetaan erikseen. Tyypillisesti avainsanat ovat joitain rajallisia tunnisteiden osajoukkoja. Joissakin kielissä (esim. PL/1) lekseemin merkitys voi riippua sen kontekstista, eikä leksikaalista analyysiä voida tehdä erillään syntaktisesta.

Analyysin lisävaiheiden näkökulmasta leksikaalinen analysaattori tuottaa kahdenlaista tietoa: leksikaalisen analysaattorin jälkeen työskentelevälle syntaktiselle analysaattorille tieto merkkien, erottimien ja avainsanojen luokkien järjestyksestä on olennaista ja kontekstianalyysi, työskennellessään syntaktisen jälkeen, tieto yksittäisten lekseemien erityisistä merkityksistä (tunnisteet, numerot jne.) on tärkeää.

Siten leksikaalisen analysaattorin yleinen kaavio on seuraava. Ensin varataan yksi merkki (ehkä käyttämällä erotinmerkkejä). Avainsanat tunnistetaan joko nimenomaisella valinnalla suoraan tekstistä tai ensin osoitetaan tunniste, jonka jälkeen tarkistetaan, kuuluuko se avainsanajoukkoon.

Jos valittu lekseema on erotin, niin se (tarkemmin sanottuna jotkin sen ominaisuudet) tulostetaan leksikaalisen analyysin tuloksena. Jos valittu lekseema on avainsana, palautetaan vastaavan avainsanan attribuutti. Jos valittu lekseema on tunniste, tunnisteen attribuutti palautetaan ja itse tunniste tallennetaan erikseen. Lopuksi, jos valittu merkki kuuluu johonkin muuhun merkkiluokkiin (esimerkiksi merkki on numero, merkkijono jne.), palautetaan vastaavan luokan attribuutti ja tunnuksen arvo tallennetaan. erikseen.

Leksikaalinen analysaattori voi olla joko itsenäinen käännösvaihe tai "anna tunnus" -periaatteella toimiva aliohjelma. Ensimmäisessä tapauksessa (kuva 3.1, a) analysaattorin ulostulona on token-tiedosto, toisessa (Kuva 3.1, b) tunniste annetaan aina, kun analysaattoria käytetään (tässä tapauksessa sääntö, merkkiluokan attribuutti palautetaan "leksikaalisen analysaattorin" tuloksena ja tunnuksen arvo välitetään globaalin muuttujan kautta). Token-arvojen käsittelyssä jäsentäjä voi joko yksinkertaisesti palauttaa kunkin tunnuksen arvon, jolloin objektitaulukoiden (tunnisteet, merkkijonot, numerot jne.) rakentaminen siirtyy myöhempään vaiheeseen, tai se voi rakentaa itse objektitaulukoita. . Tässä tapauksessa lekseemin arvoksi annetaan osoitin vastaavan taulukon merkintään.

Riisi. 3.1:

Leksikaalisen analysaattorin työn antaa jokin äärellinen automaatti. Suora kuvaus kuitenkin valtion kone käytännön kannalta hankalaa. Siksi leksikaalisen analysaattorin määrittämiseen käytetään yleensä joko säännöllistä lauseketta tai oikea-lineaarista kielioppia. Kaikilla kolmella formalismilla (äärelliset automaatit, säännölliset lausekkeet ja oikea-lineaariset kieliopit) on sama ilmaisuvoima. Erityisesti mukaan tavallinen ilme tai oikea-lineaarinen kielioppi, voidaan rakentaa tilakone, joka tunnistaa saman kielen.

Jäsennyksen päätehtävä - ohjelman rakenteen analyysi. Rakenne ymmärretään pääsääntöisesti puuksi, joka vastaa jäsentämistä kielen yhteydettömässä kielioppissa. Tällä hetkellä yleisimmin käytetään joko LL(1)-analyysiä (ja sen muunnelmaa rekursiivista laskeutumista) tai LR(1)-analyysiä ja sen muunnelmia (LR(0), SLR(1), LALR(1) ja muut). Rekursiivista laskeutumista käytetään useammin jäsennin manuaalisessa ohjelmoinnissa, LR(1) - käytettäessä automaatiojärjestelmiä jäsentimien rakentamiseen.

Jäsentämisen tulos on syntaksipuu, jossa on linkit nimitaulukkoon. Jäsennysprosessi havaitsee myös ohjelman rakenteeseen liittyvät virheet.

Kontekstianalyysin vaiheessa ohjelman osien väliset riippuvuudet, joita ei voida kuvata yhteydettömällä syntaksilla, paljastetaan. Nämä ovat pääasiassa "kuvaus-käyttö" -suhteita, erityisesti objektityyppien analysointia, laajuuksien analysointia, parametrien täsmäämistä, etikettejä ja muita. Kontekstianalyysin prosessissa rakennetaan symbolitaulukko, jota voidaan pitää nimitaulukona, jota täydennetään tiedoilla objektien kuvauksista (ominaisuuksista).

Pääasiallinen kontekstuaalianalyysissä käytetty formalismi on attribuuttien kieliopit. Kontekstianalyysivaiheen tulos on määritelty ohjelmapuu. Tieto objekteista voidaan joko hajauttaa itse puuhun tai keskittää erillisiin symbolitaulukoihin. Kontekstuaalisen analyysin prosessi voi myös havaita virheitä, jotka liittyvät esineiden väärinkäyttöön.

Sitten ohjelma voi olla muunnetaan sisäiseksi esitykseksi . Tämä tehdään optimoinnin ja/tai koodin luomisen mukavuuden vuoksi. Toinen tavoite ohjelman muuntamiseksi sisäiseksi esitykseksi on halu saada kannettava kääntäjä. Tällöin vain viimeinen vaihe (koodin luominen) on koneesta riippuvainen. Sisäisenä esityksenä voidaan käyttää etu- tai jälkiliitteen merkintää, suunnattua kuvaajaa, kolmois-, nelinkertaisia ​​ja muita.

Optimointivaiheita voi olla useita . Optimoinnit yleensä jaetaan koneista riippuvaisiin ja koneista riippumattomiin, paikallisiin ja globaaleihin. Osa konekohtaisesta optimoinnista suoritetaan koodin generointivaiheessa. Globaali optimointi yrittää ottaa huomioon koko ohjelman rakenteen, paikallisen - vain pieniä fragmentteja siitä. Globaali optimointi perustuu globaaliin virtausanalyysiin, joka suoritetaan ohjelmakaaviolle ja on olennaisesti tämän kaavion muunnos. Tässä tapauksessa voidaan ottaa huomioon sellaiset ohjelman ominaisuudet kuin prosessien välinen analyysi, moduulien välinen analyysi, muuttujien elinalueiden analyysi jne.

Lopuksi, koodin luominen- käännöksen viimeinen vaihe. Sen tuloksena on joko assembler-moduuli tai objekti- (tai käynnistys)moduuli. Koodin luomisen aikana jotkut paikalliset optimoinnit, kuten rekisterien jakaminen, pitkien tai lyhyiden hyppyjen valinta, ottaen huomioon komentojen kustannukset tiettyä komentosarjaa valittaessa. Koodin luomiseen on kehitetty erilaisia ​​menetelmiä, kuten päätöstaulukoita, dynaamista ohjelmointia sisältävää mallinsovitusta ja erilaisia ​​syntaktisia menetelmiä.

Tietyt kääntäjän vaiheet voivat tietysti puuttua kokonaan tai olla yhdistettyinä. Yksinkertaisimmassa tapauksessa yhden kierron kääntäjässä ei ole mitään eksplisiittistä vaihetta väliesityksen ja optimoinnin generoimiseksi, loput vaiheet yhdistetään yhdeksi, eikä eksplisiittisesti rakennettua syntaksipuuta ole.

Lähetä hyvä työsi tietokanta on yksinkertainen. Käytä alla olevaa lomaketta

Hyvää työtä sivustolle">

Opiskelijat, jatko-opiskelijat, nuoret tutkijat, jotka käyttävät tietopohjaa opinnoissaan ja työssään, ovat sinulle erittäin kiitollisia.

Isännöi osoitteessa http://www.allbest.ru

Johdanto

1.1 Ylhäältä alas -jäsennys

1.2 Alhaalta ylös -jäsennys

1.2.1 LR(k) - kieliopit

1.2.1.1 LR(0) - kieliopit

1.2.2 LALR(1) kieliopit

2. Kääntäjän kehittäminen

2.1 Vaatimusanalyysi

2.2 Suunnittelu

2.2.1 Leksikaalisen analysaattorin suunnittelu

2.2.4 Jäsentimen ohjelmistototeutus

2.3 Koodaus

2.4 Testaus

Johtopäätös

Luettelo käytetyistä lähteistä

Liite A. Kääntäjän ohjelmatekstin listaus

Liite B. Testitulokset

Liite C. Käännösohjelman kaavio

Johdanto

Kaukana ovat ajat, jolloin ennen ohjelman kirjoittamista piti ymmärtää ja muistaa yli tusina koneohjetta. Nykyaikainen ohjelmoija muotoilee tehtävänsä korkean tason ohjelmointikielillä ja käyttää kokoonpanokieltä vain poikkeustapauksissa. Kuten tiedetään, algoritmiset kielet tulevat ohjelmoijan saataville vasta sen jälkeen, kun näistä kielistä on luotu kääntäjät.

Ohjelmointikielet eroavat toisistaan ​​melkoisesti tarkoituksen, rakenteen, semanttisen monimutkaisuuden ja toteutusmenetelmien osalta. Tämä asettaa omat erityispiirteensä tiettyjen kääntäjien kehittämiselle.

Ohjelmointikielet ovat työkaluja eri aihealueiden ongelmien ratkaisemiseen, mikä määrittää niiden organisaation erityispiirteet ja käyttötarkoituksen erot. Esimerkkejä ovat Fortran tieteelliseen laskemiseen, C järjestelmäohjelmointiin, Prolog johtopäätösongelmien tehokkaaseen kuvaamiseen ja Lisp rekursiiviseen luettelon käsittelyyn. Näitä esimerkkejä voidaan jatkaa. Jokaisella aihealueella on omat vaatimukset itse kielen järjestämiselle. Siksi voidaan havaita operaattorien ja lausekkeiden esitysmuotojen monimuotoisuus, ero perusoperaatioiden joukossa, ohjelmoinnin tehokkuuden heikkeneminen ratkaistaessa aihealueeseen kuulumattomia ongelmia. Kielierot heijastuvat myös kääntäjien rakenteeseen. Lisp ja Prolog suoritetaan useimmiten tulkitsevassa tilassa, koska ne käyttävät dynaamista tietotyyppien generointia laskennan aikana. Fortran-kääntäjille on ominaista tuloksena olevan konekoodin aggressiivinen optimointi, joka tulee mahdolliseksi kielirakenteiden suhteellisen yksinkertaisen semantiikan ansiosta - erityisesti koska vaihtoehtoisia muuttujien nimeämismekanismeja osoittimien tai viitteiden avulla ei ole. Osoittimien läsnäolo C-kielessä tekee erityisvaatimukset Vastaanottaja dynaaminen jakelu muisti.

Kielen rakenne luonnehtii sen käsitteiden välisiä hierarkkisia suhteita, joita kuvataan syntaktisilla säännöillä. Ohjelmointikielet voivat erota hyvinkin toisistaan ​​yksittäisten käsitteiden organisoinnissa ja niiden välisessä suhteessa. PL/1-ohjelmointikieli sallii proseduurien ja funktioiden mielivaltaisen sisäkkäisyyden, kun taas C:ssä kaikkien funktioiden on oltava uloimmalla sisäkkätasolla. C++-kieli sallii muuttujien ilmoittamisen missä tahansa ohjelman kohdassa ennen sen ensimmäistä käyttöä, kun taas Pascalissa muuttujat on määritettävä erityisellä määritysalueella. PL/1 menee vielä pidemmälle tässä asiassa, mikä mahdollistaa muuttujan ilmoittamisen sen käytön jälkeen. Tai voit jättää kuvauksen kokonaan pois ja noudattaa oletussääntöjä. Riippuen päätös, kääntäjä voi analysoida ohjelman yhdellä tai useammalla kierrolla, mikä vaikuttaa käännösnopeuteen.

Ohjelmointikielten semantiikka vaihtelee hyvin laajalla alueella. Ne eroavat paitsi yksittäisten toimintojen toteutuksen erityispiirteistä, myös ohjelmointiparadigmoista, jotka määrittävät ohjelmien kehittämismenetelmien perustavanlaatuiset erot. Toiminnan toteutuksen erityispiirteet voivat koskea sekä käsiteltävien tietojen rakennetta että samojen tietotyyppien käsittelyn sääntöjä. Kielet, kuten PL/1 ja APL, tukevat matriisi- ja vektoritoimintoja. Useimmat kielet toimivat ensisijaisesti skalaarien kanssa tarjoten ohjelmoijien kirjoittamia menetelmiä ja toimintoja taulukoiden käsittelemiseksi. Mutta jopa suoritettaessa kahden kokonaisluvun lisäämistä, kielet, kuten C ja Pascal, voivat käyttäytyä eri tavalla.

Perinteisten rinnalla menettelyohjelmointi, jota kutsutaan myös pakolliseksi, on olemassa sellaisia ​​paradigmoja kuin toiminnallinen ohjelmointi, logiikka ohjelmointi ja olio-ohjelmointi. Kielten käsitteiden ja objektien rakenne riippuu voimakkaasti valitusta paradigmasta, mikä vaikuttaa myös kääntäjän toteutukseen.

Jopa sama kieli voidaan toteuttaa useilla tavoilla. Tämä johtuu siitä, että muodollisten kielioppien teoria sallii erilaisia ​​tapoja jäsentää samoja lauseita. Tämän mukaisesti kääntäjät voivat eri tavoilla saada saman tuloksen (olioohjelman) alkuperäisestä lähdetekstistä.

Kaikilla ohjelmointikielillä on kuitenkin useita Yleiset luonteenpiirteet ja parametrit. Tämä yhteisyys määrittää myös kääntäjien järjestämisen periaatteet, jotka ovat samanlaiset kaikille kielille.

Ohjelmointikielet on suunniteltu helpottamaan ohjelmointia. Siksi niiden operaattorit ja tietorakenteet ovat tehokkaampia kuin konekielissä.

Ohjelmien näkyvyyden lisäämiseksi numerokoodien sijaan symbolinen tai graafiset esitykset kielirakenteet, jotka ovat ihmisten luettavissa.

Jokaiselle kielelle on määritelty:

- joukko symboleja, joilla voidaan kirjoittaa oikeat ohjelmat (aakkoset), peruselementit,

- joukko oikeita ohjelmia (syntaksi),

- jokaisen oikean ohjelman "merkitys" (semantiikka).

Kielen erityispiirteistä riippumatta mitä tahansa kääntäjää voidaan pitää toiminnallisena muuntimena F, joka tarjoaa yksiselitteisen sovituksen X:stä Y:ksi, missä X on lähdekielen ohjelma, Y on tuloskielen ohjelma. Siksi itse käännösprosessi voidaan esittää muodollisesti melko yksinkertaisesti ja selkeästi: Y = F(X).

Muodollisesti jokainen oikea ohjelma X on jonkin aakkoston A merkkijono, joka on muunnettu vastaavaksi merkkijonoksi Y, joka koostuu aakkosten B merkeistä.

Ohjelmointikieli, kuten mikä tahansa monimutkainen järjestelmä, määritellään käsitehierarkialla, joka määrittelee sen elementtien välisen suhteen. Nämä käsitteet liittyvät toisiinsa syntaktisten sääntöjen mukaisesti. Jokaisella näiden sääntöjen mukaan rakennetulla ohjelmalla on vastaava hierarkkinen rakenne.

Tässä suhteessa kaikille kielille ja niiden ohjelmille voidaan lisäksi erottaa seuraavat yhteiset piirteet: jokaisen kielen on sisällettävä säännöt, jotka mahdollistavat tätä kieltä vastaavien ohjelmien luomisen tai kirjoitettujen ohjelmien ja tietyn kielen välisen vastaavuuden tunnistamisen.

Toinen kaikille kielille tyypillinen piirre on niiden semantiikka. Se määrittää kielioperaatioiden merkityksen, operandien oikeellisuuden. Ketjut, joilla on sama syntaktinen rakenne eri ohjelmointikielissä, voivat poiketa semantiikan suhteen (mitä havaitaan esimerkiksi C++:ssa, Pascalissa, Basicissa). Kielen semantiikan tuntemus mahdollistaa sen erottamisen syntaksistaan ​​ja sen käyttämisen toiselle kielelle muuntamiseen (koodin luomiseen).

Tämän kurssityön tarkoituksena on kehittää koulutuskääntäjä tietystä korkean tason yksinkertaistetusta tekstikielestä.

1. Jäsennysmenetelmät

Harkitse kieliopin analyysin perusmenetelmiä.

1.1 Ylhäältä alas -jäsennys

Kun jäsennetään ylhäältä alas, välipäätelmät liikkuvat puuta pitkin juurista lehtiin. Tässä tapauksessa, kun tarkastellaan ketjua vasemmalta oikealle, saadaan luonnollisesti vasen päätelmät. Deterministisessä jäsennyksessä ongelmana olisi, mitä sääntöä sovelletaan vasemmanpuoleisimman epäterminaalin laajentamiseen.

1.1.1 LL(k) - kielet ja kieliopit

Harkitse tulospuuta ketjun vasemman tulosteen saamiseksi. Tulostusprosessin väliketju koostuu pääteketjusta w, vasemmanpuoleisesta ei-päätteestä A, x:n alipainetusta osasta:

-S--

/ \

/ -A-x-\

/ | \

-w---u----

Kuvio 1

Jäsentämisen jatkamiseksi on korvattava ei-pääte A jonkin muodon A:y säännön mukaisesti. Jos jäsentämisen on oltava determinististä (ei paluuta), tämä sääntö on valittava erityisellä tavalla. Kieliopin sanotaan olevan ominaisuus LL(k), jos säännön valitsemiseksi riittää, että huomioidaan vain wax ja etsimättömän merkkijonon u ensimmäiset k merkkiä. Ensimmäinen kirjain L (vasen, vasen) viittaa syötemerkkijonon katselemiseen vasemmalta oikealle, toinen - käytettyyn vasempaan lähtöön.

Määrittelemme kaksi ketjua:

a) FIRST(x) - x:stä johdettu päätemerkkijono, joka on lyhennetty k merkkiin.

b) FOLLOW(A) - joukko päätejonoja lyhennettynä k:ksi, joka voi välittömästi seurata A:ta tulostejonoissa.

Kieliopin ominaisuus on LL(k), jos kahden vasemmanpuoleisen päättelyketjun olemassaolosta:

S::wax:wzx::wu

S::wax:wtx::wv

ehto FIRST(u)=FIRST(v) merkitsee z=t.

Tapauksessa k=1 A:lle säännön valitsemiseksi riittää, että tunnet vain ei-pääteisen A ja a - merkkijonon u ensimmäisen merkin:

- valitse sääntö A:x, jos a on kohdassa FIRST(x),

- Sääntö A:e tulee valita, jos a sisältyy FOLLOW(A) -kohtaan.

LL(k)-ominaisuus asettaa melko voimakkaita rajoituksia kielioppiin. Esimerkiksi LL(2) kielioppi S: aS | a:lla ei ole LL(1)-ominaisuutta, koska FIRST(aS)=FIRST(a)=a. Tässä tapauksessa voit pienentää k:n arvoa käyttämällä "faktorointia" (hakasuluissa tekijä):

S:aA

A: S | e

Mikä tahansa LL(k)-kielioppi on ainutlaatuinen. Vasen rekursiivinen kielioppi ei kuulu minkään k:n LL(k):iin. Joskus on mahdollista muuntaa ei-LL(1)-kielioppi vastaavaksi LL(1)-kieliopiksi poistamalla vasemmanpuoleinen rekursio ja tekijöiden jakaminen. Kuitenkin ongelmaa vastaavan LL(k)-kieliopin olemassaolosta mielivaltaiselle ei-LL(k)-kieliopille ei voida ratkaista.

1.1.2 Rekursiivinen laskeutumismenetelmä

Rekursiivinen laskeutumismenetelmä keskittyy niihin tapauksiin, joissa kääntäjä on ohjelmoitu jollakin korkean tason kielistä, jolloin rekursiivisten proseduurien käyttö on sallittua.

Rekursiivisen laskeutumisen perusidea on, että jokainen kieliopin ei-pääte liittyy proseduuriin, joka tunnistaa minkä tahansa tämän ei-terminaalin muodostaman merkkijonon. Nämä menettelyt kutsuvat toisiaan tarvittaessa.

Rekursiivista laskeutumista voidaan käyttää missä tahansa LL(1)-kieliopissa. jokainen kieliopin ei-pääte vastaa proseduuria, joka alkaa siirtymällä laskettuun nimikkeeseen ja sisältää koodin, joka vastaa kutakin tämän ei-päätelaitteen sääntöä. Niille syöttösymboleille, jotka kuuluvat valintajoukkoon tämä sääntö, laskettu haara siirtää ohjauksen koodille, joka vastaa tätä sääntöä. Muiden syötemerkkien osalta ohjaus siirtyy virheenkäsittelyrutiinille.

Minkä tahansa säännön koodi sisältää toiminnot jokaiselle merkin sisältämälle merkille oikea puoli säännöt. Toiminnot on lueteltu siinä järjestyksessä, jossa symbolit esiintyvät säännössä. Viimeisen toiminnon jälkeen koodi sisältää palautuksen proseduurista.

Rekursiivisen laskeutumisen käyttö korkean tason kielessä helpottaa ohjelmointia ja virheenkorjausta.

1.2 Alhaalta ylös -jäsennys

Tarkastellaan alhaalta ylös -jäsennystä, jossa välipäätelmät liikkuvat puuta pitkin juurta kohti. Jos luet merkkijonon merkit vasemmalta oikealle, jäsennyspuu näyttää tältä:

-S--

/ \

/-x-\

/ | \

--w--b--u-

Kuva 2

Välitulosteen muoto on xbu, jossa x on ketju päätteitä ja ei-päätteitä, joista tulostetaan pääteketjun w skannattu osa, bu on pääteketjun skannaamaton osa, b on seuraava merkki. Jatkaksesi jäsentämistä, voit joko lisätä merkin b ketjun skannattuun osaan (suorita ns. "shift") tai valita x:n lopusta sellaisen ketjun z (x=yz), joka on jokin kielioppi. sääntöjä B:z voidaan soveltaa z:hen ja korvata x ketjussa yB (suorita ns. "konvoluutio"):

-S-- -S--

/ \ / \

/-x-b- \ /yB- \

/ | \ / | \

--w--b--u- --w--b--u-

Kuva 3 - Siirron jälkeen Kuva 4 - Konvoluution jälkeen

Jos konvoluutiota sovelletaan vain viimeiset merkit x, niin saamme ketjun oikeat lähdöt. Tätä jäsentämistä kutsutaan LR:ksi, jossa symboli L (vasen, vasen) viittaa ketjun katselemiseen vasemmalta oikealle ja R (oikea, oikea) viittaa tuloksena olevaan ulostuloon.

Vuoro- ja sopimustoimintojen järjestys on olennainen. Siksi deterministinen jäsentäminen edellyttää, että valitset joka hetki siirtymän ja supistumisen (ja erilaisten konvoluutiosääntöjen) välillä.

1.2.1 LR(k) - kieliopit

Jos LR-jäsentämisen aikana on mahdollista tehdä deterministinen siirtymä/kutistumispäätös ottamalla huomioon vain merkkijono x ja syötemerkkijonon u skannaamattoman osan ensimmäiset k merkkiä (näitä k merkkiä kutsutaan ennakkomerkkijonoksi), kielioppi sanotaan olevan LR(k)-ominaisuus.

-S--

/ \

/-x-\

--w----u--

Kuva 5

Ero LL(k)- ja LR(k)-kielioppien välillä johdannaispuun suhteen:

-S-

/ | \

/A\

/ / \ \

-w---v---u-

Kuva 6

LL(k)-kielioppien tapauksessa A:hen sovellettava sääntö voidaan määrittää yksiselitteisesti w:llä ja vu:n ensimmäisellä k symbolilla ja LR(k)-kielioppien tapauksessa w,v:llä ja ensimmäisellä k:lla. symbolit sinusta. Tämä löysä argumentti osoittaa, että LL(k)-kielet< LR(k)-языки (при k > 0).

1.2.1.1 LR(0) - kieliopit

Tarkastellaan ensin tämän luokan yksinkertaisimpia kielioppeja - LR(0). Jäsennettäessä merkkijonoa LR(0)-kielellä ei tarvitse käyttää alkuketjua ollenkaan - valinta siirtymän ja supistuksen välillä tehdään merkkijonon x perusteella. Koska se muuttuu vain oikeasta päästä jäsentämisen aikana, sitä kutsutaan pinoksi. Oletetaan, että kielioppia ei ole hyödyttömiä hahmoja ja aloitussymboli ei esiinny sääntöjen oikealla puolella - silloin konvoluutio aloitussymboliin merkitsee jäsentämisen onnistunutta loppuun. Yritetään kuvata terminaalien ja ei-päätteiden ketjuja, jotka näkyvät pinossa kaikkien LR-jäsennysten aikana (eli kaikki oikeat päätelmät kieliopin perusteella).

Määrittelemme seuraavat joukot:

L(A:v) - säännön vasen konteksti A:v - pinon tilojen joukko, välittömästi ennen v:n romahtamista A:ksi kaikkien onnistuneiden LR-jäsennysten aikana. Ilmeisesti jokainen L(A:v):n merkkijono päättyy v:ään. Jos kaikkien tällaisten ketjujen häntä v katkaistaan, saadaan ketjut, jotka esiintyvät A:n vasemmalla puolella kaikkien onnistuneiden oikeanpuoleisten päätelmien prosessissa. Merkitse tätä joukkoa L(A) - ei-terminaalin A vasenta kontekstia.

Muodostetaan kielioppi joukolle L(A). Alkuperäisen kieliopin terminaalit ja ei-päätteet ovat uuden kieliopin päätteitä; uuden kieliopin ei-päätteet merkitään ,... - niiden arvot ovat alkuperäisen kieliopin ei-päätteiden vasenta kontekstia. Jos S on alkuperäisen kieliopin alkusymboli, vasemmanpuoleisten kontekstien kielioppi sisältää säännön : e - S:n vasen konteksti sisältää tyhjän merkkijonon jokaiselle alkuperäisen kieliopin säännölle, esim. A: B C d E

ja lisää säännöt uuteen kielioppiin:

: - L(B) sisältää L(A)

: B - L(C) sisältää L(A) B:n

: B C d - L(E) sisältää L(A) B C d

Tuloksena olevalla kielioppilla on erityinen muoto (tällaisia ​​​​kielioppeja kutsutaan vasen-lineaarisiksi), siksi vasemmiston kontekstien joukot

- ovat säännöllisiä. Tästä seuraa, että jonkin ei-terminaalin vasemmassa kontekstissa olevan merkkijonon jäsenyys voidaan laskea induktiivisesti äärellisellä automaatilla skannaamalla merkkijonoa vasemmalta oikealle. Kuvailkaamme tätä prosessia rakentavasti.

Kutsutaan LR(0)-tilannetta kielioppisäännöksi, jossa on yksi merkitty paikka säännön oikean puolen symbolien välissä. Esimerkiksi kielioppi S:A; A:aAA; A:b on seuraavat LR(0)-tilanteet: S:_A; S:A_; A:_aAA; A:a_AA; A:aA_A; A:aAA_; A:_b; A:b_. (sijainti on merkitty alaviivalla).

Sanotaan, että ketju x on yhdenmukainen tilanteen А:b_c kanssa, jos x=ab ja a kuuluu ryhmään L(A). (Toisin sanoen LR-päättelyä voidaan jatkaa x_... = ab_...:: abc_...:: aA_...:: S_.) Näissä termeissä L(A:b) on joukko merkkijonot, jotka vastaavat tilannetta A:b_, L(A)

- tilanteen A:_b mukaiset ketjut mille tahansa säännölle A:b.

Olkoon V(u) tilanteiden joukko, jotka ovat yhdenmukaisia ​​u:n kanssa. Osoitetaan, että funktio V on induktiivinen.

Jos joukko V(u) sisältää tilanteen A:b_cd, niin tilanne A:bc_d kuuluu ryhmään V(uc). (c - terminaalinen tai ei-pääte; b, d - terminaalien ja ei-terminaalien sekvenssit (voivat olla tyhjiä). Ei ole muita tilanteita, kuten A:b_d, jossa V(uc) ei ole tyhjä b. Jäljelle jää lisätä tilanteet muotoa C:_... V(uc):iin jokaiselle ei-terminaalille C:lle, jonka vasen konteksti sisältää uc. Jos tilanne A:..._C... (C-ei-pääte) kuuluu joukkoon V(uc), niin uc kuuluu ryhmään L(C) ja V(uc) sisältää tilanteet muotoa C:_... kaikille C-kieliopin säännöille.

V(e) sisältää tilanteet S:_... (S-alkumerkki), sekä tilanteet A:_..., jos ei-pääte A esiintyy välittömästi _:n jälkeen tilanteissa, jotka sisältyvät jo kohtaan V(e) .

Lopuksi olemme valmiita määrittelemään LR(0)-kieliopin. Olkoon u pinon sisältö LR-jäsennyksen aikana ja olkoon V(u) u:n mukaisten LR(0)-tilanteiden joukko. Jos V(u) sisältää tilanteen, joka on muotoa A:x_ (päätteiden ja ei-terminaalien x-jono), niin u kuuluu L(A:x) ja x voidaan taittaa A:ksi. Jos V(u) sisältää tilanteen A:..._a. .. (a-pääte), silloin siirto on sallittu. Siirto-vähennys-konfliktista puhutaan, jos sekä siirto että supistuminen sallitaan samalle merkkijonolle u. Puhutaan fold-fold-konfliktista, jos kippaukset ovat sallittuja eri sääntöjen mukaan.

Kielioppia kutsutaan LR(0):ksi, jos LR-päättelyprosessin kaikille pinon tiloille ei ole vaihto- tai rullauskonflikteja.

1.2.1.2 LR(k) - kieliopit

Vain pinon tilaa käytetään LR(0)-jäsennyksessä valitsemaan siirron tai supistamisen välillä. LR(k)-jäsennys ottaa huomioon myös syötemerkkijonon näkymättömän osan (ns. esimerkkijonon) k-ensimmäiset merkit. Menetelmän perustelemiseksi tulee huolellisesti toistaa edellisen osan argumentit ja tehdä muutoksia määritelmiin.

Sisällytämme myös ennakkoketjun säännön vasempaan kontekstiin. Jos oikea johtaminen käyttää johdannaista wAu: wvu, niin pari wv,FIRSTk(u) kuuluu Lk(A:v) ja pari w,FIRSTk(u) kuuluu Lk(A). Vasemmanpuoleisten kontekstien joukko, kuten LR(0):n tapauksessa, voidaan laskea käyttämällä vasemman ketjun induktiota. Kutsutaan LR(k)-tilannetta pariksi: kielioppisääntö, jossa on merkitty paikka ja enintään k pituinen etuketju. Erottelemme säännön ennakkoketjusta pystyviivalla.

Sanotaan, että ketju x on yhdenmukainen tilanteen A:b_c|t kanssa, jos on LR-ulostulo: x_yz = ab_yz:: abc_z:: aA_z:: S_ ja FIRSTk(z)=t. Tilajoukon Vk induktiivisen laskennan säännöt ovat seuraavat:

Vk(e) sisältää S:_a|e-tilanteet kaikille S:a-säännöille, joissa S on alkusymboli. Jokaiselle Vk(e)-tilanteelle A:_Ba|u, jokaiselle säännölle B:b ja FIRSTk(au:hun kuuluvalle ketjulle x) on lisättävä tilanne B:_b|x kohtaan Vk(e).

Jos tilanne A:b_cd|u tulee Vк(w), niin tilanne A:bc_d|u kuuluu Vk(wc:hen). Jokaiselle Vk(wc:n) tilanteelle A:b_Cd|u, jokaiselle säännölle C:f ja FIRSTk(du) kuuluvalle ketjulle x on lisättävä tilanne C:_f|x kohtaan Vk(wc).

Käytämme konstruoituja LR(k)-tilojen joukkoja siirtokonvoluutio-ongelman ratkaisemiseen. Olkoon u pinon sisältö ja x ennakkoketju. Ilmeisesti A:b-konvoluutio voidaan suorittaa, jos Vk(u) sisältää tilanteen A:b_|x. Siirron hyväksymisen päättäminen edellyttää tarkkuutta, jos kielioppi sisältää e-säännöt. Tilanteessa A:b_c|t (c ei ole tyhjä), siirto on mahdollista, jos c alkaa terminaalista ja x kuuluu kohtaan FIRSTk(ct). Epävirallisesti puhuen, voit työntää säännön oikean puolen vasemmanpuoleisen merkin pinoon valmistaen seuraavan konvoluution. Jos c alkaa ei-päätteestä (tilanne näyttää tältä A:b_Cd|t), niin symbolin työntäminen pinoon ja C:n foldin valmistaminen on mahdollista vain, jos C ei synnytä tyhjää merkkijonoa. Esimerkiksi tilassa V(e)= S:_A|e; A:_AaAb|e,a, A:_|e,a johdettaessa pääteketjuja A:sta, jossain vaiheessa on sovellettava sääntöä A:e ketjun vasemmassa päässä sijaitsevaan ei-terminaaliseen A:han.

Määritellään joukko EFFk(x), joka koostuu kaikista joukon FIRSTk(x) alkioista, jonka johtaminen ei korvaa x:n vasemmassa päässä olevaa ei-päätettä (jos sellainen on) tyhjällä merkkijonolla. Näissä termeissä siirto on sallittu, jos joukko Vk(u) sisältää tilanteen А:b_c|t, c ei ole tyhjä ja x kuuluu kohtaan EFFk(ct).

Kielioppia kutsutaan LR(k)-kieliopiksi, jos mikään LR(k)-tila ei sisällä kahta tilannetta A:b_|u ja B:c_d|v siten, että u kuuluu ryhmään EFFk(dv). Tällainen pari vastaa taitto-konfliktia, jos d on tyhjä, ja shift-fold-konfliktia, jos d ei ole tyhjä.

Käytännössä LR(k)-kielioppeja ei käytetä k>1:lle. Tähän on kaksi syytä. Ensimmäinen: erittäin iso luku LR(k) toteaa. Toiseksi mille tahansa LR(k)-kielen määrittelemälle kielelle on olemassa LR(1)-kielioppi; Lisäksi jokaiselle deterministiselle CF-kielelle on olemassa LR(1)-kielioppi.

LR(1)-tilojen lukumäärä käytännössä mielenkiintoisia kielioppeja myös erittäin suuri. Tällaisilla kieliopeilla on harvoin LR(0)-ominaisuus. Käytännössä käytetään yleisemmin LR(0):n ja LR(1):n välissä olevaa menetelmää, joka tunnetaan nimellä ja LALR(1).

1.2.2 LALR(1) kieliopit

Nämä kaksi menetelmää perustuvat samaan ajatukseen. Muodostetaan joukko kieliopin kanonisia LR(0)-tiloja. Jos tämä joukko ei sisällä ristiriitoja, voidaan käyttää LR(0)-jäsennintä. Muussa tapauksessa yritämme ratkaista syntyneet ristiriidat ottamalla huomioon yksimerkkinen esimerkkijono. Toisin sanoen yritetään rakentaa LR(1)-jäsennin joukolla LR(0)-tiloja.

LALR(1)-menetelmä (Look Ahead) on seuraava. Otetaan käyttöön ekvivalenssirelaatio LR(1)-tilanteiden joukkoon: katsotaan kaksi tilannetta ekvivalenttiksi, jos ne eroavat vain ennakkoketjuissa. Esimerkiksi tilanteet A:Aa_Ab|e ja A:Aa_Ab|a ovat vastaavia. Muodostetaan kanoninen joukko LR(1)-tiloja ja yhdistetään tilat, jotka koostuvat joukosta ekvivalenttitilanteita.

Jos tuloksena oleva tilajoukko ei sisällä LR(1)-ristiriitoja ja sen vuoksi mahdollistaa LR(1)-jäsentimen rakentamisen, kieliopin sanotaan olevan LALR(1)-ominaisuus.

2. Kääntäjän kehittäminen

2.1 Vaatimusanalyysi

Tässä kurssityössä on tarpeen kehittää koulutuskääntäjä tulkin muodossa vastaavan muodollisen kieliopin määrittelemästä kielestä. Tulkin kehittämisessä on neljä päävaihetta:

Leksikaalisen analysaattorin suunnittelu;

Aikakauslehtikoneen suunnittelu;

Ohjelmiston täytäntöönpano jäsentimen;

Tulkintamoduulin kehittäminen.

Kehitys toteutetaan Windows XP -käyttöjärjestelmällä henkilökohtaisella tietokoneella. IBM tietokone PC prosessorilla Intel Pentium IV.

Ohjelmistokehityssuuntien perusteella koulutuskääntäjän toteuttamiseen valittiin C#-ohjelmointikieli Visual Studio 2010 -ympäristössä.

2.2 Suunnittelu

2.1.1 Leksikaalisen analysaattorin suunnittelu

Leksikaalinen analyysi sisältää käännetyn (lähde)ohjelman skannauksen ja lähdetekstin lauseet muodostavien lekseemien tunnistamisen. Tokeneita ovat erityisesti avainsanat, operaatiomerkit, tunnisteet, vakiot, erikoismerkit jne.

Leksikaalisen analysaattorin (skannerin) työn tulos on merkkijono, ja jokaista merkkiä edustaa yleensä jokin kiinteän pituinen koodi (esimerkiksi kokonaisluku), sekä syntaktisia (leksiaalisia) koskevia viestejä. ) virheitä, jos niitä on. Jos lekseema on esimerkiksi avainsana, sen koodi antaa kaikki tarvittavat tiedot. Esimerkiksi tunnisteen tapauksessa vaaditaan lisäksi tunnistetun tunnisteen nimi, joka yleensä kirjataan tunnistetaulukkoon, joka on järjestetty pääsääntöisesti listoilla. Samanlainen taulukko tarvitaan vakioille.

Lekseema voidaan kuvata kahdella pääpiirteellä. Yksi niistä on lekseemin kuuluminen tiettyyn luokkaan (muuttujat, vakiot, operaatiot jne.) Toinen attribuutti määrittelee tämän luokan tietyn elementin.

Tietyntyyppisellä symbolitaulukolla (tietorakenteella) ei ole merkitystä lekserin tai jäsentimen kannalta. Molempien tarvitsee vain tarjota kyky hankkia indeksi, joka yksilöi esimerkiksi tietyn muuttujan, ja palauttaa indeksin arvon täydentääkseen tietoja annetusta muuttujan nimestä symbolitaulukossa.

Tunnistetaulukon tarkastelu suorittaa kaksi päätoimintoa:

a) uuden nimen kirjoittaminen taulukkoon muuttujien ilmoitusta käsiteltäessä;

b) etsi taulukkoon aiemmin tallennettu nimi.

Tämä mahdollistaa sellaisten virheellisten tilanteiden havaitsemisen, kuten muuttujan moninkertainen kuvaus ja ilmoittamattoman muuttujan läsnäolo.

Leksikaalisen analysaattorin kehittäminen koostuu osittain erilaisten automaattien mallintamisesta tunnisteiden, vakioiden, varatut sanat jne. Jos rahakkeita eri tyyppiä alkaa samalla merkillä tai samalla merkkijonolla, niiden tunnistaminen voi olla tarpeen yhdistää.

Ajamalla leksikaalista analysaattoria jaamme ohjelmamme tokeneihin, minkä jälkeen jokainen merkki läpäisee pituustarkistuksen (merkki ei saa olla yli 11 merkkiä). Kun tämä vaihe on läpäissyt onnistuneesti, tarkistamme merkkien sijainnin oikeellisuuden (avainsanat var, begin, end, for, to, do, end_for). Sitten analysoimme muuttujatokeneja - niiden kuvauksessa ei pitäisi olla numeroita ja ne toistuvat. Viimeisessä vaiheessa tarkistamme merkkien (avainsanat, tuntemattomat tunnisteet) oikeinkirjoituksen. Jos ainakin yksi tarkistuksista antaa virheen, leksikaalinen analysaattori tulostaa virheen.

Leksikaalisen analysaattorin työohjelman kaavio on esitetty liitteessä B kuvassa B.1.

2.2.2 Automaattimakasiinin suunnittelu

Määritellään seuraava kielioppi:

G: (Vt, Va, I, R),

missä Vt on päätemerkkien joukko, Va on ei-päätemerkkien joukko, I on kieliopin alkutila, R on kieliopin sääntöjen joukko.

Tätä kielioppia varten määrittelemme joukot terminaalisia ja ei-päätemerkkejä:

Laaditaan säännöt kielioppimme G:lle ja esitetään ne taulukossa 1.

Taulukko 1 - Kielioppisäännöt

säännön numero	Säännön vasen puoli	Säännön oikea puoli
		f ID = EX t EX d LE n;
Taulukon 1 jatko.
säännön numero	Säännön vasen puoli	Säännön oikea puoli

Lekseemien nimitykset, lekseemien kääntäminen koodeiksi ja luettelo kielioppinimikkeistä on esitetty taulukoissa 2, 3 ja 4.

Taulukko 2 - Lekseemien merkintä

	Lekseemin merkintä
	avainsana "aloittaa" (toimintojen kuvauksen alku)
	avainsana "end" (toimintojen kuvauksen loppu)
	avainsana "var" (muuttujien ilmoitus)
	"lue" avainsana (tiedonsyöttölause)
	"kirjoita" avainsana (tiedonantolause)
	"for" avainsana (silmukkalause)
	avainsana "to"
	avainsana "tee"
	avainsana "end_case" (silmukan loppulause)
	muuttujatyyppi "integer"
	lisäystoiminto
	vähennysoperaatio
	kertolaskutoiminto
	erotinmerkki ":"
	erotinmerkki ";"
	erotinmerkki "("
	erotinmerkki ")"
	erotinmerkki ","
	Lekseemin merkintä
	erotinmerkki "="

Taulukko 3 - Lekseemien kääntäminen koodeiksi

<цифра>
<буква>

Taulukko 4 - Luettelo kielioppisymboleista

Nimitys	Selitys
	Ohjelmoida
	Laskelmien kuvaus
	Muuttujien kuvaus
	Luettelo muuttujista
	Operaattori
	Tehtävä
	Ilmaisu
	osalauseke
	Binääritoiminnot
	Unaariset operaatiot
	Tehtävälista
	Tunniste
	Vakio

Konstruoidaan deterministinen nouseva tunnistin.

Harkitse seuraavia suhteita rakentaaksesi deterministisen alhaalta ylös -ratkaisun:

a) Jos on ryhmäsymboli B, jossa merkkijono AB sisältyy johonkin kielioppisääntöön ja on symboli xPERV "(B), niin oletetaan, että symbolien x ja A välillä on määritelty suhteet x A:N JÄLKEEN

b) Jos tietyssä kielioppissa on sääntö B-\u003e bAb A, BV a, niin A:n ja x:n välillä määritetään relaatio A MUUNNA x.

Kaikki kielioppimme pysyy samana, eli:

G: (Vt, Va, I, R),

ja kielioppisäännöt D on esitetty taulukossa 5.

Taulukko 5 - Kielioppisäännöt

säännön numero	Säännön vasen puoli	Säännön oikea puoli
		f ID = EX t EX d LE n;?
Taulukon 5 jatko.
säännön numero	Säännön vasen puoli	Säännön oikea puoli

Missä? - merkki ketjun päähän.

Määrittelemme joitain tapauksia:

a) Tunnus koostuu useista kirjaimista Latinalainen aakkoset, eli oletetaan, että u = ( a, b, c, d, e, f,g, h, i,j,k, l,m, n, o, p,q,r,s, t, u, v, w, x, y, z)

b) CO-vakio koostuu luvuista, eli oletetaan, että k = (0,1,2,3,4,5,6,7,8,9)

Jotta kielioppimme olisi sekoitettu ensisijaisuusstrategia, seuraavien ehtojen on täytyttävä:

a) E-sääntöjen puuttuminen

b) Onko olemassa sääntöjä, joiden mukaan x A:n JÄLKEEN? A MUUNTAA x = ?

c) A -> bYg

ja on välttämätöntä, että IN AFTER x? MUUNNOSSA x = ?

eli kieliopissa ne suoritetaan IN AFTER x tai A AFTER x, missä x on ketjun b symbolipredikaatti.

a) PERV "(PG) \u003d (PG?)

PRIM"(RG) = PRIM(DE) = (RG, v,:, i,;)

PRIM" (AL) = PRIM (b LE e) = (AL, b, e)

PERV" (DE) = PERV (v LV: i;) = (DE, v,:, i,;)

PERV" (LV) = PERV (ID, LV) = ( LV, ID )

PERV" (OP) =(OP, ID, CO)

PERV" (EQ) = PERV(ID = EX;) = (EQ, =,;)

PERV" (EX) = (EX, SB, -)

PERV" (BO) =(B0, +,*,-)

ENSIMMÄINEN" (SB) = ENSIMMÄINEN((EX)SB) ? ENSIMMÄINEN(OP) ? ENSIMMÄINEN(VO)=(SB, (,), OP, BO);

PERV" (LE) = PERV(EQ) = (LE, (,), =,;, f, t, d, n, w, r)

PERV" (UO) = (UO,-)

PERV" (ID) = PERV" (u) = (u)

PERV" (CO) = PERV" (k) = (k)PERV" (e) =( e)

PERV" (b) =( b)

PERV" (e) =( e)

PERV" (v) =( v)

PERV" (w) =( w)

PERV" (r) =( r)

PERV" (i) =( i)

PERV" (f) =( f)

PERV" (d) = (d)

PERV" (n) =( n)

PERV" (c) =( c)

PERV" (+) =( +)

PERV" (*) =( *)

PERV" (-) =(-)

PERV" (,) =(,)

PERV" (;) =(;)

PERV" (:) =(:)

PERV" (=) = ( = )

PERV" (() =( ()

PERV" ()) =() )

PERV" (u) = (u)

PERV" (k) = (k)

b) SEURAAVA `(AL) = (?)? SEURAAVA"(PG)=(?,b,e)

SEURAAVA ` (DE) = (?)?PRIM"(AL)= (?, b, e )

SEURAAVA ` (LV) = (?)?PRIM"(:)= (?,:)

SEURAAVA ` (OP) = (?)?PRIM"(SB)= (?,;,), d, t, +, -, *)

SEURAAVA ` (EQ) = (?)?ENSIMMÄINEN"(LE)=(?, (,),;, f, =, t, d, n,w,r )

SEURAAVA ` (EX) = (?)?PRIM"(t)?PRIM"(d)?PRIM"(;)?PRIM"())=(?, t,d,;,))

SEURAAVA ` (BO) = (?)?FIRST"(SB)= (?, (,), OP, BO)

SEURAAVA ` (UO) = (?)?PRIM"(SB)= (?, (,), OP, BO)

SEURAAVA ` (SB) = (?)? SEURAAVA"(EX)= (?, t,d,;,), +, *, -)

SEURAAVA ` (LE) = (?) ?PRIM"(e) ?PRIM"(n) = (?, e, n)

SEURAAVA `(ID)=(?)? SEURAAVA" (OP) ? ENSIMMÄINEN" (=) =(?,;,), d, t, +, -, *, =)

SEURAAVA `(CO) = (?)? SEURAAVA" (OP)= (?,;,), d, t, +, -, *, =)

SEURAAVA ` (b) =(?)?PRIM"(LE)= (?, u, =,;)

SEURAAVA ` (e) =(?)?SEURAAVA"(AL)= (?, b)

SEURAAVA ` (v) =(?)?PRIM"(LV)= (?, u )

SEURAAVA ` (w) =(?)?PRIM"(()= (?, ()

SEURAAVA ` (r) =(?)?PRIM"(() = (?, ()

SEURAAVA ` (i) =(?)?PRIM"(;)= (?,; )

SEURAAVA ` (f) =(?)?PRIM"(ID) = (?, u)

SEURAAVA ` (d) =(?)?PRIM"(LE)= (?, u, =,;)

SEURAAVA ` (n) =(?)?PRIM"(i) = (?, i )

SEURAAVA ` (+) =(?)? SEURAAVA"(IN) = (?, +,*,-)

SEURAAVA ` (-) =(?)? SEURAAVA"(IN) = (?, +,*,-)

SEURAAVA ` (*) =(?)? SEURAAVA"(IN) = (?, +,*,-)

SEURAAVA (;) =(?)?NEXT" (DE)?NEXT `(LE1)?SEURAAVA" (EQ) = (?, b, e, l, u )

SEURAAVA ` (:) =(?)?PRIM"(i)= (?, i )

SEURAAVA ` (=) = (?)?ENSIMMÄINEN"(EX) = (? (,), u, k, +, -, *)

SEURAAVA ` (() =(?)?PRIM"(DE)= (?, v,:, i,;)

SEURAAVA ` ()) =(?)? PERV"(;) = (?,; )

SEURAAVA ` (,) =(?)? PERV"(LV) = (?, u)

SEURAAVA `(u)=(?)? PERV" (ID)= ( u, ?)

SEURAAVA `(k)=(?)? PERV (CO)= (?, k)

c) PG -> DE AL

AL DE:N JÄLKEEN = (b,e) DE:N JÄLKEEN = ((b DE), (e DE) )

e LE:N JÄLKEEN = ((e LE))

VASEN b = ((,), =,;, f, t, d, n, w, r) b = (((b), ()b), (=b), (;b), ( fb), (tb), (db), (nb), (wb), (rb))

;i:n JÄLKEEN = ((; i))

i JÄLKEEN: = ( (i:) )

: LV:n JÄLKEEN = ( (: LV) )

LV JÄLKEEN v = ( (ID, v) )

LV JÄLKEEN, = ((ID,))

ID:N JÄLKEEN = ((,u))

LE AFTER EQ = ((,), =,;, f, t, d, n, w, r ) EQ = (((EQ), () EQ), (= EQ), (; EQ), ( f EQ), (t EQ), (d EQ), (n EQ), (w EQ), (r EQ))

LE -> r (DE);

; JÄLKEEN) = ((;)))

) DE:N JÄLKEEN = (((DE))

DE JÄLKEEN (= (= ((v)), (:)), (i)), (;)), (e)))

(JÄLKEEN r = (((r))

LE -> w (DE);

; JÄLKEEN) = ((;)))

) VIIMEINEN DE = (((DE))

DE JÄLKEEN (= ((v)), (:)), (i)), (;)), (e)))

(W:n JÄLKEEN = (((w))

LE -> f ID = EX t EX d LE n;

; n JÄLKEEN = ((;n))

n LE:N JÄLKEEN = ( (n, LE))

LE d:n JÄLKEEN = (((,), =,;, f, t, d, n, w, r)) ? d:n JÄLKEEN = (((d), ()d), (;d), (f d), (t d), (d d), (n d), (v d), (r d))

d EX:N JÄLKEEN = ((d, EX))

EX t:n JÄLKEEN = (BO, -) ? t:n JÄLKEEN = ((BO t), (- t))

t EXIN JÄLKEEN = ( t EX)

EX AFTER == ((BO, -) ? JÄLKEEN == ((BO=), (-=))

ID:N JÄLKEEN=((=ID))

ID f = ((ID f))

EQ -> ID = EX;

; EXIN JÄLKEEN = ((; EX )

EX AFTER == (BO, -) ? JÄLKEEN == ((BO=), (-=))

u:n JÄLKEEN = ( (=u))

SB UO:N JÄLKEEN = ( (,), OP, BO ) UO:N JÄLKEEN = (((UO), (OP UO), (BO UO) )

) EXIN JÄLKEEN = ( ()EX) )

EX AFTER (= (BO, -) ? AFTER (= ((BO (),), (- ()))

SB->SB BO SB

SB BO:N JÄLKEEN = ((,), OP, BO) BO:N JÄLKEEN = (((BO), ()BO), (OP BO), (BO BO))

BO SB:N JÄLKEEN = (+,*,-) SB:N JÄLKEEN = ((+SB), (*SB), (-SB))

ID u:n JÄLKEEN = ((u, u))

G) PG ->DE AL

AL ROLL PG = AL ROLL SEURAAVA" (PG) = ((AL ?))

e ROLL AL = e ROLL NEXT"(AL)= ((eb), (e?))

=; TAITA SEURAAVAKSI"(DE) = ((;b), (;?))

LV VIRTAUS LV = LV VIRTAUS SEURAAVA" (LV) = ((LV:), (LV?))

ID ROLL LV = ID ROLL SEURAAVA" (LV) = ((ID:), (ID ?))

; MUUNNA LE=; TAITA SEURAAVAKSI" (LE) = ((; e), (;?), (;n))

LE -> f ID = EX t EX d LE n;

; MUUNNA LE=; TAITA SEURAAVAKSI" (LE) = ((; e), (;?), (;n))

EQ ROLL LE = EQ ROLL SEURAAVA" (LE) = ((EQ e), (EQ?), (EQ n))

EQ -> ID = EX;

; MUUNTA EQ=; TAITA SEURAAVAKSI" (EQ) = ((; (), (;)), (;;), (;f), (;?), (;=), (;t), (;d), (; n), (;w), (;r))

SB ROLL EX = SB ROLL SEURAAVA" (EX) = ((SB t), (SB?), (SB d), (SB)), (SB;), (SB(), (SB=), (SBf ), (SBn), (SBw), (SBr) )

) SB ROLL = SB SEURAAVA ROLL" (SB) = (() t), ()?), () d), ())), ();))

OP ROLL SB = OP ROLL SEURAAVA" (SB) = ((OP t), (OP ?), (OP d), (OP)), (OP;))

SB->SB BO SB

SB ROLL SB = SB ROLL SEURAAVA" (SB) = ((SB, t), (SBd), (SB;). (SB)), (SB+), (SB-), (SB*), (SB? ) }

ROLL UO = - ROLL SEURAAVA" (UO) = ( (-?), (--))

ROLL BO = + ROLL SEURAAVA" (BO) = ((++), (+?), (+*), (+-))

* ROLL BO = * ROLL SEURAAVA" (BO) = ((*+), (*?), (**), (*-))

ROLL BO = - ROLL SEURAAVA" (BO) = ((-+), (-?), (-*), (--))

ID ROLL OP = ID ROLL SEURAAVA" (OP) = ((ID+), (ID?), (ID*), (ID-))

TAITTO OP = TAITTO SEURAAVANA" (OP) = ((CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

ID ROLL ID = ID ROLL SEURAAVA" (ID) = ((ID)), (ID ?), (ID k), (ID+), (ID-), (ID*), (ID=), (IDt) , (IDd)))

u ROLL ID = l ROLL NEXT" (ID) = ((u)), (u?), (uk), (u+), (u-), (u*), (u=), (ut), (ud)))

CO ROLL CO = CO ROLL SEURAAVA" (CO) = (CO+), (CO?), (CO*), (CO-), (CO;), (COd), (COt), (CO)))

k ROLL CO = k ROLL NEXT" (CO) = (k+), (k?), (k*), (k-), (k;), (kd), (kt), (k)))

Yksi ristiriitatilanne löytyi sääntöjen taittamisen yhteydessä

OP -> ID ja ID -> u ID

Kirjoitamme ID1 -> ID, joten kirjoitamme uudelleen säännön ID1 -> u ID

Siksi teemme konvoluutiooperaatioita.

ID1 ROLL ID = ID1 ROLL SEURAAVA" (ID) = ((ID1)), (ID1 ?), (ID1 k), (ID1+), (ID1-), (ID1*), (ID1=), (ID1t) , (ID1d)))

Jokaiselle parille (x, A)? x A:N JÄLKEEN rakennamme siirtymäfunktion, joka määrittää siirtotoiminnon ?? (S 0, x, A) \u003d (S 0, A)

? (S0, b, DE) = (S0, DEb)

? (S0, e, DE) = (S0, DEe)

? (S0, e, LE) = (S0, LEe)

? (S0,), b) = (S0, b))

? (S0,;, b) = (SO, b;)

? (S0, (, b) = (S0, b()

? (S0, =, b) = (S0, b=)

? (S0, f, b) = (S0, bf)

? (S0, t, b) = (S0, bt)

? (S0, d, b) = (S0, bd)

? (S0, n, b) = (S0, bn)

? (S0, w, b) = (S0, bw)

? (S0, r, b) = (S0, br)

? (S0,;, i) = (S0, i;)

? (S0, i,:) = (S0, i:)

? (S0,:LV) = (S0,LV:)

? (S0, ID, v) = (S0, vID)

? (S0,ID,) = (S0,ID)

? (S0, u) = (S0, u,)

? (S0, (, EQ)= (S0, EQ()

? (S0,), EQ)= (S0, EQ))

? (S0, =, EQ)= (S0, EQ=)

? (S0,;, EQ)= (SO, EQ;)

? (S0, f, EQ)= (S0, EQf)

? (S0, t, EQ) = (S0, EQt)

? (S0, d, EQ) = (S0, EQd)

? (S0, n, EQ) = (S0, EQn)

? (S0, w, EQ) = (S0, EQw)

? (S0, r, EQ) = (S0, EQr)

? (S0,;,)) = (S0,);)

? (S0, (, DE) = (S0, DE()

? (S0,v)) = (S0,)v)

? (S0,;,)) = (S0,);)

? (S0,i,)) = (S0,)i)

? (S0,:,)) = (S0,):)

? (S0,e,)) = (S0,)e)

? (S0, (, r) = (S0, r()

? (S0, (, w) = (S0, w()

? (SO,;, n) = (SO, n;)

? (S0, n, LE) = (S0, LEn)

? (S0, (, d) = (S0, d()

? (S0,), d) = (S0, d))

? (SO,;, d) = (SO, d;)

? (S0, f, d) = (S0, df)

? (S0, t, d) = (S0, dt)

? (S0, d, d) = (S0, dd)

? (S0, n, d) = (S0, dn)

? (S0, w, d) = (S0, dw)

? (S0, r, d) = (S0, dr)

? (S0, d, EX) = (S0, EXd)

? (S0, BO, t) = (S0, tBO)

? (S0, -, t) = (S0, t-)

? (S0, t, EX) = (S0, EXt)

? (S0, BO, =) = (S0, =BO)

? (S0, -, =) = (S0, =-)

? (S0, =, ID) = (S0, ID=)

? (S0, ID, f) = (S0, fID)

? (S0,;, EX) = (S0, EX;)

? (S0, =, u) = (S0, u=)

? (S0, (, UO) = (S0, UO()

? (S0, OP, UO) = (S0, UO OP)

? (S0, BO, UO) = (S0, UO BO)

? (S0,), EX) = (S0, EX))

? (S0, BO, () = (S0, (BO)

? (S0, BO, -) = (S0, -BO)

? (S0, (, BO) = (S0, BO()

? (S0,),BO) = (S0,)BO)

? (S0, OP, BO) = (S0, BOOP)

? (S0, +, SB) = (S0, SB+)

? (S0, *, SB) = (S0, SB*)

? (S0, -, SB) = (S0, SB-)

? (S0, u, u) = (S0, uu)

Jokaiselle parille (x, A)? Ja CONVULT x rakentaa siirtymäfunktio, joka määrittää konvoluution toiminnan? * (S 0, x, bA) \u003d (S 0, B), missä B-> bA

? * (S 0 , AL, ?) = (S 0 , PG)

? * (S 0 , e, b) = (S 0 , AL)

? * (S 0 , n, ?) = (S 0 , AL)

? * (S 0 ,;, b) = (S 0 , DE)

? * (S 0 ,;, ?) = (S 0 , DE)

? * (S 0 ,;, e) = (S 0 , DE)

? * (S 0 , LV,:) = (S 0 , LV)

? * (S 0 , LV, ?) = (S 0 , LV)

? * (S 0 , ID, ?) = (S 0 , LV)

? * (S 0 , ID, e) = (S 0 , LV)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, n) = (S 0 , LE)

? * (S 0 , EQ, n) = (S 0 , LE)

? * (S 0 , EQ, e) = (S 0 , LE)

? * (S 0 , EQ, ?) = (S 0 , LE)

? * (S 0 ,;, e) = (S 0 , LE)

? * (S 0 ,;, ?) = (S 0 , LE)

? * (S 0 ,;, () = (S 0 , EQ)

? * (S 0 ,;,)) = (S 0 , EQ)

? * (S 0 ,;, f) = (S 0 , EQ)

? * (S 0 ,;, =) = (S 0 , EQ)

? * (S 0 ,;, t) = (S 0 , EQ)

? * (S 0 ,;, d) = (S 0 , EQ)

? * (S 0 ,;, n) = (S 0 , EQ)

? * (S 0 ,;, w) = (S 0 , EQ)

? * (S 0 ,;, r) = (S 0 , EQ)

? * (S 0 , SB, ?) = (S 0 , EX)

? * (S 0 , SB, d) = (S 0 , EX)

? * (S 0 , SB,)) = (S 0 , EX)

? * (S 0 , SB,;) = (S 0 , EX)

? * (S 0 , SB, w) = (S 0 , EX)

? * (S 0 , SB, r) = (S 0 , EX)

? * (S 0 , SB, f) = (S 0 , EX)

? * (S 0 , SB, =) = (S 0 , EX)

? * (S 0 , SB, t) = (S 0 , EX)

? * (S 0 , SB, ?) = (S 0 , SB)

? * (S 0 , SB, () = (S 0 , SB)

? * (S 0 , SB,)) = (S 0 , SB)

? * (S 0 , SB, u) = (S 0 , SB)

? * (S 0 , SB, k) = (S 0 , SB)

? * (S 0 , SB, +) = (S 0 , SB)

? * (S 0 , SB, -) = (S 0 , SB)

? * (S 0 , SB, *) = (S 0 , SB)

? * (S 0 , SB, e) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

? * (S 0 ,), ?) = (S 0 , SB)

? * (S 0 ,), t) = (S 0 , SB)

(S 0 ,),)) = (S 0 , SB)

? * (S 0 ,),;) = (S 0 , SB)

? * (S 0 , -, ?) = (S 0 , UO)

? * (S 0 , -, -) = (S 0 , UO)

? * (S 0 , +, +) = (S 0 , BO)

? * (S 0 , +, ?) = (S 0 , BO)

? * (S 0 , +, *) = (S 0 , BO)

? * (S 0 , -, +) = (S 0 , BO)

? * (S 0 , -, ?) = (S 0 , BO)

? * (S 0 , -, *) = (S 0 , BO)

? * (S 0 , -, -)) = (S 0 , BO)

? * (S 0 , *, +) = (S 0 , BO)

? * (S 0 , *, ?) = (S 0 , BO)

? * (S 0 , *, *) = (S 0 , BO)

? * (S 0 , *, -)) = (S 0 , BO)

? * (S 0 , u, +) = (S 0 , BO)

? * (S 0 , u, ?) = (S 0 , BO)

? * (S 0 , u, *) = (S 0 , BO)

? * (S 0 , u, -)) = (S 0 , BO)

? * (S 0 , k, +) = (S 0 , BO)

? * (S 0 , k, ?) = (S 0 , BO)

? * (S 0 , k, *) = (S 0 , BO)

? * (S 0 , k, -)) = (S 0 , BO)

? * (S 0 , CO, ?) = (S 0 , OP)

? * (S 0 , CO, +) = (S 0 , OP)

? * (S 0 , CO, *) = (S 0 , OP)

? * (S 0 , CO, -) = (S 0 , OP)

? * (S 0 , CO,;) = (S 0 , OP)

? * (S 0 , CO, d) = (S 0 , OP)

? * (S 0 , CO, t) = (S 0 , OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, *) = (S 0 , OP)

? * (S 0 , ID, ?) = (S 0 , OP)

? * (S 0 , ID, () = (S 0 , OP)

? * (S 0 , ID,)) = (S 0 , OP)

? * (S 0 , ID, u) = (S 0 , OP)

? * (S 0 , ID, k) = (S 0 , OP)

? * (S 0 , ID, -) = (S 0 , OP)

? * (S 0 , ID, +) = (S 0 , OP)

? * (S 0 , u,)) = (S 0 , I OP)

? * (S 0 , ID1, *) = (S 0 , ID)

? * (S 0 , ID1, ?) = (S 0 , ID)

? * (S 0 , ID1, () = (S 0 , ID)

? * (S 0 , ID1,)) = (S 0 , ID)

? * (S 0 , ID1, u) = (S 0 , ID)

? * (S 0 , ID1, k) = (S 0 , ID)

? * (S 0 , ID1, -) = (S 0 , ID)

? * (S 0 , ID1, +) = (S 0 , ID)

? * (S 0 , u,)) = (S 0 , ID)

? * (S 0 , u, ?) = (S 0 , BO)

? * (S 0 , u, k) = (S 0 , ID)

? * (S 0 , u, *)) = (S 0 , ID)

? * (S 0 , u, -)) = (S 0 , ID)

? * (S 0 , u, +)) = (S 0 , ID)

? * (S 0 , u, d)) = (S 0 , ID)

? * (S 0 , u, t)) = (S 0 , ID)

? * (S 0 , u, =)) = (S 0 , ID)

? * (S 0 , CO, ?) = (S 0 , CO)

? * (S 0 , CO, +) = (S 0 , CO)

? * (S 0 , CO, -) = (S 0 , CO)

? * (S 0 , CO, *) = (S 0 , CO)

? * (S 0 , CO,;) = (S 0 , CO)

? * (S 0 , CO, d) = (S 0 , CO)

? * (S 0 , CO, t) = (S 0 , CO)

? * (S 0 , CO,)) = (S 0 , CO)

? * (S 0 , k, +) = (S 0 , CO)

? * (S 0 , k, -) = (S 0 , CO)

? * (S 0 , k, *) = (S 0 , CO)

? * (S 0 , k,;) = (S 0 , CO)

?? * (S 0 , k, d) = (S 0 , CO)

? * (S 0 , k, t) = (S 0 , CO)

? * (S 0 , k,)) = (S 0 , CO)

? * (S 0 , k, () = (S 0 , CO)

2.2.3 Jäsentimen ohjelmistototeutus

Jäsentäjä (parser) lukee leksikaalisen analysaattorin tuottaman merkkitiedoston, suorittaa kieliopillisen analyysin, näyttää viestejä mahdollisista syntaksivirheistä ja luo lähdeohjelman välimuodon. Jäsentimen kehittämisen lähtökohtana on sopivan pushdown-automaatin suunnittelu ja toteutus.

Alhaalta ylös -jäsennykseen deterministiselle alhaalta ylös -selvittimelle sen suoratoiston jälkeen oikeanlaista AFTER- ja CONVERT-toimintoja käyttämällä on suunniteltava push-pull-kone, jossa on yksityiskohtainen kuvaus kaikista siirtymätoiminnon sisällä olevista siirtymistä.

Työntöautomaattia kehitettäessä rakensimme siirtymäfunktiot, jotka tulevat olemaan jäsentimen perusta. Kaikki siirtymätoiminnot voidaan jakaa kahteen tyyppiin:

Push-pull-koneen toimintajakso ilman syöttösymbolin lukemista (tyhjä jakso);

Push-pull-automaatin sykli syötesymbolin lukemisen kanssa.

Leksikaalista analysaattoria toteutettaessa jaoimme ohjelman tokeneihin ja kirjoitimme ne listaksi. Käsittelemme sitten tämän luettelon jäsentimessä. Syötteeseen lähetämme ohjelmamme (listan), alkusymbolin (PG) ja automaattimakasiinin alamerkin (h0), jonka jälkeen valitsemme haluttu toiminto siirtymä ja rekursiivinen puhelu tehdään.

Jäsentimen työohjelman kaavio on esitetty liitteessä B kuvassa B.2.

2.2.4 Tulkintamoduulin kehittäminen

Kun kehitetään tulkkausmoduulia alkuperäisen ohjelman välimuotona yleisimmin käytetty postfix-merkintämuoto, mikä tekee käännettävän ohjelman suoritusprosessin (tulkinta) toteuttamisen melko helpoksi.

Tarkastellaanpa postfix-ilmaisumuodon muodostamisen ja suorittamisen perusperiaatteita.

Perussäännöt lausekkeen infix-merkinnän muuntamiseksi jälkiliitteeksi ovat seuraavat.

Lukuoperandit lisätään postfix-merkintään, operaatiot työnnetään pinoon.

Jos pinon yläosassa olevalla toiminnolla on korkeampi (tai yhtä suuri) prioriteetti kuin tällä hetkellä luettavalla toiminnolla, pinon toiminto lisätään postfix-merkintään ja nykyinen toiminto työnnetään pinoon. Muussa tapauksessa (alimmalla prioriteetilla) vain nykyinen toiminto työnnetään pinoon.

Luku avoin sulku työnnetään pinoon.

Sulkusulun lukemisen jälkeen kaikki toiminnot ensimmäiseen avaussulkeen asti poksataan pinosta ja lisätään postfix-tietueeseen, minkä jälkeen sekä avaus- että sulkemissulut hylätään, ts. ei ole sijoitettu postfix-tietueeseen tai pinoon.

Kun koko lauseke on luettu, loput pinon toiminnot lisätään postfix-merkintään.

Lausekkeen postfix-merkintä mahdollistaa sen arvioinnin seuraavalla tavalla.

Jos merkki on operandi, se työnnetään pinoon. Jos token on operaatio, määritetty operaatio suoritetaan viimeisille pinoon työnnetyille elementeille (viimeiselle elementille), ja nämä elementit (elementti) korvataan pinossa operaation tuloksella.

Jos leksikaaliset ja syntaktiset analyysit ovat onnistuneet, siirrymme tulkintaan. Ensin tehdään lauseita sanoista, sitten käännetään lausekkeet postfix-merkinnöiksi ja lasketaan.

Tulkin toimintakaavio on esitetty liitteessä B kuvassa B.3.

2.3 Koodaus

Ohjelma on toteutettu C#-kielellä Visual Studio 2010 ohjelmointiympäristössä. Ohjelman teksti on esitetty liitteessä A.

Ohjelmassa on viisi luokkaa. Käyttöliittymä on toteutettu MainForn-luokalla. LexAnalysis-luokan avulla toteutetaan leksikaalinen analyysimoduuli, SynAnalysis on jäsennysmoduuli, Interpreter on tulkintamoduuli, ProgramisciJakPolska on apuluokka lausekkeiden kääntämiseen käänteisiksi puolaksi (postfix).

Ohjelmassa toteutettujen menettelyjen ja toimintojen tarkoitus on kuvattu taulukoissa 6,7,8.

Taulukko 6 - Leksikaalisen analyysin menettelyjen tarkoitus ja toiminnot

Samanlaisia ​​asiakirjoja

Kääntäjä on ohjelma tai tekninen väline, joka suorittaa ohjelman kääntämisen. Pohditaan leksikaalisen analysaattorin rakentamisen pääpiirteitä. Kääntäjän kehittämisvaiheiden tuntemus korkean tason kielen rajoitetusta osajoukosta.

lukukausityö, lisätty 8.6.2013


Leksisten ja jäsennysanalysaattoreiden suunnittelu opettaa kieltä. Säännöt loogisten lausekkeiden muuntamiseksi POLIZ-muotoon. Triadien muodostaminen, niiden luettelon optimointi. Ohjelman looginen rakenne. Kääntäjä-tulkkimoduulien testaus.

lukukausityö, lisätty 28.5.2013


C-sharp-ohjelmointikielen yleiset ominaisuudet ja ominaisuuksien arviointi, sen yhtäläisyydet ja erot C++:sta ja Javasta. Kehitys tämän leksikaalin ja jäsentimen ohjelmointikielen avulla. Laskentataulukoiden kokoaminen.

lukukausityö, lisätty 11.6.2010


Analysaattoriohjelman suunnittelu, joka koostuu kahdesta osasta: leksikaalisesta analysaattorista, joka pilkkoo ohjelman lähdetekstin tokeneihin ja täyttää nimitaulukon; jäsentäjä, joka tarkistaa, vastaako teksti annettua kielioppia.

lukukausityö, lisätty 14.6.2010


Kirjoitetaan ohjelma, joka suorittaa syöttöohjelmointikielen leksikaalisen ja syntaktisen analyysin, luo lekseemitaulukon, joka ilmaisee niiden tyypit ja arvot, ja rakentaa myös syntaksipuun; syöttökielen teksti syötetään näppäimistöltä.

lukukausityö, lisätty 23.2.2012


Kehitystekniikka ja "C"-kielen kääntäjän osittainen toteutus "C++"-kielellä, joka jakaa alkuperäisen merkkijonon minimaalisiksi jakamattomiksi kielikonstruktioiksi kielen sanaston perusteella. Ohjelman analyysi.

lukukausityö, lisätty 19.3.2012


Kääntäjän rakenne, luokitus ja toteutusvaatimukset. C++-kääntäjän analysoivan osan suunnittelu ja toteutus. Tapoja toteuttaa leksikaalista analyysiä. Jäsentimen algoritmi. Ohjelmiston toteutuksen periaatteet.

lukukausityö, lisätty 26.1.2013


Kääntäjän luominen, joka käsittelee ohjelmakoodin Pascal-kielellä ja luo C-ohjelman vastaavilla operaattoreilla. Leksikaalisen analysaattorin ulkoisen määrittelyn ja toiminnan erityispiirteet. Ohjelman rakenne, tulosten näyttäminen näytöllä.

lukukausityö, lisätty 7.2.2011


Kieliopillisen analyysin menetelmät. Opetuskääntäjän rakenteen kehittäminen perusohjelmointikielellä Object Pascal olio-visuaalisen ohjelmoinnin ympäristössä Borland DELPHI 6.0 käyttöjärjestelmällä Windows XP.

lukukausityö, lisätty 12.5.2013


Ohjelmiston toteutus työpöytäsovellus käyttämällä C#-ohjelmointikieltä. Käyttöliittymän suunnittelu ja rakenne, vaatimukset sille ja toimivuuden arviointi. Käyttöoppaan kehittäminen ja käyttö.

Jokaisella tietokoneella on oma ohjelmointikieli - käskykieli tai konekieli - ja se voi suorittaa vain tällä kielellä kirjoitettuja ohjelmia. Konekielen avulla voidaan periaatteessa kuvata mikä tahansa algoritmi, mutta ohjelmointikustannukset ovat erittäin korkeat. Tämä johtuu siitä, että konekielellä voit kuvata ja käsitellä vain primitiivisiä tietorakenteita - bittiä, tavua, sanaa. Konekoodeilla ohjelmointi vaatii liikaa ohjelman yksityiskohtia ja on vain ohjelmoijien saatavilla, jotka tuntevat tietokoneen suunnittelun ja toiminnan hyvin. Tämän vaikeuden voittamiseksi sallii korkean tason kielet (Fortran, PL / 1, Pascal, C, Ada jne.), joissa on kehitetyt tietorakenteet ja niiden käsittelykeinot, riippumatta tietyn tietokoneen kielestä.

Algoritmiset korkean tason kielet antavat ohjelmoijalle mahdollisuuden kuvata algoritmeja monien sovellettujen ongelmien ratkaisemiseksi yksinkertaisesti ja kätevästi. Sellaista kuvausta kutsutaan alkuperäinen ohjelma, ja korkean tason kieli on syöttökieli.

kieliprosessori tarkoittaa konekielistä ohjelmaa, jonka avulla tietokone voi ymmärtää ja suorittaa ohjelmia syöttökielellä. Kielenkäsittelijöitä on kahta päätyyppiä: tulkit ja kääntäjät.

Tulkki on ohjelma, joka hyväksyy syötteeksi syöttökielen ohjelman ja, kun syöttökielen konstruktit tunnistetaan, toteuttaa ne tuottaen lähdössä lähdeohjelman määräämien laskelmien tulokset.

Kääntäjä on ohjelma, joka hyväksyy sisääntuloon lähdeohjelman ja generoi sen lähdössä alkuperäistä toiminnallisesti vastaavan ohjelman, ns. esine. Objektiohjelma kirjoitetaan objektikielellä. Konekieli voi tietyssä tapauksessa toimia objektikielenä ja tässä tapauksessa kääntäjän lähdöstä saatu ohjelma voidaan suorittaa välittömästi tietokoneella (tulkita). Tässä tapauksessa tietokone on konekoodien objektiohjelman tulkki. Yleensä objektikielen ei tarvitse olla konekieli tai lähellä sitä (autocode). Objektikieli voi olla jokin keskitason kieli on kieli, joka sijaitsee syöttö- ja konekielten välissä.

Jos kohdekielenä käytetään välikieltä, on kaksi vaihtoehtoa kääntäjän rakentamiseen.

Ensimmäinen vaihtoehto on, että välikielelle on olemassa (tai kehitteillä) toinen kääntäjä välikielestä konekielelle, ja sitä käytetään projisoidun kääntäjän viimeisenä lohkona.

Toinen vaihtoehto kääntäjän rakentamiseen välikielellä on rakentaa välikielen komentotulkki ja käyttää sitä kääntäjän viimeisenä lohkona. Tulkkien etu ilmenee virheenkorjauksessa ja dialogikääntäjissä, jotka tarjoavat käyttäjän työskentelyä dialogitilassa aina siihen asti, että ohjelmaan tehdään muutoksia ilman, että sitä käännetään kokonaan uudelleen.

Tulkkia käytetään myös ohjelman emuloinnissa, eli toiselle (objektiiviselle) koneelle kirjoitettujen ohjelmien suorittamisessa teknologisella koneella. Tämä vaihtoehto, käytetään erityisesti virheenkorjauksessa keskustietokoneessa olevista ohjelmista, jotka suoritetaan erikoistietokoneessa.

Kääntäjä, joka käyttää koneenläheistä kieltä (autocode tai assembler) syöttökielekseen, on perinteisesti ns. kokoaja. Korkean tason kielen kääntäjää kutsutaan kääntäjä.

Kääntäjän rakentamisessa viime vuodet on edistytty merkittävästi. Ensimmäiset kääntäjät käyttivät ns suoria lähetysmenetelmiä- Nämä ovat pääosin heuristisia menetelmiä, joissa yleisen idean perusteella jokaiselle kielikonstruktille kehitettiin oma algoritmi koneekvivalentiksi kääntämiseksi. Nämä menetelmät olivat hitaita eivätkä rakenteellisia.

Nykyaikaisten kääntäjien suunnittelumetodologia perustuu sävellyssyntaksiin perustuva menetelmä kielen käsittely. Koostumus siinä mielessä, että prosessi lähdeohjelman muuntamiseksi objektiohjelmaksi toteutetaan muodostamalla toiminnallisesti riippumattomia kartoituksia, joissa on selkeästi erotetut tulo- ja lähtötietorakenteet. Nämä kartoitukset on rakennettu siten, että lähdeohjelmaa tarkastellaan yhdistelmänä syöttökielen kuvauksen päänäkökohdista (tasoista): sanasto, syntaksi, semantiikka ja pragmatiikka, ja näiden näkökohtien tunnistaminen lähdeohjelmasta sen kääntämisen aikana. Tarkastellaan näitä näkökohtia saadaksemme yksinkertaistetun kääntäjämallin.

Minkä tahansa luonnollisen tai keinotekoisen kielen perusta on aakkoset– kielessä sallittu perusmerkkijoukko (kirjaimet, numerot ja erikoismerkit). Kyltit voidaan yhdistää sanat- kielen alkeisrakenteet, joita pidetään tekstissä (ohjelmassa) jakamattomina symboleina, joilla on tietty merkitys.

Sana voi olla myös yksi merkki. Esimerkiksi Pascal-kielessä sanat ovat tunnisteita, avainsanoja, vakioita ja erottimia, erityisesti aritmeettisten ja loogisten operaatioiden merkkejä, hakasulkuja, pilkkuja ja muita symboleja. Kielen sanasto ja kuvaus siitä, miten ne esitetään, ovat sanastoa Kieli.

Kielen sanat yhdistetään monimutkaisemmiksi rakenteiksi - lauseiksi. Ohjelmointikielissä yksinkertaisin lause on lause. Lauseet rakennetaan sanoista ja yksinkertaisemmista lauseista syntaksin sääntöjen mukaisesti. Syntaksi kieli on kuvaus oikeista lauseista. Kuvaus lauseiden merkityksestä, ts. sanojen merkitykset ja niiden sisäiset yhteydet, on semantiikka Kieli. Lisäksi huomaamme, että tietyllä ohjelmalla on jonkin verran vaikutusta kääntäjään - pragmatismi. Yhdessä kielimuodon syntaksi, semantiikka ja pragmatismi semiotiikka Kieli.

Ohjelman kääntäminen kielestä toiselle koostuu yleensä ohjelmakielen aakkosten, sanaston ja syntaksin muuttamisesta sen semantiikkaa säilyttäen. Lähdeohjelman käännösprosessi objektiksi on yleensä jaettu useisiin itsenäisiin aliprosesseihin (käännösvaiheisiin), jotka toteutetaan kääntäjän vastaavilla lohkoilla. On kätevää tarkastella kääntämisen päävaiheita leksikaalisena analyysinä, syntaktisena analyysinä, semanttisena analyysinä ja

olioohjelman synteesi. Kuitenkin monissa todellisissa kääntäjissä nämä vaiheet on jaettu useisiin alivaiheisiin, ja voi olla myös muita vaiheita (kuten objektikoodin optimointi). Kuvassa 1.1 näyttää yksinkertaistetun toimiva malli kääntäjä.

Tämän mallin mukaan syöttöohjelmalle tehdään ensin leksikaalinen käsittely. Leksikaalisen analyysin tarkoituksena on kääntää lähdeohjelma kääntäjän sisäiselle kielelle, jossa avainsanat, tunnisteet, tunnisteet ja vakiot tuodaan samaan muotoon ja korvataan ehdollisilla koodeilla: numeerisilla tai symbolisilla, joita kutsutaan kuvaajiksi. Jokainen kuvaaja koostuu kahdesta osasta: tunnuksen luokasta (tyypistä) ja osoittimesta muistiosoitteeseen, johon tiedot tietystä tunnuksesta on tallennettu. Yleensä nämä tiedot on järjestetty taulukoihin. Samanaikaisesti lähdeohjelman kääntämisen kanssa sisäiselle kielelle, leksikaalisen analyysin vaiheessa, leksikaalinen ohjaus- Ohjelmassa olevien sanojen tunnistaminen.

Jäsentäjä ottaa leksikaalisen analysaattorin lähdön ja kääntää merkkikuvioiden sekvenssin väliohjelman muotoon. Väliohjelma on pohjimmiltaan esitys ohjelman syntaksipuusta. Jälkimmäinen heijastaa alkuperäisen ohjelman rakennetta, ts. toimijoiden välistä järjestystä ja viestintää. Syntaksipuun rakentamisen aikana syntaksin ohjaus - syntaktisten virheiden havaitseminen ohjelmassa.

Varsinainen jäsennystulos voi olla komentosarja, jota tarvitaan väliohjelman rakentamiseen, hakutaulukoiden käyttämiseen ja vianmääritysviestin antamiseen tarvittaessa.

Riisi. 1.1. Kääntäjän yksinkertaistettu toimintamalli

Olioohjelman synteesi alkaa pääsääntöisesti muistin varaamisesta ja varaamisesta pääohjelman objekteille. Tämän jälkeen lähdeohjelman jokainen lause tutkitaan ja luodaan objektikielen semanttisesti vastaavat lauseet. Syöttötietona käytetään tässä ohjelman syntaksipuuta ja leksikaalisen analysaattorin lähtötaulukoita - tunnistetaulukkoa, vakiotaulukkoa ja muita. Puuanalyysin avulla voit tunnistaa objektiohjelman luomien komentojen järjestyksen, ja tunnistetaulukko määrittää komentotyypit, jotka ovat kelvollisia luotujen komentojen operandiarvoille (esimerkiksi mitkä komennot on luotava : kiinteä tai liukuluku jne.).

Varsinaista kohdeohjelman luomista edeltää usein semanttinen analyysi, joka sisältää monenlaista semanttista käsittelyä. Yksi tyyppi on semanttisten sopimusten tarkistaminen ohjelmassa. Esimerkkejä tällaisista sopimuksista: kunkin ohjelman tunnisteen kuvauksen ainutlaatuisuus, muuttujan määritelmä tehdään ennen sen käyttöä jne. Semanttinen analyysi voidaan suorittaa myöhemmissä käännösvaiheissa, kuten ohjelman optimointivaiheessa, joka voidaan myös sisällyttää kääntäjään. Optimoinnin tavoitteena on vähentää aikaresursseja tai resursseja RAM-muisti tarvitaan objektiohjelman suorittamiseen.

Nämä ovat tärkeimmät osat korkean tason kielistä käännösprosessissa. Käännöksen eri vaiheiden organisointia ja niihin liittyviä käytännön menetelmiä niiden matemaattiseen kuvaamiseen tarkastellaan tarkemmin alla.

Alan tavoitteet ja tavoitteet. Peruskäsitteet ja määritelmät. Yleiset ominaisuudet ohjelmointikielet ja kääntäjät. Kääntäjän yleinen rakenne. Kääntäjälohkojen vuorovaikutuksen muunnelmia.

Alan tavoitteet ja tavoitteet

Tällä hetkellä keinotekoisia kieliä, jotka käyttävät tekstin esittämistä aihealueen kuvaamiseen, käytetään laajasti ohjelmoinnin lisäksi myös muilla aloilla. Heidän avullaan erilaisten asiakirjojen rakenne, kolmiulotteinen virtuaalisia maailmoja, graafiset käyttöliittymät käyttäjä ja monet muut esineet, joita käytetään malleissa ja todellisessa maailmassa. Jotta nämä tekstikuvaukset voitaisiin koota oikein ja sitten tunnistaa ja tulkita oikein, käytetään erityisiä menetelmiä niiden analysointiin ja muuntamiseen. Menetelmät perustuvat kieliteoriaan ja muodollisiin kielioppiin sekä automaattien teoriaan. Ohjelmistojärjestelmät, jotka on tarkoitettu tekstien analysointiin ja tulkintaan, kutsutaan kääntäjiksi.

Huolimatta siitä, että tähän mennessä on kehitetty tuhansia eri kieliä ja niiden kääntäjiä, uusien sovellusten luominen tällä alalla ei pysähdy. Tämä liittyy sekä tietokonejärjestelmien tuotantoteknologian kehitykseen että tarpeeseen ratkaista yhä monimutkaisempia sovellettavia ongelmia. Lisäksi kielten teorian ja muodollisten kielioppien elementtejä voidaan soveltaa monilla muilla alueilla, esimerkiksi kuvattaessa tietorakenteita, tiedostoja, kuvia, jotka esitetään ei tekstinä, vaan binäärimuodossa. Nämä menetelmät ovat hyödyllisiä myös kääntäjien kehittämisessä, vaikka vastaavia analogeja olisikin jo olemassa. Tällainen kehitys voi johtua useista syistä, erityisesti toiminnallisista rajoituksista, lokalisoinnin puutteesta, alhaisesta tehokkuudesta. Esimerkiksi yksi viimeisimmistä kehityksestä Microsoft on C#-ohjelmointikieli, ja yksi syy sen luomiseen on halu vähentää Java-ohjelmointikielen suosiota. On monia muita esimerkkejä, joissa oman kääntäjän kehittäminen voi olla merkityksellistä. Siksi kieliteorian ja muodollisten kielioppien perusteet sekä käytännön menetelmiä Kääntäjien kehittäminen on informatiikan ja tietotekniikan insinöörikoulutuksen perusta.

Ehdotettu materiaali käsittelee kääntäjien kehitysmenetelmien perusteita ja sisältää tarvittavat tiedot niiden toiminnan logiikan, käytetyn matemaattisen laitteiston (teorian) tutkimiseen viralliset kielet ja muodolliset kieliopit, metakielet). Sitä käytetään osana lukukauden luentokursseja, joita pidetään Krasnojarskin valtion teknillisen yliopiston tietotekniikan ja tietokonetekniikan tiedekunnan eri erikoisaloilla. Laboratoriotöiden aikana perehdytään suoraan yksittäisiin menetelmiin kääntäjien luomiseksi.

Kurssin tarkoitus: antaa tietoa kielten teorian ja muodollisten kielioppien perusteista, automaattien teoriasta, kääntäjien kehittämismenetelmistä.

Tämän tavoitteen saavuttamiseksi tieteenalan opetuksen aikana ratkaistaan ​​seuraavat tehtävät:

1. Luentokurssilla tarkastellaan käännösprosessin organisoinnin yleisiä periaatteita ja kääntäjien rakennetta. Tutkitaan kääntäjien rakentamisen teorian perusteita.
2. Laboratorioistunnoissa ja niiden aikana itsenäinen työ toteutetaan saadun teoreettisen tiedon käytännön konsolidointi: yksinkertaisen ohjelmointikielen kääntäjää kehitetään.

Peruskäsitteet ja määritelmät

Suurin osa käsitellyistä määritelmistä on lainattu julkaisusta [ARNFTS Englanti-venäläinen-saksa-ranska tietojenkäsittelyn ja tietojenkäsittelyn sanakirja, 4132 termiä. Alla. toim. A.A. Dorodnitsyn. M.: 1978. 416 s.) ].

Kääntäjä - palveluohjelma, joka muuntaa syöttöohjelmointikielellä tarjotun lähdeohjelman objektikielellä toimitetuksi työohjelmaksi.

Yllä oleva määritelmä koskee kaikentyyppisiä lähetysohjelmia. Jokaisella näistä ohjelmista voi kuitenkin olla omat erityispiirteensä käännösprosessin organisoinnissa. Tällä hetkellä kääntäjät jaetaan kolmeen pääryhmään: kokoajat, kääntäjät ja tulkit.

kokoaja - järjestelmäapuohjelma, joka muuntaa symboliset konstruktit konekielisiksi ohjeiksi. Kokoonpanijoiden erityispiirre on, että he kääntävät kirjaimellisesti yhden symbolisen käskyn yhdeksi konekäskyksi. Siten kokoonpanokieli (kutsutaan myös autokoodiksi) on suunniteltu helpottamaan tietokoneen käskyjoukon havaitsemista ja nopeuttamaan ohjelmointia tässä käskysarjassa. Ohjelmoijan on paljon helpompi muistaa konekäskyjen muistomerkki kuin niiden binäärikoodi. Siksi suurin hyöty ei saavuteta lisäämällä yksittäisten komentojen tehoa, vaan lisäämällä niiden havainnoinnin tehokkuutta.

Samaan aikaan kokoonpanokieli sisältää konekäskyjen analogien lisäksi monia lisäohjeita, jotka helpottavat erityisesti tietokoneresurssien hallintaa, toistuvien fragmenttien kirjoittamista ja monimoduuliohjelmien rakentamista. Siksi kielen ilmaisukyky on paljon rikkaampi kuin pelkkä symbolinen koodauskieli, mikä lisää huomattavasti ohjelmoinnin tehokkuutta.

Kääntäjä - on apuohjelma, joka kääntää konekielelle lähdeohjelmointikielellä kirjoitetun ohjelman. Aivan kuten kokoaja, kääntäjä muuntaa ohjelman kielestä toiselle (useimmiten tietyn tietokoneen kielelle). Lähdekielen komennot eroavat kuitenkin merkittävästi organisaatioltaan ja teholtaan konekielisistä komennoista. On kieliä, joissa yksi lähdekielen ohje käännetään 7-10 konekäskyksi. On kuitenkin myös kieliä, joissa jokainen käsky voi vastata 100 tai useampaa konekäskyä (esimerkiksi Prolog). Lisäksi lähdekielissä käytetään usein tiukkaa tietojen tyyppiä, joka tapahtuu niiden alustavan kuvauksen kautta. Ohjelmointi ei välttämättä perustu algoritmin koodaamiseen, vaan tietorakenteiden tai luokkien huolelliseen pohtimiseen. Tällaisista kielistä käännösprosessia kutsutaan yleensä kääntämiseksi, ja lähdekieliä kutsutaan yleensä korkean tason ohjelmointikieliksi (tai korkean tason kieliksi). Ohjelmointikielen abstraktio tietokoneen komentojärjestelmästä johti useiden erilaisten kielten itsenäiseen luomiseen, jotka keskittyivät tiettyjen ongelmien ratkaisemiseen. Kielet ilmestyivät tieteellisiin laskelmiin, taloudellisiin laskelmiin, pääsyyn tietokantoihin ja muihin.

Tulkki - ohjelma tai laite, joka suorittaa operaattorikohtaisen kääntämisen ja alkuperäisen ohjelman suorittamisen. Toisin kuin kääntäjä, tulkki ei tuota konekielistä ohjelmaa tulosteena. Kun se on tunnistanut lähdekielen komennon, se suorittaa sen välittömästi. Sekä kääntäjät että tulkit käyttävät samoja jäsennysmenetelmiä lähdekoodi ohjelmia. Mutta tulkin avulla voit aloittaa tietojen käsittelyn yhden komennon kirjoittamisen jälkeen. Tämä tekee ohjelmien kehittämis- ja virheenkorjausprosessista joustavamman. Lisäksi ulostulokonekoodin puuttuminen mahdollistaa ulkoisten laitteiden "roskaamisen" lisätiedostoilla, ja itse tulkki voidaan melko helposti mukauttaa mihin tahansa konearkkitehtuuriin, koska se on kehitetty vain kerran laajasti käytetyllä ohjelmointikielellä. Siksi tulkittuja kieliä kuten JavaScript, VB Script, ovat yleistyneet. Tulkkien haittana on ohjelman alhainen suoritusnopeus. Tyypillisesti tulkitut ohjelmat toimivat 50-100 kertaa hitaammin kuin konekoodilla kirjoitetut ohjelmat.

Emulaattori - ohjelma tai ohjelmisto ja laitteistotyökalu, joka mahdollistaa ilman uudelleenohjelmointia ohjelman suorittamisen tietyllä tietokoneella, joka käyttää koodeja tai menetelmiä suorittaakseen toiminnon, joka on erilainen kuin tämä tietokone. Emulaattori on samanlainen kuin tulkki siinä mielessä, että se suorittaa suoraan jollain kielellä kirjoitetun ohjelman. Useimmiten se on kuitenkin konekieli tai välikoodi. Molemmat edustavat binäärikoodin ohjeita, jotka voidaan suorittaa välittömästi opkoodin tunnistamisen jälkeen. Toisin kuin tekstiohjelmissa, ei tarvitse tunnistaa ohjelman rakennetta, valita operandeja.

Emulaattoreita käytetään melko usein erilaisiin tarkoituksiin. Esimerkiksi uusia laskentajärjestelmiä kehitettäessä luodaan ensin emulaattori, joka ajaa ohjelmia, joita kehitetään tietokoneille, joita ei vielä ole olemassa. Tämän avulla voit arvioida komentojärjestelmää ja kehittää perusasioita ohjelmisto jo ennen kuin vastaava laitteisto on luotu.

Hyvin usein emulaattoria käytetään ajamaan vanhoja ohjelmia uusilla. tietokoneita. Tyypillisesti uudemmat tietokoneet ovat nopeampia ja niiden laatu on parempi. oheislaitteet. Näin voit emuloida vanhempia ohjelmia tehokkaammin kuin ajaa niitä vanhemmissa tietokoneissa. Esimerkki tästä lähestymistavasta on ZX Spectrum -kotitietokoneemulaattorien kehittäminen Z80-mikroprosessorilla. Tähän asti on faneja, jotka voivat pelata emulaattorilla vanhentuneessa, mutta silti menettämättä entisestään houkuttelevuuttaan, peliohjelmat. Emulaattoria voidaan käyttää myös nykyaikaisen halvempana analogina tietokonejärjestelmät, samalla kun se tarjoaa hyväksyttävän suorituskyvyn, joka vastaa joidenkin arkkitehtuuriperheiden alempia malleja. Esimerkkinä ovat IBM PC -emulaattorit. yhteensopivia tietokoneita toteutettu tehokkaammissa Apple-tietokoneissa. Useat IBM PC:lle kirjoitetut emulaattorit korvaavat onnistuneesti erilaisia ​​pelikonsoleita.

Väliesitysemulaattori, kuten tulkki, voidaan helposti siirtää tietokonearkkitehtuurista toiseen, mikä mahdollistaa mobiiliohjelmistojen luomisen. Juuri tämä ominaisuus määräsi Java-ohjelmointikielen menestyksen, josta ohjelma käännetään välikoodiksi. Suoritetaan tätä koodia virtuaalinen java kone ei ole muuta kuin emulaattori, joka käyttää mitä tahansa nykyaikaista käyttöjärjestelmää.

Transkooderi - ohjelma tai ohjelmointilaite, kääntää yhden tietokoneen konekielellä kirjoitetut ohjelmat toisen tietokoneen konekielellä kirjoitetuiksi ohjelmiksi. Jos emulaattori on tulkin vähemmän älykäs analogi, niin transkooderi toimii samassa kapasiteetissa kääntäjään nähden. Vastaavasti lähde (ja yleensä binääri) konekoodi tai väliesitys muunnetaan toiseksi samanlaiseksi koodiksi yhdessä käskyssä ja ilman lähdeohjelman rakenteen yleistä analyysiä. Transkooderit ovat hyödyllisiä siirrettäessä ohjelmia tietokonearkkitehtuurista toiseen. Niiden avulla voidaan myös rekonstruoida korkean tason kieliohjelman teksti saatavilla olevasta binäärikoodista.

Makroprosessori - ohjelma, joka korvaa yhden merkkisarjan toisella[Ruskea]. Se on eräänlainen kääntäjä. Se luo tulostekstiä käsittelemällä lähdetekstissä olevia erityisiä lisäyksiä. Nämä lisäykset on tehty erityisellä tavalla ja kuuluvat kielirakenteisiin, joita kutsutaan makrokieleksi. Makroprosessoreita käytetään usein ohjelmointikielten lisäosina, mikä lisää ohjelmointijärjestelmien toimivuutta. Lähes kaikki kokoonpanolaitteet sisältävät makroprosessorin, mikä lisää koneohjelmien kehittämisen tehokkuutta. Tällaisia ​​ohjelmointijärjestelmiä kutsutaan yleisesti makrokokoajiksi.

Makroprosessoreita käytetään myös korkean tason kielillä. Ne lisäävät kielten, kuten PL/1, C, C++, toimivuutta. Makroprosessoreita käytetään erityisen paljon C- ja C++-ohjelmissa, mikä helpottaa ohjelmien kirjoittamista. Esimerkki makroprosessorien laajasta käytöstä on Microsoft Foundation Classes (MFC) -luokkakirjasto. Makrolisäkkeiden avulla se toteuttaa viestikarttoja ja muuta ohjelmaobjekteja. Samalla makroprosessorit lisäävät ohjelmoinnin tehokkuutta muuttamatta kielen syntaksia ja semantiikkaa.

Syntaksi - tietyn kielen säännöt, jotka määräävät sen elementtien muodostumisen. Toisin sanoen tämä joukko sääntöjä semanttisesti merkityksellisten merkkijonojen muodostamiseksi tietyllä kielellä. Syntaksi määritetään käyttämällä sääntöjä, jotka kuvaavat tietyn kielen käsitteitä. Esimerkkejä käsitteistä ovat: muuttuja, lauseke, operaattori, menettely. Käsitteiden järjestys ja niiden sallittu käyttö säännöissä määrää ohjelmia muodostavat syntaktisesti oikeat rakenteet. Syntaksin avulla määritellään objektien hierarkia, ei tapa, jolla ne ovat vuorovaikutuksessa keskenään. Esimerkiksi operaattori voi esiintyä vain proseduurissa, kun taas lauseke operaattorissa, muuttuja voi koostua nimestä ja valinnaisista indekseistä ja niin edelleen. Syntaksi ei liity sellaisiin ohjelman ilmiöihin kuin "hyppy ei-olemattomaan otsikkoon" tai "annetun nimen muuttujaa ei ole määritelty". Tätä semantiikka tekee.

Semantiikka - säännöt ja ehdot, jotka määrittävät kielen elementtien ja niiden semanttisten merkityksien välisen suhteen sekä kielen syntaktisten rakenteiden merkityksellisen merkityksen tulkinnan. Ohjelmointikielen objektit eivät vain sijoiteta tekstiin tietyn hierarkian mukaisesti, vaan ne myös liitetään toisiinsa muiden käsitteiden kautta, jotka muodostavat erilaisia ​​assosiaatioita. Esimerkiksi muuttuja, jolle syntaksi määrittää kelvollisen sijainnin vain ilmoituksissa ja joissakin käskyissä, jolla on tietty tyyppi, sitä voidaan käyttää rajoitetulla joukolla operaatioita, sillä on osoite, koko ja se on ilmoitettava ennen käyttöä ohjelma.

Syntaktinen analysaattori - kääntäjäkomponentti, joka tarkistaa, että lähdelausekkeet ovat tietyn ohjelmointikielen syntaksisääntöjen ja semantiikan mukaisia. Nimestä huolimatta analysaattori tarkistaa sekä syntaksin että semantiikan. Se koostuu useista lohkoista, joista jokainen ratkaisee omat ongelmansa. Sitä tarkastellaan tarkemmin kuvattaessa kääntäjän rakennetta.

Ohjelmointikielten ja kääntäjien yleiset ominaisuudet

Ohjelmointikielet eroavat toisistaan ​​melkoisesti tarkoituksen, rakenteen, semanttisen monimutkaisuuden ja toteutusmenetelmien osalta. Tämä asettaa omat erityispiirteensä tiettyjen kääntäjien kehittämiselle.

Ohjelmointikielet ovat työkaluja eri aihealueiden ongelmien ratkaisemiseen, mikä määrittää niiden organisaation erityispiirteet ja käyttötarkoituksen erot. Esimerkkejä ovat Fortran tieteelliseen laskemiseen, C järjestelmäohjelmointiin, Prolog johtopäätösongelmien tehokkaaseen kuvaamiseen ja Lisp rekursiiviseen luettelon käsittelyyn. Näitä esimerkkejä voidaan jatkaa. Jokaisella aihealueella on omat vaatimukset itse kielen järjestämiselle. Siksi voidaan havaita operaattorien ja lausekkeiden esitysmuotojen monimuotoisuus, ero perusoperaatioiden joukossa, ohjelmoinnin tehokkuuden heikkeneminen ratkaistaessa aihealueeseen kuulumattomia ongelmia. Kielierot heijastuvat myös kääntäjien rakenteeseen. Lisp ja Prolog suoritetaan useimmiten tulkitsevassa tilassa, koska ne käyttävät dynaamista tietotyyppien generointia laskennan aikana. Fortran-kääntäjille on ominaista tuloksena olevan konekoodin aggressiivinen optimointi, joka tulee mahdolliseksi kielirakenteiden suhteellisen yksinkertaisen semantiikan ansiosta - erityisesti koska vaihtoehtoisia muuttujien nimeämismekanismeja osoittimien tai viitteiden avulla ei ole. Osoittimien läsnäolo C-kielessä asettaa erityisiä vaatimuksia dynaamiselle muistin allokoinnille.

Kielen rakenne luonnehtii sen käsitteiden välisiä hierarkkisia suhteita, joita kuvataan syntaktisilla säännöillä. Ohjelmointikielet voivat erota hyvinkin toisistaan ​​yksittäisten käsitteiden organisoinnissa ja niiden välisessä suhteessa. PL/1-ohjelmointikieli sallii proseduurien ja funktioiden mielivaltaisen sisäkkäisyyden, kun taas C:ssä kaikkien funktioiden on oltava uloimmalla sisäkkätasolla. C++-kieli sallii muuttujien ilmoittamisen missä tahansa ohjelman kohdassa ennen sen ensimmäistä käyttöä, kun taas Pascalissa muuttujat on määritettävä erityisellä määritysalueella. PL/1 menee vielä pidemmälle tässä asiassa, mikä mahdollistaa muuttujan ilmoittamisen sen käytön jälkeen. Tai voit jättää kuvauksen kokonaan pois ja noudattaa oletussääntöjä. Päätöksestä riippuen kääntäjä voi analysoida ohjelman yhdellä tai useammalla ajolla, mikä vaikuttaa käännösnopeuteen.

Ohjelmointikielten semantiikka vaihtelee hyvin laajalla alueella. Ne eroavat paitsi yksittäisten toimintojen toteutuksen erityispiirteistä, myös ohjelmointiparadigmoista, jotka määrittävät ohjelmien kehittämismenetelmien perustavanlaatuiset erot. Toiminnan toteutuksen erityispiirteet voivat koskea sekä käsiteltävien tietojen rakennetta että samojen tietotyyppien käsittelyn sääntöjä. Kielet, kuten PL/1 ja APL, tukevat matriisi- ja vektoritoimintoja. Useimmat kielet toimivat ensisijaisesti skalaarien kanssa tarjoten ohjelmoijien kirjoittamia menetelmiä ja toimintoja taulukoiden käsittelemiseksi. Mutta jopa suoritettaessa kahden kokonaisluvun lisäämistä, kielet, kuten C ja Pascal, voivat käyttäytyä eri tavalla.

Perinteisen prosessiohjelmoinnin lisäksi, jota kutsutaan myös pakolliseksi, on olemassa sellaisia ​​paradigmoja kuin toiminnallinen ohjelmointi, logiikkaohjelmointi ja olio-ohjelmointi. Toivon, että myös minun [Legalov2000] ehdottama prosessiparametrinen ohjelmointiparadigma ottaa paikkansa tässä sarjassa. Kielten käsitteiden ja objektien rakenne riippuu voimakkaasti valitusta paradigmasta, mikä vaikuttaa myös kääntäjän toteutukseen.

Jopa sama kieli voidaan toteuttaa useilla tavoilla. Tämä johtuu siitä, että muodollisten kielioppien teoria sallii erilaisia ​​tapoja jäsentää samoja lauseita. Tämän mukaisesti kääntäjät voivat eri tavoilla saada saman tuloksen (olioohjelman) alkuperäisestä lähdetekstistä.

Kaikilla ohjelmointikielillä on kuitenkin useita yhteisiä ominaisuuksia ja parametreja. Tämä yhteisyys määrittää myös kääntäjien järjestämisen periaatteet, jotka ovat samanlaiset kaikille kielille.

1. Ohjelmointikielet on suunniteltu helpottamaan ohjelmointia. Siksi niiden operaattorit ja tietorakenteet ovat tehokkaampia kuin konekielissä.
2. Ohjelmien näkyvyyden lisäämiseksi numeeristen koodien sijasta käytetään kielirakenteiden symbolisia tai graafisia esityksiä, jotka ovat helpompia havaita ne.
3. Jokaiselle kielelle on määritelty:

• Joukko symboleja, joilla voidaan kirjoittaa oikeat ohjelmat (aakkoset), peruselementit.
• Joukko oikeita ohjelmia (syntaksi).
• Jokaisen oikean ohjelman "merkitys" (semantiikka).

Kielen erityispiirteistä riippumatta mitä tahansa kääntäjää voidaan pitää toiminnallisena muuntimena F, joka tarjoaa yksiselitteisen sovituksen X:stä Y:ksi, missä X on lähdekielen ohjelma, Y on tuloskielen ohjelma. Siksi itse käännösprosessi voidaan esittää muodollisesti melko yksinkertaisesti ja selkeästi:

Muodollisesti jokainen oikea ohjelma X on merkkijono jostain aakkosesta A, joka on muunnettu vastaavaksi merkkijonoksi Y, joka koostuu aakkosten B symboleista.

Ohjelmointikieli, kuten mikä tahansa monimutkainen järjestelmä, määritellään käsitehierarkialla, joka määrittelee sen elementtien välisen suhteen. Nämä käsitteet liittyvät toisiinsa syntaktisten sääntöjen mukaisesti. Jokaisella näiden sääntöjen mukaan rakennetulla ohjelmalla on vastaava hierarkkinen rakenne.

Tässä suhteessa kaikille kielille ja niiden ohjelmille voidaan lisäksi erottaa seuraavat yhteiset piirteet: jokaisen kielen on sisällettävä säännöt, jotka mahdollistavat tätä kieltä vastaavien ohjelmien luomisen tai kirjoitettujen ohjelmien ja tietyn kielen välisen vastaavuuden tunnistamisen.

Ohjelmarakenteen ja ohjelmointikielen välistä suhdetta kutsutaan syntaktinen kartoitus.

Harkitse esimerkkinä hierarkkisen rakenteen ja seuraavan aritmeettisen lausekkeen määrittelevän merkkijonon välistä suhdetta:

Useimmissa ohjelmointikielissä tämä lauseke määrittelee ohjelmaobjektien hierarkian, jotka voidaan näyttää puuna (kuva 1.1.):

Ympyrät edustavat alkeisrakenteina käytettyjä symboleja ja suorakulmiot yhdistelmäkäsitteitä, joilla on hierarkkinen ja mahdollisesti rekursiivinen rakenne. Tämä hierarkia määritellään syntaktisten sääntöjen avulla, jotka on kirjoitettu erityisellä kielellä, jota kutsutaan metakieleksi (metakielistä keskustellaan tarkemmin muodollisia kielioppeja opiskellessa):

<выражение> ::= <слагаемое> | <выражение> + <слагаемое>

<слагаемое> ::= <множитель> | <слагаемое> * <множитель>

<множитель> ::= <буква> | (<выражение>)

<буква>

Huomautus. Merkki "::=" luetaan "se on". Pystypalkki "|" luetaan "tai".

Jos säännöt on kirjoitettu toisin, niin hierarkinen rakenne. Esimerkkinä voidaan antaa seuraava tapa kirjoittaa säännöt:

<выражение> ::= <операнд> | <выражение> + < операнд > | <выражение> * < операнд >

<операнд> ::= <буква> | (<выражение>)

<буква>::= a | b | c | d | minä | f | g | h | minä | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Jäsennyksen seurauksena sama aritmeettinen lauseke rakennetaan hierarkkinen rakenne, joka näkyy kuvassa. 1.2.

On huomattava, että hierarkkinen rakenne ei yleensä liity millään tavalla lausekkeen semantiikkaan. Molemmissa tapauksissa operaatioiden suorittamisen prioriteetti voidaan toteuttaa yleisesti hyväksyttyjen sääntöjen mukaisesti, kun kertolasku edeltää yhteenlaskua (tai päinvastoin, kaikilla operaatioilla voi olla sama prioriteetti minkä tahansa säännön mukaan). Ensimmäinen rakenne tukee kuitenkin eksplisiittisesti yhteisen prioriteetin jatkamista, kun taas toinen sopii paremmin operaatioiden toteuttamiseen samalla prioriteetilla ja niiden suorittamiseen oikealta vasemmalle.

Tietyn ohjelman syntaktisen rakenteen löytämisprosessia kutsutaan jäsentäminen.

Yhdellä kielellä oikea syntaktinen rakenne voi olla virheellinen toisessa. Esimerkiksi Forthissa yllä olevaa lauseketta ei tunnisteta. Tällä kielellä postfix-lauseke on kuitenkin oikea:

Sen syntaktista rakennetta kuvaavat säännöt:

<выражение> ::= <буква> | <операнд> <операнд> <операция>

< операнд > ::= < буква > | < выражение >

< операция > ::= + | *

<буква>::= a | b | c | d | minä | f | g | h | minä | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

Hierarkkinen puu, joka määrittää syntaktisen rakenteen, on esitetty kuvassa. 1.3.

Toinen kaikille kielille tyypillinen piirre on niiden semantiikka. Se määrittää kielioperaatioiden merkityksen, operandien oikeellisuuden. Ketjut, joilla on sama syntaktinen rakenne eri ohjelmointikielissä, voivat poiketa semantiikasta (joka havaitaan esimerkiksi C ++:ssa, Pascalissa, Basicissa yllä olevan aritmeettisen lausekkeen fragmentin kohdalla).

Kielen semantiikan tuntemus mahdollistaa sen erottamisen syntaksistaan ​​ja sen käyttämisen toiselle kielelle muuntamiseen (koodin luomiseen).

Semantiikan kuvaus ja sen oikeellisuuden tunnistaminen on yleensä kääntäjän aikaa vievin ja laajin osa, koska on tarpeen luetella ja analysoida joukko operaatioiden ja operandien mahdollisia yhdistelmiä.

Yleistetty kääntäjän rakenne

Yleiset ominaisuudet ja mallit ovat luontaisia ​​sekä eri ohjelmointikielille että näiden kielten kääntäjille. Heillä on samanlaiset prosessit lähdetekstin muuntamiseksi. Huolimatta siitä, että näiden prosessien vuorovaikutus voidaan järjestää eri tavoin, on mahdollista erottaa toimintoja, joiden suorittaminen johtaa samoihin tuloksiin. Kutsumme tällaisia ​​toimintoja käännösprosessin vaiheiksi.

Ottaen huomioon kääntäjän ja tulkin samankaltaisuuden, tarkastellaan kääntäjässä esiintyviä vaiheita. Se korostaa:

1. Leksikaalisen analyysin vaihe.
2. Jäsennysvaihe, joka koostuu:

• syntaktisen rakenteen tunnistus;
• semanttinen jäsennys, jonka aikana tehdään työtä taulukoiden kanssa, välimuotoisen semanttisen esityksen generointi tai objektimalli Kieli.

Koodin generointivaihe, joka suorittaa:

• kielen väliesityksen tai objektimallin komponenttien semanttinen analyysi;
• väliesityksen tai objektimallin kääntäminen kohdekoodiksi.

Käännösprosessin päävaiheiden ohella lisävaiheet ovat mahdollisia:

2a. Väliesityksen tutkimus- ja optimointivaihe, joka koostuu:

2a.1. väliesityksen oikeellisuuden analyysi;
2a.2. välitason esityksen optimointi.

3a. Kohdekoodin optimoinnin vaihe.

Tulkki eroaa siinä, että koodin generointivaihe korvataan yleensä kielen väliesityksen tai objektimallin elementtien emulointivaiheella. Lisäksi tulkki ei yleensä optimoi väliesitystä, vaan emuloi sitä välittömästi.

Lisäksi on mahdollista erottaa yksi prosessi kaikille ohjelman käsitellyssä lähdekoodissa olevien virheiden analysoinnin ja korjaamisen vaiheille.

Kääntäjän yleinen rakenne siinä olevat vaiheet huomioiden on esitetty kuvassa. 1.4.

Se koostuu leksikaalisesta analysaattorista, jäsentimestä, koodigeneraattorista ja virheanalysaattorista. Tulkkissa käytetään koodigeneraattorin sijaan emulaattoria (kuva 1.5), johon väliesityksen elementtien lisäksi siirretään lähdedata. Emulaattorin tulos on laskennan tulos.

Leksikaalinen analysaattori (tunnetaan myös nimellä skanneri) lukee syötetyn merkkijonon ja ryhmittelee ne perusrakenteiksi, joita kutsutaan tokeneiksi. Jokaisella tunnuksella on luokka ja arvo. Yleensä kielen alkeiskonstruktiot, esimerkiksi tunniste, reaaliluku, kommentti, toimivat ehdokkaina lekseemin rooliin. Tuloksena saadut tunnukset välitetään jäsentäjälle. Skanneri ei ole kääntäjän pakollinen osa. Sen avulla voidaan kuitenkin lisätä käännösprosessin tehokkuutta. Leksikaalista analyysiä käsitellään tarkemmin aiheessa: "Leksikaalisen analyysin organisointi".

Jäsentäjä jäsentää lähdeohjelman käyttämällä saapuvia tokeneita, rakentaa ohjelman syntaktisen rakenteen ja suorittaa semanttisen analyysin muodostamalla kielen objektimallin. Objektimalli edustaa syntaktista rakennetta, jota on täydennetty olemassa olevien käsitteiden välisillä semanttisilla linkeillä. Nämä liitännät voivat olla:

• nimitaulukoihin sijoitetut muuttujaviitteet, tietotyypit ja toimintojen nimet;
• linkit, jotka määrittävät komentojen suoritusjärjestyksen;
• linkit, jotka määrittävät kielen objektimallin elementtien sisäkkäisyyden ja muut.

Siten jäsentäjä on melko monimutkainen kääntäjälohko. Siksi se voidaan jakaa seuraaviin osiin:

• tunnistaja;
• semanttisen analyysin lohko;
• objektimalli tai väliesitys, joka koostuu nimitaulukosta ja syntaktisesta rakenteesta.

Jäsentimen yleinen rakenne on esitetty kuvassa. 1.6.

Tunnistaja vastaanottaa merkkiketjun ja jäsentää sen sen perusteella käytettyjen sääntöjen mukaisesti. Tokenit, kun säännöt on jäsennetty onnistuneesti, välitetään semanttiselle analysaattorille, joka rakentaa nimitaulukon ja korjaa syntaktisen rakenteen fragmentteja. Lisäksi nimitaulukon ja syntaktisen rakenteen välille on kiinteästi lisätty semanttisia linkkejä. Tuloksena muodostuu ohjelman objektimalli, joka on vapautettu sitoutumisesta ohjelmointikielen syntaksiin. Melko usein kieliobjektien hierarkiaa täysin kopioivan syntaktisen rakenteen sijaan luodaan sen yksinkertaistettu analogi, jota kutsutaan väliesityksenä.

Virheanalysaattori vastaanottaa tietoa kääntäjän eri lohkoissa esiintyvistä virheistä. Vastaanotetun tiedon avulla se luo viestejä käyttäjälle. Sitä paitsi, tämä lohko voi yrittää korjata virheen jatkaakseen jäsentämistä. Hän on myös vastuussa ohjelman asianmukaisesta loppuun saattamisesta siinä tapauksessa, että lähetystä ei voida jatkaa.

Koodigeneraattori rakentaa objektikonekoodin objektimallin tai väliesityksen analyysin perusteella. Koodin rakentamiseen liittyy ylimääräinen semanttinen analyysi, joka liittyy tarpeeseen muuntaa yleistetyt komennot tietyn tietokoneen koodeiksi. Tällaisen analyysin vaiheessa määritetään lopuksi muuntamisen mahdollisuus ja valitaan tehokkaat vaihtoehdot. Koodin luominen itsessään on joidenkin komentojen uudelleenkoodausta toisiin.

Vuorovaikutusvaihtoehdot kääntäjälohkoille

Käännösprosessien organisointi, joka määrää päävaiheiden toteutuksen, voidaan suorittaa eri tavoin. Tämän määräävät erilaiset kääntäjälohkojen vuorovaikutusvaihtoehdot: leksikaalinen analysaattori, jäsentäjä ja koodigeneraattori. Samasta lopputuloksesta huolimatta erilaisia ​​vaihtoehtoja Kääntäjälohkojen vuorovaikutukset tarjoavat erilaisia ​​vaihtoehtoja välitietojen tallentamiseen. Kääntäjälohkojen vuorovaikutukseen on kaksi päävaihtoehtoa:

• monivaiheinen organisaatio, jossa kukin vaiheista on itsenäinen prosessi, joka siirtää ohjauksen seuraavaan vaiheeseen vasta tietojensa täydellisen käsittelyn päätyttyä;
• yhden kierron organisaatio, jossa kaikki vaiheet edustavat yhtä prosessia ja välittävät tietoja toisilleen pieninä osina.

Kahden päävaihtoehdon perusteella voit myös luoda niistä erilaisia ​​yhdistelmiä.

Kääntäjälohkojen vuorovaikutuksen monivaiheinen järjestäminen

Tämä lohkovuorovaikutuksen muunnelma, jossa käytetään esimerkkinä kääntäjää, on esitetty kuvassa 1.7.

Leksikaalinen analysaattori käsittelee lähdetekstin kokonaan muodostaen ketjun, joka koostuu kaikista vastaanotetuista lekseemista lähdössä. Vasta sen jälkeen ohjaus siirretään jäsentimelle. Jäsentäjä vastaanottaa muodostetun merkkiketjun ja muodostaa sen perusteella väliesityksen tai objektimallin. Vastaanotettuaan koko objektimallin se siirtää ohjauksen koodigeneraattorille. Koodigeneraattori rakentaa tarvittavan konekoodin kielen objektimallin perusteella

Tämän lähestymistavan etuja ovat:

1. Yksittäisten vaiheiden eristäminen, mikä mahdollistaa niiden itsenäisen toteutuksen ja käytön.
2. Mahdollisuus tallentaa kunkin vaiheen toiminnan tuloksena saatuja tietoja ulkoisille tallennuslaitteille ja käyttää niitä tarpeen mukaan.
3. Mahdollisuus vähentää kääntäjän toiminnan edellyttämän RAM-muistin määrää vaiheiden peräkkäisen kutsun ansiosta.

Haitat on otettava huomioon.

1. Suurien määrien välitietoa, josta Tämä hetki aikaa tarvitaan vain vähän.
2. Käännösnopeuden hidastuminen johtuu vaiheiden peräkkäisestä suorittamisesta ja ulkoisten tallennuslaitteiden käytöstä RAM-muistin säästämiseksi.

Tämä lähestymistapa voi olla kätevä, kun rakennetaan kääntäjiä ohjelmointikielistä, joilla on monimutkainen syntaktinen ja semanttinen rakenne (esimerkiksi PL/I). Tällaisissa tilanteissa on vaikea kääntää yhdellä kertaa, joten on helpompi esittää aikaisempien ajojen tulokset lisävälitietoina. On huomattava, että kielen monimutkaiset semanttiset ja syntaktiset rakenteet voivat johtaa ylimääräisiin läpimenoihin, joita tarvitaan vaadittujen riippuvuuksien määrittämiseen. Passien kokonaismäärä voi olla yli kymmenen. Läpivientien määrään voi vaikuttaa myös ohjelman tiettyjen kieliominaisuuksien käyttö, kuten muuttujien ja menettelyjen ilmoittaminen niiden käytön jälkeen, oletusilmoitussääntöjen soveltaminen ja niin edelleen.

Kääntäjälohkojen vuorovaikutuksen yhden kierron järjestäminen

Yksi vaihtoehdoista kääntäjälohkojen vuorovaikutukselle yksivaiheisen organisaation kanssa on esitetty kuvassa. 1.8

Tässä tapauksessa käännösprosessi etenee seuraavasti. Leksikaalinen analysaattori lukee osan lähdetekstistä, joka tarvitaan yhden tunnuksen saamiseksi. Lekseemin muodostamisen jälkeen se kutsuu jäsentimen ja välittää luodun lekseemin sille parametrina. Jos jäsentäjä voi rakentaa väliesityksen seuraavan elementin, se tekee niin ja välittää muodostetun fragmentin koodigeneraattorille. Muussa tapauksessa jäsentäjä palauttaa ohjauksen skannerille, mikä tekee selväksi, että seuraava merkki on käsitelty ja uutta tietoa tarvitaan.

Koodigeneraattori toimii samalla tavalla. Väliesityksen vastaanotetun fragmentin perusteella se luo vastaavan objektikoodin fragmentin. Tämän jälkeen ohjaus palautetaan jäsentimelle.

Kun lähdeteksti on valmis ja kaikki välitiedot on käsitelty kussakin lohkossa, leksikaalinen analysaattori aloittaa ohjelman lopetusprosessin.

Useimmiten yksivaiheiset kääntäjät käyttävät erilaista ohjausjärjestelmää, jossa jäsentäjä toimii päälohkona (kuva 1.9).

Leksikaalinen analysaattori ja koodigeneraattori toimivat alirutiineina, joita he kutsuvat. Heti kun jäsentäjä tarvitsee toisen tunnuksen, se kutsuu skannerin. Kun väliesityksen fragmentti vastaanotetaan, soitetaan koodigeneraattorille. Käännösprosessi valmistuu viimeisen tunnuksen vastaanottamisen ja käsittelyn jälkeen, ja sen aloittaa jäsentäjä.

Kertakierrosjärjestelmän etuja ovat suurten välitietomäärien puuttuminen, suuri nopeus käsittely johtuen vaiheiden yhdistämisestä yhdessä prosessissa ja ulkoisten tallennuslaitteiden puutteesta.

Haittoja ovat: mahdottomuus toteuttaa tällaista käännösjärjestelmää kielille, joilla on monimutkainen rakenne, ja välitietojen puute, jota voidaan käyttää monimutkaiseen analyysiin ja optimointiin.

Tällaista järjestelmää käytetään usein ohjelmointikielissä, jotka ovat yksinkertaisia ​​semanttisissa ja syntaktisissa rakenteissa sekä kääntäjissä että tulkkeissa. Basic ja Pascal ovat esimerkkejä tällaisista kielistä. Klassinen tulkki rakennetaan yleensä yhden kierroksen järjestelmän mukaan, koska suora suoritus suoritetaan väliesityksen yksittäisten fragmenttien tasolla. Tällaisen tulkin lohkojen vuorovaikutuksen organisointi on esitetty kuvassa. 1.10.

Kääntäjälohkojen yhdistetyt vuorovaikutukset

Monivaiheisten ja yksivaiheisten käännösjärjestelmien yhdistelmät synnyttävät useita yhdistettyjä vaihtoehtoja, joista monia käytetään onnistuneesti. Katsotaanpa joitain niistä esimerkkinä.

Kuvassa 1.11 näyttää kääntäjälohkojen vuorovaikutuskaavion, joka jakaa koko prosessin kahteen vaiheeseen. Ensimmäisellä läpikäynnillä generoidaan ohjelman täydellinen väliesitys, ja toisella läpikäynnillä suoritetaan koodin generointi. Tällaisen järjestelmän avulla on helppo siirtää kääntäjä tietokonejärjestelmästä toiseen kirjoittamalla koodigeneraattori uudelleen.

Lisäksi koodigeneraattorin sijaan on helppo liittää väliesitysemulaattori, jonka avulla voit yksinkertaisesti kehittää ohjelmointijärjestelmää tietyllä kielellä, joka on suunnattu erilaisiin suoritusympäristöihin. Esimerkki tällaisesta kääntäjälohkojen vuorovaikutuksen järjestämisestä on esitetty kuvassa. 1.12.

Niiden järjestelmien lisäksi, joissa koodigeneraattori korvataan emulaattorilla, on olemassa kääntäjiä, jotka mahdollistavat niiden käytön yhdessä. Yksi näistä kaavoista on esitetty kuvassa. 1.13.

Käännösprosessi, mukaan lukien koodin luominen, voidaan suorittaa millä tahansa määrällä ajoja (esimerkissä käytetään aiemmin kohdassa esitettyä yhden vaiheen käännöstä). Luotua objektikoodia ei kuitenkaan suoriteta vastaavassa tietokonejärjestelmässä, vaan se emuloidaan tietokoneessa, jolla on erilainen arkkitehtuuri. Tällaista mallia sovelletaan kielen ympärille rakennetussa ympäristössä Java ohjelmointi. Kääntäjä itse luo Java-virtuaalikonekoodin, jota emuloidaan erityisillä keinoilla sekä itsenäisesti että Internet-selainympäristössä.

Esitetyllä kaaviolla voi olla laajempi tulkinta suhteessa mihin tahansa kääntäjään, joka generoi konekoodia. Asia on, että useimmat nykyaikaiset tietokoneet toteutetaan mikroohjelmaohjauksella. Mikroohjelman ohjauslaitetta voidaan pitää konekoodia emuloivana ohjelmana. Tämä antaa meille mahdollisuuden puhua viimeksi esitetyn järjestelmän laajasta käytöstä.

Hallitse kysymyksiä ja tehtäviä

1. Nimeä erot:

• kääntäjä tulkki;
• kääntäjä kokoonpanosta;
• transkooderi kääntäjästä;
• emulaattori tulkista;
• syntaksi semantiikasta.

1. Kerro meille tuntemiesi ohjelmointikielten uusimmasta kehityksestä. Kerro näiden kielten tärkeimmät ominaisuudet.
2. Anna konkreettisia esimerkkejä käännösmenetelmien käytöstä alueilla, jotka eivät liity ohjelmointikieliin.
3. Anna konkreettisia esimerkkejä käännetyistä ohjelmointikielistä.
4. Anna konkreettisia esimerkkejä tulkitetuista ohjelmointikielistä.
5. Anna konkreettisia esimerkkejä ohjelmointikielistä, joille on saatavilla sekä kääntäjiä että tulkkeja.
6. Kääntäjien tärkeimmät edut ja haitat.
7. Tulkkien tärkeimmät edut ja haitat.
8. Kuvaile tärkeimmät erot kahden tuntemasi ohjelmointikielen syntaksissa.
9. Kuvaile tärkeimmät erot kahden tuntemasi ohjelmointikielen semantiikan välillä.
10. Nimeä käännösprosessin päävaiheet ja niiden tarkoitus.
11. Nimeä yksikertaisen kääntämisen erityispiirteet.
12. Nimeä monipäästökäännöksen erityispiirteet.
13. Anna esimerkkejä mahdollisista yhden ja monikierroksen muunnoksen yhdistelmistä. Kerro käytännön käyttöä nämä suunnitelmat.