Yacc

Рачунарски програм yacc је генератор парсера, који је развио Стивен Ц. Џонсон из компаније АТ&Т за оперативни систем Јуникс. Име представља скраћеницу још један компилатор компилатора (енгл. Yet Another Compiler Compiler). Он генерише парсер (део компилатора који покушава да синтаксно обради изводни код) на основу формалне граматике записане у форми сличној БНФ. Yacc генерише код за парсер у програмском језику Ц.

Yacc је дуго био доступан као подразумевани генератор парсера на већини Јуникс система. Међутим, данас је у великој мери замењен новијим, али у великој мери компатибилним програмима, као што су Berkeley Yacc, GNU bison, MKS yacc и Abraxas pcyacc. Осамревењена верзија оригиналног АТ&Т програма је доступна као део Сановог пројекта ОпенСоларис. Сваки од ових програма пружа ситна побољшања и додатне опције у односу на оригинални yacc, али је концепт остаио исти. Yacc је такође написан и за друге програмске језике, укључујући Ратфор, ЕФЛ, МЛ, Ада, Јава, и Лимбо.

Парсеру који генерише yacc је неопходан лексички анализатор. Генератори лексичких анализатора, као што су Lex или Flex су широко доступни. IEEE POSIX P1003.2 стандард дефинише функционалност и захтеве и за Lex и за Yacc.

Рад yacc-а заснива се на методи LALR(1)-анализе. Улаз у систем yacc представља изворна датотека која садржи опис правила контекстно слободне граматике. Описи правила граматике проширују се семантичким акцијама које представљају програмски код у C-у који се извршава када се препозна одређени део улаза. Резултат рада yacc-а је датотека која се обично назива y.tab.c. Њу је потребно превести неким C преводиоцем и повезати са остатком програма који пишемо да бисмо добили извршну верзију програма.

Структура улазне датотеке

Улазна датотека yacc система обично има екстензију .c и састоји се из три дела међусобно раздвојена сепаратором %%:

Први део је део декларација који садржи декларације свих токена граматике. У њему се наводи и приоритет и асоцијативност оператора уколико је потребно и врши декларисање типа атрибута симбола дате граматике. У овом делу се могу дефинисати и декларисати разни глобални објекти на језику C који се касније могу користити у свим акцијама које врше обраду улаза. Тај C код се наводи између %{ и %}.

Централни део је део правила у коме су наведена граматичка правила проширена акцијама које представљају код који се извршава када се препозна део улаза описан тим правилом.

Трећи део је део функција који садржи функције писане у програмском језику C. Оне се, без икакве обраде, дописују на одговарајућа места у y.tab.c датотеку. У овом делу се обично налазе и дефиниције функције main() и функције yylex() која врши фазу лексичке анализе.

Види још

GNU bison: GNU верзија yacc-a
LALR парсер: алгоритам за парсирање који се налази у позадини yacc-a
Lex и Flex, лексички анализатори који се најчешће користе заједно са yacc-ом (Bison-ом)

Литература

Stephen C. Johnson. YACC: Yet another compiler-compiler. Unix Programmer's Manual Vol 2b, 1979.

Спољашње везе

Tutorial lex/yacc/компилатор туторијал
Berkeley Yacc варијанта yacc-a која је написана да би се избегла зависност од било ког конкретног компајлера за C
Yaxx варијанта yacc-a која је написана да би се избегла зависност од било ког конкретног програмског језика
Essence, генератор парсера за Scheme
CL-Yacc, генератор парсера за Lisp
Eyapp, проширење yacc-a за Perl