Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, mefrill, Вы писали:

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

VD>В каком виде?

В виде программмы на си++. Есть еще адаптер к вижуал прологу, выдает дерево вывода в приемлемом для пролога виде. Небольшая тестовая утилитка берет грамматику из текстового файла и осуществляет разбор входной строки, а затем показывает дерево вывода в контроле листвью мфс. В общем, готовая программа, но понятно, написанная достаточно небрежно. Можно ее дописать, а можно и вообще переписать, если интересно. Токены задаются в виде регулярных выражений, которые затем парсятся в детерминированный конечный автомат, минимизированный относительно количества состояний. Лексический анализатор запускает параллельно все такие автоматы и возвращает тот, который читает самую длинную строку. Синтаксический анализатор разбирает поток токенов, которые для синтаксического анализатора являются просто терминальными символами входной грамматики, и возвращает дерево вывода (или множество таких деревьев, если грамматика неоднозначная).

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

VD>Несколько вопросов:
VD>1. Какова оценочная эффективность этого алгоритма. Ведь для рельной жизни важно не только качество разбора, но и скорость парсинга.

Алгоритм Эрли позволяет разбирать линейные грамматики (т.е. грамматики, для которых только одна альтернатива, как в LL(k) или LR(k) грамматиках) за O(n), где n — длина входной терминальной строки, однозначные грамматики — за O(n^2) и неоднозначные — за O(n^3). В общем случае, алгоритм Эрли работает медленнее LR(k)-анализатора, проблема в константе для O(n). Но, в 90-х годах была придумана модификация алгоритма Эрли, которая позволяет разбирать линейные грамматики с той же скоростью, что и бизон. Для этого метода пока не создан алгоритм построения дервьев вывода, это как раз тема кандидатской диссертации. Так что, кому интересно — можно над этим поработать. Сам алгоритм можно использовать прямо сейчас, работа состоит в доказательстве его корректности.

VD>2. Где можно почитать о твоем методе. (по возможности популярно).

Мой метод — это алгоиритм Эрли, расширенный и модифицированный таким образом, чтобы строить деревья вывода, что оригинальный алгоритм Эрли делать не мог. Точнее, сам Эрли думал, что мог, но в его рассуждениях была ошибка. Эту ошибку обнаружил в 80-х Томита, исправить ее не смог и взялся за другой алгоритм — LR-анализа, расширил его и получил GLR. Я нашел как исправить эту ошибку и показал корректность работы нового алгоритма. Прочитать об алгоритме Эрли можно в моих работах, но там много математики и очень формально. Лучшее популярное описание все в той же книжке двух голландцев "Техника синтаксического анализа", насколько я помню. Вообще, там надо разобраться, знаю по своему опыту. Объяснял многим людям.

VD>3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?

Я готов помочь, объяснить алгоритм, рассказать о задачах, которые стоят и все такое прочее. Программировать я, к сожалению, не смогу. Но, можно было бы коллективно поработать над новой реализацией быстрого алгоритма Эрли с построением деревьев вывода. Если это получится (в чем я абсолютно уверен), то будет вне конкуренции.

VD>В принципе задача интересная. Ею можно было бы заняться.

По моему мнению, в таком генераторе необходимо реализовать несколько алгоритмов синтаксического анализа. Главные из них: быстрый алгоритм Эрли и GLR. Затем, необходимо реализовать адапатированный для построения деревьев вывода алгоритм Эрли (мой), так чтобы позволить легко менять исходныю грамматику прямо между двумя запусками алгоритма разбора. Бизон, например, этого делать не позволяет, также как и АНТЛР. Ведь они берут грамматику из текстового файла, обрабатывают ее, извлекая дополнительную информацию, и только затем генерируют разборщик. Я назвал такую модель генерации разборщиков статической моделью компиляции (СМК). Классический алгоритм Эрли ничего такого не требует, просто берет грамматику правило за правилом и разбирает. Я назвал такую можель динамической моделью компиляции (ДМК). ДМК полезен в тех ситуациях, когда исходный язык часто меняется, пополняется пользователем. С другой стороны, СМК работает быстрее, так как "знает" больше о свойствах грамматики. Это знание в случае LR-анализа есть LR-автомат, а случае LL(*)-анализа есть LL(*)-автомат. В общем, работы там много и работы интересной. Есть еще проблема обработки ошибок, тоже есть несколько интересных решений.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, mefrill, Вы писали:

VD>>>И почему ты думашь, что LL(*) охватывает узкий класс граматик.

M>>Я же там распинался, на конкретных примерах тебе показывал, что алгортим зацикливается для грамматик, содержащих леворекурсивные правила и правила с пустой правой частью. Как будут обрабатываться неоднозначности?

VD>При постпроении ДКА можно попытаться выявлять такие места и переписывать их.

Нет, там ничего такого не получится. В презентации предлагается либо случайно выбирать продукцию по наименьшему номеру (на стр. 11 верхняя картинка "пример неоднозначности"), либо использовать семантические предикаты, разрешая необнозначности вручную (стр. 11).

M>> Моя модификация алгоритма Эрли, например, строит всевозможные деревья вывода для входной строки, если есть неоднозначности. LL(*) не строит, а выбирает только одно дерево по ходу пъесы, руководствуясь либо семантическими ограничениями, либо случайно выбирая конкретную альтернативу. Далее, все ограничения, связанные с LL(k) алгоритмом никто не отменял и в LL(*).

VD>Насколько я понимаю основная идея этого LL(*) — это построение единого ДКА. Если состояния автомата совпадают с несколькими правилами, то входной поток сканируется до тех пор пока не будет найден токен который будет удовлетворять только одному правилу. Мне кажется, это решает большинство проблем LL(k)-анализаторов. Ну, да конечно в данной области мои познания не столь велеки.

Да, примерно эта идея. Но, проблемы, к сожалению, все-равно остаются. на странице 11 презентации как раз показан пример неоднозначности. А можно найти примеры однозначных грамматик, для которых невозможно построить LL(*) ДКА, недетерминизм по любому остается.

VD>>>Мне почему-то кажется, что LL(*) ни чем не хуже GLL.

M>>Что за GLL такой??? Не слышал о таком методе.

VD>Это не метод. Это только так "мысли в слух".
VD>Это я про идею описанную здесь: General LL

Автор: VladD2
Дата: 12.07.05

.

Ага, вспомнил.

Здравствуйте, mefrill, Вы писали:

M>В виде программмы на си++.

А он доступен?

M> Есть еще адаптер к вижуал прологу, выдает дерево вывода в приемлемом для пролога виде. Небольшая тестовая утилитка берет грамматику из текстового файла и осуществляет разбор входной строки, а затем показывает дерево вывода в контроле листвью мфс. В общем, готовая программа, но понятно, написанная достаточно небрежно.

Пролог это здорово, но я с ним знаком только по картинкам. Да и не очень практичен он. От парсера требуется максимальная скорость. Тут без хаков не обойтись.

M>Можно ее дописать, а можно и вообще переписать, если интересно. Токены задаются в виде регулярных выражений, которые затем парсятся в детерминированный конечный автомат, минимизированный относительно количества состояний. Лексический анализатор запускает параллельно все такие автоматы и возвращает тот, который читает самую длинную строку.

То есть нет единого автомата лексера? А как осуществляется выбор конкретного автомата? Перебором? Это же медленно.

Не лучше ли сделать один автомат который будет просто запихивать информацию о правилах при проходе пути? Ну, предположим правила:

