next up previous contents
Next: Входные спецификации Up: YACC - еще один Previous: YACC - еще один   Contents

Введение

Основой входной спецификации является набор грамматических правил. Каждое правило описывает допустимую структуру языка и дает ей имя. Например, правило может быть таким:

date : month_name day ',' year ; Здесь date, monthname, day, и year представляют собой структуры языка (нетерминалы) описанные где-то еще, а запятая, заключенная в кавычки означает, что после нетерминала day ожидается символ ',' как литера. Двоеточие и точка с запятой являются знаками пунктуации Yacc. Таким образом, строка January 1, 2000 попадает под вышеприведенное правило.

Yacc на основе входных спецификаций осуществляет синтаксический разбор текста, пользуясь при этом результатами лексического анализа, выполняемого внешней (по отношению к нему) подпрограммой, которая должна читать символы из входного потока, распознавать конструкции низкого уровня (лексемы) и передавать их на вход синтаксического анализатора, создаваемого Yacc. Традиционно конструкции, распознаваемые лексическим анализатором, называют терминальными символами, а распознаваемые синтаксическим - нетерминальными. В дальнейшем, во избежание путаницы, терминальные символы мы будем называть токенами (tokens).

Существует определенная свобода в выборе конструкций, распознаваемых лексическим и синтаксическим анализаторами, например, в предыдущем примере вполне могут быть использованы правила:

month_name : 'J' 'a' 'n' ; month_name : 'F' 'e' 'b' ; . . . month_name : 'D' 'e' 'c' ; В этом случае лексический анализатор должен только распознавать отдельные литеры, а monthname является нетерминальным символом. Но на работу с такими низкоуровневыми правилами тратится много времени и памяти, неимоверно распухают входные спецификации Yacca, поэтому обычно лексический анализатор (как более простой прием) распознает названия месяцев и выдает только признак того, что встретилось такое название. В этом случае monthname является токеном (терминальным символом). Специальные символы, такие, как в нашем примере, должны также распознавальтся лексическим анализатором.

Описание грамматики в виде правил является очень гибким, поэтому очень легко добавить к примеру правило:

date : month '/' day '/' year ; позволяющее вводить 1 / 1 / 2000, как синоним для
January 1, 2000. В большинстве случаев новое правило может быть введено в работающую систему легко и с минимальным риском испортить уже работающие правила.

Разбираемый текст может (иногда) не соответствовать спецификациям, что чвляется синонимом синтаксической ошибки. Такие ошибки обнаруживаются настолько быстро, насколько это возможно теоретически при сканировании слева направо. Частью входных спецификаций являются специальные правила обработки ошибок, позволяющие либо исправить неправильные символы, либо продолжить разбор после пропуска неправильных символов.

В некоторых случаях компилятором Yacc не удастся построить анализатор по входным спецификациям, так как либо заданная грамматика не является LALR(1), либо у Yacca не хватает мощности. Обычно эта проблема решается пересмотром системы правил, либо созданием более мощного лексического анализатора. Следует также заметить, что конструкции неподвластные Yacc, часто также непосильны и человеческому разуму...



2004-06-22