Отталкивание токенов в Happy и Alex

Я разбираю язык, в котором есть как <, так и <<. В моем определении Алекса у меня есть что-то, что содержит что-то вроде

tokens :-

"<"             { token Lt }
"<<"            { token (BinOp Shl) }

поэтому всякий раз, когда я сталкиваюсь с <<, это обозначается как сдвиг влево, а не как сдвиг меньше. Обычно это хорошо, так как после токенизации я выбрасываю пробелы и хочу различать 1 < < 2 и 1 << 2. Однако бывают и другие случаи, когда мне хотелось бы, чтобы << читалось как два <. Например, у меня есть такие вещи, как

<<A>::B>

который я хочу читать как

< < A > :: B >

Очевидно, я могу попытаться настроить правила синтаксического анализатора Happy, чтобы учесть дополнительные случаи, но это плохо масштабируется. В других генераторах императивных синтаксических анализаторов я мог бы попытаться сделать что-то вроде отодвигания «части» токена (что-то вроде push_back("<"), когда я столкнулся с <<, но мне нужно было только <).

Была ли у кого-нибудь еще такая проблема, и если да, то как вы с ней боролись? Есть ли способы «отталкивания» жетонов в Happy? Должен ли я вместо этого попытаться сохранить токен пробела (на самом деле я склоняюсь к последнему варианту - хотя это огромная головная боль, это позволило бы мне справиться с <<, просто убедившись, что между двумя < нет пробела).


haskell happy ghc
person Alec    schedule 10.11.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Я не знаю, как это выразить в Happy, но вам не нужен отдельный токен «пробел». Вы можете проанализировать < или > как отдельный токен «угловой скобки», если сразу за ним следует символ оператора во входных данных, без промежуточных пробелов.

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

Таким образом, a << b будет токенизирован как:

identifier "a"
left angle      -- joined with following operator
operator "<"
identifier "b"

При синтаксическом анализе оператора вы объединяете токены угла со следующим токеном оператора, создавая один токен operator "<<".

<<A>::B> будет токенизирован как:

left angle
operator "<"    -- accepted as bracket
identifier "A"
right angle
operator "::"
identifier "B"
operator ">"    -- accepted as bracket

При анализе терминов, заключенных в угловые скобки, вы принимаете как угловые токены, так и операторы </>.

Это зависит от того, что ваша грамматика не является двусмысленной. следует ли вам анализировать имя оператора или что-то в квадратных скобках.

person Jon Purdy    schedule 10.11.2016
comment
Умная идея! Хотя мне пока не удалось найти способ получить два токена от Алекса, я вижу, как это будет работать. Спасибо! - person Alec; 13.11.2016
comment
@Alec: Да, я когда-либо использовал эту технику только в Parsec, где у вас есть предварительный просмотр (например, try (Operator <$> char '<' <* notFollowedBy symbol) <|> LeftAngle <$> char '<'), но это невозможно выразить напрямую в Alex. Вероятно, вы могли бы как-то закодировать его без просмотра вперед. - person Jon Purdy; 13.11.2016

arrow_upward
0
arrow_downward

Хотя я изначально согласился с ответом @Jon, в итоге я столкнулся с множеством проблем, связанных с приоритетом (подумайте о приоритете вокруг expr < expr против expr << expr), которые вызвали у меня много головной боли. Недавно я (успешно) вернулся к использованию << в качестве одного токена. Решение было двояким:

  1. Я укусил пулю и добавил дополнительные правила для << (где раньше у меня были только правила для <). Например, в вопросе (<<A>::B>) мое правило исходило из чего-то вроде

    ty_qual_path
  : '<' ty_sum '>' '::' ident

    to

    ty_qual_path
  : '<' ty_sum '>' '::' ident
  | '<<' ty_sum '>' '::' ident '>' '::' ident

    (На самом деле правило было немного сложнее, но это не для этого ответа).

  2. Я нашел умный способ справиться с токеном, начинающимся с > (это вызовет проблемы с такими вещами, как vector<i32,vector<i32>>, где последний >> был токеном): используйте поточный лексер (раздел 2.5.2), используйте {%% ... } RHS правил, которые позволяют вам пересматривать упреждающий токен, и добавьте pushToken средство для моя монада парсера (это оказалось быть довольно простым - именно это я и сделал). Затем я добавил фиктивное правило - что-то вроде

    gt :: { () }
  : {- empty -}   {%% \tok ->
      case tok of
        Tok ">>"  -> pushToken (Tok ">")  *> pushToken (Tok ">")
        Tok ">="  -> pushToken (Tok "=")  *> pushToken (Tok ">")
        Tok ">>=" -> pushToken (Tok ">=") *> pushToken (Tok ">")
        _         -> pushToken tok
    }

    И каждый раз, когда в каком-то другом правиле я ожидал >, но также мог быть любой другой токен, начинающийся с >, я ставил перед токеном > gt. Это имеет эффект просмотра следующего токена, который может начинаться с >, но не быть >, и попытки преобразовать этот токен в один токен > и другой токен для «остатка» исходного токена.

person Alec    schedule 09.03.2017