Как вы используете парсек в жадной манере?

Question

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

Итак, давайте притворимся, что sql это "select foo from bar, где 1". Я думал, что всегда есть ключевое слово, за которым следуют данные, поэтому все, что мне нужно сделать, - это проанализировать ключевое слово, а затем перехватить все тарабарщины перед следующим ключевым словом и сохранить его для последующей очистки, если оно того стоит. Вот код:

import Text.Parsec
import Text.Parsec.Combinator
import Text.Parsec.Char
import Data.Text (strip)

newtype Statement = Statement [Atom]
data Atom = Branch String [Atom] | Leaf String deriving Show

trim str = reverse $ trim' (reverse $ trim' str)
  where
    trim' (' ':xs) = trim' xs
    trim' str = str

printStatement atoms = mapM_ printAtom atoms
printAtom atom = loop 0 atom 
  where
    loop depth (Leaf str) = putStrLn $ (replicate depth ' ') ++ str
    loop depth (Branch str atoms) = do 
      putStrLn $ (replicate depth ' ') ++ str
      mapM_ (loop (depth + 2)) atoms

keywords :: [String]
keywords = [
  "select",
  "update",
  "delete",
  "from",
  "where"]

keywordparser :: Parsec String u String
keywordparser = try ((choice $ map string keywords) <?> "keywordparser")

stuffparser :: Parsec String u String
stuffparser = manyTill anyChar (eof <|> (lookAhead keywordparser >> return ()))

statementparser = do
  key <- keywordparser
  stuff <- stuffparser
  return $ Branch key [Leaf (trim stuff)]
  <?> "statementparser"

tp = parse (many statementparser) ""

Ключевым моментом здесь является материалпарсер. Это то, что находится между ключевыми словами, это может быть что угодно, от списков столбцов до критериев. Эта функция ловит все символы, ведущие к ключевому слову. Но для этого нужно что-то еще, прежде чем оно закончится. Что делать, если есть подвыбор? msgstr "выбрать идентификатор, (выбрать продукт из продуктов) из бара". Ну, в этом случае, если он попадет в это ключевое слово, он все испортит, неправильно его проанализирует и испортит мой отступ. Также там, где пункты могут иметь круглые скобки.

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

stuffparser :: Parsec String u String
stuffparser = fmap concat $ manyTill somechars (eof <|> (lookAhead keywordparser >> return ()))
  where
    somechars = parens <|> fmap (\c -> [c]) anyChar
    parens= between (char '(') (char ')') somechars

Это будет ошибка, например, так:

> tp "select asdf(qwerty) from foo where 1"
Left (line 1, column 14):
unexpected "w"
expecting ")"

Но я не могу придумать, как это переписать, чтобы оно работало. Я попытался использовать manyTill в скобках, но у меня возникли проблемы с проверкой типов, когда в качестве альтернативы у меня есть как строковые выражения, так и одиночные символы. У кого-нибудь есть предложения, как это сделать?

Answer 1

Да, between может не работать для того, что вы ищете. Конечно, для вашего случая использования я бы последовал совету Хаммара и взял бы готовый анализатор SQL. (личное мнение: или старайтесь не использовать SQL, если в этом нет особой необходимости; идея использовать строки для запросов к базе данных была исторической ошибкой).

Примечание. Я добавляю оператор с именем <++>, который объединяет результаты двух анализаторов, будь то строки или символы. (код внизу.)

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

parseParen = char '(' <++> inner <++> char ')'

Затем функция inner должна анализировать что-либо еще: непаренс, возможно, включая другой набор скобок, и непаренский мусор, который следует.

parseParen = char '(' <++> inner <++> char ')' where
    inner = many (noneOf "()") <++> option "" (parseParen <++> inner)

Я сделаю предположение, что для остальной части решения то, что вы хотите сделать, является аналогом разделения на ключевые слова SQL верхнего уровня. (т.е. игнорируя те, что в скобках). А именно, у нас будет парсер, который будет вести себя так,

