Вот рабочий пример на 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» - или конец «file».
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.