Парсер Packrat

Парсер Packrat
Сорт	Разбор грамматик PEG
Структура данных	Нить
Худшая производительность	или без специальной обработки итеративного комбинатора
Лучшая производительность	;
Средняя производительность
Наихудшая пространственная сложность

Парсер Packrat — это тип парсера , который имеет сходство с парсером рекурсивного спуска по своей конструкции. Однако он отличается тем, что в качестве входных данных принимает грамматики синтаксического анализа (PEG), а не LL-грамматики . ^[1]

В 1970 году Александр Бирман заложил основу для анализа пакетов, представив «схему распознавания TMG» (TS) и «обобщенную TS» (gTS). Роберта М. МакКлюра TS был основан на компиляторе-компиляторе TMG Дьюи Вэла Шорра META , а gTS был основан на компиляторе-компиляторе . Работа Бирмана была позже усовершенствована Ахо и Ульманом; и переименован в язык нисходящего синтаксического анализа (TDPL) и обобщенный TDPL (GTDPL) соответственно. Эти алгоритмы были первыми в своем роде, в которых использовался детерминированный нисходящий анализ с обратным отслеживанием. ^[2]^[3]

Брайан Форд разработал PEG как расширение GTDPL и TS. В отличие от CFG , PEG однозначны и могут хорошо сочетаться с машинно-ориентированными языками. PEG, подобно GTDPL и TS, также могут выражать все LL(k) и LR(k) . Брайан также представил Packrat как парсер, использующий методы мемоизации поверх простого парсера PEG. Это было сделано потому, что PEG имеют неограниченные возможности просмотра вперед приводит к тому, что анализатор работает с экспоненциальной производительностью по времени . , что в худшем случае ^[2]^[3]

Packrat отслеживает промежуточные результаты для всех взаимно рекурсивных функций синтаксического анализа. Каждая функция синтаксического анализа вызывается только один раз в определенной позиции ввода. В некоторых случаях реализации Packrat, если не хватает памяти, некоторые функции синтаксического анализа могут потребоваться вызывать несколько раз в одной и той же позиции ввода, в результате чего синтаксический анализатор будет занимать больше времени, чем линейное. ^[4]

Синтаксис

Анализатор Packrat принимает на вход тот же синтаксис, что и PEG: простой PEG состоит из терминальных и нетерминальных символов, возможно, чередующихся с операторами, которые составляют одно или несколько правил вывода. ^[2]

Символы

Нетерминальные символы обозначаются заглавными буквами (например, $\{S,E,F,D\}$ )
Символы клемм обозначаются строчными буквами (например, $\{a,b,z,e,g\}$ )
Выражения обозначаются строчной греческой буквой (например, $\{\alpha ,\beta ,\gamma ,\omega ,\tau \}$ $\{\альфа,\бета,\гамма,\омега,\тау \}$ )
- Выражения могут представлять собой смесь терминальных символов, нетерминальных символов и операторов.

Операторы

