Рекурсивный анализатор спуска и функциональное программирование

Ответ 1

Ответ, полученный из этой статьи в блоге:

Итак, мой вопрос: как выглядит более традиционный функциональный подход к разбору (т.е. несколько побочных эффектов)?

Похоже, вам нужно отделить функциональность (как в Lisp, схеме, стандартном ML, CAML, OCaml, F #) от чистоты (отсутствие побочных эффектов, как в Haskell) и случайные языковые особенности (алгебраические типы данных, сопоставление образцов).

Благодаря алгебраическим типам данных, сопоставлению шаблонов и функциям более высокого порядка, F # хорошо подходит для синтаксического анализа и отлично подходит для преобразований и генерации кода, но большинство парсеров, написанных на F #, не являются чистыми. Исторически сложилось так, что семейство языков F # в основном выведено из (MetaLanguages ​​или MLs) были специально созданы для такого метапрограммирования.

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

> let rec (|Term|_|) = function
    | Factor(e1, t) ->
        let rec aux e1 = function
          | '+'::Factor(e2, t) -> aux (e1 + e2) t
          | '-'::Factor(e2, t) -> aux (e1 - e2) t
          | t -> Some(e1, t)
        aux e1 t
    | _ -> None
  and (|Factor|_|) = function
    | '-'::Factor(e, t) -> Some(-e, t)
    | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
    | Atom(e, t) -> Some(e, t)
    | _ -> None
  and (|Atom|_|) = function
    | c::t when '0'<=c && c<='9' -> Some(int(string c), t)
    | '('::Term(e, ')'::t) -> Some(e, t)
    | _ -> None;;
val ( |Term|_| ) : char list -> (int * char list) option
val ( |Factor|_| ) : char list -> (int * char list) option
val ( |Atom|_| ) : char list -> (int * char list) option

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

> let (Term e) = List.ofSeq "1+2*(3-4)*-5";;
val e : int * char list = (11, [])

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

type expr =
  | Int of int
  | Neg of expr
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

  static member (~-) f = Neg f
  static member (+) (f, g) = Add(f, g)
  static member (-) (f, g) = Sub(f, g)
  static member (*) (f, g) = Mul(f, g)

let rec (|Term|_|) = function
  | Factor(e1, t) ->
      let rec aux e1 = function
        | '+'::Factor(e2, t) -> aux (e1 + e2) t
        | '-'::Factor(e2, t) -> aux (e1 - e2) t
        | t -> Some(e1, t)
      aux e1 t
  | _ -> None
and (|Factor|_|) = function
  | '-'::Factor(e, t) -> Some(-e, t)
  | Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
  | Atom(e, t) -> Some(e, t)
  | _ -> None
and (|Atom|_|) = function
  | c::t when '0'<=c && c<='9' -> Some(Int(int(string c)), t)
  | '('::Term(e, ')'::t) -> Some(e, t)
  | _ -> None

let (Term e) = List.ofSeq "1+2*(3-4)*-5"

Обратите внимание, что требуется только одно небольшое изменение в парсере, поскольку AST также может быть сконструирован с использованием операторов +, - и *.

Во-вторых, стоит ли попытаться применить функциональный подход к синтаксическому анализу, или действительно ли это на оптимизации промежуточного кода, который светят функциональные языки, и я просто еще не получил его?

Вы говорите о чистоте, а не о функциональном программировании. Чистота не особенно полезна в контексте анализа текста и, по сути, может быть реальным препятствием (например, интернированные символы - это кошмар в Haskell). Тем не менее, F # имеет много других преимуществ, которые делают это хорошо для этого набора проблем. В частности, хотя другие языки, такие как OCaml, имеют гораздо лучшие инструменты для синтаксического анализа, я думаю, что F # - лучший язык .NET в этом контексте.

То есть, должен ли я fuddle через разбор в F #, используя императивный стиль, и переключиться на более функциональный подход позже?

В зависимости от того, что вы хотите сделать функциональным. Я бы использовал fslex и fsyacc с чистым кодом для создания АСТ в действиях, но примеси для чего-либо вроде хеша или создания уникальных идентификаторов.

Вы можете оценить следующие статьи, которые я написал на эту тему в этом блоге (note paywall):

• "Анализ текста с помощью Lex и Yacc" (30 сентября 2007 г.).
• "Оптимизация простого интерпретатора байт-кода" (31 октября 2007 г.).
• "Комбинаторы парсеров" (30 ноября 2007 г.).
• "Языковое программирование: интерпретатор уровня" (31 декабря 2007 г.).
• "Языковое программирование: перестановка сроков" (16 августа 2008 г.).
• "Генерация кода времени выполнения с использованием System.Reflection.Emit" (31 августа 2008 г.).
• "Анализ и визуализация бинарных данных географической информационной системы" (30 ноября 2009 г.).

Ответ 2

Одной из стратегий функционального анализа является монодичный комбинатор парсеров. Вы можете прочитать об этом здесь (и следовать ссылкам) или использовать библиотеку, например FParsec. Я не рекомендую этот подход, если вы просто учите/начинаете F #/компиляторы.

Другой подход с F # заключается в использовании FsLex/FsYacc (в PowerPack). Я немного ненавижу технологию Lex/Yacc, поэтому я также не рекомендую это.

Я думаю, что вы должны написать рекурсивный приличный парсер вручную. У меня нет сильных чувств по отношению к токенизатору, но просто пометить весь файл в (n неизменяемый) list токенов, а затем сделать рекурсивный спуск (и использовать некоторое сопоставление с образцом) - это хороший способ справиться с разбором, И, конечно же, вы захотите использовать дискриминированные союзы для представления вывода АСТ анализатора (a la здесь).

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

ИЗМЕНИТЬ

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

// AST for tiny language
type Op = 
    | Plus 
    | Minus 
type Expr = 
    | Literal of int 
    | BinaryOp of Expr * Op * Expr // left, op, right 
type Stmt =
    | IfThenElse of Expr * Stmt * Stmt // cond, then, else; 0=false in cond 
    | Print of Expr

// sample program
let input = @"
    if 1+1-1 then 
        print 42 
    else 
        print 0"

// expected AST
let goal = 
    IfThenElse(
        BinaryOp( BinaryOp(Literal(1),Plus,Literal(1)), Minus, Literal(1)), 
        Print(Literal(42)), 
        Print(Literal(0))) 

////////////////////////////////////////////////////////////////////////////
// Lexer

type Token =
    | IF
    | THEN
    | ELSE
    | PRINT
    | NUM of int  // non-negative
    | PLUS
    | MINUS
    | EOF

let makeTokenizer (s:string) =
    let i = ref 0
    let keywords = [
        "if", IF 
        "then", THEN
        "else", ELSE
        "print", PRINT
        "+", PLUS
        "-", MINUS ]
    let rec getNextToken() =
        if !i >= s.Length then
            EOF
        elif System.Char.IsWhiteSpace(s.[!i]) then
            incr i
            getNextToken()
        elif System.Char.IsDigit(s.[!i]) then
            let mutable j = !i
            while j < s.Length && System.Char.IsDigit(s.[j]) do
                j <- j + 1
            let numStr = s.Substring(!i, j - !i)
            i := j
            NUM(System.Int32.Parse(numStr)) // may throw, e.g. if > MAXINT
        else 
            let keyword = keywords |> List.tryPick (fun (kwStr,kwTok) ->
                if s.IndexOf(kwStr, !i) = !i then
                    i := !i + kwStr.Length
                    Some(kwTok)
                else
                    None)
            match keyword with
            | Some k -> k
            | None -> 
                failwith "unexpected char '%c' at position %d" s.[!i] !i
    getNextToken

let tokens = 
    let nextToken = makeTokenizer input
    let t = ref(nextToken())
    [ 
        yield !t
        while !t <> EOF do
            t := nextToken()
            yield !t
    ]

printfn "%A" tokens // sanity check our tokenizer works

/////////////////////////////////////////////////////////////////////////
// Parser

let parseExpr toks =
    match toks with
    | NUM x :: rest ->
        let mutable rest = rest
        let mutable expr = Literal x
        while rest.Head = PLUS || rest.Head = MINUS do
            let op,y,r = 
                match rest with
                | PLUS::NUM y::t -> Plus, Literal y, t
                | MINUS::NUM y::t -> Minus, Literal y, t
                | _ -> 
                    failwith "parse error in expression, expected number"
            expr <- BinaryOp(expr, op, y)
            rest <- r
        expr, rest
    | _ -> failwith "parse error in expression, expected number"
let rec parseStmt toks =
    match toks with
    | PRINT :: rest -> 
        let e,rest = parseExpr(rest)
        Print(e), rest
    | IF :: rest ->
        let e,rest = parseExpr(rest)
        match rest with
        | THEN :: rest ->
            let s1,rest = parseStmt(rest)
            match rest with
            | ELSE :: rest ->
                let s2,rest = parseStmt(rest)
                IfThenElse(e,s1,s2), rest
            | _ -> 
                failwith "parse error after if branch, espected 'else'"
        | _ -> 
            failwith "parse error after if expression, expected 'then'"
    | _ -> failwith "parse error, expected statement"
let parseProgram toks =
    let s,rest = parseStmt toks
    match rest with
    | [EOF] -> s
    | _ -> failwith "parse error after statement, expected EOF"

let p = parseProgram tokens
printfn "%A" p
assert( p = goal )

(Надеюсь, нет вопиющих ошибок.)

Ответ 3

Ответ 4

Более простой ответ, чем другие хорошие ответы:

Парсер в языке функций берет поток токенов в дерево разбора и остальную часть токена. То есть, он имеет тип

 token list -> ast * token list

Рекурсивный достойный парсер обычно имеет большое количество функций этого типа, который ест токен потока, а затем строит небольшую часть дерева синтаксического анализа. Вызывая их рекурсивно (рекурсивный порядочный), вы получаете то, что хотите.

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

Ответ 5

Я работаю над компилятором ECMAScript в F # некоторое время, поэтому я нахожусь в той же лодке, что и вы. Возможно, некоторые из моих работ могут вам помочь. Вот простая библиотека комбинаторов парсеров, над которой я работаю в сочетании с FParsec. Здесь нет идеального места, но он должен дать вам что-то достаточно простое для изучения, чтобы вы могли перейти к более продвинутым вещам. Если вы в конечном итоге используете FParsec, вы можете заметить, что здесь было вдохновлено много вещей.

module Tools =

    open System
    open System.Diagnostics
    open LazyList 

    [<Struct;DebuggerStepThrough>]
    type State<'a, 'b> (input:LazyList<'a>, data:'b) = //'
        member this.Input = input
        member this.Data = data

    type Result<'a, 'b, 'c> = //'
    | Success of 'c * State<'a, 'b>
    | Failure of list<string> * State<'a, 'b>    

    type Parser<'a, 'b, 'c> = //' 
        State<'a, 'b> -> seq<Result<'a, 'b, 'c>>

    let zero<'a, 'b, 'c> (state:State<'a, 'b>) = //'
        Seq.empty<Result<'a, 'b, 'c>>

    let item<'a, 'b> (state:State<'a, 'b>) = seq { //'
        match state.Input with
        | Cons (head, tail) ->
            yield Success(head, State (tail, state.Data))
        | Nil -> ()
    } 

    let result<'a, 'b, 'c> (value:'c) (state:State<'a, 'b>) = seq  { //'
        yield Success (value, state)
    }

    let run p i d =
        p (State(i, d)) 

    let (>>=) (m:Parser<'a, 'b, 'c>) (f:'c -> Parser<'a, 'b, 'd>) (state:State<'a, 'b>) = //'
        let rec run errors = seq {
            for r in m state do
                match r with
                | Success (v, s) ->
                    yield! f v s
                | Failure (ms, s) ->
                    yield! run (errors @ ms)
        }
        run []

    let (<|>) (l:Parser<'a, 'b, 'c>) (r:Parser<'a, 'b, 'c>) (state:State<'a, 'b>) = //'  
        let rec run p = seq {
            for result in p state do
                match result with
                | Success (_, _) ->
                    yield result
                | Failure (_, _) -> ()
        }
        Seq.append (run l) (run r)

    type ParseMonad() =        
        member this.Bind (f:Parser<'a, 'b, 'c>, g:'c -> Parser<'a, 'b, 'd>) : Parser<'a, 'b, 'd> = f >>= g //'     
        member this.Combine (f, g) = f <|> g      
        member this.Delay (f:unit -> Parser<'a, 'b, 'c>) (state:State<'a, 'b>) = f () state //'
        member this.Return x = result x
        member this.ReturnFrom p = p
        member this.Zero () = zero

    let parse = ParseMonad()

    let (|>>) (parser:Parser<'a, 'b, 'c>) (f:'c -> 'd) = parse { //'
        let! v = parser
        return f v   
    }

    let satisfy predicate = parse {
        let! value = item
        if predicate value then
            return value 
    }

    let maybe parser = parse {
        return! parser |>> Some <|> result None 
    }

    let choice (ps:seq<Parser<'a, 'b, 'c>>) (state:State<'a, 'b>) = seq { //'
        if not (LazyList.isEmpty state.Input) then
            for p in ps do
                yield! p state    
    }

    let between left right parser =
        parse {
            let! _ = left
            let! v = parser
            let! _ = right
            return v
        }

    let skip p = parse {
        let! v = p
        return ()
    }

    let many parser = 
        let rec many result = parse {
            let! v = parser
            let result = v::result
            return! many result
            return result    
        }
        many []

    let many1 parser = parse {
        let! r = many parser
        if not r.IsEmpty then
            return r
    }

    let manyFold parser start (f:_ -> _ -> _) = parse {
        let! r = many parser
        return r |> List.fold f start
    }

    let many1Fold parser start (f:_ -> _ -> _) = parse {
        let! r = many1 parser
        return r |> List.fold f start
    } 

    let isNotFollowedBy p =
        parse {
            let! v = maybe p
            match v with
            | Some _ -> ()
            | None -> return ()
        }

    let pipe2 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (f:'c -> 'd -> 'e) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            return f v1 v2
        }

    let pipe3 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (f:'c -> 'd -> 'e -> 'f) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            return f v1 v2 v3
        }

    let pipe4 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (f:'c -> 'd -> 'e -> 'f -> 'g) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            return f v1 v2 v3 v4
        }

    let pipe5 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (p5:Parser<'a, 'b, 'g>) (f:'c -> 'd -> 'e -> 'f -> 'g -> 'h) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            let! v5 = p5
            return f v1 v2 v3 v4 v5
        }

    let tuple2<'a, 'b, 'c, 'd, 'e> (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (f:'c * 'd -> 'e) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            return f (v1, v2)
        }

    let tuple3 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (f:'c * 'd * 'e -> 'f) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            return f (v1, v2, v3)
        }

    let tuple4 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (f:'c * 'd * 'e * 'f -> 'g) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            return f (v1, v2, v3, v4)
        }

    let tuple5 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (p5:Parser<'a, 'b, 'g>) (f:'c * 'd * 'e * 'f * 'g -> 'h) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            let! v5 = p5
            return f (v1, v2, v3, v4, v5)
        }

    let createParserRef<'a, 'b, 'c> () = //'
        let dummyParser = fun state -> failwith "a parser was not initialized"
        let r = ref dummyParser
        (fun state -> !r state), r : Parser<'a, 'b, 'c> * Parser<'a, 'b, 'c> ref //'

ПРИМЕЧАНИЕ. Вам понадобится FSharp PowerPack для типа LazyList.

Пример:

and conditionalExpressionNoIn = 
    parse {
        let! e1 = logicalORExpressionNoIn
        return! parse {
            do! skip expectQuestionMark
            let! e2 = assignmentExpression
            do! skip expectColon
            let! e3 = assignmentExpressionNoIn
            return ConditionalExpressionNoIn (e1, e2, e3)
        }
        return ConditionalExpressionNoIn (e1, SourceElement.Nil, SourceElement.Nil)
    }