Парсер вызова функции - FParsec

Я пытаюсь разобрать вызов функции, вот варианты:

add 8 2
add x y
add (inc x) (dec y)
funcWithoutArgs

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

add 4 7

возвращает следующий AST:

[Call ("foo",[Number 4]);
 Number 7]

Поэтому он принимает только первый параметр.

Когда я это делаю:

foo x y

Он отправляет мне обратно это АСТ:

[Call ("foo",[Call ("x",[Call ("y",[])])])]

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

Другой пример, когда я делаю это:

foo x y
inc x

Я получил:

[Call ("foo",[Call ("x",[Call ("y",[Call ("inc",[Call ("x",[])])])])])]

Он делает то же, что и выше, но также вызывает код, следующий за строкой. Когда я спрашиваю свой анализатор о новой строке (см. Код), он отправляет мне это:

[Call ("foo",[]); Call ("x",[]); Call ("y",[]); Call ("inc",[]); Call ("x",[])]

Даже в скобках это не работает:

foo (x) (y)

Дать:

[Call ("foo",[]); Call ("x",[]); Call ("y",[])]

А также:

add (inc x) (dec y)

Дать:

Error in Ln: 1 Col: 1
Note: The error occurred on an empty line.

The parser backtracked after:
  Error in Ln: 2 Col: 5
  add (inc x) (dec y)
      ^
  Expecting: end of input or integer number (32-bit, signed)

  The parser backtracked after:
    Error in Ln: 2 Col: 10
    add (inc x) (dec y)
             ^
    Expecting: ')'

[]

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

Вот минимальный функциональный код, который был использован:

open FParsec

// Ast

type Expression =
    | Number of int
    | Call of string * Expression list

type Program = Expression list

// Tools

let private bws p =
    spaces >>? p .>>? spaces

let private suiteOf p =
    sepEndBy p spaces1

let inline private betweenParentheses p label =
    between (pstring "(") (pstring ")") p
    <?> (label + " between parentheses")

let private identifier =
    many1Satisfy2 isLetter (fun c -> isLetter c)

// Expressions

let rec private call = parse {
        let! call = pipe2 (spaces >>? identifier) (spaces >>? parameters)
                        (fun id parameters -> Call(id, parameters)) // .>>? newline
        return call
    }

and private parameters = suiteOf expression

and private callFuncWithoutArgs =
    identifier |>> fun id -> Call(id, [])

and private number = pint32 |>> Number

and private betweenParenthesesExpression =
    parse { let! ex = betweenParentheses expression "expression"
            return ex }

and private expression =
    bws (attempt betweenParenthesesExpression <|>
         attempt number <|>
         attempt call <|>
         callFuncWithoutArgs)

// -------------------------------

let parse code =
    let parser = many expression .>>? eof

    match run parser code with
        | Success(result, _, _) -> result
        | Failure(msg, _, _) ->
            printfn "%s" msg
            []

System.Console.Clear()

parse @"
add 4 7

foo x y

inc x

foo (x) (y)

add (inc x) (dec y)

" |> printfn "%A"
Источник

1 ответ

Решение

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

Ваш текущий дизайн состоит в том, что выражение может быть:

  1. Выражение (так сказать, "подвыражение") в скобках (здесь нет проблем)
  2. Число (здесь нет проблем)
  3. Вызов с параметрами, который является идентификатором, за которым следует разделенный пробелами список выражений (это основная часть проблемы)
  4. Вызов без параметров, который является единым идентификатором (это усугубляет проблему)

Глядя на выражение foo x yдавайте применим эти правила по порядку, как это сделал бы парсер. Там нет скобок и foo это не число, так что это либо 3, либо 4. Сначала мы попробуем 3. foo сопровождается x y: делает x y разобрать как выражение? Почему, да, это так: он анализирует как вызов с параметрами, где x это функция и y это параметр. поскольку x y соответствует 3, анализируется в соответствии с правилом 3 без проверки правила 4 и т. д. foo x y соответствует как foo (x y) будет: вызов foo с одним параметром, который является вызовом x с параметром y,