Синтаксические правила
Оператор	Семантика
Последовательность $\alpha \beta$	Успех: Если $\alpha$ и $\beta$ признаны Неудача: Если $\alpha$ или $\beta$ не признаны Потреблено: $\alpha$ и $\beta$ в случае успеха
Заказной выбор $\alpha /\beta /\gamma$	Успех: Если какой-либо из $\{\alpha ,\beta ,\gamma \}$ распознается, начиная слева Неудача: Все $\{\alpha ,\beta ,\gamma \}$ не совпадают Потребление: атомарное выражение, приведшее к успеху. поэтому, если несколько успешны, всегда возвращается первый
И предикат $\&\alpha$	Успех: Если $\alpha$ признан Неудача: Если $\alpha$ не признан Потреблено: входные данные не потребляются.
Не предикат $!\alpha$	Успех: Если $\alpha$ не признан Неудача: Если $\alpha$ признан Потреблено: входные данные не потребляются.
Один или несколько $\alpha +$	Успех: постарайтесь распознать $\alpha$ один или несколько раз Неудача: Если $\alpha$ не признан Потреблено: максимальное количество, которое $\alpha$ признан
Ноль или больше $\alpha *$	Успех: постарайтесь распознать $\alpha$ ноль или несколько раз Неудача: Не может потерпеть неудачу Потреблено: максимальное количество, которое $\alpha$ признан
Ноль или один $\alpha ?$	Успех: постарайтесь распознать $\alpha$ ноль или один раз Неудача: Не может потерпеть неудачу Потреблено: $\alpha$ если это признано
Диапазон терминала [ $a-b$ ]	Успех: Распознать любой терминал $c$ которые находятся внутри диапазона $[a-b]$ . В случае $[{\textbf {'}}h{\textbf {'}}-{\textbf {'}}z{\textbf {'}}]$ , $c$ может быть любая буква от h до z Неисправность: Если внутри нет терминала $[a-b]$ может быть признан Потреблено: $c$ если это признано
Любой персонаж $.$	Успех: распознать любой символ во входных данных. Ошибка: если во входных данных нет символа Потребляется: любой символ на входе.

Правила

Правило вывода состоит из нетерминального символа и выражения $S\rightarrow \alpha$ .

Особое выражение $\alpha _{s}$ является отправной точкой грамматики. ^[2] В случае нет $\alpha _{s}$ указано, используется первое выражение первого правила.

Входная строка считается принятой синтаксическим анализатором, если $\alpha _{s}$ признан. В качестве побочного эффекта строка $x$ может быть распознан парсером, даже если он не был полностью использован. ^[2]

Крайним случаем этого правила является то, что грамматика $S\rightarrow x*$ соответствует любой строке.

Этого можно избежать, переписав грамматику как $S\rightarrow x*!.$

Пример

${\begin{cases}S\rightarrow A/B/D\\A\rightarrow {\textbf {'a'}}\ S\ {\textbf {'a'}}\\B\rightarrow {\textbf {'b'}}\ S\ {\textbf {'b'}}\\D\rightarrow ({\textbf {'0'}}-{\textbf {'9'}})?\end{cases}}$

Эта грамматика распознает палиндром над алфавитом. $\{a,b\}$ , с необязательной цифрой посередине.

Примеры строк, принимаемых грамматикой, включают: ${\textbf {'aa'}}$ и ${\textbf {'aba3aba'}}$ .

Левая рекурсия

Левая рекурсия происходит, когда продукция грамматики прямо или косвенно ссылается на себя как на самый левый элемент. Поскольку Packrat — это анализатор рекурсивного спуска, он не может напрямую обрабатывать левую рекурсию. ^[5] На ранних стадиях разработки было обнаружено, что леворекурсивная продукция может быть преобразована в праворекурсивную продукцию. ^[6] Эта модификация существенно упрощает задачу парсера Packrat. Тем не менее, если задействована непрямая левая рекурсия, процесс переписывания может оказаться довольно сложным и трудоемким. Если требования к временной сложности снижены с линейных до суперлинейных , можно изменить таблицу запоминания парсера Packrat, чтобы разрешить левую рекурсию, не изменяя входную грамматику. ^[5]

Итерационный комбинатор

Итеративный комбинатор $\alpha +$ , $\alpha *$ , требует особого внимания при использовании в парсере Packrat. По сути, использование итеративных комбинаторов вводит секретную рекурсию, которая не записывает промежуточные результаты в матрицу результатов. Это может привести к сверхлинейному поведению синтаксического анализатора. Эту проблему можно решить, применив следующее преобразование: ^[1]


Оригинал	Переведено
$S\rightarrow \alpha +$	$S\rightarrow \alpha S/\alpha$
$S\rightarrow \alpha *$	$S\rightarrow \alpha S/\epsilon$

