在F#中同时进行词法分析和语法分析

Question

使用fslex和fsyacc时，有没有一种简单的方法可以使词法分析和语法分析并发运行？

- J D

---

@MSX：性能。词法分析和语法分析通常是性能关键（IME），并且通常每个过程需要约50％的总时间，因此在一个核心上进行词法分析，并在另一个核心上同时解析词法标记可以提供潜在的2倍速度提升。同样，压缩/解压缩和磁盘IO都可能是性能关键，并且可以同时执行。尽管存在这种潜力，但似乎没有办法在不进行大规模重写的情况下使用F#和/或.NET来实现这一点。 - J D

好的，我没有考虑到那个。我刚刚给你的问题投了赞成票。据我所知，在fslex和fsyacc中无法完成这个操作。 - MSX

@JonHarrop 我目前正在进行你提到的大规模重写：请查看我的fsharp-tools项目。我正在努力让我的新工具与fslex和fsyacc保持一致，一旦完成，我计划实现新的后端（用于生成实现词法分析器/语法分析器的F#代码）。如果您仍然对此感兴趣，请在该项目上开启一个Github问题，以便我们进一步讨论。 - Jack P.

您是在询问以下两种情况中的哪一种：1）使用多个处理器来解析单个输入文件，还是2）使用多个处理器来解析不同的文件，其中每个文件在单个处理器上解析？ - Sam Harwell

据我所知，对于大多数编译器/程序而言，词法分析和语法分析并不是时间关键的步骤。它们都以O(n)的复杂度运行，其中n是输入的大小，而例如语义分析、活跃性分析和平铺则需要更多的时间。 - Willem Van Onsem

Answer 1

首先，在实际情况中，词法分析和语法分析非常关键。特别是如果您需要在解析之前处理令牌。例如--过滤和收集注释或解决上下文相关的冲突。在这种情况下，解析器经常等待词法分析器。

回答问题的答案。您可以使用MailboxProcessor并发运行词法分析和语法分析。

核心思想。您可以在mailBoxProcessor中运行词法分析器。词法分析器应该生成新的标记，处理并发布它们。词法分析器通常比解析器更快，并且有时应该等待解析器。解析器可以在必要时接收下一个标记。以下提供了代码。您可以修改超时时间，traceStep以找到最佳解决方案。

[<Literal>]
let traceStep = 200000L

let tokenizerFun = 
    let lexbuf = Lexing.LexBuffer<_>.FromTextReader sr                        
    let timeOfIteration = ref System.DateTime.Now
    fun (chan:MailboxProcessor<lexer_reply>) ->
    let post = chan.Post 
    async {
        while not lexbuf.IsPastEndOfStream do
            lastTokenNum := 1L + !lastTokenNum
            if (!lastTokenNum % traceStep) = 0L then 
                let oldTime = !timeOfIteration
                timeOfIteration := System.DateTime.Now
                let mSeconds = int64 ((!timeOfIteration - oldTime).Duration().TotalMilliseconds)
                if int64 chan.CurrentQueueLength > 2L * traceStep then                                                                                  
                    int (int64 chan.CurrentQueueLength * mSeconds / traceStep)  |> System.Threading.Thread.Sleep      
            let tok = Calc.Lexer.token lexbuf
            // Process tokens. Filter comments. Add some context-depenede information.
            post tok
    }   

use tokenizer =  new MailboxProcessor<_>(tokenizerFun)

let getNextToken (lexbuf:Lexing.LexBuffer<_>) =
    let res = tokenizer.Receive 150000 |> Async.RunSynchronously
    i := 1L + !i 

    if (!i % traceStep) = 0L then 
        let oldTime = !timeOfIteration
        timeOfIteration := System.DateTime.Now
        let seconds = (!timeOfIteration - oldTime).TotalSeconds          
    res

let res =         
    tokenizer.Start()            
    Calc.Parser.file getNextToken <| Lexing.LexBuffer<_>.FromString "*this is stub*"

完整解决方案在此处可用：https://github.com/YaccConstructor/ConcurrentLexPars 在此解决方案中，我们仅展示了所述想法的完整实现。性能比较不是实际的，因为语义计算非常简单且没有标记处理。

要查找性能比较结果，请查看完整报告https://docs.google.com/document/d/1K43g5jokNKFOEHQJVlHM1gVhZZ7vFK2g9CJHyAVtUtg/edit?usp=sharing。在这里，我们比较顺序和并发解析器的 T-SQL 子集的性能。顺序：27秒，同时：20秒。

此外，我们在生产 T-SQL 翻译器中使用此技术。

- gsv