Символы:
multylineCommentBody = ANY - '*'.
singlelineCommentBody = ANY - '\r' - '\n'.
Правила:
MultylineComment  : "/*" {  multylineCommentBodyn } "*/".
SinglelineComment : "//" {   } ('\r' [ '\n' ] | '\n').

Конфликтуют по первому символу. Но можно создать общий ДКА который при появлении новго символа будет запихивать/удалять в/из некоторый список информацию о удовлетворяющих правилах. Так на символе '/' в списке окажется два правила (MultylineComment и SinglelineComment). Но уже при появлении '*' или '/' правило останется одно и проблемы исчезнут. Остается только проблема при совпадении правил, но если они не порождают токенов, то и проблем нет (встраивать их тела по месту в более "широкие" правила.

Это даст скорость линейного поиска при относительно простом решении.

Вот только в современных языках есть кое какие проблемы. Например, в C# есть контексные ключевые слова. Так слова "get"/"set" встречаются только в эксесорах свойств, т.е. в:

int Property { get { return 1; } }

"get" бедет ключевым словом. А в:

int get;

нет.

Для решения этой проблемы можно просто переписать граматику объявив идентификатор таким образом:

Ident : ident | "get" | "set".

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

Еще более забавным случаем является контекстное ключевое слово "partial". Оно является ключевым только если перед ним идут слова "class"/"interface"/"struct". Тут уже просто так засунуть "partial" в Ident не удается. А на уровне лексера проблема решается путем несколькоих заглядываний вперед при появлени слова "partial". Нужно просто проверить идет ли за ним одно из этих слов, пропуская при этом коментарии и пробельные символы.

Интересно как в этих случаях может помочь распараллеливание лексера?

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

Ну, это классика.

M> и возвращает дерево вывода (или множество таких деревьев, если грамматика неоднозначная).

А насколько затормозится парсер если однозначость появляется при довольно глубоком заглядывании вперед? И как решаются проблемы "неудобных" рекурсий.

M>Алгоритм Эрли позволяет разбирать линейные грамматики (т.е. грамматики, для которых только одна альтернатива, как в LL(k) или LR(k) грамматиках) за O(n),

LL(k) за O(n)? Странно. Мне казалось, что за O(n) может работать только LL(1), а вся борба в LL(k)-апрсерах связана с оптимизицией заглядываний вперед. Я так понял, что LL(*) как раз и является разумным решением дя LL-арсеров.

M> где n — длина входной терминальной строки, однозначные грамматики — за O(n^2) и неоднозначные — за O(n^3). В общем случае, алгоритм Эрли работает медленнее LR(k)-анализатора, проблема в константе для O(n). Но, в 90-х годах была придумана модификация алгоритма Эрли, которая позволяет разбирать линейные грамматики с той же скоростью, что и бизон. Для этого метода пока не создан алгоритм построения дервьев вывода, это как раз тема кандидатской диссертации. Так что, кому интересно — можно над этим поработать. Сам алгоритм можно использовать прямо сейчас, работа состоит в доказательстве его корректности.

То есть нет полной уверенности, что алгоритм корректен?

VD>>2. Где можно почитать о твоем методе. (по возможности популярно).

M>Мой метод — это алгоиритм Эрли, расширенный и модифицированный таким образом, чтобы строить деревья вывода, что оригинальный алгоритм Эрли делать не мог. Точнее, сам Эрли думал, что мог, но в его рассуждениях была ошибка. Эту ошибку обнаружил в 80-х Томита, исправить ее не смог и взялся за другой алгоритм — LR-анализа,

Алгоритм Эрли тоже LR? А как при этом с простотой отладки граматик и с разумностью сообщений об ошибках парсинга? У Яков с Бизонами с этим серьезные проблемы.

M> расширил его и получил GLR. Я нашел как исправить эту ошибку и показал корректность работы нового алгоритма. Прочитать об алгоритме Эрли можно в моих работах, но там много математики и очень формально. Лучшее популярное описание все в той же книжке двух голландцев "Техника синтаксического анализа", насколько я помню.

К сожалению у меня ее нет. Она доступна в магазинах?
Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.

M> Вообще, там надо разобраться, знаю по своему опыту. Объяснял многим людям.

Ну, вот объясни мен и мы вместе напишем популярную статью которая откроет суть твоего алгоритма для всех.

VD>>3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?

M>Я готов помочь, объяснить алгоритм, рассказать о задачах, которые стоят и все такое прочее. Программировать я, к сожалению, не смогу.

ОК. Давай попробуем. Предлагаю для этого открыть новую тему и обсудеть суть этого алгоритма в нем.

M>Но, можно было бы коллективно поработать над новой реализацией быстрого алгоритма Эрли с построением деревьев вывода. Если это получится (в чем я абсолютно уверен), то будет вне конкуренции.

А как, по-твоему, он по сравнению тем же GLR по скорости на явзыках типа С++/C# (т.е. языках в которых есть множество мест когда конкретное правило можно определить только при многократном заглядывании вперед)?

M>По моему мнению, в таком генераторе необходимо реализовать несколько алгоритмов синтаксического анализа. Главные из них: быстрый алгоритм Эрли и GLR.

А смысл несколько?

M> Затем, необходимо реализовать адапатированный для построения деревьев вывода алгоритм Эрли (мой), так чтобы позволить легко менять исходныю грамматику прямо между двумя запусками алгоритма разбора.

На ходу? Без создания ДКА? Боюсь, что это станет тормозом. Хотя лично для моих нужд (расширение языка с целью внедрения в него средств метапрограммирования) динамический парсер был бы удобен.

M> Бизон, например, этого делать не позволяет, также как и АНТЛР. Ведь они берут грамматику из текстового файла, обрабатывают ее, извлекая дополнительную информацию, и только затем генерируют разборщик.

Дык это самое эффективное решение. Конкретная граматика превращается в эффектинвный код разбора. Никакой интерпретации. Возможность использовать хот switch-ей, хоть двумерных массивов...

M> Я назвал такую модель генерации разборщиков статической моделью компиляции (СМК). Классический алгоритм Эрли ничего такого не требует, просто берет грамматику правило за правилом и разбирает. Я назвал такую можель динамической моделью компиляции (ДМК). ДМК полезен в тех ситуациях, когда исходный язык часто меняется, пополняется пользователем. С другой стороны, СМК работает быстрее, так как "знает" больше о свойствах грамматики. Это знание в случае LR-анализа есть LR-автомат, а случае LL(*)-анализа есть LL(*)-автомат.

Боюсь, без заранее построенных автоматов (лучше в виде генерируемого кода) тут не обойтись. На сегодны динамическая компиляция не является проблемой. Так что делать интерпретатор без ДКА в основе крайне не разумно. И никакие блага простой модификации тут не перевесят. Все же в рельных проектах унжно перелопачивать по 3-15 мег кода и медленный парсет тут будет большой проблемой. Ну, и парсеры намного проще писать на языках с GC. А у них есть своим потери на разные "барьеры записи". Так что крайне желательно иметь действительно эффективный алгоритм.

M> В общем, работы там много и работы интересной.

Это понятно.

M> Есть еще проблема обработки ошибок,

Вот этого я и боюсь. Когда я сравнивал бесплатные построители парсеров, то Яки и Безоны пошли в лес отчасти потому что реализация на них осмысленных сообщений об ошибках крайне затруднительно.

M>тоже есть несколько интересных решений.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, mefrill, Вы писали:

M>>В виде программмы на си++.

VD>А он доступен?

Ну да, у меня на компутере .

M>> Есть еще адаптер к вижуал прологу, выдает дерево вывода в приемлемом для пролога виде. Небольшая тестовая утилитка берет грамматику из текстового файла и осуществляет разбор входной строки, а затем показывает дерево вывода в контроле листвью мфс. В общем, готовая программа, но понятно, написанная достаточно небрежно.

VD>Пролог это здорово, но я с ним знаком только по картинкам. Да и не очень практичен он. От парсера требуется максимальная скорость. Тут без хаков не обойтись.

О прологе можно забыть. Реализация интерфейса для пролога была связана со спецификой моей работы. Я реализовывал интерфейсную систему для базы знаний, написанной на прологе.

M>>Можно ее дописать, а можно и вообще переписать, если интересно. Токены задаются в виде регулярных выражений, которые затем парсятся в детерминированный конечный автомат, минимизированный относительно количества состояний. Лексический анализатор запускает параллельно все такие автоматы и возвращает тот, который читает самую длинную строку.

VD>То есть нет единого автомата лексера? А как осуществляется выбор конкретного автомата? Перебором? Это же медленно.

Для каждого токена строится минимизированный ДКА. Понятно, что в результате, при лексическом анализе, получается недетерминированный автомат. Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена. Такая реализация была связана со спецификой задачи, которую я реализовывал. Необходимо было создать лексический анализатор, который оперирует на основе динамически пополняемого множества токенов. Поэтому, неудобно было создавать и потом каждый раз убивать общий ДКА, очень медленно получалось. Нет никакого ограничения на построение единого ДКА для всех токенов грамматики.

VD>Не лучше ли сделать один автомат который будет просто запихивать информацию о правилах при проходе пути? Ну, предположим правила:
VD>

VD>Символы:
VD>multylineCommentBody = ANY - '*'.
VD>singlelineCommentBody = ANY - '\r' - '\n'.
VD>Правила:
VD>MultylineComment  : "/*" {  multylineCommentBodyn } "*/".
VD>SinglelineComment : "//" {   } ('\r' [ '\n' ] | '\n').
VD>

VD>Конфликтуют по первому символу. Но можно создать общий ДКА который при появлении новго символа будет запихивать/удалять в/из некоторый список информацию о удовлетворяющих правилах. Так на символе '/' в списке окажется два правила (MultylineComment и SinglelineComment). Но уже при появлении '*' или '/' правило останется одно и проблемы исчезнут. Остается только проблема при совпадении правил, но если они не порождают токенов, то и проблем нет (встраивать их тела по месту в более "широкие" правила.

VD>Это даст скорость линейного поиска при относительно простом решении.

Можно сделать и так. Но, мне бы, например, хотелось предложить альтернативу. Чтобы данный генератор работал не только для создания разборщиков для языков программирования, но и для естественных языков (для продвинутых текстовых редакторов) и для интерфейсных динамически пополняемых языков.

VD>Вот только в современных языках есть кое какие проблемы. Например, в C# есть контексные ключевые слова. Так слова "get"/"set" встречаются только в эксесорах свойств, т.е. в:
VD>

VD>int Property { get { return 1; } }
VD>

VD>"get" бедет ключевым словом. А в:
VD>

VD>int get;
VD>

VD>нет.

VD>Для решения этой проблемы можно просто переписать граматику объявив идентификатор таким образом:
VD>

VD>Ident : ident | "get" | "set".
VD>

VD>Тогда проблема решается. Но ведь мы как раз говорили, о том, что желательно иметь парсер для которого не требуется изменять граматику.

VD>Еще более забавным случаем является контекстное ключевое слово "partial". Оно является ключевым только если перед ним идут слова "class"/"interface"/"struct". Тут уже просто так засунуть "partial" в Ident не удается. А на уровне лексера проблема решается путем несколькоих заглядываний вперед при появлени слова "partial". Нужно просто проверить идет ли за ним одно из этих слов, пропуская при этом коментарии и пробельные символы.

VD>Интересно как в этих случаях может помочь распараллеливание лексера?

Здесь не нужно решать эти проблемы на уровне лексического анализатора. Лексер для того и придуман, чтобы упростить анализ, позволяя выделять простые подмножества исходного языка перед сложным анализом. В данном случае можно просто возвращать что-то типа string-token, а затем, зная контекст, уже преобразовывать его в ключевое слово или идентификатор. Но это уже проблема конкретного компилятора, а не генератора разборщиков. Можно конечно, ввести специальный контекст в лексический анализатор, но принципиально это нехорошо, т.к. ведет к излишнему усложнению системы. Можно реализовать систему фильтров. Например, в си++ токен ">>". Как известно, в определенном контексте это может быть окончание декларации шаблонного параметра шаблона плюс окончание декларации самого шаблона. Лексический анализатор, встречая подряд две угловые скобки, возвращает оператор правого побитового сдвига. Вот, пусть лексический анализатор возвращает всегда одну угловую скобку, а верхний фильтр, в зависимости от контекста, интерпретирует это как часть оператора сдвига или конец декларации шаблона или знак больше.

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

VD>Ну, это классика.

M>> и возвращает дерево вывода (или множество таких деревьев, если грамматика неоднозначная).

VD>А насколько затормозится парсер если однозначость появляется при довольно глубоком заглядывании вперед? И как решаются проблемы "неудобных" рекурсий.

Там нет "заглядываний вперед", происходит параллельное построение деревьев вывода снизу вверх.

M>>Алгоритм Эрли позволяет разбирать линейные грамматики (т.е. грамматики, для которых только одна альтернатива, как в LL(k) или LR(k) грамматиках) за O(n),

VD>LL(k) за O(n)? Странно. Мне казалось, что за O(n) может работать только LL(1), а вся борба в LL(k)-апрсерах связана с оптимизицией заглядываний вперед. Я так понял, что LL(*) как раз и является разумным решением дя LL-арсеров.

Нет, для любого LL(k) разбор идет за время O(n), для этого и придуманы множества FIRST и FOLLOW.

M>> где n — длина входной терминальной строки, однозначные грамматики — за O(n^2) и неоднозначные — за O(n^3). В общем случае, алгоритм Эрли работает медленнее LR(k)-анализатора, проблема в константе для O(n). Но, в 90-х годах была придумана модификация алгоритма Эрли, которая позволяет разбирать линейные грамматики с той же скоростью, что и бизон. Для этого метода пока не создан алгоритм построения дервьев вывода, это как раз тема кандидатской диссертации. Так что, кому интересно — можно над этим поработать. Сам алгоритм можно использовать прямо сейчас, работа состоит в доказательстве его корректности.

VD>То есть нет полной уверенности, что алгоритм корректен?

Алгоритмов на самом деле много. Есть классический алгоритм Эрли, который не строит деревьев вывода. Есть мой алгоритм, который строит деревья вывода для классического алгоритма Эрли Есть, так называемый, быстрый алгоритм Жрли, придуманный двумя канадцами в конце 90-х годов. Вот этот алгоритм стравним по скорости с LR-анализатором, быстрее которого нет ничего, но не строит деревьев вывода. Можно придумать (точнее, я уже придумал) как строить деревья вывода и для этого алгоритма. Тогда новый алгоритм будет работать быстро, а также будет позволять производить семантическую корректировку синтаксического анализа на ходу, отбрасывая семантически некорректные альтернативы и, тем самым, увеличивая скорость разбора. В этом и состоит преимущество алгоритма, который я предлагаю реализовать, перед GLR.

VD>>>2. Где можно почитать о твоем методе. (по возможности популярно).

M>>Мой метод — это алгоиритм Эрли, расширенный и модифицированный таким образом, чтобы строить деревья вывода, что оригинальный алгоритм Эрли делать не мог. Точнее, сам Эрли думал, что мог, но в его рассуждениях была ошибка. Эту ошибку обнаружил в 80-х Томита, исправить ее не смог и взялся за другой алгоритм — LR-анализа,

VD>Алгоритм Эрли тоже LR? А как при этом с простотой отладки граматик и с разумностью сообщений об ошибках парсинга? У Яков с Бизонами с этим серьезные проблемы.

Да нет у них проблем с сообщениями об ошибках. Есть проблемы с восстановлением работы после возникновения ошибки. Там это дело решается входом в так называемый "режим паники", что не есть хорошо во многих случаях. Алгоритм Эрли позволяет использовать длругую стратегию. Вообще, это тема очень обширная и требует отдельного большого обсуждения.

M>> расширил его и получил GLR. Я нашел как исправить эту ошибку и показал корректность работы нового алгоритма. Прочитать об алгоритме Эрли можно в моих работах, но там много математики и очень формально. Лучшее популярное описание все в той же книжке двух голландцев "Техника синтаксического анализа", насколько я помню.

VD>К сожалению у меня ее нет. Она доступна в магазинах?

Книжка есть в сети. Выше

Автор: mefrill
Дата: 19.07.05

я уже давал ссылку на нее.

VD>Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.

Да наверное, если что-то проклюнется, я бы мог написать такое введение (у меня что-то уже есть) и потом ответить на вопросы. Но, для этого, вероятно, необходимо уже отдельную ветку открыть. Статью я, конечно, могу прислать.

M>> Вообще, там надо разобраться, знаю по своему опыту. Объяснял многим людям.

VD>Ну, вот объясни мен и мы вместе напишем популярную статью которая откроет суть твоего алгоритма для всех.

VD>>>3. Насколко ты готов разобраться в этом вопросе тем кто займется этоим доведением до ума?

M>>Я готов помочь, объяснить алгоритм, рассказать о задачах, которые стоят и все такое прочее. Программировать я, к сожалению, не смогу.

VD>ОК. Давай попробуем. Предлагаю для этого открыть новую тему и обсудеть суть этого алгоритма в нем.

Ну вот, можно. Посмотрю что-то у меня уже есть, просто скопирую туда и статью присоеденю. А затем уже обсуждать будем.

M>>Но, можно было бы коллективно поработать над новой реализацией быстрого алгоритма Эрли с построением деревьев вывода. Если это получится (в чем я абсолютно уверен), то будет вне конкуренции.

VD>А как, по-твоему, он по сравнению тем же GLR по скорости на явзыках типа С++/C# (т.е. языках в которых есть множество мест когда конкретное правило можно определить только при многократном заглядывании вперед)?

M>>По моему мнению, в таком генераторе необходимо реализовать несколько алгоритмов синтаксического анализа. Главные из них: быстрый алгоритм Эрли и GLR.

VD>А смысл несколько?

Ну, может быть и никакого.

M>> Затем, необходимо реализовать адапатированный для построения деревьев вывода алгоритм Эрли (мой), так чтобы позволить легко менять исходныю грамматику прямо между двумя запусками алгоритма разбора.

VD>На ходу? Без создания ДКА? Боюсь, что это станет тормозом. Хотя лично для моих нужд (расширение языка с целью внедрения в него средств метапрограммирования) динамический парсер был бы удобен.

M>> Бизон, например, этого делать не позволяет, также как и АНТЛР. Ведь они берут грамматику из текстового файла, обрабатывают ее, извлекая дополнительную информацию, и только затем генерируют разборщик.

VD>Дык это самое эффективное решение. Конкретная граматика превращается в эффектинвный код разбора. Никакой интерпретации. Возможность использовать хот switch-ей, хоть двумерных массивов...

Да я не против, просто бывает, что так не получается. В случае расширяемых языков, например. Поэтому, я и говорю, что надо бы дать альтернативу.

M>> Я назвал такую модель генерации разборщиков статической моделью компиляции (СМК). Классический алгоритм Эрли ничего такого не требует, просто берет грамматику правило за правилом и разбирает. Я назвал такую можель динамической моделью компиляции (ДМК). ДМК полезен в тех ситуациях, когда исходный язык часто меняется, пополняется пользователем. С другой стороны, СМК работает быстрее, так как "знает" больше о свойствах грамматики. Это знание в случае LR-анализа есть LR-автомат, а случае LL(*)-анализа есть LL(*)-автомат.

VD>Боюсь, без заранее построенных автоматов (лучше в виде генерируемого кода) тут не обойтись. На сегодны динамическая компиляция не является проблемой. Так что делать интерпретатор без ДКА в основе крайне не разумно. И никакие блага простой модификации тут не перевесят. Все же в рельных проектах унжно перелопачивать по 3-15 мег кода и медленный парсет тут будет большой проблемой. Ну, и парсеры намного проще писать на языках с GC. А у них есть своим потери на разные "барьеры записи". Так что крайне желательно иметь действительно эффективный алгоритм.

Ну да, это более узкая задача построения трансляторов языков программирования. А вот, как быть с задаче построения анализатора грамматики в текстовом редакторе? Там неоднозначностей очень много, язык уж больно сложен, и язык часто пополняется новыми терминалами (добавить в словарь в ворде). Здесь уже можно пожертвовать скростью. при этом, это ведь тоже типичная программисткая задача. Поэтому, я считаю, что необходимо предложить альтернативу.

M>> В общем, работы там много и работы интересной.

VD>Это понятно.

M>> Есть еще проблема обработки ошибок,

VD>Вот этого я и боюсь. Когда я сравнивал бесплатные построители парсеров, то Яки и Безоны пошли в лес отчасти потому что реализация на них осмысленных сообщений об ошибках крайне затруднительно.

M>>тоже есть несколько интересных решений.

Здравствуйте, mefrill, Вы писали:

M>Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена.

Что то я не очень улвливаю. Т.е. ты создаешь из множества ДКА единый в рантайме?


M>Можно сделать и так. Но, мне бы, например, хотелось предложить альтернативу. Чтобы данный генератор работал не только для создания разборщиков для языков программирования, но и для естественных языков (для продвинутых текстовых редакторов) и для интерфейсных динамически пополняемых языков.

Я вот как раз сейчас пытаюсь создать реализацию лексера пригодную для тексового редактопра с подсветкой синтаксиса и возможно для автономного использования. Незнаю как для естественных языков, но для моих задач статического ДКА вроде хватает.

Что же до "динамически пополняемых языков", то лексер то можно пополнить, но как на это отреагирует граматическая часть?

M>Здесь не нужно решать эти проблемы на уровне лексического анализатора. Лексер для того и придуман, чтобы упростить анализ, позволяя выделять простые подмножества исходного языка перед сложным анализом. В данном случае можно просто возвращать что-то типа string-token, а затем, зная контекст, уже преобразовывать его в ключевое слово или идентификатор.

А кто будет преобразовывать? Я пиршел к выводу, что проще всего это как раз делать в лексере.

M> Но это уже проблема конкретного компилятора, а не генератора разборщиков.

Проблема генератора парсеров в том, чтобы с его помощью можно было максимально просто создать парсер для любого сязыка.

M> Можно конечно, ввести специальный контекст в лексический анализатор, но принципиально это нехорошо, т.к. ведет к излишнему усложнению системы.

А идентификатор вместо "partial" — это хорошо? Ведь все равно будет проблема. Надо будет на уровне семантики проверять, что этот идентификатор на самом деле "partial". И это еще в лучшем случае. В худшем попрут неоднозначности.

M> Можно реализовать систему фильтров. Например, в си++ токен ">>". Как известно, в определенном контексте это может быть окончание декларации шаблонного параметра шаблона плюс окончание декларации самого шаблона.

Нет. Тут ты ошибашся. В С++ >> — это всегда оператор сдвига. По этому очень часто бывает ошибка когда во вложенных шаблонах народ забывает добавить пробел между знаками ">". А вот в C# >> действительно перегружен. Но есть правило празрешения конфлитка описанное в спецификации. Я тебе уже приводил это место: http://rsdn.ru/Forum/Message.aspx?mid=958690&only=1

Автор: VladD2
Дата: 22.12.04

M> Лексический анализатор, встречая подряд две угловые скобки, возвращает оператор правого побитового сдвига. Вот, пусть лексический анализатор возвращает всегда одну угловую скобку, а верхний фильтр, в зависимости от контекста, интерпретирует это как часть оператора сдвига или конец декларации шаблона или знак больше.

Ну, примерно так и делается. Вот только такой "фильтр" выраждается в довольно сложную процедуру заглядывания вперед.

M>Там нет "заглядываний вперед", происходит параллельное построение деревьев вывода снизу вверх.

Т.е. еще на стадии построения парсера мы строим несколько автоматов и в местах где может появиться неоднозначность просто по парсим оба варианта, а там как получится?

M>Нет, для любого LL(k) разбор идет за время O(n), для этого и придуманы множества FIRST и FOLLOW.

Что-то мне казалось, что чем больше k, тем больше время.
Кстати, ты где нибудь видел человеческое описание преобразования НКА в ДКА и построение ДКА по синтаксическому дереву регулярных выражений. А то, то что я нашел это какая-то задница. Понять очень не просто.

M>Алгоритмов на самом деле много. Есть классический алгоритм Эрли, который не строит деревьев вывода. Есть мой алгоритм, который строит деревья вывода для классического алгоритма Эрли Есть, так называемый, быстрый алгоритм Жрли, придуманный двумя канадцами в конце 90-х годов. Вот этот алгоритм стравним по скорости с LR-анализатором, быстрее которого нет ничего,

Ну, LL(1) без конфликтов еще никто не обгонял.

M>но не строит деревьев вывода.

А в чем такая проблема построить деревья вывода? Это ведь как я понимаю просто путь реального разбора. Так? Ну, так для каждой однозначной ветки можно построить ДКА. Для пересекающихся это будет общий ДКА с указанием что состояние принадлежит нескольким символам разных правил. Причем, похоже, что тут и LR нафиг не упал (с магазинами). Достаточно одного аннотированного ДКА и некой механики отслеживания путей. Если путей два, то просто отплевываем два. Если один из них оборвался, то просто забываем про него.

В общем, или все очень просто и я не понимаю почему эта идея не пришла раньше никому в голову. Или у меня какая-то ошибка.

Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.

M> Можно придумать (точнее, я уже придумал) как строить деревья вывода и для этого алгоритма. Тогда новый алгоритм будет работать быстро, а также будет позволять производить семантическую корректировку синтаксического анализа на ходу, отбрасывая семантически некорректные альтернативы и, тем самым, увеличивая скорость разбора. В этом и состоит преимущество алгоритма, который я предлагаю реализовать, перед GLR.

Проясни для меня один вопрос. Вот если у нас есть некие два правила:

A : B {C|D} E;
A : B {C|D} F;

то в твоем случае парсер будет разбирать два пути пареллельно или он все же пройдет неоднозначную цепочку "B {C|D}" и разрешит проблему найдя E или F?

M>Да нет у них проблем с сообщениями об ошибках. Есть проблемы с восстановлением работы после возникновения ошибки.

Ну, можешь называть это как хочешь. Но при сканировании слева на право понять что случилось намного проще. Дубовые же Яки псото выкидывают сообщение "ожидается: ..." где "..." — это пара десятков токенов и думай что хочешь. В LL(1) парсере тебе говорят, что ожидается Х или У и нет проблем.

M> Там это дело решается входом в так называемый "режим паники", что не есть хорошо во многих случаях. Алгоритм Эрли позволяет использовать длругую стратегию. Вообще, это тема очень обширная и требует отдельного большого обсуждения.

Согласен, но по своему опыту замучу, что в LL(k) парсерах она решается куда проще. Да и рекурсивный спуск позволяет трассировать граматику понимая что происходит в данный момент.

VD>>Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.

M>Да наверное, если что-то проклюнется, я бы мог написать такое введение (у меня что-то уже есть) и потом ответить на вопросы. Но, для этого, вероятно, необходимо уже отдельную ветку открыть. Статью я, конечно, могу прислать.

Давай. И попробуем в интерактивном режиме довести ее до того состояния чтобы средний программист ее мог понять. Я как раз на этом собачек поел приизрядно.

M>Ну вот, можно. Посмотрю что-то у меня уже есть, просто скопирую туда и статью присоеденю. А затем уже обсуждать будем.

M>Да я не против, просто бывает, что так не получается. В случае расширяемых языков, например. Поэтому, я и говорю, что надо бы дать альтернативу.

А как часто в таких языках появляются новые токены?

M>Ну да, это более узкая задача построения трансляторов языков программирования. А вот, как быть с задаче построения анализатора грамматики в текстовом редакторе?

На естесвтенном языке? Дык если слово отсуствует, то кроме как некую абстракцию типа "идентификатор" ты ее не определишь. А если пользователь пополнит словарь, то не грех и автомат перестроить. Ведь динамическая компиляция это доли секунды (десятые обычно, если говорить про дотнет) и человек этой задержки даже не заметит. А вот задержку при анализе большого текста заметит. Даже если она в отдельном потоке убдет.

M> Там неоднозначностей очень много, язык уж больно сложен, и язык часто пополняется новыми терминалами (добавить в словарь в ворде). Здесь уже можно пожертвовать скростью. при этом, это ведь тоже типичная программисткая задача. Поэтому, я считаю, что необходимо предложить альтернативу.

И все же пополняться словами динамически не нужно. А человек настолько медлителен, что пересоздания кода парсера он незаметит. Ну, конечно если код будет достойно написан.

Здравствуйте, VladD2, Вы писали:

VD>Кстати, ты где нибудь видел человеческое описание преобразования НКА в ДКА и построение ДКА по синтаксическому дереву регулярных выражений. А то, то что я нашел это какая-то задница. Понять очень не просто.
ИМХО в "Красном драконе" написано достаточно понятно.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, mefrill, Вы писали:

M>>Поэтому, я на ходу произвожу моделированние ДКА делая параллельный проход по автоматам для каждого подходящего токена.

VD>Что то я не очень улвливаю. Т.е. ты создаешь из множества ДКА единый в рантайме?

Ага. Точнее, моделирую его создание в алгоритме лексического анализа. Ниже ты спрашивал, где найти хорошее описание алгоритма преобразования НКА в ДКА. Вот ключ к пониманию идеи этого алгоритма и есть то, о чем я писал. Идея проста: если у тебя есть НКА, значит из какого-то состояния есть по крайне мере два перехода по одному и тому же символу в разные состояния. Идея в том, чтобы каким-то образом "различить" эти переходы. Это возможно только "заглядыванием вперед" чтобы увидеть какие переходы будут дальше из следующих состояний. Вот идешь параллельно по таким двум разным путям, покуда не раличишь, т.е. не найдешь разные переходы. По пути получаешь последовательность состояний. Это есть подмножество множества всех состояний данного НКА. Поэтому состояниями ДКА будем подмножества состояний исходного НКА. Например, у тебя есть два ДКА 1-a->2-b->3 и 4-a->5-c->6. Один допускает строку ab, другой — строку ac. Сливая их, мы объединяем начальные состояния 1 и 4 и получаем недетерминизм: из состояния (1,4) есть два перехода по симолу a, в состояние 2 и состояние 5. Конструируем ДКА: идем по первомй пути, получаем последовательность {(1,4),2}, по второму пути — {(1,4),5}. Из первого состояния переход в состояние 3 по символу b, из второго в остояние 6 по символу c. Вот и все. Тоже самое делал и я в динамическом варианте лексического анализатора на основе ДКА для каждого токена. Вначале я запускал все ДКА с начального состояния, затем, считал переходы по входному символу. Если был недетерминизм, то как раз и получались такие пути-последовательности множеств состояний каждого ДКА.

M>>Можно сделать и так. Но, мне бы, например, хотелось предложить альтернативу. Чтобы данный генератор работал не только для создания разборщиков для языков программирования, но и для естественных языков (для продвинутых текстовых редакторов) и для интерфейсных динамически пополняемых языков.

VD>Я вот как раз сейчас пытаюсь создать реализацию лексера пригодную для тексового редактопра с подсветкой синтаксиса и возможно для автономного использования. Незнаю как для естественных языков, но для моих задач статического ДКА вроде хватает.

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

VD>Что же до "динамически пополняемых языков", то лексер то можно пополнить, но как на это отреагирует граматическая часть?

M>>Здесь не нужно решать эти проблемы на уровне лексического анализатора. Лексер для того и придуман, чтобы упростить анализ, позволяя выделять простые подмножества исходного языка перед сложным анализом. В данном случае можно просто возвращать что-то типа string-token, а затем, зная контекст, уже преобразовывать его в ключевое слово или идентификатор.

VD>А кто будет преобразовывать? Я пиршел к выводу, что проще всего это как раз делать в лексере.

M>> Но это уже проблема конкретного компилятора, а не генератора разборщиков.

VD>Проблема генератора парсеров в том, чтобы с его помощью можно было максимально просто создать парсер для любого сязыка.

M>> Можно конечно, ввести специальный контекст в лексический анализатор, но принципиально это нехорошо, т.к. ведет к излишнему усложнению системы.

VD>А идентификатор вместо "partial" — это хорошо? Ведь все равно будет проблема. Надо будет на уровне семантики проверять, что этот идентификатор на самом деле "partial". И это еще в лучшем случае. В худшем попрут неоднозначности.

Ну да, так и надо. Это как раз и позволит четко отделить семантику от синтаксиса.

M>> Можно реализовать систему фильтров. Например, в си++ токен ">>". Как известно, в определенном контексте это может быть окончание декларации шаблонного параметра шаблона плюс окончание декларации самого шаблона.

VD>Нет. Тут ты ошибашся. В С++ >> — это всегда оператор сдвига. По этому очень часто бывает ошибка когда во вложенных шаблонах народ забывает добавить пробел между знаками ">". А вот в C# >> действительно перегружен. Но есть правило празрешения конфлитка описанное в спецификации. Я тебе уже приводил это место: http://rsdn.ru/Forum/Message.aspx?mid=958690&only=1

Автор: VladD2
Дата: 22.12.04

Пару лет назад кто-то мне говорил, что в новом стандарте хотели сделать это свойство. Чтобы в шаблонном параметре можно было писать две завершающие угловые скобки без пробела. Значит, не сделали.

M>> Лексический анализатор, встречая подряд две угловые скобки, возвращает оператор правого побитового сдвига. Вот, пусть лексический анализатор возвращает всегда одну угловую скобку, а верхний фильтр, в зависимости от контекста, интерпретирует это как часть оператора сдвига или конец декларации шаблона или знак больше.

VD>Ну, примерно так и делается. Вот только такой "фильтр" выраждается в довольно сложную процедуру заглядывания вперед.

M>>Там нет "заглядываний вперед", происходит параллельное построение деревьев вывода снизу вверх.

VD>Т.е. еще на стадии построения парсера мы строим несколько автоматов и в местах где может появиться неоднозначность просто по парсим оба варианта, а там как получится?

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

M>>Нет, для любого LL(k) разбор идет за время O(n), для этого и придуманы множества FIRST и FOLLOW.

VD>Что-то мне казалось, что чем больше k, тем больше время.

Вообще говоря, конечно это так. Дело здесь в поиске по множествам FIRST и FOLLOW. Но это совершенно не зависит от длины входной строки, т.е. считается, в данном случае, константой. Т.е. скорость есть O(n), но величина константы больше.

VD>Кстати, ты где нибудь видел человеческое описание преобразования НКА в ДКА и построение ДКА по синтаксическому дереву регулярных выражений. А то, то что я нашел это какая-то задница. Понять очень не просто.

M>>Алгоритмов на самом деле много. Есть классический алгоритм Эрли, который не строит деревьев вывода. Есть мой алгоритм, который строит деревья вывода для классического алгоритма Эрли Есть, так называемый, быстрый алгоритм Жрли, придуманный двумя канадцами в конце 90-х годов. Вот этот алгоритм стравним по скорости с LR-анализатором, быстрее которого нет ничего,

VD>Ну, LL(1) без конфликтов еще никто не обгонял.

Ну как же, LR-анализатор быстрее работает. Он делает примерно тоже самое, но еще и учитывает контекст.

M>>но не строит деревьев вывода.

VD>А в чем такая проблема построить деревья вывода? Это ведь как я понимаю просто путь реального разбора. Так? Ну, так для каждой однозначной ветки можно построить ДКА. Для пересекающихся это будет общий ДКА с указанием что состояние принадлежит нескольким символам разных правил. Причем, похоже, что тут и LR нафиг не упал (с магазинами). Достаточно одного аннотированного ДКА и некой механики отслеживания путей. Если путей два, то просто отплевываем два. Если один из них оборвался, то просто забываем про него.

Не все так просто. Там сложнее на самом деле.

VD>В общем, или все очень просто и я не понимаю почему эта идея не пришла раньше никому в голову. Или у меня какая-то ошибка.

VD>Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.

Нет, LALR(k) — это тот же LR(k), но для уменьшения количества состояний LR(k)-автомата некоторые состояния сливаются. Это, так называемые, состояния с одиннаковыми ядрами. Получается в результате автомат, который хоть и, бывает, не допускает некоторые строки, как это делает LR(k)-автомат, но все-же достаточно мощный и, главное, содержит намного меньше состояний, что в 70-х годах имело большое значение. интересная проблема была в том, чтобы получить LALR(k)-атвомат, не строя LR(k)-автомата. Здесь в 1978 году был придуман алгоритм Де Ремьера, который является ни чем иным, как алгоритмом нахождения сильно связанных компонент графа за линейное время Боба Тарджана. Алгоритм, приведенный в красном драконе был применен в яке, я называю его "алгоритмом прибытия на станции" и он не так эффективен. В бизоне уже применен алгоритм Де Ремьера. Хотя бизон, на самом деле, это стыренный беркли як.

M>> Можно придумать (точнее, я уже придумал) как строить деревья вывода и для этого алгоритма. Тогда новый алгоритм будет работать быстро, а также будет позволять производить семантическую корректировку синтаксического анализа на ходу, отбрасывая семантически некорректные альтернативы и, тем самым, увеличивая скорость разбора. В этом и состоит преимущество алгоритма, который я предлагаю реализовать, перед GLR.

VD>Проясни для меня один вопрос. Вот если у нас есть некие два правила:
VD>

VD>A : B {C|D} E;
VD>A : B {C|D} F;
VD>

VD>то в твоем случае парсер будет разбирать два пути пареллельно или он все же пройдет неоднозначную цепочку "B {C|D}" и разрешит проблему найдя E или F?

Честно говоря, не вижу здесь неоднозначности. Разве два дерева вывода строится?

M>>Да нет у них проблем с сообщениями об ошибках. Есть проблемы с восстановлением работы после возникновения ошибки.

VD>Ну, можешь называть это как хочешь. Но при сканировании слева на право понять что случилось намного проще. Дубовые же Яки псото выкидывают сообщение "ожидается: ..." где "..." — это пара десятков токенов и думай что хочешь. В LL(1) парсере тебе говорят, что ожидается Х или У и нет проблем.

M>> Там это дело решается входом в так называемый "режим паники", что не есть хорошо во многих случаях. Алгоритм Эрли позволяет использовать длругую стратегию. Вообще, это тема очень обширная и требует отдельного большого обсуждения.

VD>Согласен, но по своему опыту замучу, что в LL(k) парсерах она решается куда проще. Да и рекурсивный спуск позволяет трассировать граматику понимая что происходит в данный момент.

Так и построение дерева снизу вверх также позволяет все это понимать. Только изучение труднее и все.

VD>>>Кстати, может быть первым делом сделать доступную статью и опубликовать ее у нас? Я мог бы помочь в плане разжевывания и упрощения изложения. Думаю это могло бы двинуть энтузиазм, ну, и за одно я бы по ходу пьесы разобрался бы в алгоритме.

M>>Да наверное, если что-то проклюнется, я бы мог написать такое введение (у меня что-то уже есть) и потом ответить на вопросы. Но, для этого, вероятно, необходимо уже отдельную ветку открыть. Статью я, конечно, могу прислать.

VD>Давай. И попробуем в интерактивном режиме довести ее до того состояния чтобы средний программист ее мог понять. Я как раз на этом собачек поел приизрядно.

Ага, вечером из дома вышлю.

M>>Ну вот, можно. Посмотрю что-то у меня уже есть, просто скопирую туда и статью присоеденю. А затем уже обсуждать будем.

M>>Да я не против, просто бывает, что так не получается. В случае расширяемых языков, например. Поэтому, я и говорю, что надо бы дать альтернативу.

VD>А как часто в таких языках появляются новые токены?

M>>Ну да, это более узкая задача построения трансляторов языков программирования. А вот, как быть с задаче построения анализатора грамматики в текстовом редакторе?

VD>На естесвтенном языке? Дык если слово отсуствует, то кроме как некую абстракцию типа "идентификатор" ты ее не определишь. А если пользователь пополнит словарь, то не грех и автомат перестроить. Ведь динамическая компиляция это доли секунды (десятые обычно, если говорить про дотнет) и человек этой задержки даже не заметит. А вот задержку при анализе большого текста заметит. Даже если она в отдельном потоке убдет.

Ну как хочешь. Можно реализовать только быстрый алгоритм Эрли. Если ставить только специфическую задачу разработки транслятора для языков программирования.

M>> Там неоднозначностей очень много, язык уж больно сложен, и язык часто пополняется новыми терминалами (добавить в словарь в ворде). Здесь уже можно пожертвовать скростью. при этом, это ведь тоже типичная программисткая задача. Поэтому, я считаю, что необходимо предложить альтернативу.

VD>И все же пополняться словами динамически не нужно. А человек настолько медлителен, что пересоздания кода парсера он незаметит. Ну, конечно если код будет достойно написан.

mefrill,

m> Пару лет назад кто-то мне говорил, что в новом стандарте хотели сделать
m> это свойство. Чтобы в шаблонном параметре можно было писать две
m> завершающие угловые скобки без пробела. Значит, не сделали.

Просто новый стандарт еще не выходил. Выйдет году в 2009 или около того.

Здравствуйте, WolfHound, Вы писали:
WH>ИМХО в "Красном драконе" написано достаточно понятно.

Просто никак. Первод убит до ужаса.

Здравствуйте, mefrill, Вы писали:

M>Ага. Точнее, моделирую его создание в алгоритме лексического анализа. Ниже ты спрашивал, где найти хорошее описание алгоритма преобразования НКА в ДКА. Вот ключ к пониманию идеи этого алгоритма и есть то, о чем я писал. Идея проста: если у тебя есть НКА, значит из какого-то состояния есть по крайне мере два перехода по одному и тому же символу в разные состояния. Идея в том, чтобы каким-то образом "различить" эти переходы. Это возможно только "заглядыванием вперед" чтобы увидеть какие переходы будут дальше из следующих состояний. Вот идешь параллельно по таким двум разным путям, покуда не раличишь, т.е. не найдешь разные переходы. По пути получаешь последовательность состояний. Это есть подмножество множества всех состояний данного НКА. Поэтому состояниями ДКА будем подмножества состояний исходного НКА. Например, у тебя есть два ДКА 1-a->2-b->3 и 4-a->5-c->6. Один допускает строку ab, другой — строку ac. Сливая их, мы объединяем начальные состояния 1 и 4 и получаем недетерминизм: из состояния (1,4) есть два перехода по симолу a, в состояние 2 и состояние 5. Конструируем ДКА: идем по первомй пути, получаем последовательность {(1,4),2}, по второму пути — {(1,4),5}. Из первого состояния переход в состояние 3 по символу b, из второго в остояние 6 по символу c. Вот и все. Тоже самое делал и я в динамическом варианте лексического анализатора на основе ДКА для каждого токена. Вначале я запускал все ДКА с начального состояния, затем, считал переходы по входному символу. Если был недетерминизм, то как раз и получались такие пути-последовательности множеств состояний каждого ДКА.

Ясно. Но это интерпретация, а значит замедление. Все же лучше объеденять ДКА заранее и аннотировать общие состояния (как я уже описывал).

M>Ну может быть, для этих задач и хватает. Я еще писал не только о подсветке, а о синтаксическом анализе предложений, как в ворде подчеркивание зеленым цветом, не красным.

Как я уже говорил, добавление новых токенов настолько редки по сравнению с постоянным анализом огромных текстов, что я бы предпочел динамическую компиляцию. Я переодически правлю генератор парсеров CocoR и даже не замечаю его перекомпиляции.

VD>>А идентификатор вместо "partial" — это хорошо? Ведь все равно будет проблема. Надо будет на уровне семантики проверять, что этот идентификатор на самом деле "partial". И это еще в лучшем случае. В худшем попрут неоднозначности.

M>Ну да, так и надо. Это как раз и позволит четко отделить семантику от синтаксиса.

Дык намного проще заложить проверку в лексере. Там делов то будет:

if (token.Kind == Tokens.Partial)
{
    Token next = Peek();
    
    if (next.Kind == Tokens.Class)
        token = Tokens.Identifier;
}

или что-то в этом ролде. А вот в парсере... Как обяснить автомату?

M>Пару лет назад кто-то мне говорил, что в новом стандарте хотели сделать это свойство. Чтобы в шаблонном параметре можно было писать две завершающие угловые скобки без пробела. Значит, не сделали.

Последний стандарт С++ был впринят в 1998-ом году. Может это он о том, что будет в 2008? Ну, да это меня пока не трогает. Ладно. Это все фигня.

M>Нет, там по другому. Автоматы строятся в быстром алгоритме Эрли, но только для того, чтобы увеличить скорость разбора, сам алгоритм Эрли обходится без автоматов.

Хм... загадочно. Опять боюсь что "быстрый" на деле окажется не очень быстрым.

VD>>Ну, LL(1) без конфликтов еще никто не обгонял.

M>Ну как же, LR-анализатор быстрее работает. Он делает примерно тоже самое, но еще и учитывает контекст.

Да что же может быть быстрее простого рекурсивного спуска?

VD>>Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.

M>Нет, LALR(k) — это тот же LR(k),

Ну, это не важно. Я про саму суть. Как только вместо некоторого k появляется * (т.е. бесконечность), то возможно разница между снизу вверх и сверху вниз уже может стереться. Ведь всегда можно простроить все дерево со всеми неоднозначностями до конца и получить просто направленный ациклический граф. А там уже можно безать по нему и тупо делать то что нужно.

Вопрос опять таки в обработке ошибок. Ведь не так просто бодет сопоставить ДКА и исходную граматику.

VD>>Проясни для меня один вопрос. Вот если у нас есть некие два правила:
VD>>

VD>>A : B {C|D} E;
VD>>A : B {C|D} F;
VD>>

VD>>то в твоем случае парсер будет разбирать два пути пареллельно или он все же пройдет неоднозначную цепочку "B {C|D}" и разрешит проблему найдя E или F?

M>Честно говоря, не вижу здесь неоднозначности. Разве два дерева вывода строится?

Ну, это как реализовать. Я зе не знаю суть предлагаемых тобой алгоритмов.

M>Так и построение дерева снизу вверх также позволяет все это понимать. Только изучение труднее и все.

Ага. Всего лишь труднее. Остается только понять насколько.

M>Ага, вечером из дома вышлю.

Тогда поключай ее к новой теме.

M>Ну как хочешь. Можно реализовать только быстрый алгоритм Эрли. Если ставить только специфическую задачу разработки транслятора для языков программирования.

А как же какая-то там ошибка?

Здравствуйте, VladD2, Вы писали:



VD>>>Хотя может это и есть LALR(*) вид сбоку и LL(*), LALR(*) с GLL есть не что иное как разные точки зрения на один алгоритм.

M>>Нет, LALR(k) — это тот же LR(k),

VD>Ну, это не важно. Я про саму суть. Как только вместо некоторого k появляется * (т.е. бесконечность), то возможно разница между снизу вверх и сверху вниз уже может стереться. Ведь всегда можно простроить все дерево со всеми неоднозначностями до конца и получить просто направленный ациклический граф. А там уже можно безать по нему и тупо делать то что нужно.


Очень интересно как они будут обрабатывать левую рекурсию типа

  A-> ( A "," a )| a

Здравствуйте, VladD2, Вы писали:

WH>>ИМХО в "Красном драконе" написано достаточно понятно.
VD>Просто никак. Первод убит до ужаса.
Ну не знаю я с первого раза понял

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Просто новый стандарт еще не выходил. Выйдет году в 2009 или около того.

Уже на год подвинули?

Здравствуйте, WolfHound, Вы писали:

WH>Ну не знаю я с первого раза понял

Понял? Попробуй написать на ЯП. А я посмотрю сколько времени и сил убъёш. Ну, или в своих словах пересказать.

VladD2,

> ПК> Просто новый стандарт еще не выходил. Выйдет году в 2009 или около того.
>
> Уже на год подвинули?

Это первая относительно официально озвученная цифра. До этого были только частные догадки.

Здравствуйте, VladD2, Вы писали:

WH>>Ну не знаю я с первого раза понял
VD>Понял? Попробуй написать на ЯП. А я посмотрю сколько времени и сил убъёш. Ну, или в своих словах пересказать.
Писать не буду. Не до того сечас. А словами объяснить могу.
Преобразование НДКА в ДКА.
Из каждого состояния НДКА может быть неограниченое колличество переходов по одному и томуже сигналу. Так же может быть неограниченое колличество эпсилон переходов те переходов по которым может быть произведен переход по любому сигналу.
Имея на входе НДКА нужно построить ДКА. Для этого нам понадобятся две вспомогательные функции.
Первая функция (Move) по списку состояний НДКА и сигналу должна возвращать список состояний НДКА в которые можно перейти из данных состояний по данному сигналу.
Вторая функция (EpsilonMove) должна возвращать по списку состояний НДКА список состояний НДКА в которые можно перейти по одному или нескольким эпсилон переходам также в это множество нужно включить исходное множество переходов.
Работа алгоритма сводится к тому что несколько состояний НДКА превращаютя в одно состояние ДКА.
Состояния ДКА с одинаковым набором состояние НДКА являются одним и темже состоянием.
Теперь сам алгоритм

Берем список стартовых состояний НДКА и применяем EpsilonMove. 
Мы получили стартовое состояние ДКА. 
Добавляем это состояние в список состояний ДКА.
пока есть непомеченые состояния ДКА
{
    состояние = берем первое не помеченое состояние ДКА
    помечаем состояние
    для каждого сигнала
    {
        новое_состояние = EpsilonMove(Move(состояние, сигнал))
        если новое_состояние еще не добавлено то добавляем его
        создаем переход по текущему сигналу из состояния в новое_состояние
    }
}

Понятно?
Чтобы было понятнее посмотри пример из красного дракона на странице 130

Как-то больно примитивно. Фактически переложение доказательства теоремы о том, что для любого НДКА существует эквивалентный ДКА, единственная здравая мысль — строить состояния ДКА динамически, но это неизбежно, поскольку ДКА из НДКА получается невероятно большим.

Здравствуйте, Quintanar, Вы писали:

Q>Как-то больно примитивно. Фактически переложение доказательства теоремы о том, что для любого НДКА существует эквивалентный ДКА, единственная здравая мысль — строить состояния ДКА динамически, но это неизбежно, поскольку ДКА из НДКА получается невероятно большим.

На практике, не таким уж и большим, ведь не всякое подмножество состояний исходного НКА есть состояние полученного ДКА, это еще зависит от количества переходов. Кроме того, можно затем мимнимизировать полученный ДКА по количеству состояний, часто получается ДКА с количеством состояний, меньшим чем исходный НКА.

Здравствуйте, little_alex, Вы писали:

VD>>Ну, это не важно. Я про саму суть. Как только вместо некоторого k появляется * (т.е. бесконечность), то возможно разница между снизу вверх и сверху вниз уже может стереться. Ведь всегда можно простроить все дерево со всеми неоднозначностями до конца и получить просто направленный ациклический граф. А там уже можно безать по нему и тупо делать то что нужно.

_>Очень интересно как они будут обрабатывать левую рекурсию типа
_>

  A->> ( A "," a )| a
_>

_>

В том то и дело, что никак. Такова цена метода построения дерева вывода сверху вниз и с разбором альтернатив в глубину. Поэтому я и говорю, что толку от этого GLL будет мало, альтернативы то он распараллеливать будет, но на простой левой рекурсии зациклится.

Здравствуйте, fplab, Вы писали:

F>У меня есть такая. Кому надо — вышлю по запросу в мыло. Объем 1.2 Мб в zip

Был бы очень признателен uladzimir <at> gmail.com