А.А. Вылиток - Генератор синтаксических анализаторов yacc1 (1115012)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

А. А. ВылитокГенератор синтаксических анализаторов yacc1Программе yacc на вход подается КС-грамматика, на выходе получаетсясинтаксический анализатор, написанный на языке Си.Анализатор, построенный yacc’ом, основан на восходящем методе построениядерева вывода, а не на методе рекурсивного спуска. Построение дерева снизу вверх, отлистьев к корню, соответствует построению правого вывода «задом наперед»:анализируемая цепочка постепенно сворачивается к цели грамматики (к начальномусимволу).

Поясним это на примере грамматики для простых выражений.S→ S+T|TT→ T*F|FF→ 0|1Рассмотрим цепочку 0 + 1*1 и построим для нее правый вывод «задом наперед»,читая цепочку слева направо и применяя правила грамматики так, что правая частьправила, входящая в сентенциальную форму, заменяется на нетерминал, стоящий в левойчасти (такая замена называется сверткой):0 + 1 * 1 ← F + 1*1 ← T + 1*1 ← S + 1*1 ← S + F*1 ← S + T*1 ← S + T*F ← S + T ← SПодчеркиванием выделены вхождения правых частей, заменяемые на очередномшаге.Грамматику можно снабдить действиями (на языке Си).

Действие выполняется,когда происходит свертка. Для каждого правила вида A → A1A2…An , в действиях можноиспользовать обозначения $1, $2, …,$n, которые содержат значения, полученные присвертках соответственно к A1, A2, …, An. (если Ai — терминал, то у него нет значения);$$ — это значение, вырабатываемое при свертке к A. Его можно задать в видеприсваивания: $$=….Добавим в нашу грамматику действия по вычислению значения выражения.S → S + T 〈$$=$1+$3;〉 | T〈$$=$1;〉T → T * F 〈$$=$1*$3;〉 | F〈$$=$1;〉F → 0 〈$$=0;〉 | 1〈$$=1;〉Рассмотрим вывод для 0 + 1*1, указывая в угловых скобках вычисляемые значениядля нетерминалов.