Как это исправить? Ну, вы можете попробовать поменять местами порядок 3 и 4, чтобы перед вызовом с параметрами проверялся вызов функции без параметров (что x y разобрать как раз x, Но это не получится, потому что foo x y будет соответствовать как раз foo, Таким образом, размещение правила 4 перед правилом 3 здесь не работает.

Реальное решение состоит в том, чтобы разделить правила для выражения на два уровня. "Внутренний" уровень, который я назову "значением", может быть:

  1. Выражение в скобках
  2. Число
  3. Вызов функции без параметров

И "внешний" уровень, правила разбора для выражений, будет:

  1. Вызов функции с параметрами, которые являются значениями, а не выражениями
  2. Ценность

Обратите внимание, что эти уровни синтаксического анализа являются взаимно рекурсивными, поэтому вам необходимо использовать createParserForwardedToRef в вашей реализации. Давайте посмотрим, как foo x y будет проанализирован с этим дизайном:

Первый, foo анализирует как идентификатор, поэтому проверьте, может ли это быть вызов функции с параметрами. Есть ли x разбирать как значение? Да, согласно правилу 3 ценностей. И делает y разбирать как значение? Да, согласно правилу 3 ценностей. Так foo x y разбирает как вызов функции.

Теперь насчет funcWithoutParameters? Это не выполнит правило 1 выражений, потому что за ним не следует список параметров. Таким образом, он будет проверен на правило 2 выражений, а затем будет соответствовать правилу 3 значений.

Хорошо, базовая проверка работоспособности псевдокода работает, поэтому давайте превратим это в код. Но сначала я упомяну другую проблему в вашем парсере, которую я еще не упомянул, а именно то, что вы не понимаете, что FParsec spaces Парсер также соответствует символам новой строки. Поэтому, когда вы заверните expression парсер в bws ("между пробелами"), он также будет использовать новые строки после текста, который он анализирует. Поэтому, когда вы анализируете что-то вроде:

foo a b
inc c

suiteOf expression видит список a b inc c и превращает все это в параметры для foo, В моем коде ниже я различаю FParsec spaces синтаксический анализатор (который включает новые строки) и анализатор, который анализирует только горизонтальные пробелы (пробел и табуляция, но не перевод строки), используя каждый в соответствующем месте. Следующий код реализует дизайн, который я упомянул в этом ответе, и его вывод выглядит мне правильно для всех тестовых выражений, которые вы написали:

open FParsec

// Ast

type Expression =
    | Number of int
    | Call of string * Expression list

type Program = Expression list

// Tools

let private justSpaces  = skipMany  (pchar ' ' <|> pchar '\t')
let private justSpaces1 = skipMany1 (pchar ' ' <|> pchar '\t')

let private bws p =
    spaces >>? p .>>? spaces

let private suiteOf p =
    sepEndBy1 p (justSpaces1)

let inline private betweenParentheses p label =
    between (pstring "(") (pstring ")") p
    <?> (label + " between parentheses")

let private identifier =
    many1Satisfy2 isLetter (fun c -> isLetter c)

// Expressions

let private expression, expressionImpl = createParserForwardedToRef()

let private betweenParenthesesExpression =
    parse { let! ex = betweenParentheses expression "expression"
            return ex }

let private callFuncWithoutArgs =
    (identifier |>> fun id -> Call(id, []))

let private number = pint32 |>> Number

let private value =
    justSpaces >>? (attempt betweenParenthesesExpression <|>
                    attempt number <|>
                    callFuncWithoutArgs)

let private parameters = suiteOf value

let rec private callImpl = parse {
        let! call = pipe2 (justSpaces >>? identifier) (justSpaces >>? parameters)
                          (fun id parameters -> Call(id, parameters))
        return call }

let call = callImpl

expressionImpl.Value <-
    bws (attempt call <|>
         value)

// -------------------------------

let parse code =
    let parser = many expression .>>? (spaces >>. eof)

    match run parser code with
        | Success(result, _, _) -> result
        | Failure(msg, _, _) ->
            printfn "%s" msg
            []

System.Console.Clear()

parse @"
add 4 7

foo x y

inc x

foo (x) (y)

add (inc x) (dec y)
" |> printfn "%A"

PS Я использовал следующий оператор, предложенный http://www.quanttec.com/fparsec/users-guide/debugging-a-parser.html чтобы сильно помочь мне в отслеживании проблемы:

let (<!>) (p: Parser<_,_>) label : Parser<_,_> =
    fun stream ->
        printfn "%A: Entering %s" stream.Position label
        let reply = p stream
        printfn "%A: Leaving %s (%A)" stream.Position label reply.Status
        reply

Использование: поворот let parseFoo = ... в let parseFoo = ... <!> "foo", Затем вы получите поток отладочной информации в консоли, который выглядит примерно так:

(Ln: 2, Col: 20): Entering expression
(Ln: 3, Col: 1): Entering call
(Ln: 3, Col: 5): Entering parameters
(Ln: 3, Col: 5): Entering bwParens
(Ln: 3, Col: 5): Leaving bwParens (Error)
(Ln: 3, Col: 5): Entering number
(Ln: 3, Col: 6): Leaving number (Ok)
(Ln: 3, Col: 7): Entering bwParens
(Ln: 3, Col: 7): Leaving bwParens (Error)
(Ln: 3, Col: 7): Entering number
(Ln: 3, Col: 8): Leaving number (Ok)
(Ln: 3, Col: 8): Leaving parameters (Ok)
(Ln: 3, Col: 8): Leaving call (Ok)
(Ln: 3, Col: 8): Leaving expression (Ok)

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

Источник
Другие вопросы по тегам