LINUX.ORG.RU

объясните, пожалуйста, непонятный английский текст по-русски

 ,


0

3

вот он: http://www.larc.usp.br/~pbarreto/LR.pdf

нету ли где на просторах интернета такого же или подобного ему, но понятного?

Мне не ясно, как рассчитывается третья часть расширенного Item (ну, это когда Item выглядит так:
A -> b, [$eof]
третья часть - это то, что после запятой)

бизон так умеет, но я хочу понять, как это делать руками.

Вопрос в том, как рассчитывать вот это (страница 6, алгоритм 1, строчка 22):

v ← ctx(X, N) ⊕ first(γu)

Или что-то другое? Чтобы понять, как работает бизон, достаточно разобрать пару примеров из Ахо-Ульмана: руками на бумажке прогнать алгоритм, или написать программу которая это делает.

Если нет литературы на русском, могу поделиться PDF-ками которые нам когда-то препод в универе делал — там есть конкретный пример построения таблиц.

skvadrik ()

Объясните зачем это нужно когда есть PEG?

loz ★★★★★ ()
Ответ на: комментарий от loz

Для скорости исполнения.

Даже если рассматривать PEG с мемоизацией (packrat parsing), принять алгоритмическую сложность за линейную и не учитывать возможный экспоненциальный рост памяти, то LR парсер всё равно допускает более эффективную реализацию в виде стекового автомата, зашитого в код (этот метод называется recursive ascent).

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

Даже табличный LR парсер (например сгенерированный бизоном) может быть в разы медленнее recursive ascent за счёт таких мелочей как отсутствие перехода по таблице на каждой итерации.

skvadrik ()
Ответ на: комментарий от skvadrik

Чтобы понять, как работает бизон, достаточно разобрать пару примеров из Ахо-Ульмана

Книжек Ахо-Ульман несколько в таком составе авторов:
1972, Alfred V. Aho and Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing
1973, Alfred V. Aho and Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Volume 2: Compiling
1977, Alfred V. Aho and Jeffrey D. Ullman, Principles of Compiler Design
какая имелась в виду? Допустим, что первая

Есть две вещи, которые можно понимать:
1) как работает парсер, созданный бизоном
2) как работает сам бизон, когда он создаёт парсер

В примерах Ахо-Ульмана расписывается первое, но не второе.

Вопрос в том, как рассчитывать вот это (страница 6, алгоритм 1, строчка 22)

мне непонятны уже строчки 2 и 3. Я понимаю, что там написано, но не понимаю, как это вычислять. Нужно им было дополнительно описать вспомогательные алгоритмы.

Einstok_Fair ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.