Как создать анализатор предложений, используя только стандартную библиотеку c ++?

Question

Я разрабатываю текстовую игру, похожую на Zork, и мне бы хотелось, чтобы она могла анализировать отправку и выводить ключевые слова, такие как TAKE, DROP ect. Дело в том, что я хотел бы сделать это через стандартную библиотеку c ++ ... Я слышал о внешних библиотеках (таких как flex / bison), которые эффективно выполняют это; однако я пока не хочу связываться с ними.

То, что я думаю о реализации, - это система на основе токенов, в которой есть список слов, которые парсер может распознать, даже если они находятся в предложении типа «возьми меч и убей монстра» и знай, что согласно правилам грамматики парсера TAKE, SWORD, KILL и MONSTER все распознаются как токены и будут выдавать результат «Monster kill» или что-то в этом роде. Я слышал, что в стандартной библиотеке c ++ есть функция strtok, которая делает это, но я также слышал, что это «небезопасно». Поэтому, если бы кто-нибудь здесь мог протянуть руку помощи, я был бы очень признателен.

Answer 1

Функция strtok взята из стандартной библиотеки C и имеет несколько проблем. Например, он изменяет строку на месте и может вызвать проблемы с безопасностью из-за переполнения буфера. Вместо этого вам следует изучить использование классов IOStream в стандартной библиотеке C ++, а также контейнеров и алгоритмов Standard Template Library (STL) *1007*.

Пример:

#include <algorithm>
#include <cctype>
#include <iostream>
#include <sstream>

using namespace std;

int
main()
{
    string line;

    // grab a line from standard input
    while (getline(cin, line)) {

        // break the input in to tokens using a space as the delimeter
        istringstream stream(line);
        string token;
        while (getline(stream, token, ' ')) {

            // convert string to all caps
            transform(token.begin(), token.end(), token.begin(), (int(*)(int)) toupper);

            // print each token on a separate line
            cout << token << endl;
        }
    }
}

Answer 2

В зависимости от сложности синтаксического анализа этого языка, вы можете использовать Технический отчет C ++ 1 библиотеки регулярных выражений.

Если это недостаточно мощно, то струнные потоки могут куда-то вас привести, но через некоторое время вы, вероятно, решите, что генератор синтаксических анализаторов, такой как Flex / Bison, является наиболее кратким способом выражения вашей грамматики.

Вам нужно будет выбрать инструмент в зависимости от сложности разбираемых предложений.

Answer 3

Если ваш язык не чрезвычайно прост , вы хотите выполнить шаги написания парсера.

1. Напишите формальную грамматику. Формально я не хочу вас пугать: напишите это на салфетке, если это звучит менее тревожно. Я имею в виду только правильную грамматику и не переходите к следующему шагу раньше, чем вы. Например:

   action := ('caress' | 'kill') creature

   creature := 'monster' | 'pony' | 'girlfriend'

2. Напишите лексер. При наличии потока лексер будет принимать по одному символу за раз, пока не сможет выяснить, какой токен следующий, и вернет этот токен. Он отбросит символы, которые составляют этот токен, и оставит все остальные символы в потоке нетронутыми. Например, он может получить символ d, затем r, затем o и p, считая, что следующий токен является токеном DROP, и вернуть его.

3. Написать парсер. Я лично нахожу, что парсеры рекурсивного спуска довольно легко написать, потому что все, что вам нужно сделать, это написать ровно одну функцию для каждого из ваших правил, которая выполняет именно то, что определяет правило. Парсер будет принимать по одному токену за раз (вызывая лексера). Он точно знает, какой токен он собирается получить от лексера (или знает, что следующий токен является одним из ограниченного набора возможных токенов), потому что он следует грамматике. Если он получает неожиданный токен, он сообщает о синтаксической ошибке.

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

Answer 4

Для реализации naive с использованием std :: string , контейнера std :: set и этой функции токенизации (Alavoor Vasudevan ) вы можете сделать это:

#include <iostream>
#include <set>
#include <string>

int main()
{
 /*You match the substring find in the while loop (tokenization) to 
 the ones contained in the dic(tionnary) set. If there's a match, 
 the substring is printed to the console.
 */

    std::set<std::string> dic;
    dic.insert("sword");
    dic.insert("kill");
    dic.insert("monster");

    std::string str = "take sword and kill monster";
    std::string delimiters = " ";    

    std::string::size_type lastPos = str.find_first_not_of(delimiters, 0);
    std::string::size_type pos = str.find_first_of(delimiters, lastPos);

    while (std::string::npos != pos || std::string::npos != lastPos)
    {
        if(dic.find(str.substr(lastPos, pos - lastPos)) != dic.end())
            std::cout << str.substr(lastPos, pos - lastPos) 
                    << " is part of the dic.\n";
        lastPos = str.find_first_not_of(delimiters, pos);
        pos = str.find_first_of(delimiters, lastPos);
    }

    return 0;
}

Будет выведено:

Меч является частью Дик.
убийство является частью диктата.
монстр является частью диктата.

Примечания:

• Разделитель токенов (пробел) очень (слишком) прост для естественных языков.
• Вы можете использовать некоторые утилиты в boost ( split , tokenizer ).
• Если бы ваш словарь (список слов) был действительно большим, можно было бы использовать хэш-версию set ( unordered_set ).

С буст-токенизатором это может выглядеть так (это может быть не очень эффективно):

boost::tokenizer<> tok(str);
BOOST_FOREACH(const std::string& word,tok)
{
    if(dic.find(word) != dic.end())
        std::cout << word << " is part of the dic.\n";
}   

Answer 5

Если вы действительно хотите кодировать синтаксический анализ самостоятельно, я настоятельно рекомендую вам использовать «что-то вроде Lex / Yacc».На самом деле, я настоятельно рекомендую вам использовать Antlr.См. Мой ранее принятый ответ на аналогичный вопрос на На каком языке мне следует написать текстовый анализатор и отобразить результаты в удобной для пользователя форме?

---

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

Если вы хотите запрограммировать текстприключение, тогда я рекомендую вам использовать один из языков программирования, специально предназначенных для этой цели.Их много, см.

• http://www.brasslantern.org/writers/howto/chooselang.html
• http://www.brasslantern.org/editorials/easyif.html
• http://www.onlamp.com/pub/a/onlamp/2004/11/24/interactive_fiction.html
  или Google для «если язык программирования» (Interactive Fiction))

Вы, вероятно, определитесь с TADS, Inform или Hugo (мой личный голос - за TADS).

Вы можете получить хороший совет, если отправите сообщение на rec.arts.int-фантастика, объясняющая, чего вы надеетесь достичь, и дающая свой уровень или навыки программирования.

Веселитесь!