Имхо

Не надо портить грамматику, надо хачить парсер. Если сам пишешь LL-парсер, то на каждой ветке, которая дошла до курсора, дочерние узлы текущего узла - это возможные следующие токены. Загоняешь их в список, предлагаешь пользователю.

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

Про push parser, видимо, то же самое, только предлагается эту логику держать в обработчике события (типа on_cursor), а сам парсер не трогать.

В том-то и дело, что я хочу (уже использую) готовый bison и хачить его как-то опасаюсь.

Самая большая моя проблема: я не могу получить возможные варианты для «еще незавершенной лексемы» или незаматчившейся лексемы: если рассматривать, например, SQL, то select очень примитивно можно описать так:

select:
  TOK_SELECT {compl_candidats(COMPL_FIELDS, @$);}
      fields {compl_string_candidat("from", @$);}
    TOK_FROM {compl_candidats(COMPL_TABLES, @$);}
      tables where_clause;
fields:
    ASTERISK
  | TOK_IDENTIFIER
  | TOK_IDENTIFIER COMMA fields;

tables:
    TOK_IDENTIFIER
  | TOK_IDENTIFIER COMMA tables;

where_clause: ...

Здесь compl_candidats говорит, что «начиная с позиции @$ можно предлагать такие-то варианты дополнения». Беда в том, что я не знаю, как совместить такие хинты из разных частей правил. Ну и ко всему прочему в грамматике получается просто охренительно много мусора.

То есть, вся моя проблема сводится к тому, что парсер-то знает, какие токены он ожидает увидеть в следующий момент, а я эту информацию из него никак вытянуть не могу. Или я просто чего-то не знаю о bison-е?

Просто усложнить грамматику не поможет: с такой грамматикой IDE будет предлагать автокомплит до посинения на каждый несчастный идентификатор вместо того чтоб скомпилировать наконец код (или понадобятся хитрые эвристики, когда предлагать, а когда нет). Автокомплит должен происходить по какому-то событию: TAB, пользователь задумался, etc. При этом парсер должен получать на вход часть кода (до курсора). Как сделать, чтоб парсер остановился на курсоре — дело вкуса: вставить туда error и обработать ошибку, вставить eof и использовать push парсер, следить за сонным пользователем из лексера и в нужный момент подсовывать спецсимвол autocomplete (потребует добавки правила в грамматику).

Методы можно поделить по степени взаимодействия с кишками парсера:

• изменение состояния парсера извне грубой силой: надо чтоб кишки были доступны, сложно, очень гибко (можно исследовать стек и т.д.)
• изменение состояния официальными средствами парсерогенераторов
• подстраивание грамматики и лексера под ситуацию

Хороший, простой, понятный пример push парсера (взят из этого треда).

Собирать так:

$ make

Запускать так (графический UI):

$ ./calc

Или так (консольный UI):

$ ./calc --tty

На нём удобно побаловаться: попробовать расковырять состояние парсера в момент прерывания (конкретно bison мало что говорит о своих кишках), повставлять местами error и т.п.

Вообще, я б сначала определилась, что именно надо автодополнять: для лексем (в т.ч. идентификаторов) парсер прерывать не нужно, достаточно просто из лексера заглянуть в таблицу символов. Если всё же прерывать парсер, то есть два варианта: или просто предлагать один из lookahead символов (как слово «from» в твоём примере), или предлагать пустой шаблон какой-нибудь синтаксической конструкции (например по слову «try» предлагать пустой блок «try/catch»).

Последние два варианта (с парсером) bison в чистом виде не даст сделать. Но должно быть не сложно и интересно написать к нему какой плагин, чтоб на некоторые состояние парсер хранил варианты автокомплита.

что именно надо автодополнять

Предопределенные лексемы «по месту». Для примера с SELECT:

(0)SELECT (1)field(2), (3)field (4)FROM (5)table

Получается, ты хочешь привязать действия не ко всему правилу, а к его частям. У бизона есть mid-rule actions для этого, но учти, что это синтаксический сахар, транслирующийся в обычные правила (добавленные правила повышают вероятность конфликтов).