Main> parseTest parseSqlToplevel "select asdf(select m( 2) fr(o)m w where n) from b where delete 4"
[(Select," asdf(select m( 2) fr(o)m w where n) "),(From," b "),(Where," "),(Delete," 4")]

Предположим, у нас есть синтаксический анализатор parseKw, который получит значения, подобные select и т. Д. После того, как мы используем ключевое слово, нам нужно прочитать до следующего ключевого слова [верхнего уровня]. Последний трюк с моим решением - использовать комбинатор lookAhead, чтобы определить, является ли следующее слово ключевым словом, и вернуть его, если так. Если это не так, то мы потребляем скобки или другой символ, а затем возвращаемся к остальным.

-- consume spaces, then eat a word or parenthesis
parseOther = many space <++>
    (("" <$ lookAhead (try parseKw)) <|> -- if there's a keyword, put it back!
     option "" ((parseParen <|> many1 (noneOf "() \t")) <++> parseOther))

Мое полное решение выглядит следующим образом

-- overloaded operator to concatenate string results from parsers
class CharOrStr a where toStr :: a -> String
instance CharOrStr Char where toStr x = [x]
instance CharOrStr String where toStr = id
infixl 4 <++>
f <++> g = (\x y -> toStr x ++ toStr y) <$> f <*> g

data Keyword = Select | Update | Delete | From | Where deriving (Eq, Show)

parseKw =
    (Select <$ string "select") <|>
    (Update <$ string "update") <|>
    (Delete <$ string "delete") <|>
    (From <$ string "from") <|>
    (Where <$ string "where") <?>
    "keyword (select, update, delete, from, where)"

-- consume spaces, then eat a word or parenthesis
parseOther = many space <++>
    (("" <$ lookAhead (try parseKw)) <|> -- if there's a keyword, put it back!
     option "" ((parseParen <|> many1 (noneOf "() \t")) <++> parseOther))

parseSqlToplevel = many ((,) <$> parseKw <*> (space <++> parseOther)) <* eof

parseParen = char '(' <++> inner <++> char ')' where
    inner = many (noneOf "()") <++> option "" (parseParen <++> inner)

edit - версия с поддержкой цитат

вы можете сделать то же самое, что и с паренами для поддержки кавычек,

import Control.Applicative hiding (many, (<|>))
import Text.Parsec
import Text.Parsec.Combinator

-- overloaded operator to concatenate string results from parsers
class CharOrStr a where toStr :: a -> String
instance CharOrStr Char where toStr x = [x]
instance CharOrStr String where toStr = id
infixl 4 <++>
f <++> g = (\x y -> toStr x ++ toStr y) <$> f <*> g

data Keyword = Select | Update | Delete | From | Where deriving (Eq, Show)

parseKw =
    (Select <$ string "select") <|>
    (Update <$ string "update") <|>
    (Delete <$ string "delete") <|>
    (From <$ string "from") <|>
    (Where <$ string "where") <?>
    "keyword (select, update, delete, from, where)"

-- consume spaces, then eat a word or parenthesis
parseOther = many space <++>
    (("" <$ lookAhead (try parseKw)) <|> -- if there's a keyword, put it back!
     option "" ((parseParen <|> parseQuote <|> many1 (noneOf "'() \t")) <++> parseOther))

parseSqlToplevel = many ((,) <$> parseKw <*> (space <++> parseOther)) <* eof

parseQuote = char '\'' <++> inner <++> char '\'' where
    inner = many (noneOf "'\\") <++>
        option "" (char '\\' <++> anyChar <++> inner)

parseParen = char '(' <++> inner <++> char ')' where
    inner = many (noneOf "'()") <++>
        (parseQuote <++> inner <|> option "" (parseParen <++> inner))

Я попробовал это с parseTest parseSqlToplevel "select ('a(sdf'())b". веселит