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

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

<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;;

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

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


.net f# tail-recursion fparsec
person pad    schedule 12.02.2012    source источник

Ответы (1)


arrow_upward
6
arrow_downward

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

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

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

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

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

person Stephan Tolksdorf    schedule 12.02.2012
comment
К сожалению, все тесты, которые я использую, созданы машиной. Поскольку язык должен быть дружественным к машинам и простым для анализа, я не могу предсказать глубину вложенности. Можете ли вы пролить свет на то, как реализовать парсеры на основе кучи с помощью низкоуровневого API? - person pad; 13.02.2012
comment
Контрольные показатели не обязательно должны отражать использование в реальном мире и могут быть просто созданы искусственно для стресс-тестирования синтаксического анализатора. У меня есть подозрение, что глубина вложенности в несколько тысяч уровней на практике очень редка (мне было бы очень интересно услышать о любых реальных входных данных, которые содержат такую ​​вложенность). Прежде чем переписывать свой синтаксический анализатор, я бы убедился, что просто установить стек на 10 или даже 50 МБ действительно недостаточно. - person Stephan Tolksdorf; 13.02.2012
comment
Сказав это, если вы действительно хотите переписать свой синтаксический анализатор, просто подумайте о том, как бы вы реализовали синтаксический анализатор, если бы вы вручную анализировали непосредственно из строки. Низкоуровневый синтаксический анализатор FParsec будет выглядеть очень похоже, только с заменой строкового доступа вызовами метода CharStream и конечным результатом или ошибкой, возвращаемой в значении Reply. Для не-(глубоко)рекурсивных частей грамматики вы, конечно, можете использовать обычные парсеры FParsec. Может быть, позже у меня будет время, чтобы реализовать пример. - person Stephan Tolksdorf; 13.02.2012
comment
+1, я попробую с большим пространством стека. Небольшой пример, демонстрирующий хвостовую рекурсию, был бы очень полезен. - person pad; 13.02.2012
comment
Хорошие новости: когда я увеличиваю лимит стека до 50 МБ, я могу успешно анализировать 40000 тестов, некоторые из которых имеют довольно глубокую вложенность. Спасибо за прекрасную библиотеку. Однако меня все еще интересует пример хвостовой рекурсии. - person pad; 14.02.2012