Syntaksipuu

Syntaksin , johtamista tai jäsennyspuun on termi teoreettisen tietojenkäsittelyopin ja kielitiede . Se kuvaa hierarkkisen esityksen tekstin erittelystä. Syntaksipuita käytetään sekä apuna erittelyn graafisessa visualisoinnissa että tietorakenteen muodossa tämän erittelyn näyttämiseksi koneenkäsittelyä varten, esim. B. kääntäjässä tai kääntäjässä .

Eri termejä ei käytetä kirjallisuudessa yhtenäisesti. Vain termi derivaatiopuu , joka perustuu termiin derivaatio, on muodollisesti määritelty tarkasti . Muut erityyppisten puiden muut nimet voidaan sitten määritellä teknisesti yksityiskohtaisemmin, kuten alla kuvataan, tarvittaessa.

Päinvastoin kuin tietojenkäsittelytieteessä, jossa kielet voidaan määritellä myös teknisten mahdollisuuksien mukaan, kielitiede löytää vaikeammat edellytykset käsitellessään luonnollisia kieliä lähinnä siksi, että lauseen komponenttien järjestys voi vaihdella.

esittely

Johdepuun esitys

Vuonna (mekaaninen) analyysi luonnollisen kielen lauseita tai virallisia tekstejä (esimerkiksi tietokoneohjelmat), The leksikaalinen analyysi (jakautuvat siten kuponkia tai symboleja ) seuraa usein hierarkkisen yhteenveto symbolien liittyvien lauseiden osia ( ainesosien ) tai jaksoihin sen sijaan muodollisen tekstin. Käänteisesti tämä voidaan ymmärtää myös tekstin leikkauksena. Tuloksena on oikealla näkyvä puu . Graafisen lomakkeen lisäksi sulkeissa olevia esityksiä käytetään myös syntaksipuissa:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ pallo]]]].}$

Teknisesti vasemmalla olevaa puuta kutsutaan myös konkreettiseksi johdepuuksi , koska se näyttää tuloksena olevan rakenteen tarkalleen käyttäen konkreettista tekstiä. Kielitieteessä on kuitenkin myös yleisiä malleja, jotka tarjoavat useita esityskerroksia (esim. Pinta- ja syvyysrakenne ).

Usein puun solmut rikastetaan ominaisuuksilla (kielitieteessä nämä ovat pääasiassa morfologisia luokkia ). Tämä antaa sinulle määritetyn syntaksipuun ja siihen liittyvän määritetyn kieliopin . Vaikka kontekstivapaata kielioppia käytetään kahdessa ensimmäisessä puuesityksessä , kontekstiriippuvuus tulee esiin jälkimmäisessä . Nämä erot heijastuvat Chomsky-hierarkiassa . Tällaisissa tapauksissa termiä semanttinen analyysi käytetään kääntäjän rakentamisessa .

Johtopuut

Harkitse kontekstivapaata kielioppia . Johtopuu tälle on puu, jonka solmut on merkitty symboleilla (eli pääte- ja ei-päätemerkit ja tyhjä sana ). Puu on tilattu , ts. H. jokaisen solmun lapsilla on kiinteä järjestys, ja seuraava koskee merkintöjä: ${\ displaystyle G = \ vasen (N, \ Sigma, P, S \ oikea)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• Juuri on merkitty kanssa lähtösymbolista . Tätä ominaisuutta ei joskus vaadita. Puuta, joka tyydyttää heitä, kutsutaan täydelliseksi johtopuuksi .${\ displaystyle S}$
• Jos sisäsolmun, johon on merkitty, lapset on merkitty symboleilla (tässä järjestyksessä), kieliopin on sisällettävä sääntö .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ - z_ {1} \ ldots z_ {m}}$
• Lehdet puussa on merkitty symboleilla .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Jos lehti on merkitty, se on edeltäjänsä ainoa seuraaja.${\ displaystyle \ varepsilon}$

Sisäisiksi solmuiksi voidaan käyttää vain ei-terminaalisia symboleja, ja vain päätemerkkejä tai tyhjää sanaa lehdille.

Johtopuiden rakentaminen

Mahdolliset syntaksipuut / kaaviot voidaan usein luoda helposti lyhyille teksteille noudattamalla tuotantosääntöjä. Monia mekaanisia menetelmiä on saatavana pidemmille teksteille .