По-моему, такой подход странноват: парсер точно знает, какой lookahead он ожидает в каждом shift-состоянии. А ты хочешь наваять костылей, чтоб самому с горем пополам предсказывать этот lookahead. Куда лучше пропатчить парсерогенератор, чтоб парсер позволял его получить.

парсер точно знает, какой lookahead он ожидает в каждом shift-состоянии

Беда как раз в том, что я не знаю, как из него извлечь эту информацию.

А ты хочешь наваять костылей, чтоб самому с горем пополам предсказывать этот lookahead

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

Куда лучше пропатчить парсерогенератор, чтоб парсер позволял его получить.

Конечно лучше, но это крайне нетривиально.

Беда как раз в том, что я не знаю, как из него извлечь эту информацию.

Вот хорошая статья, объясняющая, как сгенерированные бизоном парсеры устроены. Бизон хранит данные в очень сжатой и поэтому непонятной форме, но если немного разобраться и оттрейсить yyparse (или yypush_parse), то все нужные данные можно декодировать (сгенерированный парсер содержит в себе таблицы и никто не мешает в них ковыряться).

Понятно, что это несерьёзное решение (нельзя полагаться на bison internals), но способствует пониманию.

Для примера вот кусок кода (построенный на основе yyparse), позволяющий для состояния yystate и символа yychar определить, допустим ли shift. (Внимание, это не то же самое, что все допустимые lookahead символы: код не определяет символы, требующие дополнительных редукций и переходов в новое состояние.)

int yyn = yypact[yystate];
if (!yypact_value_is_default (yyn))
{
    int yytoken = YYTRANSLATE (yychar);
    yyn += yytoken;
    if (!(yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken))
    {
        yyn = yytable[yyn];
        if (yyn > 0)
        {
            ... // valid lookahead symbol
        }
    }
}

Конечно лучше, но это крайне нетривиально.

Да, но если ты хочешь «как у взрослых», то оно и будет нетривиально. Кстати, по-моему, написать/пропатчить парсерогенератор куда проще, чем написать парсер какого-нибудь C++.

bison же вроде умеет печатать «expected tokens»? Наверное, есть способ получить их в обработчике ошибки.

Я с бизоном мало сталкивался, вот в lemon можно сделать приблизительно так. Вводим псевдотокен AUTO_COMPLETE. И нигде в грамматике его не используем. Когда нужно получить дополнение, даем парсеру токены с AUTO_COMPLETE в конце, чтоб получить ошибку разбора. В обработчике ошибки смотрим какие ожидались токены (для lemon это довольно просто http://stackoverflow.com/a/13010096 ). Ну и собственно дополняем.

Интересно. А смена связки flex/bison на flex/lemon требует серьезного перелопачивания кода?

смена связки flex/bison на flex/lemon требует серьезного перелопачивания кода?

Да они в общем похожи. Но я описывал общую технику, в bison можно делать почти так же. Ну, с небольшим трюком.

В обработчик ошибки bison не передает состояние парсера, его можно передать небольшим шаманством с макросом:

В первой секции

%{
/* ... */
#define  YYERROR_VERBOSE 1 /* для отладки */
#define yyerror(MSG) yyerror_wstate(MSG, yystate)
void yyerror_wstate(char *msg, int yystate);
%}

И наша расширенная функция (проверять, ошибка это или автокомплит можно по последнему токену, yytoken)

/* Called by yyparse on error */
void yyerror_wstate(char *msg, int yystate)
{
  int yyx;
  int yytoken;
  int yyn = yypact[yystate];
  int yyxbegin = yyn < 0 ? -yyn : 0;
  int yychecklim = YYLAST - yyn + 1;
  int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;

  printf("bison error: %s\n\n", msg);

  yytoken = YYTRANSLATE (yychar);
  printf("error near token %s\n", yytname[yytoken]);

  for (yyx = yyxbegin; yyx < yyxend; ++yyx) {
    if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR) {
      /* expected tokens */
      printf("expected %s\n", yytname[yyx]);
    }
  }
}