[ Содержание ] [ Предыдущая ] [ Следующая ]
Yacc обеспечивает общее средство для придания структуры входным данным компьютерных программ. Пользователь Yacc-а готовит спецификацию процесса ввода; она включает в себя правила, описывающие структуру входных данных, код, вызываемый, когда распознаны эти правила, и низкоуровневая процедура для простого ввода. Затем Yacc генерирует функцию, контролирующую процесс ввода
Эта функция, называемая синтаксическим анализатором, вызывает пользовательскую низкоуровневую процедуру простого ввода (лексический анализатор) для извлекания элементарных токенов из входного потока. Эти токены организованы в соответсвии с правилами структур входных данных, называемых грамматическими правилами; когда одно из этих правил распознается, вызывается пользовательский код для этого правила, или действие; действия способны возвращать значения и использовать значения других действий.
Yacc написан на переносимом диалекте C1 и акции и выходные подпрограммы также на C. Больее того, многие синтаксические соглашения Yacc-а вытекают из C.
Сердцем спецификаций ввода является коллекция грамматических правил. Каждое правило описывает допустимую структуру и дает ей имя. Hапример, грамматическое правило может выглядеть так:
date : month_name day ',' year;
Здесь date, month_name, day и year представляют собой структуры, of interest для процесса ввода; предположительно month_name, day и year определены где-либо еще. Запятая "," заключена в одиночные кавычки; это значит, что кавычки должны появиться в тексте буквально. Двоеточие и точка с запятой служат просто как знаки препинания в правиле и не имеют никакого значения при контроле входных данных. Таким образом, при должных определениях ввод
July 4, 1776
будет соответствовать вышеуказанному правилу.
Важная часть процесса ввода выполняется лексическим анализатором. Процедура пользователя читает входной поток, распознает структуры низкого уровня и передает эти токены парсеру. По историческим причинам структуры, распознаваемые парсером называются нетерминальным символом. Во избежание недоразумений терминальные символы обычно будут называться токенами.
При принятии решения, распознавать ли структуры используя лексический анализатор или грамматические правила, нет слишком большой свободы действий. Hапример, в вышеприведенном примере могут использоваться следующие правила:
month_name : 'J' 'a' 'n';
month_name : 'F' 'e' 'b';
. . .
month_name : 'D' 'e' 'c';
Лексическому анализатору надо будет распознать только отдельные буквы, и month_name будет нетерминальным символом. Такие низкоуровневые правила ведут к потере времени и места и могут настолько усложнить спецификации, что Yacc не сможет с ними справиться. Обычно лексический анализатор распознает названия месяцев и возвращает признак того, что найден month_name; в этом случае month_name будет токеном.
Литеральные символы, такие как "," также должны проходить через лексический анализатор и также считаются токенами.
Файлы спецификации очень гибки. Относительно просто добавить к вышеприведенному примеру правило
date : month '/' day '/' year;
позволяющее
7 / 4 / 1776
в качестве синонима к
July 4, 1776
В большинстве случаев это новое правило может быть легко вставлено в работающую систему с минимальными усилиями и незначительной опасностью разрушения существующих входных данных.
Входные данные могут не соответствовать спецификациям. Эти ошибки данных определяются настолько рано, насколько возможно при чтении слева-направо; таким образом, не только в значительной степени понижается вероятность чтения и работы с неправильными данными, но и плохие данные могут быть быстро обнаружены. Обработка ошибок, обеспечиваемая как часть спецификаций входных данных, позволяет повторный ввод неправильных данных или продолжение процесса ввода после пропуска неверных данных.
В некоторых случаях Yacc отказывается генерировать парсер с некоторыми наборами спецификаций. Hапример, спецификации могут быть противоречивыми, или могут требовать более мощного механизма распознавания, чем тот, что доступен Yacc-y. Первый случай означает ошибки при проектировании; случаи второго типа часто могут быть скорректированы при помощи более лексического анализатора или с помощью переписывания некоторых грамматических правил. Тогда как Yacc не может обрабатывать все возможные спецификации, сравнение с аналогичными системами в пользу Yacc-а; более того, конструкции, которые сложны для обработки Yaccом часто сложны также и для людей. Hекоторые пользователи сообщали, что дисциплина формулирования верных спецификаций Yacc-а для их входных данных открывал ошибки в концепции или разработке на ранней стадии разработки.
Теория, лежащая в основе Yacc-а описана в других источниках [2] [3] [4] Yacc широко применялся в многочисленных практических приложениях, включая lint, [5] Переносимый Компилятор C6 и систему для математического типографского набора [7]
[ Содержание ] [ Предыдущая ] [ Следующая ]
| c 1998-2000 SoloTony (Antonio Solo) | solotony@mail.ru |