Очень простой английский синтаксический анализатор грамматики
Это напоминает мне цитату из фильма «Равновесие»:
«Какой, по-твоему, самый простой способ отобрать оружие у клерика Грамматона?»
«Вы просите его об этом».
Мы так привыкли бороться за решения, когда иногда лучше спросить. (Есть веские причины, по которым мы обычно этого не делаем, но это всегда вариант.) Все предложения здесь блестящие, но простое решение может состоять в том, чтобы ваша программа спросила, какой iPad они используют, когда они запускают его. .
Я знаю, что это нахальный ответ, но я надеюсь, что это напоминание о том, что нам не нужно бороться за все. (Я приготовился к отрицательным голосам.: P)
Некоторые примеры:
- Обнаружение клавиатуры во время установки ОС иногда не может обнаружить конкретную клавиатуру, поэтому установщик должен спросить.
- Windows спрашивает, является ли сеть, к которой вы подключаетесь, домашней или общедоступной сетью.
- Компьютеры не могут обнаружить человека, который собирается его использовать, поэтому им требуются имя пользователя и пароль.
Желаем удачи - надеюсь, вы найдете отличное решение! Если вы этого не сделаете, не забудьте об этом.
9 ответов
Меня заинтриговал этот вопрос. Я собираюсь помочь ОП, Алекс, приготовить что-нибудь, но, поскольку я не очень хорошо знаю C ++, это будет псевдо-C ++. Он также не будет использовать lex / yacc, потому что Алекс хочет узнать, как они созданы. Такие инструменты, как lex и yacc, становятся «черными ящиками», если вы их используете. У меня нет времени собирать все это прямо сейчас, но я могу работать над ним по частям в течение нескольких часов. Я просто хотел начать это прямо сейчас.
Первое, что нам нужно сделать, это очистить грамматику. У вас есть предложение, определенное следующим образом:
sentence : noun verb
| article sentence
| sentence conjunction sentence
Эта грамматика некорректна. Такое предложение, как «рыба плывет», действительно, потому что предложение определяется само по себе. Рекурсия - нормальная часть грамматики, но с ней нужно обращаться правильно. Я рискну предположить, что ты не Я не хочу, чтобы две или более статьи отображались подряд.
Лучшая грамматика для предложения:
sentence : clause conjunction clause
| clause
clause : nounphrase verbphrase
nounphrase : noun
| article noun
Это устраняет неограниченную рекурсию, которая могла вызвать бесконечные циклы.
Теперь мы готовы заняться самим анализатором. . Поскольку это C ++, мы могли бы сделать его объектно-ориентированным. Сейчас мне нужно уйти, но я дам вам подсказку: для каждого из производственных правил будет класс.
Большая часть синтаксического анализа, как и синтаксический анализ текста программы, выполняется с помощью синтаксических анализаторов грамматики. Английский и большинство разговорных языков не являются формальными грамматиками, и вам будет очень трудно их разобрать. Эта проблема сковывала доктора наук на протяжении десятилетий, но без особого успеха.
Части речи
Чтобы получить части речи вам понадобится словарь с частями речи . Помимо хэш-таблицы, отображающей слова в списки частей речи, еще один возможный способ проверки части (частей) речи - загрузить каждый набор слов для каждой части речи в свой собственный фильтр Блума (своего рода сжатая хешированная карта из строк в логические).
Одним из аспектов грамматик естественных языков является то, что они часто неоднозначны. Например, английский сентанс:
Однажды я застрелил слона в своей пижаме. Как он попал в мою пижаму, я никогда не узнаю
- Граучо Маркс
Фраза «в моей пижаме» неоднозначно описывает субъект «я» или объект «слон». Без семантического контекста было бы невозможно правильно построить AST.
Если вы хотите избежать этого, вам, вероятно, понадобится какой-то способ полезной обработки неоднозначности. Одна из стратегий - производить все возможные производные неоднозначных фраз. Одним из инструментов, который делает это возможным, является Earley Parser . В отличие от других типов синтаксических анализаторов, таких как синтаксические анализаторы с рекурсивным спуском, синтаксические анализаторы Эрли генерируют все производные в форме переходов состояний синтаксического анализатора, а не в виде простого дерева. На практике с этим работать не труднее.
Хорошо, так ... У меня не будет ответов на ваши конкретные вопросы, но я хочу указать вам на некоторые общие идеи, о которых следует подумать при работе над этим . Во-первых, разбор сложен. У вас простая грамматика, но это ВСЕ ЕЩЕ может быть сложно. Внешние интерфейсы компилятора отвечают за синтаксический анализ ... просто чтобы дать некоторый контекст.
Существует два основных типа синтаксического анализа ... синтаксический анализ сверху вниз и анализ снизу вверх. Они названы в соответствии с тем, как они проходят по синтаксическому дереву (подумайте, какое синтаксическое дерево будет создано для возможных конструкций). Анализ сверху вниз прост и, вероятно, будет работать для того, что вы хотите сделать. Самый распространенный метод синтаксического анализа сверху вниз - это синтаксический анализ с рекурсивным спуском: http://en.wikipedia.org/wiki/Recursive_descent_parser
Однако, чтобы использовать синтаксический анализ с рекурсивным спуском, ваша грамматика должна быть в определенном формате .. .Для некоторых грамматик невозможно их разобрать методом рекурсивного спуска. Тем не менее, вы должны быть в состоянии реформировать свою грамматику, чтобы соответствовать этому.
Нисходящие синтаксические анализаторы легко писать ... поскольку вам понадобится всего несколько функций для небольшого языка.
Второй способ синтаксического анализа - снизу парсинг вверх. Это обычно используется в компиляторах, так как не имеет ограничений сверху вниз. Также легче создавать отчеты об ошибках, если данная строка не соответствует языку.
Анализаторы снизу вверх ТРУДНО писать ... большинство людей используют генератор синтаксических анализаторов для выполнения своей работы. Я немного работал с YACC. Вы в основном вводите грамматику (и действия, которые нужно предпринять, когда это правило соблюдается), и он анализирует грамматику.
Восходящие синтаксические анализаторы используют так называемый синтаксический анализ сдвиг-уменьшение. Это метод обработки ввода и соответствия правилам.
Еще раз взглянув на ваш код, я бы сказал, что вы можете использовать нисходящий синтаксический анализатор. Извините, я не могу указать конкретный код, но поиск в Google примеров синтаксического анализатора сверху вниз (или примеров синтаксического анализатора с рекурсивным спуском), вероятно, предоставит вам нужный код.
Я немного работал с YACC. Вы в основном вводите грамматику (и действия, которые нужно предпринять, когда это правило соблюдается), и он анализирует грамматику.Восходящие синтаксические анализаторы используют так называемый синтаксический анализ сдвиг-уменьшение. Это метод обработки ввода и соответствия правилам.
Еще раз взглянув на ваш код, я бы сказал, что вы можете использовать нисходящий синтаксический анализатор. Извините, я не могу указать конкретный код, но поиск в Google примеров синтаксического анализатора сверху вниз (или примеров синтаксического анализатора с рекурсивным спуском), вероятно, предоставит вам нужный код.
Я немного работал с YACC. Вы в основном вводите грамматику (и действия, которые нужно предпринять, когда это правило соблюдается), и он анализирует грамматику.Восходящие синтаксические анализаторы используют так называемый синтаксический анализ сдвиг-уменьшение. Это метод обработки ввода и соответствия правилам.
Еще раз взглянув на ваш код, я бы сказал, что вы можете использовать нисходящий синтаксический анализатор. Извините, я не могу указать конкретный код, но поиск в Google примеров синтаксического анализатора сверху вниз (или примеров синтаксического анализатора с рекурсивным спуском), вероятно, предоставит вам нужный код.
Я бы сказал, что вы можете использовать синтаксический анализатор сверху вниз. Извините, я не могу указать конкретный код, но поиск в Google примеров синтаксического анализатора сверху вниз (или примеров синтаксического анализатора с рекурсивным спуском), вероятно, предоставит вам нужный код. Я бы сказал, что вы можете использовать синтаксический анализатор сверху вниз. Извините, я не могу указать конкретный код, но поиск в Google примеров синтаксического анализатора сверху вниз (или примеров синтаксического анализатора с рекурсивным спуском), вероятно, предоставит вам нужный код.Используйте Flex и Bison:
Правило Граммера в Bison:
%%
English : SentenceList
SentenceList : Sentence
| Article Sentence
| Sentence Conjunction Sentence
Sentence : Noun Verb
Conjunction : TOKEN_WordAnd
| TOKEN_WordOr
| TOKEN_WordBut
Noun : TOKEN_WORD_BIRDS
| TOKEN_WORD_FISH
| TOKEN_WORD_CPP
Verb: : TOKEN_WORD_RULES
| TOKEN_WORD_FLY
| TOKEN_WRD_SWIM
Article : TOKEN_WORD_THE
%%
Вы можете взять добычу в Ubiquity , это плагин для Firefox, который нацелен на использование естественного языка для выполнения обычных веб-задач (он написан на JavaScript, но, возможно, вы можете получить общий алгоритм, который будет полезен)
Прежде чем вы зайдете слишком далеко в написании синтаксического анализатора, могу ли я предложить изучить пару lex и yacc или flex и bison? Эти инструменты были специально созданы для создания синтаксических анализаторов и лексеров.
Они автоматически сгенерируют ваш код c / c ++ (возможно, другой), поэтому вам не придется беспокоиться о всяких граничных случаях для пользовательских аргументов. Вы можете составить указанную выше грамматику менее чем за 30 минут.
Что касается ваших вопросов:
Для слова функции (существительное, глагол, и т. д.) как мне проверить если они верны? (как при проверке, если на входе пользователя есть птицы, рыбы, мухи, плавать и т. д.)
Здесь требуется широкое использование strcasecmp (), а также всевозможные проверки на ошибки.
Как мне обрабатывать соединение вызов и вывод?
Я не очень понимаю, что вы здесь имеете в виду. Я бы просто вернул какое-то контрольное значение, если оно действительное или нет.
Должен ли я обрабатывать вывод из основная функция или функции вызова?
В основном из функций вызова, поскольку они имеют индивидуальные функции, которые вас интересуют. main () - это просто клей, скрепляющий их.
Ни один из приведенных выше вопросов не имеет значения, если мой псевдо-код совершенно неверен. Является Что-то не так с основами?
Это выглядит вполне выполнимо, но вы избавите себя от огромной головной боли, переключившись на lex / yacc или flex / bison
Если вы не против тратить деньги на ссылку на мертвое дерево, Rails Way действительно того стоит. Опубликованные руководства, вероятно, будут вашим лучшим выбором на этот раз, но если вы планируете много работать с Rails, эта книга действительно ломает его и делает понятным. Мне это очень помогло. Удачи.
Сначала вы должны разметить входной поток в подходящие токены. Слова были бы очевидным выбором, но это оставило бы много работы для синтаксической фазы. Поэтому я бы сгруппировал ваши слова по следующим типам (Conjunction, Noun, Verb, Article), а затем написал бы лексический анализатор, чтобы возвращать правильные лексемы.
Lexer.cpp
enum Lexeme { END,Conjunction,Noun,Verb,Article };
Lexem getNextLexme(std::istream in)
{
std::string word;
in >> word;
if (!in) {return END;}
if (word == "and") return Conjunction;
else if (word == "birds") return Noun;
else if (word == "fly") return Verb;
else if (word == "the") return Article;
... etc
}
Итак, теперь вы можете написать свой синтаксический анализатор в терминах упрощенного потока токенов.
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
Слова были бы очевидным выбором, но это оставило бы много работы для синтаксической фазы. Поэтому я бы сгруппировал ваши слова по следующим типам (Conjunction, Noun, Verb, Article), а затем написал бы лексический анализатор, чтобы возвращать правильные лексемы.
Lexer.cpp
enum Lexeme { END,Conjunction,Noun,Verb,Article };
Lexem getNextLexme(std::istream in)
{
std::string word;
in >> word;
if (!in) {return END;}
if (word == "and") return Conjunction;
else if (word == "birds") return Noun;
else if (word == "fly") return Verb;
else if (word == "the") return Article;
... etc
}
Итак, теперь вы можете написать свой синтаксический анализатор в терминах упрощенного потока токенов.
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
Слова были бы очевидным выбором, но это оставило бы много работы для синтаксической фазы. Поэтому я бы сгруппировал ваши слова по следующим типам (Conjunction, Noun, Verb, Article), а затем написал бы лексический анализатор, чтобы возвращать правильные лексемы.
Lexer.cpp
enum Lexeme { END,Conjunction,Noun,Verb,Article };
Lexem getNextLexme(std::istream in)
{
std::string word;
in >> word;
if (!in) {return END;}
if (word == "and") return Conjunction;
else if (word == "birds") return Noun;
else if (word == "fly") return Verb;
else if (word == "the") return Article;
... etc
}
Итак, теперь вы можете написать свой синтаксический анализатор в терминах упрощенного потока токенов.
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
Поэтому я бы сгруппировал ваши слова по следующим типам (Conjunction, Noun, Verb, Article), а затем написал бы лексический анализатор, чтобы возвращать правильные лексемы.
Lexer.cpp
enum Lexeme { END,Conjunction,Noun,Verb,Article };
Lexem getNextLexme(std::istream in)
{
std::string word;
in >> word;
if (!in) {return END;}
if (word == "and") return Conjunction;
else if (word == "birds") return Noun;
else if (word == "fly") return Verb;
else if (word == "the") return Article;
... etc
}
Итак, теперь вы можете написать свой синтаксический анализатор в терминах упрощенного потока токенов.
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
Поэтому я бы сгруппировал ваши слова по следующим типам (Conjunction, Noun, Verb, Article), а затем написал бы лексический анализатор, чтобы возвращать правильные лексемы.
Lexer.cpp
enum Lexeme { END,Conjunction,Noun,Verb,Article };
Lexem getNextLexme(std::istream in)
{
std::string word;
in >> word;
if (!in) {return END;}
if (word == "and") return Conjunction;
else if (word == "birds") return Noun;
else if (word == "fly") return Verb;
else if (word == "the") return Article;
... etc
}
Итак, теперь вы можете написать свой синтаксический анализатор в терминах упрощенного потока токенов.
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
bool ParseSentence(std::istream in)
{
Lexeme token = getNextLexme(in);
switch(token)
{
case Noun: if (!parseVerb(in))
{ return false;
}
return parseConjunctionOrEnd(in);
case Article: return ParseSentence();
case END: return true;
}
}
bool parseVerb(std::istream in)
{
Lexeme token = getNextLexeme(in);
if (token != Verb) { /*ERROR*/ return false;}
return true;
}
// etc
Другой вариант синтаксического анализа - это создание таблицы состояний. Но это требует ручного анализа грамматика и определения состояний. Это должно быть выполнено только с самыми тривиальными грамматиками, все, что больше, чем у вас здесь, должно быть предоставлено инструментам, которые могут автоматически генерировать таблицу состояний.
Итак, предполагая, что граммер я определил в моем исходном посте ниже:
И надеюсь, что я понял это правильно, так как я не надуваемый инструмент: -)
State 1: Start <Nothing Happened>
Article -> State 2
Noun -> State 3
Otherwise Error
State 2: Seen Article.
Noun -> State 3
Otherwise Error
State 3: Seen Noun in Sentence.
Verb -> State 4
Otherwise Error
State 4: Seen Noun Verb
End -> State 5
Conjunction -> State 1
State 5: Finished:
State 0: Error State.
int stateTable[][] // CurrentState,CurrentObject
= {/*State 0: Error State:*/{},
// END,Conjunction,Noun,Verb,Article
/*State 1: Start*/ { 0, 0, 3, 0, 2},
/*State 2: Article*/ { 0, 0, 3, 0, 0},
/*State 3: Noun*/ { 0, 0, 0, 4, 0},
/*State 4: Noun Verb*/ { 5, 1, 0, 0, 0},
/*State 5: End*/ {}
};
bool parseSentence(std::iostream& in)
{
int currentState = 1;
while((currentState != 0) && (currentState != 5))
{
int token = getNextLexme(in);
currentState = stateTable[currentState][token];
}
return currentState == 5;
}