如何使FsLex规则尾递归/防止StackOverflowExceptions

Question

我正在用fslex / fsyacc实现一种脚本语言，并且存在大量用户输入(即>1k脚本)的问题，特别是当lexer分析一个非常大的字符串时，就会发生此错误。

我扫描自定义的lexer函数中的字符串(允许用户用反斜杠转义字符，如引号)。以下是功能：

and myText pos builder = parse 
| '\\' escapable                 { let char = lexbuf.LexemeChar(1)
                                   builder.Append (escapeSpecialTextChar char) |> ignore
                                   myText pos builder lexbuf 
| newline                        { newline lexbuf; 
                                   builder.Append Environment.NewLine |> ignore 
                                   myText pos builder lexbuf 
                                 }
| (whitespace | letter | digit)+ { builder.Append (lexeme lexbuf) |> ignore
                                   myText pos builder lexbuf     
                                 } // scan as many regular characters as possible
| '"'                            { TEXT (builder.ToString())   } // finished reading myText
| eof                            { raise (LexerError (sprintf "The text started at line %d, column %d has not been closed with \"." pos.pos_lnum (pos.pos_cnum - pos.pos_bol))) }
| _                              { builder.Append (lexbuf.LexemeChar 0) |> ignore
                                   myText pos builder lexbuf 
                                 } // read all other characters individually

函数只解释不同的字符，然后递归地调用自己--或者在读取结束引号时返回读字符串。当输入太大时，将在_或(whitespace | ...规则中抛出一个(whitespace | ...。

生成的Lexer.fs包含以下内容：

(* Rule myText *)
and myText pos builder (lexbuf : Microsoft.FSharp.Text.Lexing.LexBuffer<_>) = _fslex_myText pos builder 21 lexbuf
// [...] 

and _fslex_myText pos builder _fslex_state lexbuf =
  match _fslex_tables.Interpret(_fslex_state,lexbuf) with
  | 0 -> ( 
# 105 "Lexer.fsl"
                                                   let char = lexbuf.LexemeChar(1) in
                                                   builder.Append (escapeSpecialTextChar char) |> ignore
                                                   myText pos builder lexbuf 
// [...]

因此，实际的规则变成了_fslex_myText，myText用一些内部_fslex_state来调用它。

我认为这就是问题所在：myText不是尾递归的，因为它被转换成两个相互调用的函数，这在某种程度上导致了一个StackOverflowException。

，所以我的问题是：

1)我的假设正确吗？或者，F#编译器可以像对尾递归函数那样优化这两个函数，生成一个while循环而不是递归调用吗？(函数式编程对我来说还是新的)

2)如何使函数尾递归/防止StackOverflowException？FsLex文档没有那么广泛，我也不知道官方的F#编译器有什么不同--显然它在大字符串方面没有问题，但是它的字符串规则也是递归地调用自己，所以我在这里感到很困惑:/

Answer 1

正如所写的，您的myText函数似乎没有问题-- F#编译器应该能够进行尾递归。

有一件事需要检查--您是在Debug或Release配置中编译/运行这个程序吗？默认情况下，F#编译器只在Release配置中进行尾调用优化。如果在调试时希望进行尾调用，则需要在项目的属性(在Build选项卡上)中显式地启用该功能。