Сжатие таблицы перехода «Next + check», также называемое алгоритмом гребенки, описано в книге Dragon относительно лексеров в Разделе 3.9 с примечанием в главе 4 об его использовании с таблицами синтаксического анализатора.
Алгоритм хранит разреженную матрицу путем наложения строк так, чтобы действительные записи перекрывались только с отсутствующими записями. Для поиска значения в сжатой таблице необходим вектор начального индекса для каждой строки. Затем вы добавляете номер столбца, который вы ищете, к этому начальному индексу. Наконец, вам нужно знать, соответствует ли запись строке, в которой вы смотрите; вектор check содержит номер строки, для которой действительна каждая запись таблицы.
Это называется компрессией гребня из-за идеи, что каждая строка похожа на гребень со многими сломанными зубцами.
В каркасе парсера этот код (или что-то похожее на него) будет использоваться для определения действия парсера, соответствующего токену. Возможные ответы:
Сдвиньте токен и go в состояние S. (Pu sh токен в стек и прочитайте новый взгляд вперед).
Уменьшите стек, используя производственный номер P. (Снимите правую часть со стека, выполните действие сокращения, go до состояния, найденного путем обращения к таблице GOTO из состояния, выявленного pop и номер сокращенного нетерминала, pu sh сокращенного нетерминала в стек, а затем продолжить с тем же маркером предварительного просмотра.)
Сигнализировать об ошибке.
Подтвердите ввод. (Только если жетон предпросмотра является маркером конца ввода. Эта возможность часто имеет особый случай.)
Полагаю, вы правы в том, что они являются отдельными сдвигами и сокращают таблицы действий. , Возможно, что строки будут перекрываться лучше, если вы сжимаете действия по отдельности, хотя сжатие должно было бы быть намного лучше, чтобы компенсировать дополнительный проверочный массив.
Учитывая, что код используется для построения списка завершения, Я предполагаю, что он используется в симуляции анализа для каждого возможного следующего токена, чтобы решить, каковы действительные кандидаты в следующий токен. Оператор возвращает true, если с токеном можно воздействовать (если нет, кандидата можно просто удалить из списка завершения), и устанавливает yyn для следующего действия. Необходимо будет различать guish между действиями Shift и Reduce. В некоторых средах синтаксического анализа знак действия используется для этой цели, но есть и другие возможности.
Поэтому я бы назвал функцию find_parse_action (или find_parse_action_if_any, если вам нравятся более громкие имена).
Обратите внимание, что в синтаксическом анализаторе LALR симуляция должна будет итеративно применять действия сокращения, поскольку приемлемость токена не известна до тех пор, пока не произойдет действие сдвига. Имитация сокращений включает выталкивание стека, что было бы разрушительным, если применить его к реальному стеку синтаксического анализатора. Таким образом, часть кода, вероятно, создает и управляет имитируемым стеком. (Хотя также возможно, что bya cc использует стек спагетти. На самом деле я никогда не смотрел на его скелет.)
Bison использует подобный код для реализации "Исправления Lookahead" (LA C), которое используется для создания более информативных сообщений об ошибках. («Ожидается X или Y или Z», что является еще одним действием в списке завершения.) Таким образом, вы можете увидеть другой возможный метод реализации в скелете Bison. IIR C, он создает копию стека для имитации всплывающих окон.