"Модель вычислений для класса Parsing Expression Languages"

Класс языков, известный сейчас как Parsing Expression Languages (PEL) был открыт в 60-х годах А. Бирманом и Дж. Ульманом. Они построили формализм (top-down parsing languages), который расширял LL-грамматики и был удобен для описания синтаксиса языка программирования; они же предложили линейный алгоритм парсинга (построения дерева разбора) для этой модели, однако в те годы он был неприменим на практике из-за ограниченной у ЭВМ памяти. В 2000-х годах Б. Форд расширил усовершенствовал этот формализм до Parsing Expression Grammars, которые нашли широкое практическое применение и дал определение класса PEL, доказав эквивалентность своего формализма с формализмом Бирмана и Ульмана. В докладе будет рассказано о модели вычислений для класса PEL, получающейся модификацикей детерминированного магазинного автомата; с её помощью устанавливаются интересные структурные свойства этого класса. Доказывается замкнутость класса PEL относительно левой конкатенации с языками из класса регулярное замыкание детеримнированных КС-языков (RDCFL); из этого результата следует, что булево замыкание класса RDCFL распознаётся за линейное время в RAM-модели, что усиливает ранее известный результат о линейном распознавании класса RDCFL.