Отступы, выражения, операторы и StackOverflowException с FParsec - ошибки - PullRequest
Новая
       53

Отступы, выражения, операторы и StackOverflowException с FParsec - ошибки

0 голосов
/ 10 декабря 2018

Я проверяю отступ с помощью FParsec, в соответствии с этой реализацией , но когда я делаю его немного более сложным, добавляя выражения (литералы, списки, кортежи и арифметические операции), позволяя выражениям переходить на верхний уровень,и добавление оператора создания переменной;Сначала я получаю ошибку StackOverflowException .На мой взгляд, это связано с тем, что синтаксический анализатор выражений запрашивается таким образом, чтобы сделать бесконечный цикл в программе.Я не вижу другой причины, однако, я не знаю, как решить эту проблему.

Если я удалю attempt pexpression из данных моего парсера statement, больше не будет StackOverflowException , тем не менее, модуль IndentationParserWithoutBacktracking (следовательно, управляет отступами) говорит мне, что в анализируемом коде отсутствует "новая строка": 

Failure: Error in Ln: 2 Col: 1
loop i 0 10
^
Expecting: let or print

The parser backtracked after:
  Error in Ln: 3 Col: 5
      let myVar = 2 + 1
      ^
  Expecting: loop or print

  The parser backtracked after:
    Error in Ln: 3 Col: 17
        let myVar = 2 + 1
                    ^
    Expecting: newline

Все это в соответствии со следующим текстом для анализа: 

loop i 0 10
    let myVar = 2 + 1
    print myVar

Вот мой код: 

open FParsec

// module IndentationParserWithoutBacktracking // see the link

// Utils

open IndentationParserWithoutBacktracking

let isBlank = fun c -> c = ' ' || c = '\t'
let ws  = spaces
let ws1 = skipMany1SatisfyL isBlank "whitespace"
let str s = pstring s .>> ws

let keyword str = pstring str >>? nextCharSatisfiesNot (fun c -> isLetter c || isDigit c) <?> str

// AST

type Identifier = Identifier of string

type InfixOp = 
    | Sum | Sub | Mul | Div | Pow | Mod
    | And | Or | Equal | NotEqual | Greater | Smaller | GreaterEqual | SmallerEqual

type Value =
    | Int of int
    | Float of float
    | Bool of bool
    | String of string
    | Char of char
    | Variable of Identifier

type Expr =
    | Literal of Value
    | Infix of Expr * InfixOp * Expr
    | List of Expr list
    | Tuple of Expr list

type Statement =
    | Expression of Expr
    | Let of Identifier * Statement list
    | Loop of Identifier * Expr * Expr * Statement list
    | Print of Identifier

// Literals

let numberFormat = NumberLiteralOptions.AllowMinusSign   ||| NumberLiteralOptions.AllowFraction |||
                   NumberLiteralOptions.AllowHexadecimal ||| NumberLiteralOptions.AllowOctal    |||
                   NumberLiteralOptions.AllowBinary      ||| NumberLiteralOptions.AllowPlusSign

let literal_numeric =
    numberLiteral numberFormat "number" |>> fun nl ->
        if nl.IsInteger then Literal (Int(int nl.String))
        else Literal (Float(float nl.String))

let literal_bool = 
    (choice [
        (stringReturn "true" (Literal (Bool true)))
        (stringReturn "false" (Literal (Bool false)))
    ]
    .>> ws) <?> "boolean"

let literal_string = 
    (between (pstring "\"") (pstring "\"") (manyChars (satisfy (fun c -> c <> '"')))
    |>> fun s -> Literal (String s)) <?> "string"

let literal_char = 
    (between (pstring "'") (pstring "'") (satisfy (fun c -> c <> '''))
    |>> fun c -> Literal (Char c)) <?> "character"

let identifier =
    (many1Satisfy2L isLetter (fun c -> isLetter c || isDigit c) "identifier"
    |>> fun i -> Identifier i) <?> "valid identifier"

let betweenParentheses p =
    (between (str "(") (str ")") p)

let variable = identifier |>> fun id -> Literal (Variable id)

let literal = (attempt literal_numeric  <|>
               attempt literal_bool     <|>
               attempt literal_char     <|>
               attempt literal_string   <|>
               attempt variable)        <?> "literal"

// Expressions

let pexpr, pexprimpl = createParserForwardedToRef()

let term =
    (ws >>. literal .>> ws) <|>
    (betweenParentheses (ws >>. pexpr)) <|>
    (ws >>. pexpr .>> ws)

let infixOperator (p: OperatorPrecedenceParser<_, _, _>) op prec map =
    p.AddOperator(InfixOperator(op, ws, prec, Associativity.Left, map))

let ops =
    // Arithmetic
    [ "+"; "-"; "*"; "/"; "%" ] @
    // Logical
    [ "&&"; "||"; "=="; "!="; ">"; "<"; ">="; "<=" ]

let opCorrespondance op =
    match op with
    // Arithmetic operators
    | "+"  -> Sum
    | "-"  -> Sub
    | "*"  -> Mul
    | "/"  -> Div
    | "%"  -> Mod
    // Logical operators
    | "&&" -> And
    | "||" -> Or
    | "==" -> Equal
    | "!=" -> NotEqual
    | ">"  -> Greater
    | "<"  -> Smaller
    | ">=" -> GreaterEqual
    | "<=" -> SmallerEqual

let opParser = new OperatorPrecedenceParser<_, _, _>()

for op in ops do
    infixOperator opParser op 1 (fun x y -> Infix(x, opCorrespondance op, y))

opParser.TermParser <- term

let list = between (str "[") (str "]") (sepBy pexpr (str ",")) |>> List

let tuple = between (str "(") (str ")") (sepBy pexpr (str ",")) |>> Tuple

let expression =
    opParser.ExpressionParser   <|> // I removed this line to don't have the mistake again.
    list                        <|>
    tuple                       <|>
    literal

pexprimpl := attempt expression

// Statements

let statements, statementsRef = createParserForwardedToRef()

let pexpression = expression |>> Expression

let plet =
    pipe2
        (keyword "let" >>. ws1 >>. identifier)
        (ws >>. str "=" >>. ws >>. statements)
        (fun id gtt exp -> Let(id, gtt, exp))

// From the link, but "revisited"
let ploop =
    pipe4
        (keyword "loop" >>. ws1 >>. identifier)
        (ws1 >>. literal) // If I put 'pexpr', it doesn't work too...
        (ws1 >>. literal)
        (statements)
        (fun id min max stmts -> Loop(id, min, max, stmts))

let print = keyword "print" >>. (ws1 >>. identifier |>> Print)

let statement =
    attempt plet        <|>
    attempt print       <|>
    attempt ploop       <|>
    attempt pexpression

statementsRef := indentedMany1 statement "statement"

let document = statements .>> spaces .>> eof

let test str =
    match runParserOnString document (UserState.Create()) "" str with
        | Success(result, _, _)   -> printfn "Success: %A" result
        | Failure(errorMsg, _, _) -> printfn "Failure: %s" errorMsg

System.Console.Clear()

test @"
loop i 0 10
    let myVar = 2 + 1
    print myVar
"

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

Мне бы очень хотелось понять свои ошибки, чтобы спроектировать парсер для очень маленького языка, похожего на ML.

Спасибо.

Редактировать

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

open IndentationParserWithoutBacktracking // So from the link

let isBlank = fun c -> c = ' ' || c = '\t'
let ws  = spaces
let ws1 = skipMany1SatisfyL isBlank "whitespace"
let str s = pstring s .>> ws

let keyword str = pstring str >>? nextCharSatisfiesNot (fun c -> isLetter c || isDigit c) <?> str

// AST

type Identifier = Identifier of string

type Value =
    | Int of int
    | Float of float
    | Bool of bool
    | String of string
    | Char of char
    | Variable of Identifier

// In FP, "all" is an expression, so:

type Expr =
    // Arithmetic + lists and tuple
    | Literal of Value
    | Infix of Expr * InfixOp * Expr
    | List of Expr list
    | Tuple of Expr list
    // Statements
    | Return of Expr
    | Loop of Identifier * Expr * Expr * Expr list
    | Print of Identifier
and InfixOp = 
    | Sum | Sub | Mul | Div | Pow | Mod
    | And | Or | Equal | NotEqual | Greater | Smaller | GreaterEqual | SmallerEqual

// Literals

let numberFormat = NumberLiteralOptions.AllowMinusSign   ||| NumberLiteralOptions.AllowFraction |||
                   NumberLiteralOptions.AllowHexadecimal ||| NumberLiteralOptions.AllowOctal    |||
                   NumberLiteralOptions.AllowBinary

let literal_numeric =
    numberLiteral numberFormat "number" |>> fun nl ->
        if nl.IsInteger then Literal (Int(int nl.String))
        else Literal (Float(float nl.String))

let literal_bool = 
    (choice [
        (stringReturn "true" (Literal (Bool true)))
        (stringReturn "false" (Literal (Bool false)))
    ]
    .>> ws) <?> "boolean"

let literal_string = 
    (between (pstring "\"") (pstring "\"") (manyChars (satisfy (fun c -> c <> '"')))
    |>> fun s -> Literal (String s)) <?> "string"

let literal_char = 
    (between (pstring "'") (pstring "'") (satisfy (fun c -> c <> '''))
    |>> fun c -> Literal (Char c)) <?> "character"

let identifier =
    (many1Satisfy2L isLetter (fun c -> isLetter c || isDigit c) "identifier"
    |>> fun i -> Identifier i) <?> "identifier"

let betweenParentheses p =
    (between (str "(") (str ")") p) <?> ""

let variable = identifier |>> fun id -> Literal (Variable id)

let literal = (attempt literal_numeric  <|>
               attempt literal_bool     <|>
               attempt literal_char     <|>
               attempt literal_string   <|>
               attempt variable)        <?> "literal"

// Expressions and statements

let pexprs, pexprimpl = createParserForwardedToRef()

// `ploop` is located here to force `pexprs` to be of the type `Expr list`, `ploop` requesting an expression list.
let ploop =
    pipe4
        (keyword "loop" >>. ws1 >>. identifier)
        (ws1 >>. literal)
        (ws1 >>. literal)
        (pexprs)
        (fun id min max stmts -> Loop(id, min, max, stmts))

// `singlepexpr` allows to use only one expression.
let singlepexpr =
    pexprs |>> fun ex -> ex.Head

let term =
    (ws >>. singlepexpr .>> ws) <|>
    (betweenParentheses (ws >>. singlepexpr)) <|>
    (ws >>. literal .>> ws) <|>
    (betweenParentheses (ws >>. literal))

let infixOperator (p: OperatorPrecedenceParser<_, _, _>) op prec map =
    p.AddOperator(InfixOperator(op, ws, prec, Associativity.Left, map))

let ops =
    // Arithmetic
    [ "+"; "-"; "*"; "/"; "%" ] @
    // Logical
    [ "&&"; "||"; "=="; "!="; ">"; "<"; ">="; "<=" ]

let opCorrespondance op =
    match op with
    // Arithmetic operators
    | "+"  -> Sum
    | "-"  -> Sub
    | "*"  -> Mul
    | "/"  -> Div
    | "%"  -> Mod
    // Logical operators
    | "&&" -> And
    | "||" -> Or
    | "==" -> Equal
    | "!=" -> NotEqual
    | ">"  -> Greater
    | "<"  -> Smaller
    | ">=" -> GreaterEqual
    | "<=" -> SmallerEqual

let opParser = new OperatorPrecedenceParser<Expr, unit, UserState>()

for op in ops do
    infixOperator opParser op 1 (fun x y -> Infix(x, opCorrespondance op, y))

opParser.TermParser <- term

let list = (between (str "[") (str "]") (sepBy singlepexpr (str ",")) |>> List) <?> "list"

let tuple = (between (str "(") (str ")") (sepBy singlepexpr (str ",")) |>> Tuple) <?> "tuple"

// Statements

// A commented `let` expression, commented for tests with the `return` instruction.

//let plet =
//    pipe3
//        (keyword "let" >>. ws1 >>. identifier)
//        (ws >>. gtt ":")
//        (ws >>. str "=" >>. ws >>. pexprs)
//        (fun id gtt exp -> Let(id, gtt, exp))

let preturn = 
    keyword "return" >>. ws >>. singlepexpr
    |>> fun ex -> Return ex

let print = keyword "print" >>. (ws1 >>. identifier |>> Print)

let instruction =
    print <|>
    ploop <|>
    preturn <|>

    opParser.ExpressionParser <|> // So we add the arithmetic, like x + y or 21 * 32 - 12 for example
    list <|>
    tuple <|>
    literal

pexprimpl := indentedMany1 instruction "instruction"

let document = pexprs .>> spaces .>> eof

let test str =
    match runParserOnString document (UserState.Create()) "" str with
        | Success(result, _, _)   -> printfn "%A" result
        | Failure(errorMsg, _, _) -> printfn "%s" errorMsg

System.Console.Clear()

// The test code that give an error of "newline" expecting
let code = test @"
return 2 + 1
"

А вот несколько скриншотов об ошибке:

enter image description here enter image description here enter image description here

1 Ответ

0 голосов
/ 10 декабря 2018

Причина, по которой indentedMany1 говорит вам, что он ожидает новой строки в вашем примере кода, заключается в том, что это то, что он ищет: отступ блок .Не выражение в одной строке.Так что ваша строка let myVar = 2 + 1 запутывает это.Если вы написали это как: 

let myVar =
    2 + 1

, то держу пари, что это сработает.

Я думаю, что вам нужно изменить синтаксический анализатор let, чтобы разрешить одну из двух вещей: либо выражение в одной строке, или блок операторов (ваш statements синтаксический анализатор).То есть что-то вроде: 

let pLetValue = expression <|> statements
let plet =
    pipe2
        (keyword "let" >>. ws1 >>. identifier)
        (ws >>. str "=" >>. ws >>. pLetValue)
        (fun id gtt exp -> Let(id, gtt, exp))

Обратите внимание, что я не проверял это, так как у меня сегодня не так много времени.Возможно, что вместо expression выше вы захотите attempt expression (или pexpr, что одно и то же).Немного поэкспериментируйте и посмотрите, что получится;и если вы полностью потерялись, пытаясь выяснить, как FParsec обрабатывает данное выражение, запомните совет, приведенный в http://www.quanttec.com/fparsec/users-guide/debugging-a-parser.html.

...