Парсер
Од Википедија, слободна енциклопедија
Во компјутерската наука, парсирањето е процес на анализирање за секвенца на токени за да се одреди нивната граматичка структура според некаква формална граматика. Парсер е компјутерски програм кој ја извршува оваа задача и тој е составна компонента на компајлерот.
Парсерот го трансформира влезниот текст во податочна структура, најчесто дрво, која е соодветна за подоцнежно процесирање. Лексичката анализа креира токени од влезните знаци и овие токени се обработени од парсерот за да се изгради таа податочна сструктура т.н. парсирачко дрво или абстрактно синтаксно дрво.
Постојат многу алатки кои автоматски генерираат парсери од спецификациите на јазичната граматика напишана во Bacus Naum форма, како на пример Yacc (Yet another compiler compiler).
Најважната улога на парсерот е како компонента на компајлерот, тоа е поради потребата да се парсира изворниот код на компјутерските јазици. Програмските јазици се базирани на контекстно слободните граматики затоа што така за нив можат да се напишат брзи и ефикасни парсери. Но, контекстно слободните граматики се ограничени во нивните можности за изразување бидејќи тие можат да опишат само одредено множество на јазици. Неформално, тоа е поради тоа што меморијата за таквите јазици е ограничена. Тоа е поради тоа што граматиката не може да запамети присуство на некој влез, ова е потребно на пример во јазик во кој некое име треба да биде декларирано пред да се употреби. Од друга страна пак помоќни граматики не можат да се испарсираат со доволна ефикасност. Вообичаена стратегија е да се креира флексибилен парсер за контекстно слободна граматика кој прифаќа множество од некои јазични конструкции (некои од нив не се валидни), а потоа несаканите конструкции да ги изфилтрира. Вообичаено е да се креира контекстно слободна граматика која ги вклучува сите посакувани конструкции, но од друга страна, често е невозможно да се креира контекстно слободна граматика која што ги прифаќа само посакуваните конструкции. Парсерите обично не се пишуваат на рака туку ги генерираат генераторите за парсери.
[уреди] Разгледување на процесот
Следниов пример демонстрира вообичаен случај на парсирање на компјутерски јазик со две ниво во граматиката: лексичка и синтакасичка.
Прва фаза е генерирањето на токени, или лексичка анализа, со која влезот се дели на низа од значајни симболи дефинирана од граматиката на регуларни изрази. На пример, една програма- калкулатор ќе добие на влез нешто што изгледа вака “12*(3+4)^2” и ќе го подели на токените 12, *, (, 3, +, 4, ), ^ и 2, секој од нив е симбол со значење во контекст на аритметичките изрази. Парсерот ќе има правила со кои ќе каже дека знаците +,*,‘,( и)означуваат почеток на нов токен, па одтука следи дека незначајните токени 12 и3 нема да бидат генерирани.
Следен чекор е синтаксичкото парсирање или синтаксичката анализа, што всушност значи дека токените се дозволени изрази. Ова обично се прави со соодветната контекстно слободна граматика која рекурзивно ги дефинира компонентите која што кажува во кој редослед треба да се појавуваат изразите. Но, не сите правила на програмските јазици можат да се дефинираат и изразат преку контекстно слободна граматика, на пример неможат да се изразат некои типови на валидност или соодветнадекларација.
Последната фаза е семантичко парсирање или анализа, која работи само со импликациите на изразите кои самошто се валидирани и ги превзема соодветните активности. Во случајот на калкулаторот , акцијата е да го оцени изразот, од друга страна ќе генерира код.
[уреди] Типови на парсери
Задачата на парсерот одреди како влезот ќе води од стартниот симбол со правилата на формалната граматика. Тоа може да се направи на два начина :
- Top-down парсирање- Парсерот може да почне со стартниот симбол и да се обиде да го трансформира во влезот. Парсерот започнуава од најголемите елементи и се обидува да ги подели нив на помали делови. LL парсерите се пример за ваквиот вид напарсирање.
- Bottom-up парсирање- Парсерот започнува со стартниот симбол и се обидува да го презапише како стартен симбол. Тој се обидува да ги лозира најосновните елементи, потоа елементите кои ги содржат овие елементи итн. 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"
Buttom Up парсирање
Top-Down парсирање