Расчленување (информатика)

Расчленување или синтаксичка анализа (наречено и „парсирање“ од анг. parsing) — процес на анализирање за низа на токени за да се одреди нивната граматичка структура според некаква формална граматика. Расчленувач е сметачки програм кој ја извршува оваа задача и тој е составна компонента на компајлерот.

Расчленувачот го претвора влезниот текст во податочна структура, најчесто дрво, која е соодветна за подоцнежна обработка. Лексичката анализа создава токени од влезните знаци и овие токени се обработени од расчленувачот за да се изгради таа податочна структура т.н. разчленвачко дрво или апстрактно синтаксно дрво.

Постојат многу алатки кои автоматски создаваат расчленувачи од спецификациите на јазичната граматика напишана во Bacus Naum форма, како на пример Yacc (Yet another compiler compiler).

Најважната улога на расчленувач е како компонента на компајлерот, тоа е поради потребата да се расчленува изворниот код на сметачки јазици. Програмските јазици се засновани на контекстно слободните граматики затоа што така за нив можат да се напишат брзи и ефикасни расчленувачи. Но, контекстно слободните граматики се ограничени во нивните можности за изразување бидејќи тие можат да опишат само одредено множество на јазици. Неформално, тоа е поради тоа што меморијата за таквите јазици е ограничена. Тоа е поради тоа што граматиката не може да запамети присуство на некој влез, ова е потребно на пример во јазик во кој некое име треба да биде декларирано пред да се употреби. Од друга страна пак помоќни граматики не можат да се расчленат со доволна ефикасност. Вообичаена стратегија е да се создава флексибилен расчленувач за контекстно слободна граматика кој прифаќа множество од некои јазични конструкции (некои од нив не се валидни), а потоа несаканите конструкции да ги изфилтрира. Вообичаено е да се создава контекстно слободна граматика која ги вклучува сите посакувани конструкции, но од друга страна, често е невозможно да се создава контекстно слободна граматика која што ги прифаќа само посакуваните конструкции. Расчленувачите обично не се пишуваат на рака туку ги создаваат создавачите за расчленувачи.

Разгледување на процесот

Следниов пример демонстрира вообичаен случај на расчленување на сметачки јазик со две ниво во граматиката: лексичка и синтакасичка.

Прва фаза е создавањето на токени, или лексичка анализа, со која влезот се дели на низа од значајни симболи дефинирана од граматиката на регуларни изрази. На пример, една програма- калкулатор ќе добие на влез нешто што изгледа вака “12*(3+4)^2” и ќе го подели на токените 12, *, (, 3, +, 4, ), ^ и 2, секој од нив е симбол со значење во контекст на аритметичките изрази. Раслченувачот ќе има правила со кои ќе каже дека знаците +,*,‘,( и)означуваат почеток на нов токен, па оттука следи дека незначајните токени 12 и3 нема да бидат создадени.

Следен чекор е синтаксичкото расчленување или синтаксичката анализа, што всушност значи дека токените се дозволени изрази. Ова обично се прави со соодветната контекстно слободна граматика која рекурзивно ги дефинира компонентите која што кажува во кој редослед треба да се појавуваат изразите. Но, не сите правила на програмските јазици можат да се дефинираат и изразат преку контекстно слободна граматика, на пример неможат да се изразат некои типови на валидност или соодветнадекларација.

Последната фаза е семантичко расчленување или анализа, која работи само со импликациите на изразите кои самошто се валидирани и ги презема соодветните активности. Во случајот на калкулаторот , акцијата е да го оцени изразот, од друга страна ќе создаде код.

Видови раслченувачи

Задачата на раслченувачот е да одреди како влезот ќе води од почетниот симбол со правилата на формалната граматика. Тоа може да се направи на два начина:

• Надолно расчленување — раслченувачот може да почне со почетниот симбол и да се обиде да го трансформира во влезот. Раслченувачот започнуава од најголемите елементи и се обидува да ги подели нив на помали делови. LL раслченувачите се пример за ваквиот вид на расчленување.
• Нагорно расчленување — раслченувачот започнува со почетниот симбол и се обидува да го презапише како почетен симбол. Тој се обидува да ги лозира најосновните елементи, потоа елементите кои ги содржат овие елементи итн. LR-расчленувачите се претставници на ваквиот начин на расчленување. Друг поим кој се користи за ваквиот вид расчленување е расчленување со намалено поместување (shift-reduce).

Пример

grammar    :  rule(s)         # граматиката е од едно или повеќе правила

rule       :  production      
          |  production_2    
          |  production_3

production :  terminal_x  subrule  terminal_y

subrule    :  terminal_x {action}

terminal_x :  'x'

terminal_y :  'y'

action     :  "print 123"