Использование UNIX для синтаксического и лексического анализа

       

Правила грамматики Yacc


В основе работы Yacc лежит определение грамматики. Грамматика оговаривает набор правил, которые формулируются для построения связанного выражения. Формат:

Цель: Тело

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

Допускается определять символьные литералы, включая их в одиночные кавычки. В качестве примера приведем лексему высшего уровня для грамматики Yacc:

grammar: declarations MARK rules tail;

MARK соответствует символу %%. Так как раздел программ не является обязательным, MARK включена в определение правила tail.

Более сложное правило поможет определить действие при поиске соответствия. Правила могут быть довольно сложными, поэтому легко совершить ошибку. Наиболее частыми ошибками являются конфликты при синтаксическом анализе методом сдвига/уменьшения. Это означает, что синтаксический анализатор не в состоянии уверенно определить, передать ли текуший блок информации конструкции с более высоким приоритетом или продолжать набирать данные в стек.

Обычно это является результатом неоднозначной, двусмысленной грамматики. Yacc по-прежнему в состоянии создать синтаксический анализатор для этой грамматики, но результаты его работы могут быть непредсказуемы.



Содержание раздела