Хвост-рекурсия в FParsec - PullRequest
Новая
       36

Хвост-рекурсия в FParsec

3 голосов
/ 12 февраля 2012

У меня возникла проблема с парсерами, имеющими две ветви рекурсии. Чтобы продемонстрировать проблему проще, я использую простую грамматику лямбда-исчисления из статьи, написанной Лукой Болоньезе в качестве примера: 

<expression> ::= <name> | <function> | <application>  
<name> ::= non­blank character sequence  
<function> ::= \ <name> . <body>  
<body> ::= <expression>  
<application> ::= ( <function expression> <argument expression> )  
<function expression> ::= <expression>  
<argument expression> ::= <expression>

Парсер в статье довольно лаконичен: 

let ws = " \t\n" 
let specialChars = ".)(\\\n" 

let pWs = spaces 
let pName = manyChars (noneOf (ws + specialChars)) |>> EName 

let pExpr, pExprRef = createParserForwardedToRef<Expression, Unit>() 

let curry2 f a b = f(a,b) 
let pFunction = pchar '\\' >>. pipe2 pName (pchar '.' >>. pExpr) (curry2 Function) 

let pApplication = pchar '(' >>. pipe2 pExpr (pWs >>. pExpr) (curry2 Application)
                            .>> pWs .>> pchar ')'

do pExprRef := pFunction <|> pApplication <|> pName 

let pExpressions = sepBy pExpr spaces1 

let fparseString text = 
    match run pExpressions text with 
    | Success(result, _, _)   -> result 
    | Failure(errorMsg, _, _) -> failwith (sprintf "Failure: %s" errorMsg)

Я заинтересован в pApplication, поскольку они состоят из двух pExpr с, что, в свою очередь, также может составлять pApplication с. Синтаксическому анализатору не хватает места в стеке в следующем тесте: 

let generateString level =
    let rec loop i =
        seq {
                if i < level then
                    yield "("
                    yield! loop level
                    yield " "
                    yield! loop (i+1)
                    yield ")"
                else 
                    yield "(x x)"
        }
    loop 0 |> String.concat ""

let N = 5000
let s = generateString N;; 
let _ = fparseString s;;

Как переписать синтаксический анализатор так, чтобы он был хвостово-рекурсивным?

Я обнаружил проблему при попытке написать парсер для языка, похожего на Лисп, и проверить его на реальных тестах. У меня есть Term и VarBinding, которые являются взаимно рекурсивными типами, и let синтаксический анализатор, который показывает ту же проблему, что и pApplication выше. Мой синтаксический анализатор на github на случай, если анализ неверен в отношении нерекурсивной проблемы.

1 Ответ

6 голосов
/ 13 февраля 2012

Встроенные синтаксические анализаторы FParsec, как правило, не допускают реализации хвостово-рекурсивного синтаксического анализатора, главным образом из-за способа обработки ошибок.

Это означает, что глубина рекурсии синтаксического анализатора FParsec ограничена размером стека, как в случае большинства анализаторов рекурсивного спуска. Конечно, это не влияет на разбор последовательностей с many, sepBy, chainl и т. Д., Потому что все эти комбинаторы FParsec имеют реализации с постоянным использованием стека.

Размер стека по умолчанию в .NET обычно более чем достаточен для анализа созданного человеком ввода в хорошо определенных форматах с помощью FParsec (при условии, что вы анализируете последовательности с помощью встроенных комбинаторов). Однако сгенерированный машиной ввод с глубоко вложенной структурой (например, ваши s-выражения уровня 5000) может легко привести к переполнению стека.

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

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

...