Есть ли простой способ заставить lexing и parsing работать одновременно при использовании fslex и fsyacc?
Лексинг и синтаксический анализ одновременно в F #
Ответ 1
Прежде всего, в реальном случае лексирование и синтаксический анализ являются критическими по времени. Особенно, если вам нужно обработать токены перед разбором. Например - фильтрация и сбор комментариев или разрешение конфликтов, зависящих от контекста. В этом случае парсер часто ждет лексера.
Ответ на вопрос. Вы можете запускать лексирование и синтаксический анализ одновременно с MailboxProcessor.
Ядро идеи. Вы можете запустить lexer в mailBoxProcessor. Lexer должен создавать новые маркеры, обрабатывать и публиковать их. Lexer часто быстрее, чем парсер, и иногда он должен ждать анализатора. При необходимости Parser может получить следующий токен. Код приведен ниже. Вы можете изменить таймауты, 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-трансляторе.