Рекурсивные грамматики в FParsec - PullRequest
Новая
       34

Рекурсивные грамматики в FParsec

10 голосов
/ 31 мая 2011

Я решил проверить FParsec и попытался написать синтаксический анализатор для λ-выражений. Оказывается, рвение затрудняет рекурсивный анализ. Как я могу решить это?

Код: 

open FParsec

type λExpr =
    | Variable of char
    | Application of λExpr * λExpr
    | Lambda of char * λExpr

let rec FV = function
    | Variable v -> Set.singleton v
    | Application (f, x) -> FV f + FV x
    | Lambda (x, m) -> FV m - Set.singleton x

let Λ0 = FV >> (=) Set.empty

let apply f p =
    parse
        { let! v = p
          return f v }

let λ e =

    let expr, exprR = createParserForwardedToRef()

    let var = lower |> apply Variable

    let app = tuple2 expr expr
                 |> apply Application

    let lam = pipe2 (pchar 'λ' >>. many lower)
                        (pchar '.' >>. expr) (fun vs e ->
                                                List.foldBack (fun c e -> Lambda (c, e)) vs e)

    exprR := choice [
                    lam
                    app
                    var
                    (pchar '(' >>. expr .>> pchar ')')
                    ]

    run expr e

Спасибо!

1 Ответ

8 голосов
/ 01 июня 2011

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

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

Вы можете объединить правила для приложения и переменной следующим образом: 

let rec varApp = parse {
  let! first = lower |> apply Variable
  let! res = 
    choice [ expr |> apply (fun e -> Application(first, e))
             parse { return first } ]
  return res }

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

and lam = 
  pipe2 (pchar 'λ' >>. many lower)
        (pchar '.' >>. expr) (fun vs e ->
    List.foldBack (fun c e -> Lambda (c, e)) vs e)
and brac = pchar '(' >>. expr .>> pchar ')'
and expr = parse.Delay(fun () ->
  choice 
    [ lam; varApp; brac ])

Я просто избежал необходимости явной мутации, используя parse.Delay() (что позволяет создавать рекурсивные ссылки на значения). В принципе это можно записать так: 

and expr = parse {
  return! choice [ lam; varApp; brac ] }

... но по какой-то причине FParsec не реализует элемент ReturnFrom, который необходим, если вы хотите использовать return! в выражениях вычислений.

...