Forum.iFiction.Ru

iFiction.Ru · ifHub · FAQ · IFWiki · QSP · URQ · INSTEAD · AXMA

форум об interactive fiction, текстовых приключенческих играх и всём таком...

Вы не зашли.

0    0    #1
05.10.2004 07:02

Алексей
Гость

Мысли о парсерах

   Читая материалы, посвещенные разработке адвентюрных игр (или как их тут называют IF), мне постоянно попадаются одинаковые жалобы на недостатки русскоязычных парсеров.  Именно русскоязычных, потому как именно в русском языке сложная система родоых и числовых окончаний, произвольное расположение подлежащего и сказуемого и еще некоторые вещи, не свойственные английскому.
    Это наталкнуло на некоторые мысли по поводу. Поскольку я профессиональный программист (правда не под персоналки - но это не важно), то именно с этой точки зрения постараюсь взглянуть на проблему.

    Итак, пусть нам дано некоторое предложение (которое ввел пользователь):
    "Быстро иди по дороге на север и затем на  восток, подойти к старику и сказать ему "Здравствуй". "
    Пусть программе известны следующие слова:
    - иди
    - север, юг, восток, запад
    - подойди
    - старик
    - сказать
    - здравствуй
    - ему, ей, его, ее
   Я пока нарочно не останавливаюсь на падеже-роде-числе. Об этом позже.
    Как по моему мнению должен работать парсер ? Очень просто. Прежде всего, надо преобразовать исходное предложение в несколько простых предложений, состоящее только из известных программе слов.
    Правила просты. Запятая - конец простого предложения. Связка "и" - требует особой обработки. Слова "ему", "ей", "его", "ее" заменяются на последнее встреченное существительное. Неизвестные слова - выбрасываются.
    Таким образом, получим:

     Исходное: "Быстро иди по дороге на север и затем на  восток, подойти к старику и сказать ему "Здравствуй". "
     
     Выходные :
1. идти север и восток
2. подойти старику и сказать старику "здравствуй"
 
     Далее в этих предложениях надо обработать связки "и". Правила так же не сложны.
- Правило 1. Если слова, стоящие непосредственно перед "и"  и непосредственно после - входит в список существительных - надо перед словом, стоящим после "и" повторить глагол, стоящий перед словом, стоящим непосредственно перед "и". Часть предложения до "и" сохраняем в новое предложение как есть. А часть после "и" сохраняем в новое предложение с добавлением глагола.
    То есть: "идти север и восток" преобразуется в два простых
  1а."идти север".
  1б."идти восток".

- Правило 2. Если слово, стоящее непосредственно перед "и" - входит в список существительных, а слово, стоящее непосредственно после "и" - в список глаголов, то связка "и" играет ту же роль, что и запятая, связывая два предложения.
    Тоесть "подойти старику и сказать "здравствуй" " преобразуется в два простых предложения:
    2.а "подойти старику"
    2.б "сказать старику "здравствуй" "

Итак, из исходного предложения мы получили 4 более простых, которые соответствуют шаблону "[действие] [объект]".

Исходное: "Быстро иди по дороге на север и затем на  восток, подойти к старику и сказать ему "Здравствуй". "

Получили:
  1а."идти север".
  1б."идти восток".
  2.а "подойти старику"
  2.б "сказать старику "здравствуй" "

Теперь эти элементарные действия надо просто по порядку выполнить. Результат выполнения будет зависить от конкретной програмы. Если какоето из действий выполнить невозможно, то последующие за ним действия так же не выполняются. Скажем вы успешно можете выполнить 1а и 1б, но не можете сделать почему-либо 2а. В этом случае и 2б выполнять не надо.