Значение для S на последнем шаге будет значением всего выражения.0 + 1*1 ← F〈0〉 + 1*1 ← T〈0〉 + 1*1 ← S〈0〉 + 1*1 ← S〈0〉 + F〈1〉*1 ← S〈0〉 + T〈1〉*1 ← S〈0〉 +T〈1〉*F〈1〉 ← S〈0〉 + T〈1〉 ← S〈1〉Запись грамматических правил и действий для программы yacc имеет своиособенности. Вместо стрелки для разделения левой и правой частей правил ставитсядвоеточие. Действия записываются не в угловых, а в фигурных скобках. (Фигурныескобки в роли итераторов в yacc не используются.)Укажем общий вид входного потока для yacc:%{Операторы и директивы Си типа #include, описания и т.д.1От англ. «yet another compiler-compiler» (еще один компилятор компиляторов). Так назвал своюпрограмму С. Джонсон, поскольку во время ее разработки уже были подобные программы. Но именноэта, благодаря Unix, дожила до наших дней.Эта часть не обязательна.%}yacc-описания: лексемы, грамматические переменные, информация о приоритетах иассоциативности.%%грамматические правила и действияеще операторы Си (необязательно):main() {…;yyparse;…}yylex(){…}…Входной поток обычно записывается в файл с расширением y (например, file.y) иподается программе yacc командой Unix:$ yacc –o file.c file.yРезультат будет записан в файл file.c (если в команде не указано явно имявыходного файла, то результат запишется в файл y.tab.c).Файл-результат имеет следующую структуру:Операторы на Си между %{ и %} исходного файла, если естьОператоры на Си из части после второй комбинации %%, если есть:main() {…;yyparse; …}yylex(){…}…yyparse(){анализатор, который обращается за очередной лексемой к функцииyylex()}Имена функций yyparse () и yylex () фиксированы.

Функцию лексического анализаyylex () мы должны написать самостоятельно и вставить в исходный файл. Передачалексемы в синтаксический анализатор осуществляется через переменную yylval. Такжеможно добавить в исходный файл функции, реализующие сложные семантическиедействия. Обращения к этим функциям указываются в грамматике. Функциясинтаксического анализа (с семантическими действиями) yyparse () строится программойyacc автоматически по грамматике с действиями и добавляется в выходной файл.

Висходный файл можно добавить управляющую функцию (например, main ()), котораябудет вызывать синтаксический анализатор yyparse ().Полученную с помощью yacc программу на Си можно откомпилировать (gcc),возможно, связать с другими программами на Си и выполнить.Примеры использования yaccСкобочной системой называется цепочка, порождаемая грамматикой S → (S) S | ε.Пустая цепочка, как следует из определения, тоже считается скобочной системой.Непустая скобочная система неделима, если ее нельзя представить в виде конкатенации(сцепления) двух непустых скобочных систем.

Например, (( )( )), ((( ))) — неделимыесистемы, а системы ( )( )( ) и ( )((( ))) таковыми не являются.Протяжением скобочной системы называется максимальное число неделимыхсистем, сцепление которых дает данную систему. Например, ( )(( )( )( )) имеетпротяжение 2; (( ))( )( ) — протяжение 3; пустая цепочка ε имеет протяжение 0.Глубина скобочной системы — это максимальный уровень вложенности скобок.Пустая система имеет глубину 0; глубина ( )( )( ) равна 1; глубина ( )(( )(( )))( )( ) равна 3.Ширина скобочной системы — это максимальное протяжение среди всехподсистем, входящих в данную систему.

Пустая система имеет ширину 0; ширина ( (( )))( )равна 2; ширина ( )(( )( )( )) равна 3.Построим с помощью yacc программу, вычисляющую глубину скобочной системы.В грамматику нужно добавить действия по вычислению глубины: пустая имеет глубинуноль, глубина системы вида (S) S вычисляется как максимальная из глубин двух частей:неделимой подсистемы (S) и «хвостовой» подсистемы S. Для удобства введем новыйначальный символ P и добавим к грамматике правило P → S c действием вывестирезультат — глубину скобочной системы.Приведем текст исходного файла depth.y для вычисления глубины.%{/* Программа вычисления глубины скобочной системы */#include <stdio.h>%}%%P: S { printf ( "depth: %d\n", $1 ); }S: '('S')'S { $$ = $2+1; if ( $$<$4 ) $$=$4; }| /*empty*/{ $$ = 0; }%%main () {printf ( "type a string, please: " );yyparse ();}yylex () {int c;c = getchar ();if ( c=='\n' ) return 0;yylval = c;return c;}yyerror ( char *s ) {printf ( "Depth eval: %s\n", s );}Теперь вычислим ширину скобочной системы с помощью yacc.

Для вычисленияширины опишем глобальную переменную width, которую обнулим сначала, в ней будемхранить текущий максимум для протяжений подсистем. Действия по вычислению: для εпротяжение равно нулю, для (S)S протяжение на 1 больше, чем для «хвоста» S. Еслипротяжение (S)S больше чем widh, полагаем widh равным протяжению (S)S.Файл widh.y для вычисления ширины скобочной системы:%{#include <stdio.h>int width=0;%}%%P: S { printf ( "width: %d\n", width ); }S: '('S')'S { $$=$4+1; if ( width<$$ ) width=$$; }| /*empty*/{ $$=0; }%%main() {printf ( "type a string, please: " );yyparse ();}yylex () {int c;c = getchar();if ( c=='\n' ) return 0;yylval = c;return c;};yyerror ( char *s ) {printf ( "Width eval: %s\n", s );};Задачи для самостоятельного решения1.

С помощью yacc построить программу, вычисляющую протяжение скобочнойсистемы.2. С помощью системы yacc построить программу-калькулятор для выражений,содержащих целые числа, операции «+», «*» , «−» , «/» и круглые скобки.Приоритет операций «*» и «/» выше, чем у «+», «*». Все операциилевоассоциативны..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы