F # FParsec умножение при разборе - PullRequest
Новая
       59

F # FParsec умножение при разборе

2 голосов
/ 07 марта 2019

Я пытаюсь заняться самой страшной для меня частью программирования, а именно парсингом и AST.Я работаю над тривиальным примером, используя F # и FParsec.Я хочу разобрать простую серию умножений.Я только получаю первый срок, хотя.Вот что у меня есть: 

open FParsec

let test p str =
    match run p str with
    | Success(result, _, _) -> printfn  "Success: %A" result
    | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

type Expr =
| Float of float
| Multiply of Expr * Expr

let parseExpr, impl = createParserForwardedToRef ()

let pNumber = pfloat .>> spaces |>> (Float)
let pMultiply = parseExpr .>> pstring "*" >>. parseExpr
impl := pNumber <|> pMultiply

test parseExpr "2.0 * 3.0 * 4.0 * 5.0"

Когда я запускаю это, я получаю следующее: 

> test parseExpr "2.0 * 3.0 * 4.0 * 5.0";;
Success: Float 2.0
val it : unit = ()

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

1 Ответ

6 голосов
/ 07 марта 2019

Комбинаторы парсеров, такие как FParsec, не эквивалентны грамматикам БНФ. Большая разница в том, что когда у вас есть альтернатива (<|> в FParsec), дела рассматриваются в порядке . Если левый парсер успешен, то он возвращается, а правый парсер не пробуется. Если левый синтаксический анализатор дает сбой после использования некоторого ввода, то возвращается ошибка и правый синтаксический анализатор также не пробуется. Только в том случае, если левый синтаксический анализатор дает сбой без использования какого-либо ввода, пробуется правый синтаксический анализатор. [1]

В вашем pNumber <|> pMultiply, pNumber успешно и сразу же возвращается без попытки сделать pMultiply. Можно подумать, чтобы исправить это, написав pMultiply <|> pNumber вместо этого, но это тоже нехорошо: при анализе последнего числа pMultiply не сможет найти * после использования некоторого ввода для его parseExpr, поэтому все парсинг будет помечен как сбойный.

Как правило, вы хотите максимально использовать функции комбинатора FParsec, и в этом случае наилучшим решением, вероятно, будет использование chainl1. 

let pNumber = pfloat .>> spaces |>> Float
let pTimes = pstring "*" .>> spaces >>% (fun x y -> Multiply (x, y))
let pMultiply = chainl1 pNumber pTimes

Если ваша цель состояла в том, чтобы научиться использовать грамматики BNF, вы, вероятно, захотите взглянуть на FsLex и FsYacc , а не на FParsec.

[1] Есть функция attempt, которая превращает сбой в потреблении в сбой, не потребляющий, но ее следует использовать как можно реже.

...