Благодаря этому преобразованию промежуточные результаты можно правильно запомнить.

Техническая мемоизация

Мемоизация — это метод оптимизации вычислений, целью которого является ускорение программ за счет сохранения результатов дорогостоящих вызовов функций. Этот метод по существу работает путем кэширования результатов, так что при повторении тех же входных данных кэшированный результат просто возвращается, что позволяет избежать трудоемкого процесса повторных вычислений. ^[7] При использовании синтаксического анализа и мемоизации Packrat следует отметить, что функция синтаксического анализа каждого нетерминала основана исключительно на входной строке. Это не зависит от какой-либо информации, собранной в процессе анализа. По сути, записи таблицы мемоизации не влияют и не зависят от конкретного состояния синтаксического анализатора в любой момент времени. ^[8]

Анализ Packrat сохраняет результаты в матрице или аналогичной структуре данных, которая позволяет осуществлять быстрый поиск и вставку. При обнаружении производства матрица проверяется, чтобы убедиться, что оно уже произошло. Если да, то результат извлекается из матрицы. Если нет, производится оценка продукции, результат вставляется в матрицу и затем возвращается. ^[9] При оценке всего $m*n$ матрицу в табличном подходе, это потребует $\Theta (mn)$ космос. ^[9] Здесь, $m$ представляет количество нетерминалов, и $n$ представляет размер входной строки.

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

Парсер Packrat можно улучшить, чтобы он обновлял только необходимые ячейки в матрице посредством посещения каждого дерева подвыражений в глубину. Следовательно, используя матрицу размерностью $m*n$ часто является расточительным, поскольку большинство записей останутся пустыми. ^[5] Эти ячейки связаны с входной строкой, а не с нетерминалами грамматики. Это означает, что увеличение размера входной строки всегда будет увеличивать потребление памяти, а количество правил синтаксического анализа меняет только худшую пространственную сложность. ^[1]

Оператор вырезания

еще один оператор Cut, В Packrat был введен чтобы еще больше снизить среднюю сложность пространства. Этот оператор использует формальные структуры многих языков программирования, чтобы исключить невозможные выводы. Например, анализ операторов управления на стандартном языке программирования является взаимоисключающим, начиная с первого распознанного токена, например: $\{if,do,while,switch\}$ . ^[10]

Оператор	Семантика
Резать ${\begin{array}{l}\alpha \uparrow \beta /\gamma \\(\alpha \uparrow \beta )*\end{array}}$	если $\alpha$ признан, но $\beta$ нет, пропустите оценку альтернативы. В первом случае не оценивайте $\gamma$ если $\alpha$ был признан Второе правило можно переписать как $N\rightarrow \alpha \uparrow \beta N/\epsilon$ и могут применяться те же правила.

Когда парсер Packrat использует операторы обрезки, он эффективно очищает стек поиска с возвратом. Это связано с тем, что оператор разреза уменьшает количество возможных альтернатив в упорядоченном выборе. Добавляя операторы вырезания в нужные места определения грамматики, результирующий парсер Packrat требует лишь почти постоянного объема памяти для запоминания. ^[10]

Алгоритм

Эскиз реализации алгоритма Packrat в Lua-подобном псевдокоде. ^[5]

INPUT(n) -- return the character at position n

RULE(R : Rule, P : Position )
    entry = GET_MEMO(R,P) -- return the number of elements previously matched in rule R at position P
    if entry == nil then
        return EVAL(R, P);
    end
    return entry;


