Мой вопрос: есть ли способ сказать бизону, что нужно обращаться с токеном как с дополнительным токеном?
Нет, нет. (Более подробное объяснение с диаграммами см. Ниже).
Тем не менее, обходной путь не так уж и страшен, как вы думаете, хотя и не без проблем.
Чтобы упростить ситуацию, яЯ собираюсь предположить, что лексер может быть убежден в том, что он производит только один токен '\n', независимо от того, сколько последовательных символов новой строки появляется в тексте программы, включая случай, когда есть комментарии, разбросанные по пустым строкам. Этого можно достичь с помощью сложного регулярного выражения, но более простой способ сделать это - использовать начальное условие для подавления токенов \n до тех пор, пока не встретится обычный токен. Начальное условие запуска лексера должно быть тем, которое подавляет токены новой строки, так что пустые строки в начале текста программы не должны ничего путать.
Теперь, ключевой момент в том, что нам не нужновставьте маркеры «возможно, новую строку» по всей грамматике, поскольку каждая новая строка должна появляться сразу после какого-то реального токена. А это значит, что мы можем просто добавить один нетерминал для каждого терминала:
tok_id: ID | ID '\n'
tok_if: "if" | "if" '\n'
tok_then: "then" | "then" '\n'
tok_else: "else" | "else" '\n'
tok_do: "do" | "do" '\n'
tok_semi: ';' | ';' '\n'
tok_dot: '.' | '.' '\n'
tok_plus: '+' | '+' '\n'
tok_dash: '-' | '-' '\n'
tok_star: '*' | '*' '\n'
tok_slash: '/' | '/' '\n'
tok_caret: '^' | '^' '\n'
tok_open: '(' | '(' '\n'
tok_close: ')' | ')' '\n'
tok_openb: '[' | '[' '\n'
tok_closeb: ']' | ']' '\n'
/* Etc. */
Теперь, это просто вопрос замены использования терминала соответствующим нетерминалом, определенным выше. (Нет w нетерминала требуется.) Как только мы сделаем это, bison сообщит о нескольких конфликтах сдвига-уменьшения в только что добавленных нетерминальных определениях;любой терминал, который может появиться в конце выражения, вызовет конфликт, так как символ новой строки может быть поглощен нетерминальной оболочкой терминала или производством expr_semicolon_list. Мы хотим, чтобы символ новой строки был частью expr_semicolon_list, поэтому нам нужно добавить объявления приоритетов, начинающиеся с символа новой строки, чтобы он имел более низкий приоритет, чем любой другой токен.
Это, скорее всего, будет работать для вашей грамматики, ноэто не на 100% уверен. Проблема с решениями, основанными на приоритетах, заключается в том, что они могут скрывать реальные конфликтные проблемы. Поэтому я бы порекомендовал запустить bison для грамматики и убедиться, что все конфликты сдвига и уменьшения появляются там, где и ожидалось (в обработчиках-оболочках), прежде чем добавлять объявления приоритетов.
Почему откат токена не так просткак это выглядит
Теоретически, было бы возможно реализовать функцию, аналогичную той, которую вы предлагаете. [Примечание 1]
Но это нетривиально, потому что алгоритм построения синтаксического анализатора LALR объединяет состояния. В результате синтаксический анализатор может «не знать», что токен предпросмотра не может быть сдвинут до тех пор, пока он не выполнит одно или несколько сокращений. Таким образом, к тому времени, когда он выясняет, что токен предпросмотра недействителен, он уже выполнил сокращения, которые должны были бы быть отменены, чтобы продолжить анализ без маркера предвкушения.
Большинство генераторов синтаксического анализатора усугубляют проблему следующим образом:удаление действий ошибки, соответствующих токену предпросмотра, если действие по умолчанию в состоянии для этого токена является сокращением. Эффект снова заключается в задержке обнаружения ошибки до одного или нескольких бесполезных сокращений, но он имеет преимущество, заключающееся в значительном уменьшении размера таблицы переходов (поскольку записи по умолчанию не нужно сохранять явно). Так как задержанная ошибка будет обнаружена до того, как будет использован какой-либо другой вход, задержка обычно считается приемлемой. (Однако у Bison есть возможность предотвратить эту оптимизацию.)
В качестве практической иллюстрации приведем очень простую грамматику выражений только с двумя операторами:
prog: expr '\n' | prog expr '\n'
expr: prod | expr '+' prod
prod: term | prod '*' term
term: ID | '(' expr ')'
, которая приводит к этой диаграмме состояний[Примечание 2]: 
Давайте предположим, что мы хотели игнорировать переводы строки в виде строки, допуская ввод
(
a + b
)
Это означает, что анализатор должен игнорироватьсимвол новой строки после b, поскольку входные данные могут быть
(
a + b
* c
)
(что хорошо в Python, но не в случае, если я правильно понимаю, в MAXScript.)
Конечно, новая строка будет распознаваться как разделитель операторов, если входные данные не были заключены в скобки:
a + b
Глядя на диаграмму состояний, мы можем видеть, что парсер окажется в состоянии 15 послеb читается независимо от того, заключено ли выражение в скобки. В этом состоянии новая строка помечается как действительный запрос для действия сокращения, поэтому будет выполнено действие сокращения, предположительно создав узел AST для суммы. Только после этого сокращения синтаксический анализатор заметит, что для новой строки нет никаких действий. Если он теперь отбрасывает символ новой строки, будет слишком поздно;теперь нет способа уменьшить b * c, чтобы сделать его операндом суммы.
Bison позволяет запрашивать синтаксический анализатор Canonical LR, который не объединяет состояния. В результате, конечный автомат становится намного больше;настолько, что Canonical-LR все еще считается непрактичным для не игрушечных грамматик. В приведенной выше простой грамматике выражения с двумя операторами запрос о синтаксическом анализаторе Canonical LR только увеличивает число состояний с 16 до 26, как показано здесь: 
В синтаксическом анализаторе Canonical LRЕсть два разных состояния для уменьшения term: term '+' prod. Состояние 16 применяется на верхнем уровне, и, таким образом, просмотр включает в себя символ новой строки, но не ) Внутри скобок парсер вместо этого достигнет состояния 26, где ) является допустимым заголовком, а символ новой строки - нет. Таким образом, по крайней мере в некоторых грамматиках использование синтаксического анализатора Canonical LR может сделать прогноз более точным. Но функции, которые зависят от использования гигантского автомата разбора, не особенно практичны.
Одной из альтернатив было бы то, что синтаксический анализатор реагировал бы на новую строку, сначала моделируя действия сокращения, чтобы увидеть, будет ли сдвиг в конечном итоге успешным,Если вы запрашиваете корректировку Lookahead (%define parse.lac full), bison вставит код, чтобы сделать именно это. Этот код может создавать значительные накладные расходы, но многие люди все равно запрашивают его, потому что он делает подробные сообщения об ошибках более точными. Поэтому, безусловно, было бы возможно переназначить этот код для обработки отката токена, но никто, на самом деле, этого не делал, насколько я знаю.
Примечания:
Подобный вопрос, который возникает время от времени, заключается в том, можете ли вы сказать зубру, чтобы он переклассифицировал токен в резервный токен, если нет возможности сместить токен. (Это было бы полезно для синтаксического анализа языков, таких как SQL, которые имеют много незарезервированных ключевых слов.)
Я сгенерировал графы состояний с помощью опции -g Bison:
bison -o ex.tab.c --report=all -g ex.y
dot -Tpng -oex.png ex.dot
Для создания Canonical LR я определил lr.type как canonical-lr:
bison -o ex_canon.c --report=all -g -Dlr.type=canonical-lr ex.y
dot -Tpng -oex_canon.png ex_canon.dot