Jäsentäminen alaspäin

Ylhäältä alas -jäsennys on yksi menetelmistä määrittää, kuuluuko syöttömerkkijono johonkin LL(k) -yhteydettömän kieliopin kuvaamaan muodolliseen kieleen . Tämä on kieliopin analyysialgoritmien luokka , jossa formaalin kieliopin sääntöjä laajennetaan aloitusmerkistä alkaen, kunnes vaadittu merkkijono saadaan aikaan .

Menetelmäidea

Kullekin ei-päätteiselle symbolille K rakennetaan funktio, joka mille tahansa syöttösanalle x tekee kaksi asiaa:

Löytää sanan x suurimman alun z , joka voi olla K : stä johdetun sanan alku
Määrittää, johdetaanko alkuperä z K : stä

Tällaisen toiminnon on täytettävä seuraavat kriteerit:

lukea vielä käsittelemättömästä syöttövirrasta A :n maksimialku, joka on jonkin K :stä tulostetun sanan alku
määrittää, onko A johdettavissa K :stä vai yksinkertaisesti K :stä johdettavan sanan ei-johdannainen alku

Jos tällaista alkua ei voida laskea (ja funktion oikeellisuus ei-terminaalille K on todistettu), syötetiedot eivät vastaa kieltä ja jäsentäminen tulee lopettaa.

Jäsentäminen koostuu yllä kuvattujen funktioiden kutsumisesta. Jos luettavalle ei-päätteelle on yhdistelmäsääntö, sen jäsentämisen yhteydessä kutsutaan muita toimintoja jäsentämään siihen sisältyvät terminaalit. Kutsupuu, joka alkaa "ylhäältä"-funktiosta, vastaa jäsennyspuuta.

Yksinkertaisin ja "inhimillisin" tapa luoda jäsennin rekursiivisen laskeutumismenetelmän avulla on suora ohjelmointi kullekin päättelysäännölle kieliopin ei-päätteille.

Käyttöehdot

Olkoon N äärellinen joukko ei-terminaalisia symboleja tietyssä formaalissa kielioppissa; Σ on äärellinen joukko päätemerkkejä, jolloin rekursiivista laskeutumismenetelmää voidaan soveltaa vain, jos jokaisella tämän kieliopin säännöllä on seuraava muoto:

tai , missä , ja tämä on ainoa tulossääntö tälle ei-päätteelle $A\nuoli oikealle\alpha$ $\alpha \subset (\Sigma \cup N)*$
tai kaikille $A\rightarrow a_{1}\alpha _{1}|a_{2}\alpha _{2}|...|a_{n}\alpha _{n}$ $i=1,2...n;a_{i}\neq a_{j},i\neq j;\alpha \subset (\Sigma \cup N)*$

Ylhäältä alas -jäsennysalgoritmit

Rekursiivinen laskeutumisparser ( en:Recursive descent parser )
LL-jäsennin ( en:LL-jäsennin )
Roskapostin jäsentäjä ( en:Packrat parser )

Kirjallisuus

A. Shen . Ohjelmointi: lauseet ja tehtävät. 2. painos, M.: MTsNMO, 2004
Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Kääntäjät: periaatteet, tekniikat ja työkalut = kääntäjät: periaatteet, tekniikat ja työkalut. - 2. painos - M .: Williams , 2008. - ISBN 978-5-8459-1349-4 .
Robin Hunter. Kääntäjän peruskäsitteet = Kääntäjien olemus. - M . : "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .