емы "-" в момент, когда разобранная часть строки приведена к виду expr*expr. Два возможных действия анализатора состоят в следующем: Можно ввести следующий символ и без применения правила подстановки перейти в новое состояние. В разделе 1 мы назвали такое действие сдвигом. Выбор сдвига приведет к тому, что в одном из следующих состояний ко второй части конструкции для приведения ее к expr будет приме- нено правило (3), а затем вся полученная конструкция сведется к expr применением правила (4). - 20 - Можно сразу применить к конструкции expr*expr правило (4), тем самым приведя ее к expr, и без ввода нового символа перейти в очередное состояние. Такое действие в разделе 1 было названо сверткой. Использование свертки в данном состоянии приведет к применению в дальнейшем правила (3) для свертывания оставшейся части конструк- ции в expr. Неоднозначность такого рода будем называть конфликтом "сдвиг/свертка". (Выше этот конфликт был умышленно показан на примере выражения, порядок разбора которого существен в связи с различием приоритетов операций. На самом деле конф- ликт сдвиг/свертка возникает и при разборе такой строки, как expr-expr-expr. В этом случае разница в разборе ведет лишь к трактовке операции "-" как лево- или правоассоциативной. Однако, как известно, ассоциативность иногда играет важную роль, например, для операций присваивания, возведения в сте- пень. Возможен другой вид конфликта, состоящий в выборе между двумя возможными свертками; будем называть его конф- ликтом "свертка/свертка". Для примера подобного конфликта приведем грамматику, задающую десятичную и шестнадцатеричную форму записи константы: const: const_10 /*1*/ | const_16 ; /*2*/ const_10: dec_sequence; /*3*/ const_16: hex_sequence 'x'; /*4*/ dec_sequence:digit /*5*/ | dec_sequence digit; /*6*/ hex_sequence:digit /*7*/ | ABCDEF /*8*/ |hex_sequence digit /*9*/ |hex_sequence ABCDEF; /*10*/ ABCDEF : 'A'|'B'|'C'|'D'|'E'|'F'; digit:'0'|'1'|'2'|'3'|'4'|'5'|'6' |'7'|'8'|'9'; При появлении на входе первой же десятичной цифры (если с нее начинается последовательность) после ее замены нетер- миналом digit возникает конфликт между двумя возможными свертками: к нетерминалу dec_sequence в результате примене- ния правила (5) и к нетерминалу hex_sequence с помощью пра- вила (7). Заметим, что эта грамматика, в отличиe от грамма- тики в предыдущем примере, не позволяет корректно разобрать какую-либо строку двумя способами и в принципе нетерминал const определен однозначно. Однако, алгоритм разбора с просмотром вперед на 1 символ не в состоянии правильно осу- ществить выбор нужного правила. Следовательно, в этом случае речь идет о неоднозначности грамматики по отношению к приня- тому в yacc методу разбора. Поскольку вопрос о принципиаль- ной неоднозначности грамматики формально неразрешим, будем в дальнейшем понимать под неоднозначностью невозможность для - 21 - анализатора в некоторые моменты разбора выбрать очередное действие. Каждая ситуация (т.е. появление в некотором состо- янии некоторой входной лексемы), которая при разборе спо- собна вызвать конфликт "сдвиг/свертка" или "свертка/ свертка", выявляется yacc уже на этапе построения граммати- ческого анализатора. При этом yacc выдает сообщение о числе выявленных конфликтных ситуаций обоих видов, а в выходной файл y.output (если он формируется) помещается подробное описание всех конфликтов. Однако, yacc не считает наличие конфликтов фатальной ошибкой грамматики и строит граммати- ческий анализатор, заранее разрешая все возможные конфликты путем выбора в каждой ситуации единственного действия. При работе yacc используются два способа разрешения конфликтов. Первый способ действует по умолчанию (т.е. при отсутствии специальной пользовательской информации) и заклю- чается в применении следующих двух правил для выбора дейст- вия в конфликтных ситуациях: В случае конфликта сдвиг/свертка по умолчанию делается сдвиг. В случае конфликта свертка/свертка по умолчанию дела- ется свертка по тому из конкурирующих правил, которое задано первым в спецификационном файле. Грамматический анализатор, построенный с использованием этих правил, может не обеспечивать "правильного" с точки зрения пользовательской грамматики разбора. В частности, для первого из приведенных выше примеров разбор заключался бы в сворачивании арифметических выражений справа налево без учета приоритетов операций. Во втором примере в результате замены первой конструкции digit нетерминалом dec_sequence все числа, начинающиеся с цифры, разбирались бы как десятич- ные, а появление одной из букв от A до F или символа "x" в конце числа неверно трактовалось как ошибка во входном тексте. Однако, в ряде ситуаций описанный способ разрешения конфликтов приводит к нужному результату. Например, рассмот- рим фрагмент грамматики языка программирования, описывающий условный оператор: оператор: if '(' условие ')' оператор /*1*/ | if '(' условие ')' оператор else оператор; /*2*/ Входная строка вида: if(C1) if(C2) S1 else S2 вызвала бы при разборе конфликт сдвиг/свертка в момент - 22 - просмотра символа else. Введенная часть строки к этому вре- мени имеет вид: if (условие) if (условие) оператор Если выполнить свертку второй части конструкции по правилу (1), то строка сведется к: if (условие) оператор (Заметим, что применить еще раз правило(1) мешает просмот- ренный заранее символ else). После ввода конструкции S2 и замены ее нетерминалом оператор к строке: if (условие) оператор else оператор будет применено правило (2). Полученный разбор соответствует следующей интерпретации входной строки: if (C1) {if(C2) S1} else S2 При альтернативном подходе в случае применения сдвига в момент появления else входная строка была бы введена пол- ностью: if (условие) if (условие) оператор else оператор Ко второй части строки можно применить правило (2), а затем свернуть полученную конструкцию: if (условие) оператор по правилу (1). Такой разбор соответствует второй возможной интерпретации входной строки: if (C1) {if(C2) S1 else S2} Как известно, в большинстве языков программирования принята именно эта интерпретация (каждый else относится к ближайшему предшествующему if). Значит, выбор сдвига, осуществляемый по умолчанию, для данной грамматики верен. В качестве рекомендации отметим,что применение принципа умолчания для конфликтов сдвиг/свертка приводит к положи- тельному результату, если в грамматике принята правоассоциа- тивная интерпретация соответствующих конструкций и для них отсутствует понятие приоритета. Что касается конфликтов свертка/свертка, то стандартный способ их разрешения оказы- вается полезным только тогда, когда при любых конфликтах между данными двумя правилами справедлив выбор одного и того же правила. - 23 - В любом случае, если yacc сообщил о наличии конфликтных ситуаций, пользователь должен тщательно проанализировать содержательный смысл каждого конфликта и правильность выб- ранного yacc действия. Вся необходимая для этого информация содержится в файле y.output, структура которого будет расс- мотрена ниже. Если оказалось, что конфликты разрешены неу- довлетворительно, то грамматика должна быть перестроена или уточнена пользователем. В случае конфликтов свертка/свертка всегда требуется изменение самих грамматических правил; для конфликтов сдвиг/свертка есть возможность без перестройки правил уточнить грамматику путем задания информации о прио- ритетах и ассоциативности лексем и правил. В качестве примеров устранения конфликтов путем измене- ния правил приведем перестроенные варианты рассматривавшихся выше грамматик. Поскольку исходные конфликтные грамматики полностью удовлетворяют требованиям генерируемых ими языков, но содержат недостаточно информации для однозначного раз- бора, перестройка правил носит уточняющий характер. Перестроенная грамматика константного арифметического выражения: expr: expr1 | expr '+' expr1 | expr '-' expr1; expr1: CONST | expr1 '*' CONST | expr1 '/' CONST; Ниже будет приведен также вариант грамматики, полученной из исходной введением приоритетов (без перестройки правил). Перестроенная грамматика для задания константы: const: const_10 | const_16; const_10: dec_sequence ; const_16: hex_sequence 'x' | dec_sequence 'x'; dec_sequence: digit | dec_sequence digit; hex_sequence: ABCDEF | dec_sequence ABCDEF | hex_sequence ABCDEF |hex_sequence dec_sequence; ABCDEF:... digit:... - 24 - Рассмотрим теперь второй из используемых yacc способов раз- решения конфликтов, базирующийся на задании пользователем информации о приоритетах и ассоциативности. Отметим предва- рительно две основные причины конфликтности грамматик: принципиальная невозможность задать генерируемый язык бесконфликтной грамматикой; недостаточность информации для построения однозначного грамматического разбора. Грамматики, конфликтные по второй причине, всегда допускают преобразование правил до полного устранения конф- ликтов; в случае конфликтов сдвиг/свертка yacc всегда может построить для этих грамматик корректный разбор путем разре- шения конфликтов. Для грамматик, конфликтных по причине 1, попытки разрешения конфликтов не приведут к нужному резуль- тату. Однако, надо убедиться в том, что конфликтная грамма- тика действительно отражает входной язык: возможно, конф- ликты не имеют отношения к этому языку, а вызваны неодноз- начностью другого, реально описанного языка. Вообще, конф- ликты стоит рассматривать как повод проверить грамматику на соответствие языку (хотя последнее не гарантируется и отсутствием конфликтов). Задание приоритетов для неверной грамматики не приведет к генерации нужного языка, но может замаскировать ошибки, сняв вопрос о конфликтах. Приоритетное разрешение конфликтов сдвиг/свертка сос- тоит в том, что с обоими действиями yacc ассоциирует приори- теты (со сдвигом - приоритет лексемы, чтение которой вызы- вает данный конфликт, со сверткой - приоритет конкурирующего правила) и выбирает более приоритетное действие. В случае равенства приоритетов yacc руководствуется при выборе свойством ассоциативности. Приоритеты и ассоциативность отдельных лексем (явно) и правил (явно и неявно) задаются пользователем, все остальные приоритеты считаются неизвест- ными. yacc использует для разрешения конфликта данный спо- соб, если известны приоритеты обоих конкурирующих действий. Поэтому для разрешения ряда конфликтов на приоритетной основе необходимо установить приоритеты участвующих в них лексем и правил. Следует понимать,что задание приоритетов не ведет к устранению конфликтов и не делает грамматику однозначной. Но в отличие от конфликтов, разрешаемых yacc по принципу умол- чания, пользователь получает здесь возможность управлять разрешением конфликтов. yacc, сообщая общее число конфлик- тов, не учитывает в нем конфликтов, разрешенных в соответст- вии с информацией о приоритетах и не включает в выходной файл y.output описания этих конфликтов. Приоритеты и ассоциативность лексем задаются в секции деклараций с помощью директив трех видов: - 25 - %left <список_лексем> %right <список_лексем> %nonassoc <список_лексем> Каждая директива приписывает всем перечисленным в списке лексемам одинаковый приоритет. Директивы %left и %right одновременно задают соответственно левую или правую ассоциа- тивность лексем. Директива %nonassoc говорит об отсутствии у перечисленных лексем свойства ассоциативности. Устанавли- ваемый директивами приоритет не имеет численного выражения, а его относительное значение возрастает сверху вниз. Пример задания приоритетов лексем: %token OR NOR XOR AND NAND %right '=' %left OR NOR XOR %left AND NAND %left '+' '-' %left '*' '/' /* самый низкий приоритет имеет лексема "=", самый высокий - лексемы "*" и "/" */ Приоритет правила автоматически определяется приорите- том последней лексемы в теле правила. Если в секции деклара- ций для этой лексемы не задан приоритет или если правая часть правила вообще не содержит лексем, то приоритет пра- вила не определен. Этот принцип можно отменить явным зада- нием приоритета правила равным приоритету любой (имеющей приоритет) лексемы с помощью директивы: %prec <лексема> помещенной вслед за правой частью правила (перед точкой с запятой или действием). Например, правилу: expr: '-' expr %prec '*'; директива %prec придает приоритет лексемы "*" (лексема "-" при задании грамматики выражений часто используется для обозначения унарной и бинарной операций, имеющих разный при- оритет; с помощью директивЫ %prec унарной операции можно приписать более высокий приоритет. Иногда, чтобы связать с правилом приоритет, не совпадающий с приоритетом ни одной лексемы, вводят псевдолексему, задав ей в секции деклараций уникальный приоритет, и приписывают приоритет псевдолексемы правилу. В примере грамматики настольного калькулятора, при- водимом в приложении, с операцией "унарный минус" связан приоритет псевдолексемы UMINUS). - 26 - Сформулируем теперь полностью используемые yacc правила разрешения конфликтов сдвиг/свертка на основе информации о приоритетах и ассоциативности (напомним, что конфликты свертка/свертка разрешаются только по принципу умолчания): Если для входной лексемы и правила заданы приоритеты и эти приоритеты различны, то выбирается действие с боль- шим приоритетом. Больший приоритет правила вызывает свертку по нему, больший приоритет лексемы вызывает сдвиг. Если приоритеты заданы и совпадают, то принимается во внимание заданная одновременно с приоритетом ассоциа- тивность: в случае левой ассоциативности используется свертка, в случае правой - сдвиг. Отсутствие свойства ассоциативности (директива %nonassoc) в данном случае указывает на ошибку во входном тексте и анализатор воспримет вызвавшую данный конфликт лексему как ошибоч- ную. Если не задан приоритет входной лексемы и/или приоритет правила, то действует принцип разрешения конфликтов по умолчанию, в результате чего выбирается сдвиг. Пример грамматики константного выражения, уточненной зада- нием приоритетов: %left '+' '-' %left '*' '/' %% expr: CONST | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr; 9. Структура информационного входного файла y.output Основную часть данного файла составляет описание состо- яний построенного грамматического анализатора. Информация о каждом состоянии приводится в следующем порядке: - Перечень соответствующих данному состоянию конфигураций грамматики (конфигурация характеризуется определенным грамматическим правилом и позицией в его правой части, достигнутой к данному моменту разбора). Каждая конфигу- рация представляется правилом с отмеченной с помощью символа подчеркивания "_" распознанной частью (позицией конфигурации). Например, конфигурация: expr: expr +_expr - 27 - соответствует распознанной при разборе строки по ука- занному правилу последовательности символов expr+. - Действия анализатора при вводе в качестве очередного просматриваемого символа каждой из лексем. Различные виды действий указываются следующим образом: <лексема> сдвиг <номер_состояния> - сдвиг при вводе данной лексемы в состояние с указанным номером; <лексема> свертка <номер_правила> - свертка при вводе лексемы по правилу с указанным номе- ром; <лексема> error - выдача сообщения об ошибке во входных данных ("синтак- сическая ошибка") и возврат из процедуры грамматичес- кого анализа с кодом 1 (дальнейший разбор невозможен); <лексема> accept - возврат из процедуры грамматического анализа с кодом 0 (успешное завершение разбора). Последняя из строк, описывающих действия анализатора, содержит вместо ука- зания лексемы символ "." и сообщает действие, выполняе- мое анализатором для всех лексем, не перечисленных в данном состоянии. Часто эта строка имеет вид: . error и указывает, что все перечисленные лексемы в данном состоянии являются недопустимыми. - Перечень переходов для данного состояния. Каждый пере- ход задается строкой <имя_терминала> переход <номер_состояния> сообщающей, в какое состояние перейдет анализатор после свертки указанного нетерминала, если его распознавание было начато из данного состояния. Кроме того, описанию состояния может предшествовать информация о конфликтах обнаруженных yacc для этого состоя- ния и разрешенных по принципу умолчания. Информация о конф- ликте содержит тип конфликта (св/св или сдв/св), конкурирую- щие действия анализатора (при этом для сдвига указывается номер состояния, для свертки - номер правила) и лексему, при появлении которой возникает данный конфликт. Узнать, какое - 28 - из возможных действий будет выполнено анализатором, можно из описания самого состояния. Пример описания состояния: 8:Конфликт сдв/св (сдвиг 5,свертка 2) при + Состояние 8 a:a_+a a:a+a_ (2) + сдвиг 5 . свертка 2 Состоянию 8 здесь соответствуют две различные позиции, дос- тигнутые при разборе по правилу a: a '+' a Kонфликт между сверткой по этому правилу и сдвигом в состоя- ние 5 при вводе лексемы "+" разрешен в пользу сдвига. Ввод остальных лексем вызывает свертку. После описания состояния возможен ряд сообщений о нес- вернутых правилах (с указанием этих правил), т.е. о прави- лах, свертка по которым не будет произведена ни в одном из состояний. Наличие таких правил с большой вероятностью сви- детельствует о некорректности грамматики. В конце файла приводится информация статистического характера о реальном и предельном количестве терминальных и нетерминальных символов, грамматических правил и состояний. Фиксируется число конфликтов каждого типа, число различных действий грамматического анализатора, занимаемый им объем памяти, приводятся данные об использовании внутренних струк- тур данных (множеств). 10. Обработка ошибок при грамматическом разборе Если входной поток не удовлетворяет заданной грамма- тике, то грамматический анализатор в момент ввода лексемы, делающей невозможным продолжение разбора, фиксирует ошибку. Эту лексему мы в дальшейшем будем называть ошибочной лексе- мой. Реально ошибка может быть вызвана не только неверными входными данными, но и некорректностью самого грамматичес- кого анализатора, являющейся следствием некорректной грамма- тики. Стандартной реакцией грамматического анализатора на ошибку является выдача сообщения ("синтаксическая ошибка") и прекращение разбора. Эту реакцию можно несколько изменить, например, сделать сообщение об ошибке несколько более инфор- мативным, задав собственную процедуру yyerror. Однако, наи- более важная задача состоит в том, чтобы заставить анализа- тор в этом случае продолжать просмотр входного потока, в - 29 - частности, для выявления остальных ошибок. Применяемый yacc механизм восстановления основан на чтении и отбрасывании некоторого числа входных лексем; от пользователя требуется введение дополнительных грамматичсеких правил, указывающих, в каких конструкциях синтаксические ошибки являются допусти- мыми (в отношении возможности восстановления). Одновременно эти правила определяют путь дальнейшего разбора для ошибоч- ных ситуаций. Для указания точек допустимых ошибок исполь- зуется зарезервированное с этой целью имя лексемы error. Пример: a: b c d ; /*1*/ a: b c error; /*2*/ d: d1 d2 d3; /*3*/ Второе правило указывает путь разбора в случае, если при распознавании нетерминала a встретится ошибка после выделе- ния элементов b и c. yacc обрабатывает правила, содержащие лексему error, так же, как все остальные правила. В результате в ряде сос- тояний построенного анализатора оказывается предусмотренным действие для лексемы error (отличное от действия error). Будем говорить, что в этих состояниях лексема error допус- тима. Рассмотрим порядок работы анализатора при появлении во входном потоке ошибочной лексемы (т.е. лексемы, ввод которой в данном состоянии вызывает действие error): Фиксируется состояние ошибки; вызывается функция yyer- ror для выдачи сообщения. Путем обратного просмотра пройденных состояний,начиная с данного, делается попытка найти состояние, в котором допустима лексема error. Отсутствие такого состояния говорит о невозможности восстановления, и разбор прек- ращается. Осуществляется возврат в найденное состояние (кроме случая, когда им является непосредственно то состояние, в котором встретилась ошибка) Выполняется действие, заданное в этом состоянии для лексемы error. Очередной входной лексемой становится лексема, вызвавшая ошибку. Разбор продолжается, но анализатор остается в состоянии ошибки до тех пор, пока не будут успешно прочитаны и обработаны три подряд идущие лексемы. При нахождении анализатора в состоянии ошибки отличие в обработке оши- бочной лексемы заключается в том, что сообщения об ошибке не выдается, а сама лексема игнорируется. - 30 - После обработки трех допустимых лексем считается, что восстановление произошло, и анализатор выходит из сос- тояния ошибки. Итак, грамматический анализатор, встретив ошибку, пыта- ется найти ближайшую точку во входном потоке, где разрешена лексема error. При этом сначала делается попытка возврата в рамках правила, по которому шел разбор в момент появления ошибочноЙ лексемы, затем поиск распространяется на правила все более высокого уровня. В примере, приведенном в начале раздела, ввод недопустимой лексемы после того, как прочитана строка b c d1 d2 вызовет возврат к состоянию, характеризую- щемуся конфигурациями: a: b c_d; a: b c_error; и продолжение разбора по правилу (2). Часто правила, учитывающие возможность ошибки, задаются на уровне основных структурных единиц входного текста. Нап- ример, для пропуска в тексте ошибочных операторов может быть использовано правило оператор: error; При этом восстановление из состояния ошибки произойдет после нахождения трех лексем, которые могут следовать после опера- тора, например, начинать новый оператор. Если точно распоз- нать начало оператора невозможно, то ошибочное состояние может быть подавлено преждевременно, а обработка нового опе- ратора начата с середины ошибочного, что, вероятно, приведет к повторному сообщению об ошибке (на самом деле не существу- ющей). Учитывая это, более надежного результата следует ожи- дать от правил вида: оператор: error ';' Здесь восстановление произойдет только после нахождения ";" и двух начальных лексем следующего оператора; все лексемы после найденной ошибочной до ";" будут отброшены. С правилами, включающими лексему error, могут быть свя- заны действия. С их помощью пользователь может самостоя- тельно обработать ошибочную ситуацию. Кроме обычных операто- ров, здесь можно использовать специальные операторы yyerror и yyclearin, которые yacc на макроуровне расширяет в нужные последовательности. Оператор yyerror аннулирует состояние ошибки. Таким образом, можно отменить действие принципа "трех лексем". Это помогает предотвратить маскирование новых ошибок в случаях, когда конец ошибочной конструкции распоз- нается самим пользователем или однозначно определяется в правиле по меньшему числу лексем. - 31 - Оператор yyclearin стирает хранимую анализатором пос- леднюю входную лексему, если поиск нужной точки для возоб- новления ввода обеспечивается в заданном пользователем действии. Приведем общую форму правила с восстановительным дейст- вием оператор : error {resynch(); yyclearin; yyerror;} Предполагается, что пользовательская процедура resynch() просматривает входной поток до начала очередного оператора. Вызвавшая ошибку лексема, хранимая анализатором в качестве входной лексемы, стирается, после этого гасится состояние ошибки. При построении анализаторов, работающих в интерактивном режиме, для обработки ошибок рекомендуются правила вида: входная_строка : error '\n' {yyerrok; printf("Повторите последнюю строку \n");} входная_строка {$$=$4;} В действии, предусмотренном после ввода ошибочной строки, пользователю делается подсказка, а состояние ошибки гасится. Значением нетерминала после свертки здесь становится значе- ние повторно введенной строки. 11. Диагностика ошибок yacc выдает ряд сообщений об ошибках в случае невозмож- ности построения грамматического анализатора. В тексте сооб- щения, предваряемом заголовком "ошибка:", содержится указа- ние причины ошибки и номер просматриваемой в момент ее появ- ления строки спецификационного файла. Перечислим основные типы фиксируемых yacc ошибок: неверно заданные флаги командной строки; невозможность открытия входного или временных файлов; отсутствие файла /usr/lib/yaccpar с текстом процедуры yyparse; неверная структура спецификационного файла; ошибки в задании директив; синтаксические ошибки в описании грамматических правил, незавершенность комментариев, строк символов и дейст- вий; - 32 - некорректное использование псевдопеременных; неопределенные нетерминальные символы; нарушение количественных ограничений (по числу терми- нальных или нетерминальных символов, грамматических правил, состояний и проч.). - 33 - Приложение 1 Ниже приведен полный входной файл для yacc, реализующий небольшой настольный калькулятор; калькулятор имеет 26 регистров, помеченных буквами от a до z и разрешает исполь- зовать арифметические выражения, содержащие операции +, -, *, /, % (остаток от деления), & (побитовое и), | (побитовое или) и присваивание. Как и в Си, целые числа, начинающиеся с 0, считаются восьмеричными, все остальные - десятичными. В примере демонстрируются способы использования приори- тетов для разрешения конфликтов, а также простые операции по восстановлению из состояния ошибки. Калькулятор работает в интерактивном режиме с построчным формированием выхода. %token DIGIT LETTER /* имена лексем */ %left '|' /* задание приоритетов */ %left '&' /* операций */ %left '+' '-' %left '*' '/' '%' %left UMINUS /* установка приоритета операции унарный минус */ %{ /* oписания, используемые */ int base, regs[26]; /* в действиях */ %} %% /* начало секции правил */ list: | list stat '\n' | list stat error '\n' {yyerrok; } stat: expr {printf("%d\n",$1);} | LETTER '=' expr {regs[$1]=$3; } expr: '(' expr ')' { $$=$2; } | expr '+' expr { $$=$1+$3; } | expr '-' expr { $$=$1-$3; } | expr '*' expr { $$=$1*$3; } | expr '/' expr { $$=$1/$3; } | expr '%' expr { $$=$1%$3; } | expr '&' expr { $$=$1&$3; } | expr '|' expr { $$=$1|$3; } | '-' expr %prec UMINUS { $$= -$2; } | LETTER { $$=regs[$1]; } | number; number: DIGIT { $$=$1; base=10; if($1==0) base=8; } - 34 - | number DIGIT {$$=base*$1+$2; } %% /* начало секции программ */ /* * Программа лексического анализа * для строчных латинских букв * возвращает LETTER, * значение yylval от 0 до 25; * для цифр - DIGIT, * значение yylval от 0 до 9; * остальные символы возвращаются * непосредственно */ yylex() { int c; while( (c=getchar()) == ' ' ); if( c>='a' && c<='z' ) { yylval = c - 'a'; return(LETTER); } if( c>='0' && c<='9' ) { yylval = c - '0'; return(DIGIT); } return(c); } - 35 - Приложение 2 Анализ и преобразование в матричную форму входных дан- ных для задачи линейного программирования. Входная информация из обычной алгебраической формы: c1X1+c2X2+...+cnXn -> min(max) a11x1+a12X2+...+a1nXn=b1 am1X1+am2X2+...+amnXn=bm преобразуется в матричную: C: c1 c2 ... cn A: a11 a12 ... a1n ... am1 am2 ... amn B: b1 b2 ... bm Одновременно изменяются знаки коэффициентов при неизвестных в ограничениях с отрицательным свободным членом, а также знаки коэффициентов линейного функционала в случае его мак- симизации. С иллюстративной целью допускаются некоторые варианты синтаксической записи. Предусмотрена возможность повторного задания ошибочных строк. %token число Xi оптим %% злп:функционал '\n' система_ограничений {final();} | система_ограничений функционал '\n' { final();} функционал: линейная_функция {stf();} /* По умолчанию - минимизация */ | оптим '(' линейная_функция ')' {if($1) conv(); stf();} /* В случае максимизации выполнить conv() */ | линейная_функция '-''>' оптим {if($4) conv();stf();} линейная_функция: элем1 | линейная_функция элем ; элем: знак число Xi {stc($1*$2,$3); } | знак Xi '*' число { stc($1*$4,$2);} | знак Xi { stc($1,$2);} /* Формы записи коэффициентов */ элем1: элем | число Xi { stc($1,$2);} | Xi '*' число { stc($3,$1);} - 36 - | Xi { stc(1,$1); } знак: '+' {$$=1; } | '-' {$$= -1;} система_ограничений: ограничение '\n' | система_ограничений ограничение '\n' | система_ограничений error '\n' {aclear();yyerrok; printf("повторите последнюю строку\n");} /* В случае ошибки: стирание инф. о строке, восстановление и выдача подсказки */ ограничение: линейная_функция '=' число { stcb($3);} | линейная_функция '=' знак число { if($3<0) conv(); stcb($4);} /* Если bi<0, выполнить conv() */ %% #include "stdio.h" #define MAXM 100 /* предельное число */ #define MAXN 100 /* ограничений и перем.*/ int c[MAXN],b[MAXM],a[MAXM+1][MAXN], neqs,nx,x[MAXN]; /* Лексический анализатор возвращает: * для целых чисел - число, * yylval равно знач. числа; * для идент.вида xi, i=1,2,...XI* * yylval равно его порядк. номеру; * для max/min - оптим, * yylval равно соответственно 1 или 0 */ yylex() { char c,i; while((c=getc(stdin))==' '); switch(c) { case'0': case'1': case'2': case'3': case'4': case'5': case'6': case'7': case'8': case'9': yylval=c-'0'; while((c=getc(stdin))<='9'&&c>='0') yylval=yylval*10+c-'0'; ungetc(c,stdin); return(число); - 37 - case'm': if((c=getc(stdin))=='i') yylval=0; else if(c=='a') yylval=1; else return('m'); while((c=getc(stdin))<='z'&&c>='a'); ungetc(c,stdin); return(оптим); case'X': case'x': if((c=getc(stdin))<'0' || c>'9') return('x'); yylval=0; while(c<='9'&&c>='0') {yylval=yylval*10+c-'0';c=getc(stdin);} ungetc(c,stdin); for(i=0;i<nx;i++) if(x[i]==yylval){yylval=i;return(Xi);} x[nx]=yylval; yylval=nx++;return(Xi); } return(c); } /* Печать условия задачи в матричной форме */ final() { char i,j; printf("c:\n"); for(i=0;i<nx;i++) printf("%8d",c[i]); printf("\na:\n"); for(i=0;i<neqs;i++) { for(j=0;j<nx;j++) printf("%8d",a[i][j]); printf("\n"); } printf("b:\n"); for(i=0;i<neqs;i++) printf("%8d",b[i]); } /* Изменение знаков коэффициентов */ conv() { char i; for(i=0;i<nx;i++) a[neqs][i]*=(-1); } /* Запоминание коэффициентов функционала */ stf() { char i; for(i=0;i<nx;i++) { c[i]=a[neqs][i]; a[neqs][i]=0; } } /* Запоминание очередного коэффициента */ stc(nmb,adr) { a[neqs][adr]=nmb; } /* Запоминание свободного члена */ stcb(nmb) { b[neqs++]=nmb; } - 38 - /* Стирание ошибочной строки*/ aclear(){ char i; for(i=0;i<nx;i++) a[neqs][i]=0; } - 39 - Приложение 3 Формальное описание структуры спецификационного файла. файл_спецификаций: секция_деклараций '%''%' '\n' секция_правил '%''%' '\n' секция_программ | секция_деклараций '%''%' '\n' секция_правил ; секция_деклараций: | секция_деклараций дир_или_описание '\n' ; дир_или_описание: '%''{''\n'ВНЕШНИЕ_ОПИСАНИЯ '\n''%''}' | '%''s''t''a''r''t' ИДЕНТИФИКАТОР | '%''t''o''k''e''n'список_им_лексем | ассоциативность список_лексем ; ассоциативность: '%''l''e''f''t' | '%'''r''i''g''h''t' | '%''n''o''n''a''s''s''o''c' ; список_им_лексем: | декл_имени_лексемы | список_им_лексем декл_имени_лексемы ; список_лексем: декл_лексемы | список_лексем декл_лексемы ; декл_имени_лексемы: ИДЕНТИФИКАТОР | ИДЕНТИФИКАТОР ЦЕЛОЕ_БЕЗ_ЗНАКА; декл_лексемы: декл_лексемы | декл_литерала; декл_литерала: ЛИТЕРАЛ | ЛИТЕРАЛ ЦЕЛОЕ_БЕЗ_ЗНАКА; секция_правил: набор_правил | '%''{''\n'СИ_ОПЕРАТОРЫ'\n''%''}' '\n' набор_правил '\n' ; набор_правил: правило | набор_правил ';' правило ; правило: левая_часть ':' альтернатива | правило '|' альтернатива ; левая_часть: ИДЕНТИФИКАТОР ; альтернатива: - 40 - правая_часть | правая_часть изм_приор | правая_часть изм_приор действие | правая_часть действие ; правая_часть: | правая_часть лит_или_идент | правая_часть действие лит_или_идент; изм_приор: секция_программ: ПРОГРАММНЫЕ_КОМПОНЕНТЫ ; При описании структуры спецификационного файла не рас- шифровывались некоторые исходные конструкции, совпадающие с аналогичными конструкциями Си: идентификатор, литерал, целое без знака. Не описаны также и более сложные конструкции, являющиеся фрагментами Си-программ, переносимыми в текст анализатора (внешние описания, Си-операторы). Под расширен- ными Си-операторами понимаются операторы с возможным исполь- зованием псевдопеременных. ПРОГРАММНЫЕ_КОМПОНЕНТЫ включают операторы препроцессора, описания внешних переменных и функ- ций (возможный состав их приводится в разделе 4.3). - 41 - СОДЕРЖАНИЕ . Аннотация ......................................... 2 1. Принципы работы yacc .............................. 3 2. Входные и выходные файлы, структура грамматического анализатора ....................................... 4 3. Процедура построения грамматического анализатора .. 5 4. Задание входной информации yacc ................... 6 4.1. Структура спецификационного файла ............... 6 4.2. Секция правил ................................... 7 4.3. Секция деклараций ............................... 12 5. Декларация имен лексем ............................ 13 6. Декларация приоритетов и ассоциативности лексем ... 13 7. Декларация имени начального символа ............... 15 7.1. Секция программ ................................. 15 7.2. Действия с использованием псевдопеременных ...... 17 8. Конфликты грамматического разбора ................. 20 9. Структура информационного входного файла y.output .......................................... 27 10. Обработка ошибок при грамматическом ра