Лексирование и разбор одновременно в F#

Question

Есть ли простой способ заставить lexing и синтаксический анализ работать одновременно при использовании fslex и fsyacc?

Answer 1

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

Ответ на вопрос. Вы можете запускать lexing и анализ одновременно с MailboxProcessor.

Суть идеи. Вы можете запустить лексер в mailBoxProcessor. Lexer должен производить новые токены, обрабатывать и публиковать их. Лексер часто быстрее парсера, а иногда его стоит дождаться парсера. Парсер может получить следующий токен при необходимости. Код предоставлен ниже. Вы можете изменить тайм-ауты, 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 переводчика.