Esimerkiksi johdannossa esitetty syntaksikaavio sisältää muun muassa. perustuvat seuraaviin sääntöihin:

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & NP \ VP \\ NP & \ rightarrow & {\ mathtt {John}} \\ NP & \ rightarrow & Det \ N \\ VP & \ rightarrow & V \ NP \\\ end {array}} \ quad \ quad {\ begin {array} {lll} V & \ rightarrow & {\ mathtt {hit}} \\ Det & \ rightarrow & {\ mathtt {the} } \\ N & \ oikealle ja {\ mathtt {pallo}} \ end {array}}}$

Johtopuun luomiseksi sääntöjä voidaan soveltaa vaiheittain juuresta korvaamalla systemaattisesti yksi säännön vasemmalla puolella oleva nonterminal oikealla puolella olevilla symboleilla, kunnes vain terminaaleja on jäljellä:

${\ displaystyle S \ \ Rightarrow \ NP \ VP \ \ Rightarrow \ {\ mathtt {John}} \ VP \ \ Rightarrow \ {\ mathtt {John}} \ V \ NP \ Rightarrow \ {\ mathtt {John \ hit }} \ NP \ \ Rightarrow \ {\ mathtt {John \ hit}} \ Det \ N \ Rightarrow \ {\ mathtt {John \ hit \ the}} \ N \ Rightarrow \ {\ mathtt {John \ hit \ the \ pallo}}}$

Piirrät jokaisella vaiheella osan syntaksipuun ylhäältä alas. Mutta voit myös soveltaa sääntöjä päinvastoin ja aloittaa kirjoitetulla lauseella ja sitten rakentaa puun askel askeleelta alhaalta ylös.

Johtopuut yksiselitteisille ja epäselville kielioppeille

Jos kieliopin kielellä sanalle on useampi kuin yksi johdepuu, puhutaan epäselvästä kieliopista , muuten yksiselitteisestä. Esimerkiksi seuraava kielioppi on epäselvä

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & S \ S \\ S & \ rightarrow & a \ end {array}}}$

koska "aa a" voidaan jakaa kahteen eri tapaan: "[aa] a" ja "a [aa]". Kuitenkin vain yksi mahdollinen luokittelu sallii seuraavan kieliopin

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & a \ S \\ S & \ rightarrow & a \ end {array}}}$

Epäselvän kieliopin tapauksessa yhden ja saman sanan mahdollisten johtopuiden määrä voi kasvaa voimakkaasti sanan pituuden myötä. Tällöin johdannapuut eivät enää ole sopiva esitys mahdollisille johdannaisille. Muodollisten kielten tapauksessa konkreettinen (pinta) kielioppi muotoillaan yleensä yksiselitteisesti. Abstraktit kieliopit puolestaan ​​ovat usein epäselviä, jolloin abstraktin johdepuun ainutlaatuisuus johtuu analyysin aikana konkreettisuudesta.

Abstraktit syntaksipuut

Syntaksipuiden esittämiseksi tietorakenteena tietokoneessa käytetään nyt abstraktin syntaksipuun (AST) nimitystä melko tasaisesti. B. myös abstrakteista johdepuista , operaattoripuista tai vastaavista. voidaan puhua. Tarkka yhteys abstraktin syntaksipuun ja konkreettisen johdepuun välillä on esitetty kirjallisuudessa esim. T. ilmoitettu. Johdepuun karkeuden lisäksi rakenteeseen sisältyy myös jatkokäsittelyvaatimuksia, joten pinnan kieliopista johtuva suora muodollinen johtaminen ei yleensä johda tähän.

Kontekstittoman pinnan kielioppi on sitten vastakkainen abstraktille kieliopille , joka kapeammassa mielessä on enimmäkseen algebrallinen tietotyyppi . Syntaksipuut esitetään sitten teknisesti monipuolisina termeinä . Analyysi on siirtymässä kieliopin ja algebrallisen-loogisen termin välillä, jotta täällä voidaan puhua sujuvasti ei-terminaaleista ja -tyypeistä tai puista ja termeistä.

esimerkki

Betoni (vasen) ja abstrakti (oikea) syntaksipuu lausekkeelle ${\ displaystyle a \ kertaa (b + 3)}$

Vastakkaisessa kuvassa esitetään seuraavien kieliopien konkreettiset ja abstraktit syntaksipuut.

E :: E "+" T - lauseke
  :: T
T :: T "*" F-termi
  :: F
F :: V - kerroin
  :: N
  :: "(" E ")"
