Насколько большим может быть автомат LR (1) для языка, чем соответствующий автомат LR (0)?

В синтаксическом анализаторе LR (0) каждое состояние состоит из набора элементов LR (0), которые являются продукцией, аннотированной позицией. В синтаксическом анализаторе LR (1) каждое состояние состоит из набора элементов LR (1), которые являются продукцией, аннотированной позицией и символом предпросмотра.

Известно, что при наличии состояния в автомате LR (1) конфигурирующий набор, сформированный путем сбрасывания жетонов предпросмотра из каждого элемента LR (1), дает конфигурационный набор, соответствующий некоторому состоянию в автомате LR (0). В этом смысле основное различие между автоматом LR (1) и автоматом LR (0) состоит в том, что автомат LR (1) имеет больше копий состояний в автомате LR (0), каждое из которых снабжено аннотацией Информация. По этой причине автоматы LR (1) для данного CFG обычно больше соответствующего анализатора LR (0) для этого CFG.

Мой вопрос - насколько большим может быть автомат LR (1). Если в алфавите грамматики есть различных терминальных символов, то в принципе нам может потребоваться повторить каждое состояние в автомате LR (0) хотя бы один раз на подмножество этих различных терминальных символов, что может привести к LR (1). ) автомат, который в раз больше исходного автомата LR (0). Учитывая, что каждый отдельный элемент в автомате LR (0) состоит из набора различных предметов LR (0), мы можем получить еще больший взрыв. $n$ $n$ $2^n$

Тем не менее, я не могу найти способ построить семейство грамматик, для которых автомат LR (1) значительно больше, чем соответствующий автомат LR (0). Все, что я пробовал, привело к небольшому увеличению размера (обычно около 2-4х), но я не могу найти модель, которая приводит к большому взрыву.

Существуют ли известные семейства контекстно-свободных грамматик, у которых автоматы LR (1) экспоненциально больше соответствующих автоматов LR (0)? Или известно, что в худшем случае вы не сможете получить экспоненциальный взрыв?

Спасибо!

context-free parsers lr-k templatetypedef
источник

такие проблемы иногда поддаются эмпирическому тестированию. Что бы вы подумали об отдельных экземплярах, сгенерированных случайным образом, которые (выбраны для) демонстрируют взрыв? в этих типах вопросов есть закономерность, что «случайные» конструкции демонстрируют наибольшую «сложность» ...

vzn

Случаи наихудшего случая обычно трудно найти случайной выборкой, по крайней мере, если средний случай значительно лучше.

Рафаэль

ps было бы полезно, если бы вы включили примеры случаев 2x-4x взрыва где-то, а не в посте ...

vzn

идея / руководство: перестановки парсинга LR (cstheory.se)

vzn

LALR (1) обычно представляется как способ достаточно приблизиться к силе LR (1), чтобы быть полезным с гораздо меньшим количеством состояний (если использовать слова из книги Дракона). Интересно, было бы достаточно простого фактора от 2 до 4, чтобы отклонить LR (1) как запретительный до изобретения LALR (1). Если я подумаю об этом, когда они станут доступны, я посмотрю в Aho & Ullman Theory of parsing, translation and compiling и в Grune Parsing Techniques, если у них есть что-то о числах.

AProgrammer

Ответы:

Грамматика

\begin{array}{l} S \to T_{0} \\ T_{N} \to a T_{N + 1} \\ T_{N} \to б T_{N + 1} \\ T_{N} \to б T_{N + 1} T_{N} \\ T_{N} \to T_{N} \end{array}

$\begin{array}{l} S \rightarrow T_0 \\ T_n \rightarrow a \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \; t_n \\ T_N \rightarrow t_N \end{array}$

T_{N} \to T_{N} \dot{}

$T_N \rightarrow t_N \dot \\$

2^{N}

$2^N$

{t_{0} \dots t_{N - 1}}

$\{t_0 \dots t_{N-1}\}$

N

$N$

2^{N} / N

$2^N/N$

~~$T_N \rightarrow T_0$~~

AProgrammer
источник

Такие нижние границы иногда сложно построить и могут вызвать более глубокую теорию CS (например, в случаях, разделения классов сложности). Эта статья, кажется, дает теоретическую конструкцию / нижние границы, которые вы ищете, например, в теореме 5, которая устанавливает нижнюю границу для суммарных символов и, следовательно, также состояний. Ссылки также включают другие подобные конструкции / нижние границы.

$f(n,k) = 2^{\frac{1}{4}(n - k)} / n^2$ $k = 0,1;...,n−1$ $L_n$ $n \geq 3$ $f(n,k)$ $f(n,k)$

О размерах парсеров и LR (k) -граммеров / Леунга, Вотшкеба

ВЗН
источник

2^{(n - 1) / 4} / n^{2}

$2^{(n-1)/4}/n^2$

2^{n / 4} / n^{2}

$2^{n/4}/n^2$ ограничен размером автомата LR (0) для этого языка. Таким образом, этот ответ не отвечает на вопрос, который был задан.

1.1892

$1.1892$

DW думает, что ваше возражение является и законным, и подходит для укладки волос. Большое спасибо за разъяснения / детали. это актуальный / почти прямой научный ответ / систематическое изучение его вопроса, который, по сути, касается наихудшего построения языка (ов) / раздувания в LR (n). Возможно, это (почти?) «самые известные результаты» в этой области. законный ответ на вопрос может быть отрицательным, иначе говоря, НЕТ, нет результатов лучше известных, чем найденный спрашивающим (он еще не выставлял их вообще) или в литературе. с нетерпением жду каких-либо окончательных ответов сам!

vzn