Рашчлањивање
У рачунарству и лингвистици, рашчлањивање (парсирање, формалније: синтаксна анализа) је поступак анализирања низа токена ради утврђивања граматичке структуре у односу на дату (више или мање) формалну граматику. Дакле, рашчлањивач је један од делова интерпретатора или компилатора, у којој се прихвата подразумевана хијерархија улазног текста и претвара у облик који је погодан за даљу обраду (најчешће у неки облик стабла рашчлањивања, апстрактног синтаксног стабла или неке друге хијерархијске структуре), притом обично проверавајући и евентуалне грешке у синтакси. Рашчлањивач често користи посебан лексички анализатор за издвајање токена из низа улазних знакова. Рашчлањивачи могу бити програмирани ручно или створени полуаутоматски (у неком програмском језику) употребом програмских алата (попут Yaccа) полазећи од граматике у Бекус-Науровој форми.
Поред тога, рашчлањивачи могу бити конструисани и као извршне спецификације граматика у функционалним програмским језицима. Фрост, Хафиз и Калахан (енг. Callaghan) су на основу радова других направили скуп функција вишег реда (названи рашчлањивачки комбинатори) који омогућавају конструкцију рашчлањивача за анализу наниже, полиномијалне временске и просторне сложености, као извршне спецификације за вишезначне граматике које садрже лево-рекурзивна правила. На сајту X-SAIGA може се наћи више појединости о алгоритмима и детаљима уграђивања.
Природни језици[уреди | уреди извор]
- Погледајте и рашчлањивање природних језика
Код неких система за машинско превођење и обраду природних језика, природне језике рашчлањују рачунарски програми. Програми не могу лако да рашчлањују реченице које формирају људи, с обзиром на то да је вишезначност једна од основних одлика у структури језика које користе људи. Да би рашчлањивали податке природног језика истраживачи прво морају да се договоре која ће се граматика користити. На избор синтаксе утичу како лингвистичка тако и питања рачунарске обраде; на пример, неки системи за рашчлањивање користе лексичке функционалне граматике, али у општем случају, рашчлањивање граматика ове врсте припада проблемима класе сложености НП. Head-driven phrase structure grammar је још један лингвистички формализам који је био популаран у рашчлањивачкој заједници, али други истраживачки напори су се фокусирали на мање сложене формализме као што су они који су коришћени у Penn банци дрвета. Плитко рашчлањивање има за циљ само одређивање граница главних саставних делова као што су именичке фразе. Још једна популарна стратегија за избегавање лингвистичких контроверзи је рашчлањивање зависних граматика.
Већина савремених рашчлањивача је бар делом статистичка; односно, они се ослањају на корпус већ забележених (ручно рашчлањених) података. Овај приступ дозвољава систему да прикупља информације о учесталости појављивања разних конструкција у одређеном контексту. (Видети машинско учење) Приступи који су коришћени обухватају праволинијске SCFG (стохастичке контекстно слободне граматике), максималну ентропију, и неуронске мреже. Већина успешнијих система користи лексичку статистику (то јест, разматра идентитет употребљених речи, као и њихов говорни део).
Алгоритми за рашчлањивање природних језика не могу да се ослоне на то да ће граматика имати „фине“ особине као ручно прављене граматике за програмске језике. Како је већ раније поменуто, неке граматичке формализме је веома тешко рашчланити уз помоћ рачунара; у принципу, чак и у случају када жељена структура није контекстно слободна, користи се нека врста контекстно слободне апроксимације у односу на граматику која се користи да би се извршио први пролазак. Алгоритми који користе контекстно слободне граматике често се ослањају на неку варијанту CYK алгоритма, обично са неком хеуристиком за одбацивање непотребних анализа да би се уштедело на времену. (Видети табеларно рашчлањивање.) Ипак, неки системи су жртвовали брзину у циљу тачности коришћењем нпр. линеарних алгоритама са пребацивање-свођење (енг. shift-reduce) конфликтима. Нешто скорији развој је прерангирање рашчлањивања у којем рашчлањивач предлаже велики број анализа, а сложенији систем бира најбољу опцију.
Програмски језици[уреди | уреди извор]
Рашчлањивач се најчешће користи као део компилатора или интерпретатора. Он рашчлањује изворни код програмског језика да би створио неки облик интерне репрезентације. Обично се програмски језици описују контекстно слободним граматикама јер се за њих могу написати брзи и ефикасни рашчлањивачи. Рашчлањивачи се пишу ручно или се стварају употребом генератора рашчлањивача.
Контекстно слободне граматике су ограничене у мери у којој могу да изразе све језичке захтеве. Неформално, разлог је да је ограничено памћење тог језика. Граматика не може да запамти присуство неке конструкције у односу на произвољно дуг улаз; ово је неопходно за језик у којем, на пример, име мора бити декларисано пре његовог позивања. Моћније граматике које могу да изразе ова ограничења, с друге стране, не могу да се рашчлањују ефикасно. Због тога је уобичајена стратегија прављење мање прецизног рашчлањивача за контекстно слободну граматику који прихвата надскуп жељених језичких конструкција (то јест, прихвата и неке конструкције које нису коректне), а нежељене конструкције касније могу бити избачене.
Преглед поступка[уреди | уреди извор]
Следећи пример показује уобичајени случај рашчлањивања рачунарског језика са два нивоа граматике: лексичким и синтаксним.
Прву фазу представља екстраховање токена, или лексичка анализа, којом се улазна струја карактера дели у основне симболе чије је значење дефинисано граматиком регуларних израза. На пример, програм за израчунавање ће тражити улаз као што је 12*(3+4)^2 и поделити га на токене 12, *, (, 3, +, 4, ), ^ и 2, од који сваких представља симбол који има значење у контексту аритметичког израза. Рашчлањивач треба да садржи правила која ће му рећи да слова *, +, ^, ( и ) означавају почетак новог токена, тако да бесмислени токени као што су 12* или (3 неће бити екстраховани.
Следећа фаза је рашчлањивање или синтаксна анализа, којом се проверава да ли отпаковани токени формирају израз који је дозвољен. Ово се обично чини коришћењем контекстно слободне граматике која рекурзивно дефинише компоненте које могу чинити израз и редослед којим оне морају да се појављују. Ипак, не могу сва правила која дефинишу програмске језике да се изразе само преко контекстно слободних граматика, на пример, исправност типова и одговарајуће декларације идентификатора. Ова правила могу формално да се изразе помоћу атрибутских граматика.
Последња фаза је семантичко рашчлањивање или анализа, којом се обрађују импликације управо потврђених израза и предузимају одговарајуће радње. У случају калкулатора или интерпретатора, радња је израчунавање израза или програма, док би, с друге стране, компилатор створио неку врсту кода. Атрибутске граматике могу бити употребљене и за дефинисање ових радњи.
Врсте рашчлањивача[уреди | уреди извор]
Основни задатак рашчлањивача је да одреди да ли и како се дати улаз може добити из почетног симбола граматике. Постоје два основна начина да се то уради:
- Синтаксна анализа наниже - Синтаксна анализа наниже се може посматрати као покушај налажења најлевљег извођења неке струје улазних карактера конструисањем дрвета синтаксичке анализе које започиње од корена и напредује ка листовима на основу правила задате формалне граматике. Читање улазних карактера врши се слева надесно. Укључивање избора се користи за прилагођавање вишезначности проширивањем свих могућих десних страна граматичких правила. ЛЛ-анализатори и рашчлањивачи који користе методу рекурзивног спуста су примери рашчлањивача који користе синтаксну анализу наниже, који се не могу прилагодити граматикама које садрже лево-рекурзивна правила. Иако се веровало да се једноставна уграђивања синтаксне анализе наниже не могу прилагодити граматикама са директном и индиректном левом рекурзијом и да могу да захтевају експоненцијалну временску и просторну сложеност при рашчлањивању вишезначних контекстно слободних граматика, Фрост, Хафиз и Калахан су направили нешто сложенији алгоритам за синтаксну анализу наниже који се може применити и на вишезначне и лево-рекурзивне граматике, полиномијалне временске сложености, који ствара репрезентације полиномијалне просторне сложености потенцијално експоненцијалног броја стабала синтаксичке анализе. Њихов алгоритам може да ствара оба, и најлевље и најдешње извођење неке улазне ниске, коришћењем правила задате КСГ.
- Синтаксна анализа навише - Рашчлањивач покушава да улазну ниску токена сведе на почетни симбол, конструишући дрво синтаксичке анализе полазећи од његових листова, поступним свођењем ка корену. Поступак свођења се састоји у томе да се у појединим корацима анализе, препозната десна страна неког правила граматике замени одговарајућом левом страном тог правила. ЛР-анализатори су примери рашчлањивача који користе синтаксну анализу навише.
Још једна значајна разлика између ова два наведена начина синтаксне анализе је у томе да ли одговарајући рашчлањивач описује најлевље или најдешње извођење задате ниске (погледати: контекстно слободне граматике). ЛЛ-анализатори ће створити најлевље извођење, док ће ЛР-анализатори створити најдешње извођење, али у обрнутом редоследу (од листова ка корену).
Примери рашчлањивача[уреди | уреди извор]
Синтаксна анализа наниже[уреди | уреди извор]
Неки од рашчлањивача који користе синтаксну анализу наниже:
[уреди | уреди извор]
Неки од рашчлањивача који користе синтаксну анализу навише: