Разбор ML-подобного синтаксиса на основе отступа и всего, что считается инструкцией / выражением

Question

ПРИМЕЧАНИЕ. Не так давно я уже задавал аналогичный вопрос .Это не дублирование, но запрашиваемые разъяснения не попадают в сферу действия самого предмета.Поэтому я позволю себе открыть другую позицию, касающуюся анализа ML-подобного синтаксиса, основанного на отступе, и рассматривающего все как инструкцию / выражение.

Например: "Hello" является выражением, let foo = 2 + 1это инструкция, использующая выражение (2 + 1), print foo это инструкция, ...

Короче говоря, синтаксис и семантика, которые являются достаточно модульными и динамическими.Как и F # или OCaml.

Для этого я использую F # с API (доступно в nuget) FParsec.Вики FParsec предоставляет пример синтаксиса, основанного на отступе , поэтому я снова рассмотрел его.В приведенном ниже коде используется модуль IndentationParserWithoutBacktracking.

. Пример кода, который нужно проанализировать, использует элементарный отступ, не смешивая «литерал» и «инструкции / выражения»:

loop i 1 10
  loop k 1 10
    print k
  print i
print j

Простой код без контекста (но это сейчас не важно).

Моя реализация допускает такие коды, как:

let foo = a + b

let foo =
    let a = 9
    let b = 1
    a + b

let foo = 7

let foo =
    loop i 1 10
        print i

Например.(loop и print существуют только для тестов ...)

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

Это относится ко всемпримеры, упомянутые выше.Я не совсем понимаю проблему, и поэтому не знаю, как ее решить.

Вот код, протестированный для этого вопроса, он соответствует минимальным и функциональным критериям кода, однако, FParsec должен использоваться:

open FParsec

// This module come from 'https://github.com/stephan-tolksdorf/fparsec/wiki/Parsing-indentation-based-syntax-with-FParsec'
// I used the second module: 'IndentationParserWithoutBacktracking'

module IndentationParserWithoutBacktracking =

    let tabStopDistance = 8

    type LastParsedIndentation() =
        [<DefaultValue>]
        val mutable Value: int32
        [<DefaultValue>]
        val mutable EndIndex: int64

    type UserState = 
        {Indentation: int
         // We put LastParsedIndentation into the UserState so that we 
         // can conveniently use a separate instance for each stream.
         // The members of the LastParsedIndentation instance will be mutated
         // directly and hence won't be affected by any stream backtracking. 
         LastParsedIndentation: LastParsedIndentation}
        with
           static member Create() = {Indentation = -1
                                     LastParsedIndentation = LastParsedIndentation(EndIndex = -1L)}

    type CharStream = CharStream<UserState>
    type Parser<'t> = Parser<'t, UserState>

    // If this function is called at the same index in the stream
    // where the function previously stopped, then the previously
    // returned indentation will be returned again. 
    // This way we can avoid backtracking at the end of indented blocks.
    let skipIndentation (stream: CharStream) =    
        let lastParsedIndentation = stream.UserState.LastParsedIndentation
        if lastParsedIndentation.EndIndex = stream.Index then
            lastParsedIndentation.Value
        else
            let mutable indentation = stream.SkipNewlineThenWhitespace(tabStopDistance, false)
            lastParsedIndentation.EndIndex <- stream.Index
            lastParsedIndentation.Value <- indentation
            indentation

    let indentedMany1 (p: Parser<'t>) label : Parser<'t list> =
        fun stream ->
            let oldIndentation = stream.UserState.Indentation
            let indentation = skipIndentation stream
            if indentation <= oldIndentation then 
                Reply(Error, expected (if indentation < 0 then "newline" else "indented " + label))
            else
                stream.UserState <- {stream.UserState with Indentation = indentation}            
                let results = ResizeArray()
                let mutable stateTag = stream.StateTag
                let mutable reply = p stream // parse the first element
                let mutable newIndentation = 0
                while reply.Status = Ok 
                      && (results.Add(reply.Result)
                          newIndentation <- skipIndentation stream
                          newIndentation = indentation)
                   do
                     stateTag <- stream.StateTag
                     reply <- p stream
                if reply.Status = Ok 
                   || (stream.IsEndOfStream && results.Count > 0 && stream.StateTag = stateTag) 
                then
                    if newIndentation < indentation || stream.IsEndOfStream then
                        stream.UserState <- {stream.UserState with Indentation = oldIndentation}
                        Reply(List.ofSeq results)
                    else
                        Reply(Error, messageError "wrong indentation")
                else // p failed
                    Reply(reply.Status, reply.Error) 

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

// A value is just a literal or a data name, called here "Variable"
type Value =
    | Int of int   | Float of float
    | Bool of bool | String of string
    | Char of char | Variable of Identifier

// All is an instruction, but there are some differences:
type Instr =
    // Arithmetic
    | Literal of Value   | Infix of Instr * InfixOp * Instr
    // Statements (instructions needing another instructions)
    | Let of Identifier * Instr list
    | Loop of Identifier * Instr * Instr * Instr list
    // Other - the "print" function, from the link seen above
    | Print of Identifier
and InfixOp =
    // Arithmetic
    | Sum | Sub | Mul | Div
    // Logic
    | 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"
    |>> Identifier) <?> "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)

// Instressions and statements

let pInstrs, pInstrimpl = createParserForwardedToRef()

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

// `singlepInstr` allows to use only one Instression, used just after.
let singlepInstr =
    pInstrs |>> fun ex -> ex.Head

let term =
    (ws >>. singlepInstr .>> ws) <|>
    (betweenParentheses (ws >>. singlepInstr)) <|>
    (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
    // Logical operators
    | "&&" -> And           | "||" -> Or
    | "==" -> Equal         | "!=" -> NotEqual
    | ">"  -> Greater       | "<"  -> Smaller
    | ">=" -> GreaterEqual  | "<=" -> SmallerEqual
    | _ -> failwith ("Unknown operator: " + op)

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

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

opParser.TermParser <- term

// Statements

(*
- let:

        let <identifier> = <instruction(s) / value>

- print:

        print <identifier>

- loop:

        loop <identifier> <literal> <literal> <indented statements>

*)

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

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

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

    opParser.ExpressionParser <|>
    literal

pInstrimpl := indentedMany1 instruction "instruction"

let document = pInstrs .>> 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()

let code = test @"
let foo = a + b
"

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

В ожидании спасительного ответа, спасибо.

Answer 1

Чтобы понять, почему ваш парсер не работает, вам нужно изолировать проблемы.

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

let x = instruction
let b =
  instruction
  instruction

Если вы не можетечтобы ваша существующая реализация работала, я бы рекомендовал вернуться к реализации в вики и попытаться просто добавить поддержку оператора let.

Например, я заставил парсер Wiki принимать простые операторы let сследующие модификации:

type Statement = Loop of Identifier * int * int * Statement list
               | Print of Identifier
               | Let of Identifier * Statement list

let ws = skipManySatisfy isBlank
let str s = pstring s .>> ws

let statement, statementRef = createParserForwardedToRef()

let indentedStatements = indentedMany1 statement "statement"

let plet = keyword "let" >>. pipe2 (ws1 >>. identifier)
                                   (ws >>. str "=" >>. ws
                                    >>. (indentedStatements
                                         <|> (statement |>> fun s -> [s])))
                                   (fun id exp -> Let(id, exp))
statementRef := print <|> loop <|> plet

Обратите внимание, что в измененной версии statement теперь является анализатором, перенаправленным в ячейку ссылки, а не indentedStatements.

Обратите внимание, что ws не реализован с spaces, как в вашем парсере.Это важно, потому что spaces также использует новые строки, что помешает indentedMany1 видеть новую строку и правильно рассчитывать отступ.

Причина, по которой ваш синтаксический анализатор выдал ошибку "Expecting: newline", заключается в том, что indentedMany1 нужна новая строка в начале последовательности с отступом, чтобы можно было рассчитать отступ.Вам придется изменить реализацию indentedMany1, если вы хотите поддержать, например, следующий шаблон отступа:

let x = instruction
        instruction
        instruction