Правила yacc

Раздел правил файла грамматики содержит одно или несколько грамматических правил. Каждое правило описывает структуру и присваивает ей имя.

Грамматические правила задаются в следующем виде: 
A : ТЕКСТ;

Здесь A - нетерминальное имя, а ТЕКСТ - последовательность из 0 или более имен, литералов и семантических действий, после которых могут следовать правила приоритета. Для описания грамматики необходимы только имена и литералы. Семантические действия и правила приоритетов необязательны. Двоеточие и точки запятой должны быть указаны в определениях правил yacc обязательно.

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

Правила приоритетов определяются ключевым словом %prec и изменяют приоритет соответствующего правила грамматики. Зарезервированное слово %prec может располагаться непосредственно после текста грамматического правила, в нем может указываться имя лексемы или литерал. При использовании такой конструкции приоритет правила становится равным приоритету имени лексемы или литерала.

Повторение нетерминальных имен

Если нетерминальное имя применяется в нескольких грамматических правилах, то эти правила можно объединить в одно с помощью символа | (символ конвейера). В этом случае символ ; (точка с запятой) ставится в конце набора объединенных правил. Например, следующие грамматические правила: 
A  :  B  C  D  ;
A  :  E  F  ;
A  :  G  ;
могут быть описаны в программе yacc следующим образом: 
A  :  B  C  D
   |  E  F
   |  G
   ;

Использование рекурсии в файле грамматики

Рекурсия позволяет определять функцию через себя саму. В определении языков такие правила обычно имеют следующую форму: 

правило    :        КонечноеУсловие
        | rule EndCase

Таким образом, в простейшем варианте правило соответствует значению КонечноеУсловие, но при этом правило может содержать произвольное число повторений значения КонечноеУсловие. Вторая строка, использующая правило внутри описания конструкции правило, применяет рекурсию. Анализатор последовательно обрабатывает входной поток, пока он не сократится до единственного значения КонечноеУсловие.

Если в правиле используется рекурсия, то имя правила всегда должно быть самым левым в теле правила (как в предыдущем примере). Если оно не будет первым, как в следующем примере, то может возникнуть переполнение стека, в результате чего анализатор прервет работу. 
правило    :        КонечноеУсловие
        | EndCase rule

Приведенный ниже пример определяет правило line (строка) как произвольную комбинацию элементов string (текст), завершающуюся символом новой строки (\n):

lines   :        line
        |        lines line
        ;

line    :        string '\n'
        ;

Пустая строка

Для обозначения нетерминального символа, соответствующего пустой строке, используйте в качестве тела правила одиночный символ ; (точка с запятой). Для определения правила empty, соответствующего пустой строке, используйте правило, аналогичное следующему: 
empty   :  ;
        | x;
ИЛИ 
empty   :
        | x
        ;

Маркер конца ввода

Когда лексический анализатор достигает конца входного потока, он передает синтаксическому анализатору маркер конца ввода. Этот маркер является специальной лексемой со значением 0, называемой маркером конца. Когда синтаксический анализатор получает маркер конца, он проверяет, для всех ли входных данных были выбраны правила грамматики и образует ли обработанная информация законченный блок (в соответствии с правилами файла грамматики yacc). Если образован законченный блок, анализатор завершает работу. Если блок не образован, анализатор передает сообщение об ошибке и также завершает работу.

Лексический анализатор должен передавать маркер конца в некоторый обоснованный момент - например, по достижении конца файла или конца записи.