YACC переводит спецификацию в программу на язык С, которая и обрабатывает входной поток в соответствии с заданными правилами. Алгоритм получения программы разбора по спецификации довольно сложен и здесь рассматриваться не будет. Сама же программа разбора относительно несложна, и понимание принципов ее работы хотя и не обязательно, может существенно облегчить процедуру построения функций обработки ошибок и анализ возможных неоднозначностей.
Получаемая программа разбора является стековым конечным автоматом. Также существует возможность чтения и запоминания следующей входной лексемы, называемой очередной. Текущее состояние всегда находится в вершине стека. Состояниям конечного автомата присвоены метки в виде небольших целых чисел. В начале работы автомат находится в состоянии 0 и стек содержит только метку 0; очередная лексема не прочитана. Автомат может выполнять четыре типа действий: сдвиг, свертка, ввод и ошибка. Операция программы разбора выполняется следующим образом:
1. Основываясь на текущем состоянии, программа разбора определяет, нужна ли для выполняемого действия очередная лексема. Если да, а она не прочитана, для ее ввода вызывается функция yylex.
2. Используя текущее состояние и, при необходимости, очередную лексему, программа разбора определяет следующее действие и выполняет его. Это может привести к помещению состояний в стек или их извлечению из стека, а также к обработке или обходу очередной лексемы.
Наиболее распространенным действием служит сдвиг. Для этого действия всегда нужна очередная лексема. Например, в состоянии 56 может выполняться следующее действие:

IF shift 34

Это означает, что если очередная лексема есть IF, состояние 56 заталкивается в стек, а текущим состоянием (верхушка стека) становится 34. Очередная лексема обнуляется.
Свертка нужна для ограничения роста стека. Это действие уместно при обнаружении правой части грамматического правила и подготовке к замене ее левой частью. Иногда для выяснения необходимости свертки нужно проверить очередную лексему, но чаще всего без этого можно обойтись. Фактически, действием по умолчанию (обозначаемым символом '.') обычно служит свертка.
Свертка часто связывается с отдельными грамматическими правилами. Эти правилам также присваиваются небольшие целые числа, что ведет к путанице. Действие

. reduce 18

ссылается на правило 18, а действие

IF shift 34

ссылается на состояние 34.
Предположим, что свертываемое правило выглядит следующим образом:

A: x y z;

Свертка зависит от символа в левой части (в данном случае A) и количества символов в правой части (в данном случае три). Для свертки из стека выталкиваются три состояния. (В общем случае, количество выталкиваемых состояний равно количеству символов в правой части.) Фактически, эти действия были помещены в стек при распознавании x, y и z и больше они не нужны. После этого текущим состоянием становится состояние, в котором находился распознаватель перед обработкой правила. С помощью этого состояния и символа в левой части правила выполним сдвиг A. Полученное новое состояние помещается в стек, и разбор продолжается. Однако, существуют значительные различия между обработкой символа в левой части и обычным сдвигом лексемы, поэтому это действие называется переходом. В частности, очередная лексема при сдвиге очищается, а при переходе нет. В любом случае новое состояние содержит строку вида

A goto 20

вследствие чего состояние 20 помещается в стек м становится текущим.
Фактически, свертка переводит стрелку часов распознавателя назад, выталкивая состояния из стека и приводя его к моменту первого обнаружения правой части правила. Распознаватель введет себя так, как если бы он впервые увидел левую часть правила. Если правая часть правила пуста, состояния из стека не выталкиваются, выявленное состояние становится текущим.
Свертка также существенна при обработке задаваемых пользователем значений и действий. При свертывании правила программный фрагмент, связанный с ним, выполняется перед выравниваем стека. В дополнение к стеку, содержащему состояния, существует стек, в котором содержатся значения, возвращаемые лексическим анализатором и действиями. При сдвиге ввнешняя переменная yylval копируется в стек значений. Свертка выполняется после возврата из пользовательского фрагмента. При переходе в стек значений копируется внешняя переменная yyval. К стеку значений можно обращаться по именам псевдопеременных $1, $2 и т.д.
Два других действия распознавателя значительно проще. Ввод означает, что распознана входная информация, удовлетворяющая спецификации. Это действие выполняется только если очередная лексема является конечным маркером, и означает успешное завершение работы. Действие по ошибке, напротив, сигнализирует, что распознаватель больше не может продолжать обработку спецификации. Входная лексема вместе с очередной не удовлетворяют ни одному правилу. Распознаватель сообщает об ошибке и пытается возобновить работу. Восстановление после ошибок (в отличие от их обнаружения) описано в следующем разделе. Рассмотрим следующий пример:

%token DING DONG DELL
%%
rhyme: sound place
          ;
          sound: DING DONG ; 
                           place: DELL
;

При вызове yacc с флагом -v выдается файл y.output, содержащий читаемое описание распознавателя. Ниже приведен файл, соответствующий данной грамматике:

state 0
          $accept : _rhyme $end
                                  DING  shift 3
      . error
          rhyme  goto 1        sound  goto 2
state 1
                               $accept :  rhyme_$end
          $end  accept
      . error
state 2
                               rhyme :  sound_place
          DELL  shift 5
      . error
          place  goto 4
state 3
                               sound :  DING_DONG
          DONG  shift 6
      . error
state 4
          rhyme :  sound place_    (1)
  . reduce 1
state 5
                               place :  DELL_    (3)

  . reduce 3
      state 6
                  sound :  DING DONG_    (2)
              . reduce 2

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

DING DONG DELL

Полезно рассмотреть по шагам все действия распознавателя. Первоначальное состояние 0. Для выбора действий состояния 0 распознаватель должен прочесть что-либо со входа. Читается первая лексема DING, которая становится очередной. При чтении DING в состоянии 0 выполняется действие shift 3, поэтому состояние 3 заносится в стек, и очередная лексема очищается. Следующей лексемой становится DONG. При чтении DONG в состоянии 3 выполняется действие shift 6, поэтому состояние 6 заносится в стек, и очередная лексема очищается. В стеке содержится 0,3 и 6. В состоянии 6, не обращаясь к очередной лексеме, распознаватель выполняет свертку по правилу 2.

sound: DING DONG

У правила в правой части 2 символа, поэтому состояния 6 и 3 выталкиваются из стека, выявляя состояние 0. Затем проверяется описание состояния 0 в поисках перехода по sound:

sound goto 2

При этом состояние 2 заносится в стек и становится текущим. В состоянии 2 должна быть прочитана следующая лексема DELL. Действием служит shift 5, поэтому состояние 5 заносится в стек, который теперь содержит 0,2 и 5, и очередная лексема очищается. В состоянии 5 единственным действием служит свертка по правилу 3. У него в правой части только один символ, поэтому из стека выталкивается состояние 5, открывая состояние 2. Переход в состоянии 2 на place, левую часть правила 3, дает состояние 4. Теперь стек содержит 0,2 и 4. В состоянии 4 единственное действие - свертка по правилу 1. В правой части 2 символа, поэтому выталкиваются два верхних значения, открывая состояние 0. В состоянии 0 выполняется переход по rhyme, переводя распознаватель в состояние 1. В этом состоянии при вводе обнаруживается конечный маркер, указываемый в файле с помощью $end. Выполняется действие состояния 1, и распознаватель успешно заканчивает работу.
Рекомендуется самостоятельно рассмотреть случаи некорректного ввода: DING DONG DONG, DING DONG, DING DONG DELL и пр. Потратив на анализ подобных примеров несколько минут, вы сэкономите себе время в более сложных случаях.