LINUX.ORG.RU

Syntax-aware autocomplete

 ,


1

2

Допустим, у нас есть лексер и грамматика некоего DSL. Мы хотим сделать хорошую интерактивную среду, как у «взрослых»: чтобы аргументы у функций предлагались, исходя из контекста.

То есть, если есть правило

let_stmnt:
  TOK_LET TOK_IDENTIFIER TOK_ASSIGN expr;
то хотелось бы, чтобы нажатие на <TAB> при нахождении в месте ввода идентификатора понимало, что сейчас мы хотим предложить автокомплит по известным именам переменных.

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

let_stmnt:
  TOK_LET variable TOK_ASSIGN expr;

variable:
  TOK_IDENTIFIER { add_completion(COML_VAR, @$); }
Где add_completion добавляет в список возможных вариантов дополнений, что в таких-то позициях строки можно дополнять имя переменной. По мне, так выглядит как-то очень костыльно, ведь чем удобнее захочется сделать грамматику, тем больше правил будут давать «мусорные» варианты дополнения.

В процессе гугления находил только рекомендации использовать push parser для такого, но без конкретики или примеров.

Ну и вообще, для «дружественного DSL» хотелось бы более понятных сообщений об ошибке, нежели «expected expr», ведь из частично заматчившихся правил можно сузить набор возможных на данной позиции лексем.

Имхо

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

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

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

anonymous ()
Ответ на: Имхо от anonymous

В том-то и дело, что я хочу (уже использую) готовый 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-е?

kawaii_neko ★★★ ()

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

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

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

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

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

$ make

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

$ ./calc

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

$ ./calc --tty

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

anonymous ()
Ответ на: комментарий от kawaii_neko

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

(0)SELECT (1)field(2), (3)field (4)FROM (5)table
В позиции (0) нужно предлагать допустимые ключевые слова, в позиции (1) — «*» или все подряд имена полей (для простоты можно считать, что имена столбцов не зависят от указанной позже таблицы); в позиции (2) можно предложить «FROM», а вот в позиции (3) после запятой — имя поля. В (5) — предлагать таблицы.

kawaii_neko ★★★ ()
Ответ на: комментарий от kawaii_neko

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

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

anonymous ()
Ответ на: комментарий от anonymous

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

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

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

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

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

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

kawaii_neko ★★★ ()
Ответ на: комментарий от kawaii_neko

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

Вот хорошая статья, объясняющая, как сгенерированные бизоном парсеры устроены. Бизон хранит данные в очень сжатой и поэтому непонятной форме, но если немного разобраться и оттрейсить 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
        }
    }
}
anonymous ()
Ответ на: комментарий от kawaii_neko

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

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

anonymous ()

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

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

vmx ★★ ()
Ответ на: комментарий от vmx

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

kawaii_neko ★★★ ()
Ответ на: комментарий от kawaii_neko

смена связки 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]);
    }
  }
}
vmx ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.