Теперь о родах, падежах. Надо сравнивать слова не по первым 4-5 буквам, а с шаблонами. Что такое шаблон - всем хорошо известно. Скажем шаблон для слова "старик" будет выглядеть примерно так:
  старик[а|у|ом]. Что это значит ? Квадратные скобки говорят, что то, что в них написано - необязательно, может отсутствовать. Черта "|" - разделитель того, что может присутствовать в квадратных скобках. Т.е под описанный шаблон подойдут слова:
  "старик", "старика", "старику", "стариком". - для программы это должно быть одно и то же слово.
  Еще один пример шаблона:
  [по]смотр<и|еть>  - Скобки <> означают, что окончание обязательно есть, а варианты разделены чертой "|".
Под этот шаблон подойдут слова: "смотреть","посмотреть", "смотри", "посмотри".

Подобная шаблонная организация сравнений слов - один из способов понять пользователя. Несомненно, все что я тут написал усложнит парсер. Но ничего нереализуемого тут нет.
Критику и предложения-замечания - пишите...

0    0    #2
05.10.2004 11:55

GrAndrey
папа RTADS и Бяка (+49, -2)
Откуда: Москва
Зарегистрирован: 15.09.2002
Сообщений: 1198
Вебсайт

меньше слов

Re: Мысли о парсерах

Спасибо. Ты все правильно написал. Все тобою предложенное уже используется или в русской версии ТАДС, или Информ.
Наречия (быстро) - хотя потенциально и поддерживаются, но не рекомендуются в связи с их бесполезностью. "Идти по дороге" - тоже лишняя морока для игрока и автора. Проще объяснить, что дорога идет на север, но если програма будет понимать и эту фразу - это только плюс.
Вообще, главная проблема русского IF сегодня - недостаток активных авторов, а не технические трудности.

Неактивен

0    0    #3
05.10.2004 12:06

Olegus t.Gl.
Участник (+1053, -249)
Откуда: Москва
Зарегистрирован: 01.03.2001
Сообщений: 2879
Вебсайт

Re: Мысли о парсерах

Разумно, вот только не рассмотрен вопрос о командах, подразумевающих большее число членов, чем действие и объект. Взять ту же "сказать старику "здравствуй". Даже если автор получает команду по "расчленённым" кускам, остаётся весьма важный вопрос: а как эти куски ему обрабатывать?..

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

Неактивен

0    0    #4
03.04.2005 15:44

Gray_Flannel_Armor
Участник
Зарегистрирован: 26.01.2004
Сообщений: 45

Кто хочет найти зло - найдет его. Авраам Линкольн.

Re: Мысли о парсерах

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

Что такое конечный автомат? Это по сути набор состояний с переходами. Переход из состояния в состояние осуществляется под воздействием входного сигнала, положим символа или части речи.

Например, состояние 0 - начальное. Если на вход поступает глагол, то переход в состояние 1, если что-либо другое - переход в ошибочное состояние. Состояние 1 фиксирует глагол в какой-либо переменной, ошибочное состояние выводит что-нибудь типа "первым должен идти глагол". Далее, в состоянии 1 может поступить предлог (переход в состояние 2) или существительное (переход в состояние 3), при этом из состояния 2 в 3 переход осуществляется по существительному. Конец ввода пользователя - это тоже входной сигнал, который может привести в зависимости от состояния в ошибочное состояние (если, допустим, ввод закончился на предлоге) или в состояние, когда инициируется обработка ввода.

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

Собственно говоря, такая система используется в платформе "6 дней". Вышло что-то около 7 или 8 состояний, при этом парсер был написан буквально за 3 дня (в конечном варианте) с возможностью воспринимать конструкции типа "взять зеленое и красное яблоки и положить их на стол"

Неактивен

0    0    #5
03.04.2005 18:45

GrAndrey
папа RTADS и Бяка (+49, -2)
Откуда: Москва
Зарегистрирован: 15.09.2002
Сообщений: 1198
Вебсайт

меньше слов

Re: Мысли о парсерах

Gray_Flannel_Armor написал:

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

Конечные автоматы подходят для соотвествующих грамматик, и отсюда ограничения на ввод игрока.

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

Неактивен

Powered by PunBB
© copyright 2001–2024 iFiction.Ru