EVAL(R : Rule, P : Position )
    start = P;   
    for choice in R.choices -- Return a list of choice
        acc=0;
        for symbol in choice then -- Return each element of a rule, terminal and nonterminal
            if symbol.is_terminal then
                if INPUT(start+acc) == symbol.terminal then
                    acc = acc + 1; --Found correct terminal skip pass it
                else
                    break;                
                end
            else 
                res = RULE(symbol.nonterminal , start+acc ); -- try to recognize a nonterminal in position start+acc
                SET_MEMO(symbol.nonterminal , start+acc, res ); -- we memoize also the failure with special value fail
                if res == fail then  
                    break; 
                end
                acc = acc + res;
            end
            if symbol == choice.last -- check if we have matched the last symbol in a choice if so return
                return acc;
        end
    end
    return fail; --if no choice match return fail

Пример

Учитывая следующий контекст, свободная грамматика, которая распознает простые арифметические выражения, состоящие из одиночных цифр, чередующихся суммой, умножением и круглыми скобками.

${\begin{cases}S\rightarrow A\\A\rightarrow M\ {\textbf {'+'}}\ A\ /\ M\\M\rightarrow P\ {\textbf {'*'}}\ M\ /\ P\\P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ D\\D\rightarrow ({\textbf {'0'}}-{\textbf {'9'}})\end{cases}}$

Обозначается $\dashv$ терминатор строки, мы можем применить алгоритм Packrat

Вывод

2*(3+4)\dashv

Синтаксическое дерево

Действие

Стол Пакрат

Правила вывода	Ввод смещен
${\begin{array}{l}S\rightarrow A\\A\rightarrow M\ {\textbf {'+'}}\ A\\M\rightarrow P\ {\textbf {'*'}}\ M\\P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\end{array}}$	е
Примечания	Ввод слева
Ввод не соответствует первому элементу в выводе. Вернитесь к первому грамматическому правилу с неисследованной альтернативой. ${\textstyle P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ {\underline {D}}}$	$2*(3+4)\dashv$


	Индекс
	1	2	3	4	5	6	7
С
А
М
П
Д
	2	*	(	3	+	4	)

Нет обновления, поскольку ни один терминал не был распознан

