Комбинаторика в парсере русского языка
Блог им. ASBer, 30 марта 2015

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

Функции в ТОМ2

Функции в ТОМ2 несколько специфичны — они не имеют имён, а описания аргументов служат шаблоном для подбора функции к введенной команде, или вызову в коде.
Пример описания функции:

Код:

action(осматривать#Пф, мусор#Вп){ ...code... }

Я не буду здесь глубоко вдаваться в работу функций, это отдельная большая тема.
Здесь для нас важно что функция, описанная выше, должна срабатывать на команды:
> осмотри мусор
> мусор осмотри

Перебор перестановок делается с помощью очень простого и старого алгоритма, открытого аж в 14 веке индийским математиком Пандитом Нарайаной.

Алгоритм Нарайаны

Описание и реализацию алгоритма практически на любом языке программирования можно легко нагуглить.
Вот мой вариант:

Код:

bool __fastcall token_line::NextComb(void)
{ //перебираем перестановки
  for(int m=FnLen-2; m>=0; m--)
    //найдем крайний правый m больший чем m+1
    if(operator[](Pos+m).p < operator[](Pos+m+1).p)
    { //справа от m найдём наименьший k больший чем m
      int k=m+1;
      for(int i=k+1; i<FnLen; i++)
        if( operator[](Pos+i).p > operator[](Pos+m).p &&
            operator[](Pos+i).p < operator[](Pos+k).p ) k=i;
      //переставляем m и k
      int x=operator[](Pos+m).p;
      operator[](Pos+m).p=operator[](Pos+k).p;
      operator[](Pos+k).p=x;
      //переворачиваем позиции справа от m
      m++; k=FnLen-1;
      while(m<k)
      { x=operator[](Pos+m).p;
        operator[](Pos+m++).p=operator[](Pos+k).p;
        operator[](Pos+k--).p=x;
      }
      return true;
    }

  return false; //перестановок больше нет
}

Здесь:
token_line — список токенов введенной команды, массив объектов типа token;
operator[](0) — первое слово в команде, operator[](1) — второе слов и т.д.
token_line::Pos — позиция первого слова в команде (для упрощения можно считать = 0);
token_line::FnLen — длина функции, к которой примеряется команда.
operator[](n).p — номер аргумента функции, с которым сопоставляется токен n;

Перед началом перебора индекс p всех токенов устанавливаются в начальную позицию 0,1,2...FnLen-1. Далее в цикле перебираются все варианты перестановок, каждый вариант проверяется на применимость к функции. Варианты, не прошедшие проверку, откидываются, прошедшие — обрабатываются далее.
Сама проверка довольно сложная и многоступенчатая, здесь мы её рассматривать не будем.

Всё это замечательно работает, пока не возникает необходимость в усложнении команд. Практически любая команда может иметь дополнительные обстоятельства, важные или не важные в зависимости от ситуации, сконструированной автором игры:
> возьми яблоко
> возьми яблоко со стола
> возьми яблоко левой рукой
Количество функций в этом случае растет по правилу комбинаторного взрыва, хотя делают они примерно одно и то же. Комбинаторный взрыв, это как раз то, от чего хотелось бы оградить и себя и всех авторов. Автор должен заниматься творческим трудом, а перебирать комбинации может и машина.
Все похожие варианты можно описать с помощью одной единственной функции, если в описании обозначить необязательные аргументы:

Код:

action(осматривать#Пф, мусор#Вп, [на], [пол#ПпМу]){ ...code... }

функция с таким описанием должна срабатывать на следующие команды:
> осмотри мусор
> осмотри мусор на полу
> на полу осмотри мусор
> осмотри на полу мусор
> мусор осмотри
> мусор осмотри на полу
> на полу мусор осмотри
> мусор на полу осмотри

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

Но вся прелесть алгоритма Нарайаны в том, что ему совершенно всё равно какую последовательность чисел перемешивать. С пропусками или без: 1-2-3 или 1-4-6, алгоритм в любом случае переберёт все необходимые нам перестановки.
То есть, для функции с необязательными аргументами задача сводится к формированию начальной расстановки.

Получается 2 вложенных цикла. В первом мы перебираем все возможные варианты состава аргументов функции, во втором цикле перебираем перестановки токенов по текущему варианту аргументов функции.

Код

Методы первого цикла:

Код:

void __fastcall fn_it::FirstComb(void)
{ //подготовим карту аргументов
  BitMap = 1 << Fn.GetCount();
  BitMap--;
}

bool __fastcall fn_it::NextComb(void)
{ //получим следующий вариант расстановки аргументов
  unsigned int Flag = 1 << (Fn.GetCount()-1);
  for(int i=Fn.GetCount()-1; i>=0; i--)
  { if(!Fn[i].Required)
    { if(BitMap&Flag)
      { BitMap^=Flag;
        return true;
      }
      else BitMap|=Flag;
    }
    Flag>>=1;
  }

  return false;
}

Здесь:
fn_it — объект для подбора функций;
fn_it::BitMap — карта расстановки аргументов. Каждый бит соответствует аргументу с тем же номером;
fn_it::Fn — массив аргументов функции;
fn_it::Fn[n] — n-ый аргумент;
fn_it::Fn[i].Required — флаг обязательности аргумента.

Методы второго цикла:

Код:

bool __fastcall token_line::FirstComb(unsigned int BitMap)
{ //BitMap - карта расстановки аргументов по позициям
  //расставляем токены на исходную позицию
  int p=-1, t=-1;
  for(; BitMap; BitMap>>=1) //цикл по карте
  { p++;
    if(!(BitMap&1)) continue; //пропускаем позицию

    t++;
    if(Pos+t>=GetCount()) return false; //вышли за пределы выражения
    token&Token=operator[](Pos+t); //текущий токен
    if(Token.GetCount()==0) return false; //нет значений

    Token.p = p; //назначаем токену начальную позицию в функции
  }
  FnLen = t+1; //запомним длину обрабатываемой функции
  return true;
}

Здесь:
token_line — список токенов введенной команды, массив объектов типа token;
token_line::Pos — позиция первого слова в команде (для упрощения можно считать = 0);
token_line::FnLen — длина функции, к которой примеряется команда.
Token.p — номер аргумента функции, с которым сопоставляется токен;

Метод token_line::NextComb(void) остаётся без изменений, см. код выше.

Ну и сами циклы в упрощенном виде выглядят так:

Код:

for(int f=Fns.GetCount()-1; f>=0; f--) //цикл по списку функций
{
    Fns[f].FirstComb();
    do //цикл по аргументам
    {

      if(Tokens.FirstComb(Fns[f].BitMap)) do //цикл по перестановкам
      {
             ... проверка ....

             ... обработка ....
  
      }while(Tokens.NextComb()); //цикл по перестановкам

    }while(Fns[f].NextComb()); //цикл по аргументам

    ... отбраковка функций ...

} //цикл по списку функций

Здесь:
Fns — список функций, массив объектов класса fn_it.

Надеюсь, данная статья будет интересна тем, кто вплотную занимается парсерами.

P.S. поддержка необязательных аргументов функций появятся на платформе ТОМ2 в следующей версии 2.a.4.3
Следите за обновлениями.