Тема: Сложность преобразования LL(k) линейных грамматик и конъюнктивных LL(k) линейных к LL(1) линейным

ЬЬ(к)-анализ — один из самых известных методов синтаксического анализа, работающих за линейное время. В этом методе дерево разбора последовательно восстанавливается сверху вниз, по мере чтения строки слева направо. При этом нужное правило вывода синтаксический ана¬лизатор выбирает, заглядывая вперёд не более, чем на к символов. Класс LL(k) грамматик, к которому он применим, был изучен в работах Кнута [1971], Льюиса и Стирнса [1968], Розенкранца и Стирнса [1970]. При этом Розенкранц и Стирнс, а также Курки-Суонио [1969] установили, что, для всякого к грамматики из класса LL(k + 1) порождают больше языков, чем грамматики из класса LL(k), и таким образом появляется иерархия классов LLграмматик.
Важный подкласс линейных LL(k) грамматик впервые изучался Ибаррой и др. [1988] и Холвцером и Ланге [199.3], получивших ряд результатов о вычислительной сложности языков, задаваемых такими грамматиками. Однако очевидный вопрос о существовании иерархии классов ЬЬ(к)-линейных грамматик остался нерассмотренным.
В данной работе даётся отрицательный ответ на этот вопрос: оказывается, что в линейном случае иерархия по к обрушивается, то есть все языки, задаваемые грамматиками из класса ЬЬ(к)-линейных для некоторого к, задаются и грамматиками из класса ЬЬ(1)-линейных. Доказательство проводится эффективным преобразованием, состоящем из двух этапов и описанном в разделах гена первом этапе произвольная LL(k)- линейная грамматика преобразуется к некоторому нормальному виду, а на втором этапе — далее к ЬЬ(1)-линейной.
Полученное построение приводит к сильному росту числа нетерминальных символов грамматики: их становится больше примерно в |S|2k раз, где S — алфавит языка. Поэтому естественным образом возникает вопрос об эффективности приведённого построения и о нижней оценке количества нетерминальных символов ЬЬ(1)-линейной грамматики, задающей тот же язык, что и данная ЬЬ(к)-линейная. Нельзя ли разработать другое, улучшенное построение, которое не будет приводить к столь значительному росту?
Оказывается, что нет. В разделе |Б]устанавливается, что такой рост количества нетерминальных символов неизбежен, и приводимое построение на самом деле близко к оптимальному: строятся примеры LL(k)- линейных грамматик с nнетерминальными символами, для которых доказывается, что всякая ЬЬ(1)-.линейная грамматика, задающая тот же язык, должна иметь не менее чем n | S|2fc-O(logk)нетерминальных символов.
Третий результат этой работы посвящён более мощному классу формальных грамматик — конъюнктивным грамматикам. Конъюнктивные грамматики, введённые Охотиным [2001], обобщают обыкновенные грамматики введением операции конъюнкции в правила. Для них также определены ЬЬ(к)-подкласс и линейный подкласс, и, таким образом, можно рассматривать LL (к)-линейные конъюнктивные грамматики; их определение приведено в разделе [7[Ранее Охотин [2011] определил простейшие ограничения выразительной мощности этого подкласса, но в целом класс остаётся малоизученным. В частности, вопрос о существовании иерархии по к не рассматривался.
В разделах этой работы установлено, что ЬЬ(к)-линейные конъюктивные грамматики можно перевести в LL(1)-линейные конъюнктивные. Результат доказывается обобщением построения для случая обыкновенных грамматик.
Результаты разделов заданной работы представлены в двух статьях, опубликованных в сборниках докладов конференций RuFiDiM 2019 и CSR 2020.

Купить

Полученные результаты заставляют задуматься о нескольких близких вопросах. Неизбежен ли рост размера грамматики пи преобразовании ЬЬ(к)-линейных конънктивных грамматик в ЬЬ(1)-линейные конъюнктивные? Существует ли иерархия ЬЬ(к)-конъюнктивных грамматик (без свойства линейности) по к? Вообще, о классе ЬЬ(к)-конъюнктивных грамматик известно очень мало, и он ждёт своего исследователя.
Купить