Почему в этом примере попытка не запускает поиск с возвратом
Я пытаюсь понять, как писать синтаксический анализатор с использованием parsec в Haskell, в частности, как работает откат.
Возьмем следующий простой парсер:
import Text.Parsec
type Parser = Parsec String () String
parseConst :: Parser
parseConst = do {
x <- many digit;
return $ read x
}
parseAdd :: Parser
parseAdd = do {
l <- parseExp;
char '+';
r <- parseExp;
return $ l <> "+" <> r
}
parseExp :: Parser
parseExp = try parseConst <|> parseAdd
pp :: Parser
pp = parseExp <* eof
test = parse pp "" "1+1"
test имеет значение
Left (line 1, column 2):
unexpected '+'
expecting digit or end of input
На мой взгляд, это должно получиться, так как я использовал комбинатор try на parseConst в определении parseExp.
Что мне не хватает? Меня также интересуют указатели на то, как отлаживать это самостоятельно, я пытался использовать parserTraced, что просто позволило мне сделать вывод, что это действительно не откат.
PS. Я знаю, что это ужасный способ написания синтаксического анализатора выражений, но я хотел бы понять, почему он не работает.
Ответы 1
Здесь много проблем.
Во-первых, parseConst никогда не может работать правильно. Тип говорит, что он должен производить String, поэтому read :: String -> String. Этот конкретный экземпляр Read требует, чтобы ввод был строкой в кавычках, поэтому передача 0 или более цифровых символов в read всегда будет приводить к вызову error, если вы попытаетесь оценить полученное значение.
Во-вторых, parseConst может успешно сопоставить ноль символов. Я думаю, вы, вероятно, хотели some вместо many. Это фактически приведет к сбою, если он встретит ввод, который не начинается с цифры.
В-третьих, (<|>) делает не то, что вы думаете. Вы можете подумать, что (a <* c) <|> (b <* c) взаимозаменяемо с (a <|> b) <* c, но это не так. Нет никакого способа добавить try и сделать его таким же. Проблема в том, что (<|>) фиксирует любую успешную ветку, если она это делает. В (a <|> b) <* c, если a совпадает, нет возможности позже вернуться и попробовать b там. Неважно, как вы крутите try, это не может отменить того факта, что (<|>) привержен a. Напротив, (a <* c) <|> (b <* c) не фиксируется до тех пор, пока оба a и c или b и c не совпадут с вводом.
Это ситуация, с которой вы столкнулись. У вас есть (try parseConst <|> parseAdd) <* eof после небольшого встраивания. Поскольку parseConst всегда будет успешным (см. второй выпуск), parseAdd никогда не будет опробован, даже если eof потерпит неудачу. Таким образом, после того, как parseConst потребляет ноль или более начальных цифр, синтаксический анализ завершится ошибкой, если только это не конец ввода. Обойти это, по сути, требует тщательного планирования вашей грамматики, чтобы любое использование (<|>) было безопасным для локальной фиксации. То есть содержимое каждой ветви не должно перекрываться таким образом, чтобы неоднозначность устранялась только более поздними частями грамматики.
Обратите внимание, что это неприятное поведение с (<|>) связано с тем, как работает семейство библиотек parsec, но не с тем, как работают все библиотеки парсеров в Haskell. Другие библиотеки работают без смещения влево или поведения при фиксации, которое выбрало семейство parsec.
Спасибо! Кажется, мне еще предстоит пройти совсем немного, прежде чем я достигну своего прежнего уровня владения YACC :).
tryзаставляетparseExprпытатьсяparseAddс исходным вводом, когдаparseConstтерпит неудачу. Но в этом случаеparseConstуспешно разбирает1, так что этотtryничего не делает.