V - muuttuja
N - numero

E :: E "+" E
  :: E "*" E
  :: V
  :: N

tyyppi E = lisää (E, E);
        mul (E, E);
        var (V);
        numero (N)

Tämän esimerkin konkreettisen kieliopin on säänneltävä järjestystä, jossa operaattoreita käytetään (osittaisiin) lausekkeisiin - eli piste ennen viivaa ja saman prioriteetin osailmaisuudet on ryhmiteltävä vasemmalta oikealle. Mahdollisuus luoda erilainen yhteenveto tarjotaan myös suluissa olevilla ilmaisuilla. Yhdessä tiettyjen päätelaitteiden (tässä "(", ")", "+", "*") kanssa nämä ovat vain syntaktisen pinnan ominaisuuksia, joilla ei enää ole merkitystä myöhemmässä analyysissä ja jatkokäsittelyssä. Erityisesti erityyppisten lausekkeiden (tässä E, T ja F) ja avainsanojen välinen ero voidaan jättää kokonaan väliin, kuten voidaan nähdä abstraktista syntaksipuusta, joka on myös paljon lähempänä sanan "sisältöä". ilmaisu. Näiden pinta-yksityiskohtien takia betonijohdannaispuista tulee paitsi hämmentäviä myös, mutta ne vievät yksityiskohtiensa vuoksi enemmän tallennustilaa kuin tarvitaan tietorakenteena tietokoneessa. Tämä heijastuu myös niiden ohjelmien ajonaikaan ja monimutkaisuuteen, joiden on myöhemmin käsiteltävä johtopuu. Teknisistä syistä lähdetekstin erittelyä ei siis yleensä esitetä tietyllä johdannaispuussa.

Esitys abstrakteista syntaksipuista

Esimerkissä esitetyn graafisen esityksen (operaattori) puuna lisäksi abstraktit syntaksipuut merkitään teknisesti termeinä , esim. B.: mul(var('a'), add(var('b'), num(3))).

Abstrakti kielioppi

Abstraktit syntaksipuut ovat tietorakenteita ja algebralliset tyypit ottavat niissä kieliopin roolin, mutta kirjallisuudessa, erityisesti kalkkien yhteydessä, annetaan usein vain karkea, epäselvä kielioppi, jolla on, kuten yllä olevassa esimerkissä on, sama rakenne kuin termit, mutta sisältävät silti avainsanoja. Tämä muoto mahdollistaa abstraktin syntaksipuun miellyttävän kirjoittamisen, joka on usein hyvin lähellä varsinaista lähdettä. Yleensä johdannossa huomautetaan, että sulkeita voidaan käyttää täsmentämisessä. Yllä olevan esimerkin abstrakti syntaksipuu a * (b + 3)kirjoitettaisiin sitten nimellä. Tämän kirjallisuuden yhteydessä keskitytään kuitenkin aina termiin, kuten mainittiin, kieliopin ja algebran väliset rajat hämärtyvät pelaamalla muodolla.

Tyypillinen esimerkki ovat lambda-laskennan lausekkeet , joiden abstrakti kielioppi kirjoitetaan usein vasta . Samaa tekniikkaa käytetään myös laajoissa kielioppeissa. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

kirjallisuus

• Ingo Wegener : Tietojenkäsittelyteoria . Algoritmikeskeinen johdanto. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Esimerkkejä kontekstivapaista kielistä ja syntaksipuista, s. 147-148 . 
• Uwe Schöning : Tietojenkäsittelyteoria - pähkinänkuoressa . 5. painos. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntaksipuut, s. 15-17 . 
• Juraj Hromkovič : Tietojenkäsittelyteoria . Muodolliset kielet, ennustettavuus, monimutkaisuuden teoria, algoritmit, viestintä ja salaus. 3. painos. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Kontekstittomat kieliopit ja painike-automaatit, s. 378 . 
• Hans Zima: Compiler minä . Analyysi. Bibliographisches Institut, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01644-2 , 4.3 Tiivistelmäpuita ja niiden määrittelyä, s. 216-229 . 
• Stefan Müller : Kielioppi. Transformaatiokieliopista rajoituksiin perustuviin lähestymistapoihin. 2. painos. Language Science Press, Berliini 2018, ISBN 978-3-96110-074-3 , luku . 2 ( langsci-press.org ). 

Yksittäiset todisteet

1. ↑ Müller (2018), s.59f.