Правила вывода	Ввод смещен
$P\rightarrow D$ $D\rightarrow 2$	$2$
Примечания	Ввод слева
Сдвиг ввода на единицу после получения терминала $2$	$*(3+4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М
П	1
Д	1
	2	*	(	3	+	4	)

Обновлять:

Д(1) = 1;

Р(1) = 1;

Правила вывода	Ввод смещен
$M\rightarrow P\ {\textbf {'*'}}\ M$ $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$2*($
Примечания	Ввод слева
Сдвиг ввода на два терминала $\{{\textbf {*}},{\textbf {(}}\}$	$3+4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М
П	1
Д	1
	2	*	(	3	+	4	)

Обновлений нет, поскольку ни один нетерминал не был полностью распознан.

Правила вывода	Ввод смещен
$A\rightarrow M\ {\textbf {'+'}}\ A$ $M\rightarrow P\ {\textbf {'*'}}\ M$ $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$2*($
Примечания	Ввод слева
Ввод не соответствует первому элементу в выводе. Вернитесь к первому грамматическому правилу с неисследованной альтернативой. ${\textstyle P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ {\underline {D}}}$	$3+4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М
П	1
Д	1
	2	*	(	3	+	4	)

Нет обновления, поскольку ни один терминал не был распознан

Правила вывода	Ввод смещен
$P\rightarrow D$ $D\rightarrow 3$	$2*($
Примечания	Ввод слева
Сдвиг ввода на единицу после получения терминала $3$ но новый ввод не будет соответствовать внутри $M\rightarrow P\ {\textbf {''}}\ M$ поэтому развертывание необходимо для $M\rightarrow P\ {\textbf {''}}\ M\ /\ {\underline {P}}$	$3+4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М
П	1			1
Д	1			1
	2	*	(	3	+	4	)

Обновлять:

Д(4) = 1;

Р(4) = 1;

Правила вывода	Ввод смещен
$M\rightarrow P$	$2*(3+$
Примечания	Ввод слева
Откатиться к $M\rightarrow P\ {\textbf {'*'}}\ M\ /\ {\underline {P}}$ И мы не расширяем его, если у нас есть попадание в таблицу запоминания P(4) ≠ 0, поэтому сдвиньте входные данные на P(4). Сдвиньте также $+$ от $A\rightarrow M\ {\textbf {'+'}}\ A$	$4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М				1
П	1			1
Д	1			1
	2	*	(	3	+	4	)

Ударьте по P(4)

Обновить M(4) = 1, поскольку M был распознан.

Правила вывода	Ввод смещен
$A\rightarrow M\ {\textbf {'+'}}\ A$ $M\rightarrow P\ {\textbf {'*'}}\ M$ $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$2*(3+$
Примечания	Ввод слева
Ввод не соответствует первому элементу в выводе. Вернитесь к первому грамматическому правилу с неисследованной альтернативой. ${\textstyle P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}\ /\ {\underline {D}}}$	$4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М				1
П	1			1
Д	1			1
	2	*	(	3	+	4	)

Нет обновления, поскольку ни один терминал не был распознан

Правила вывода	Ввод смещен
$P\rightarrow D$ $D\rightarrow 4$	$2*(3+$
Примечания	Ввод слева
Сдвиг ввода на единицу после получения терминала $4$ но новый ввод не будет соответствовать внутри $M\rightarrow P\ {\textbf {'*'}}\ M$ поэтому развертывание необходимо	$4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М				1
П	1			1		1
Д	1			1		1
	2	*	(	3	+	4	)

Обновлять:

Д(6) = 1;

Р(6) = 1;

Правила вывода	Ввод смещен
$M\rightarrow P$	$2*(3+$
Примечания	Ввод слева
Откатиться к $M\rightarrow P\ {\textbf {'*'}}\ M\ /\ {\underline {P}}$ И мы не расширяем его, если у нас есть попадание в таблицу запоминания P(6) ≠ 0, поэтому сдвиньте входные данные на P(6). но новый ввод не будет соответствовать $+$ внутри $A\rightarrow M\ {\textbf {'+'}}\ A$ поэтому развертывание необходимо	$4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А
М				1		1
П	1			1		1
Д	1			1		1
	2	*	(	3	+	4	)

Ударьте по P(6)

Обновить M(6) = 1, поскольку M был распознан.

Правила вывода	Ввод смещен
$A\rightarrow M$	$2*(3+4)$
Примечания	Ввод слева
Откатиться к $A\rightarrow M\ {\textbf {'+'}}\ A\ /\ {\underline {M}}$ И мы не расширяем его, если у нас есть попадание в таблицу запоминания M(6) ≠ 0, поэтому сдвиньте входные данные на M(6). Также сдвиньте $)$ от $P\rightarrow {\textbf {'('}}\ A\ {\textbf {')'}}$	$\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А				3
М				1		1
П	1		5	1		1
Д	1			1		1
	2	*	(	3	+	4	)

Ударить по М(6)

Обновление A(4) = 3, поскольку A был распознан.

Обновить P(3)=5, поскольку P был распознан.

Правила вывода	Ввод смещен
	$2*$
Примечания	Ввод слева
Откатиться к $M\rightarrow P\ {\textbf {''}}\ M\ /\ {\underline {P}}$ как терминал $\neq \dashv$	$(3+4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А				3
М				1		1
П	1		5	1		1
Д	1			1		1
	2	*	(	3	+	4	)

Нет обновления, поскольку ни один терминал не был распознан

Правила вывода	Ввод смещен
$M\rightarrow P$	$2*(3+4)$
Примечания	Ввод слева
мы не расширяем его, поскольку у нас есть попадание в таблицу запоминания P(3) ≠ 0, поэтому сдвиньте входные данные на P(3).	$\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А				3
М	7			1		1
П	1		5	1		1
Д	1			1		1
	2	*	(	3	+	4	)

Ударьте по P(3)

Обновить M(1)=7, поскольку M был распознан.

Правила вывода	Ввод смещен

Примечания	Ввод слева
Откатиться к $A\rightarrow M\ {\textbf {'+'}}\ A\ /\ {\underline {M}}$ как терминал $+\neq \dashv$	$2*(3+4)\dashv$

	Индекс
	1	2	3	4	5	6	7
С
А				3
М	7			1		1
П	1		5	1		1
Д	1			1		1
	2	*	(	3	+	4	)

Нет обновления, поскольку ни один терминал не был распознан

Правила вывода	Ввод смещен
$A\rightarrow M$	$2*(3+4)\dashv$
Примечания	Ввод слева
Мы не расширяем его, поскольку в таблице запоминания есть совпадение M(1) ≠ 0, поэтому сдвиньте входные данные на M(1). S был полностью уменьшен, поэтому входная строка распознается.

	Индекс
	1	2	3	4	5	6	7
С	7
А	7			3
М	7			1		1
П	1		5	1		1
Д	1			1		1
	2	*	(	3	+	4	)

Ударить по М(1)

Обновить A(1)=7, поскольку A был распознан.

Обновить S(1)=7, поскольку S был распознан.

Выполнение

Имя	парсинга Алгоритм	Языки вывода	Грамматика, код	Платформа разработки	Лицензия
ОстинИкс	Пакрат (модифицированный)	Ява	Отдельный	Все	Бесплатно, БСД
зубры	Пакрат	C , OCaml , Java	Смешанный	Все	Бесплатно, GNU GPL
Навес	Пакрат	Java , JavaScript , Python , Руби	Отдельный	Все	Бесплатно, GNU GPL
CL-привязка	Пакрат	Общий Лисп	Смешанный	Все	Бесплатно, Массачусетский технологический институт
Drat!	Пакрат	Д	Смешанный	Все	Бесплатно, GNU GPL
Фрисби	Пакрат	Хаскелл	Смешанный	Все	Бесплатно, БСД
грамматика::привязка	Пакрат	Ткл	Смешанный	Все	Бесплатно, БСД
ЖелезоМета	Пакрат	С#	Смешанный	Окна	Бесплатно, БСД
PEG-парсер	Packrat (поддержка левой рекурсии и грамматической неоднозначности)	С++	Идентичный	Все	Бесплатно, БСД
Нарвал	Пакрат	С	Смешанный	POSIX , Windows	Бесплатно, БСД
неотома	Пакрат	Эрланг	Отдельный	Все	Бесплатно, Массачусетский технологический институт
Омета	Пакрат (модифицированный, частичная мемоизация)	JavaScript , Писк , Python	Смешанный	Все	Бесплатно, Массачусетский технологический институт
ПакCC	Packrat (модифицированная поддержка левой рекурсии)	С	Смешанный	Все	Бесплатно, Массачусетский технологический институт
Пакрат	Пакрат	Схема	Смешанный	Все	Бесплатно, Массачусетский технологический институт
Паппи	Пакрат	Хаскелл	Смешанный	Все	Бесплатно, БСД
Пастернак	Пакрат	С++	Смешанный	Окна	Бесплатно, GNU GPL
PEG.js	Пакрат (частичная мемоизация)	JavaScript	Смешанный	Все	Бесплатно, Массачусетский технологический институт
Пегги ^[11]	Пакрат (частичная мемоизация)	JavaScript	Смешанный	Все	Бесплатно, Массачусетский технологический институт
Пегас	Рекурсивный спуск, Пакрат (выборочно)	С#	Смешанный	Окна	Бесплатно, Массачусетский технологический институт
Маленький парсер	Пакрат	Smalltalk , Java , Дарт	Смешанный	Все	Бесплатно, Массачусетский технологический институт
PyPy rlib	Пакрат	Питон	Смешанный	Все	Бесплатно, Массачусетский технологический институт
Крысы!	Пакрат	Ява	Смешанный	виртуальная машина Java	Бесплатно, GNU LGPL
бродяга	Пакрат	Идти	Идентичный	Все	лицензия GPLv3

См. также

Ссылки

^ Jump up to: ^а ^б ^с Форд, Брайан (2006). «Разбор Packrat: простое, мощное, ленивое, линейное время». arXiv : cs/0603077 .
^ Jump up to: ^а ^б ^с ^д ^и Форд, Брайан (1 января 2004 г.). «Разбор грамматик выражений» . Материалы 31-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ПОПЛ '04. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 111–122. дои : 10.1145/964001.964011 . ISBN 978-1-58113-729-3 . S2CID 7762102 .
^ Jump up to: ^а ^б Флодин, Дэниел. «Сравнение синтаксического анализа Packrat и обычного синтаксического анализа со сдвигом-сокращением реальных грамматик и входных данных» (PDF) .
^ Мидзусима, Кота; Маэда, Атуси; Ямагути, Ёсинори (6 мая 2010 г.). «Парсеры Packrat могут обрабатывать практические грамматики практически в постоянном пространстве». Материалы 9-го семинара ACM SIGPLAN-SIGSOFT по программному анализу для программных средств и инженерии . АКМ. стр. 29–36. дои : 10.1145/1806672.1806679 . ISBN 978-1-4503-0082-7 . S2CID 14498865 .
^ Jump up to: ^а ^б ^с ^д Варт, Алессандро; Дуглас, Джеймс Р.; Миллштейн, Тодд (7 января 2008 г.). «Парсеры Packrat могут поддерживать левую рекурсию» . Материалы симпозиума ACM SIGPLAN 2008 года по частичной оценке и манипулированию программами на основе семантики . ПЭПМ '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 103–110. дои : 10.1145/1328408.1328424 . ISBN 978-1-59593-977-7 . S2CID 2168153 .
^ Ахо, Альфред В.; Лам, Моника С.; Сетхи, Рави; Уллман, Джеффри Д., ред. (2007). Составители: принципы, методы и инструменты (2-е изд.). Бостон, Мюнхен: Пирсон Аддисон-Уэсли. ISBN 978-0-321-48681-3 .
^ Норвиг, Питер (1 марта 1991 г.). «Методы автоматического запоминания с приложениями для контекстно-свободного анализа» . Компьютерная лингвистика . 17 (1): 91–98. ISSN 0891-2017 .
^ Дуброй, Патрик; Варт, Алессандро (23 октября 2017 г.). «Инкрементальный парсинг пакрата» . Материалы 10-й Международной конференции ACM SIGPLAN по языковой инженерии программного обеспечения . SLE 2017. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 14–25. дои : 10.1145/3136014.3136022 . ISBN 978-1-4503-5525-4 . S2CID 13047585 .
^ Jump up to: ^а ^б Наука, Международный журнал научных исследований; Эйсрсет, Инженерия и технологии. «Обзор парсера Packrat» . Обзор парсера Packrat .
^ Jump up to: ^а ^б Мидзусима, Кота; Маэда, Атуси; Ямагути, Ёсинори (6 мая 2010 г.). «Парсеры Packrat могут обрабатывать практические грамматики практически в постоянном пространстве» . Материалы 9-го семинара ACM SIGPLAN-SIGSOFT по программному анализу для программных средств и инженерии . ВСТАВИТЬ '10. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 29–36. дои : 10.1145/1806672.1806679 . ISBN 978-1-4503-0082-7 . S2CID 14498865 .
^ Поддерживаемая вилка PEG.js.

Внешние ссылки

[:3-1] Jump up to: ^а ^б ^с Форд, Брайан (2006). «Разбор Packrat: простое, мощное, ленивое, линейное время». arXiv : cs/0603077 .

[:1-2] Jump up to: ^а ^б ^с ^д ^и Форд, Брайан (1 января 2004 г.). «Разбор грамматик выражений» . Материалы 31-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . ПОПЛ '04. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 111–122. дои : 10.1145/964001.964011 . ISBN 978-1-58113-729-3 . S2CID 7762102 .

[:0-3] Jump up to: ^а ^б Флодин, Дэниел. «Сравнение синтаксического анализа Packrat и обычного синтаксического анализа со сдвигом-сокращением реальных грамматик и входных данных» (PDF) .

[4] Мидзусима, Кота; Маэда, Атуси; Ямагути, Ёсинори (6 мая 2010 г.). «Парсеры Packrat могут обрабатывать практические грамматики практически в постоянном пространстве». Материалы 9-го семинара ACM SIGPLAN-SIGSOFT по программному анализу для программных средств и инженерии . АКМ. стр. 29–36. дои : 10.1145/1806672.1806679 . ISBN 978-1-4503-0082-7 . S2CID 14498865 .

[:2-5] Jump up to: ^а ^б ^с ^д Варт, Алессандро; Дуглас, Джеймс Р.; Миллштейн, Тодд (7 января 2008 г.). «Парсеры Packrat могут поддерживать левую рекурсию» . Материалы симпозиума ACM SIGPLAN 2008 года по частичной оценке и манипулированию программами на основе семантики . ПЭПМ '08. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 103–110. дои : 10.1145/1328408.1328424 . ISBN 978-1-59593-977-7 . S2CID 2168153 .

[6] Ахо, Альфред В.; Лам, Моника С.; Сетхи, Рави; Уллман, Джеффри Д., ред. (2007). Составители: принципы, методы и инструменты (2-е изд.). Бостон, Мюнхен: Пирсон Аддисон-Уэсли. ISBN 978-0-321-48681-3 .

[7] Норвиг, Питер (1 марта 1991 г.). «Методы автоматического запоминания с приложениями для контекстно-свободного анализа» . Компьютерная лингвистика . 17 (1): 91–98. ISSN 0891-2017 .

[8] Дуброй, Патрик; Варт, Алессандро (23 октября 2017 г.). «Инкрементальный парсинг пакрата» . Материалы 10-й Международной конференции ACM SIGPLAN по языковой инженерии программного обеспечения . SLE 2017. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 14–25. дои : 10.1145/3136014.3136022 . ISBN 978-1-4503-5525-4 . S2CID 13047585 .

[:4-9] Jump up to: ^а ^б Наука, Международный журнал научных исследований; Эйсрсет, Инженерия и технологии. «Обзор парсера Packrat» . Обзор парсера Packrat .

[:5-10] Jump up to: ^а ^б Мидзусима, Кота; Маэда, Атуси; Ямагути, Ёсинори (6 мая 2010 г.). «Парсеры Packrat могут обрабатывать практические грамматики практически в постоянном пространстве» . Материалы 9-го семинара ACM SIGPLAN-SIGSOFT по программному анализу для программных средств и инженерии . ВСТАВИТЬ '10. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 29–36. дои : 10.1145/1806672.1806679 . ISBN 978-1-4503-0082-7 . S2CID 14498865 .

[11] Поддерживаемая вилка PEG.js.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т и Алгоритмы разбора
Сверху вниз	Эрли LL Рекурсивный спуск Хвостовая рекурсия
Вверх дном	Приоритет Простой Оператор Маневровый двор ЛР Простой смотреть вперед Канонический Обобщенный ГАЛОЧКА Рекурсивное восхождение Shift-уменьшить
Смешанное, другое	Комбинатор Диаграмма Левый угол Статистический
Связанные темы	ПЭГ Определенная грамматика предложения Детерминированный анализ Динамическое программирование Мемоизация Генератор парсера ЛАЛР Дерево разбора АСТ Бессканерный парсинг История создания компилятора Сравнение генераторов парсеров Грамматика приоритета операторов