Блог

Просто чтобы уточнить, это не домашнее задание. Меня попросили помочь в этом, и я не могу этого сделать, поэтому это превратилось в личный поиск решения.

Представьте, что у вас есть грамматика для английского предложения, подобного этому:

 S => NP VP | VP
NP => N | Det N | Det Adj N
VB => V | V NP
N => i you bus cake bear
V => hug love destroy am
Det => a the
Adj => pink stylish
  

Я искал несколько часов, и у меня действительно закончились идеи.
Я нашел статьи, в которых говорится о мелком разборе, возврате в глубину и связанных с этим вещах, и хотя я знаком с большинством из них, я все еще не могу применить их к этой проблеме. Я пометил Lisp и Haskell, потому что на этих языках я планирую реализовать это, но я не возражаю, если вы используете другие языки в своих ответах.

Я был бы признателен за подсказки, хорошие статьи и все в целом.

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

 {-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Applicative ((<*))
import Control.Monad
import Text.ParserCombinators.Parsec

ensure p x = guard (p x) >> return x
singleToken t = tokenPrim id (pos _ _ -> incSourceColumn pos 1) (ensure (==t))
anyOf xs = choice (map singleToken xs)
  

Теперь, когда с нулем покончено … сначала мы определяем тип данных для наших абстрактных синтаксических деревьев. Мы можем просто следовать форме грамматики здесь. Однако, чтобы сделать это более удобным, я учел несколько правил грамматики; в частности, два правила

 NP => N | Det N | Det Adj N
VB => V | V NP
  

так удобнее писать, когда дело доходит до фактического написания синтаксического анализатора:

 NP => N | Det (Adj | empty) N
VB => V (NP | empty)
  

В любой хорошей книге по синтаксическому анализу будет глава о том, почему этот вид факторинга является хорошей идеей. Итак, тип AST:

 data Sentence
    = Complex NounPhrase VerbPhrase
    | Simple VerbPhrase
data NounPhrase
    = Short Noun
    | Long Article (Maybe Adjective) Noun
data VerbPhrase
    = VerbPhrase Verb (Maybe NounPhrase)
type Noun      = String
type Verb      = String
type Article   = String
type Adjective = String
  

Затем мы можем создать наш синтаксический анализатор. Этот еще более точно соответствует (факторизованной) грамматике! Единственная проблема здесь в том, что мы всегда хотим, чтобы наш анализатор использовал все предложение целиком, поэтому мы должны явно попросить его сделать это, потребовав «eof» — или конец «файла».

 s   = (liftM2 Complex np vp <|> liftM Simple vp) <* eof
np  = liftM Short n <|> liftM3 Long det (optionMaybe adj) n
vp  = liftM2 VerbPhrase v (optionMaybe np)
n   = anyOf ["i", "you", "bus", "cake", "bear"]
v   = anyOf ["hug", "love", "destroy", "am"]
det = anyOf ["a", "the"]
adj = anyOf ["pink", "stylish"]
  

Последняя часть — это токенизатор. Для этого простого приложения мы просто будем маркировать на основе пробелов, поэтому встроенная words функция работает просто отлично. Давайте попробуем! Загрузите весь файл в ghci:

 *Main> parse s "stdin" (words "i love the pink cake")
Right (Complex (Short "i") (VerbPhrase "love" (Just (Long "the" (Just "pink") "cake"))))
*Main> parse s "stdin" (words "i love pink cake")
Left "stdin" (line 1, column 3):
unexpected "pink"
expecting end of input
  

Здесь Right указывает на успешный синтаксический анализ и Left указывает на ошибку. Номер «столбца», указанный в ошибке, на самом деле является номером слова, в котором произошла ошибка, из-за способа, которым мы вычисляем исходные позиции в singleToken .

Существует несколько различных подходов к синтаксическому разбору с использованием контекстно-свободной грамматики.

Если вы хотите реализовать это самостоятельно, вы могли бы начать с ознакомления с алгоритмами синтаксического анализа: вы можете посмотреть здесь и здесь, или, если вы предпочитаете что-то на бумаге, глава о синтаксическом анализе в Jurafsky amp; Martin может быть хорошим началом.

Я знаю, что реализовать простой синтаксический анализатор на языке программирования Prolog не так уж сложно. Просто найдите в Google ‘prolog shift reduce parser’ или ‘prolog scan predict parser’. Я не знаю Haskell или Lisp, но могут быть сходства с prolog, так что, возможно, вы сможете почерпнуть некоторые идеи оттуда.

Если вам не нужно самостоятельно реализовывать полный анализатор, я бы взглянул на Python NLTK, который предлагает инструменты для CFG-синтаксического анализа. В книге NLTK есть глава об этом.

Хорошо, есть несколько алгоритмов, которые вы могли бы использовать. Ниже приведены некоторые популярные алгоритмы динамического программирования: 1) Алгоритм CKY: грамматика должна быть в форме CNF 2) Алгоритм Эрли 3) Анализ диаграммы.

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

Вы предоставили пример непрофессиональной грамматики. Таким образом, вы можете использовать инструменты ANTLR, JFlex, Scala Parser Combinators, Parsers python library для реализации синтаксического анализа по этой грамматике в очень похожем коде, который вы предоставили.

Я думаю, что проблема для вас может заключаться в том, что способ, которым вы анализируете компьютерный язык, сильно отличается от способа, которым вы анализируете естественный язык.

Компьютерные языки разработаны так, чтобы быть однозначными и относительно легко получать точное значение с компьютера.

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