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

CVL>Ну и как прогресс? Есть ли уже наработанный материал? Проект стартовал?

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

Предлагаю присоедениться к обсуждению тем, кому интересно.

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

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

M>Предлагаю присоедениться к обсуждению тем, кому интересно.

Меня смущают оценки производительности алгоритма. O(n*n) и темболее O(n*n*n) не приемлемые характеристики для реального применения.

Насктолько граматики вроде C# 2.0/C++ будут близки к O(n) (или наоборот)?

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

VD>Меня смущают оценки производительности алгоритма. O(n*n) и темболее O(n*n*n) не приемлемые характеристики для реального применения.
VD>Насктолько граматики вроде C# 2.0/C++ будут близки к O(n) (или наоборот)?

Ну так и будут O(n) если язык таков, что есть грамматика, позволяющая линейный разбор вести. Для C#, как я понимаю, такая грамматика есть и сам синтаксис проектировался с учетом того, чтобы его грамматика была линейной. Константа там будет побольше примерно в два раза. Для LR-анализаторов есть экспериментальная оценка: алгоритм Эрли примерно в два раза медленнее работает. Но ведь этот алгоритм для линейных грамматик нет смысла применять, для этого есть более быстрые алгоритмы. Алгоритм Эрли необходим когда язык сложен, когда его грамматика неоднозначная или не позволяет разбирать без откатов. Или когда хочется написать анализатор на основе той грамматики, которая кажется естественной для языка и для человека (как в стандарте си++ например). Не думать про то левую рекурсию или цепные правила в грамматике. В противном случае, конечно, применять этот алгоритм нет смысла.

Вообще, о чем бы мне еще хотелось поговорить, это о языках с расширяющимся синтаксисом. Всем известны, например, сложности с синтаксисом шаблонов Си++, которые очень затрудняют програмимрование и требуют специальных знаний. Можно было бы попытаться позволить расширять синтаксис языка самому пользователю так, чтобы этот синтаксис отражал специфику программной задачи. Например, если я реализую анонимные функции по типу лямбда исчисления, то ввести в язык соответствующие синтаксические правила и ключевые слова. Или, делаю я финансовую программу, ввожу в язык синтаксис, описывающий финансовые термины, строю на них функции и т.д. это было бы здорово. Здесь, конечно, куча невыясненных проблем возникает. С синтаксисом вот я вроде уже разобрался, алгоритм будет работать всегда и достаточно быстро. Но осталась семантика, как ее задавать, как разрешать неоднозначности и т.д. Вот кто что думает по этому поводу?

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

M>Предлагаю присоедениться к обсуждению тем, кому интересно.

А почему не используется сжатие деревьев вывода?
Когда деревья соответствующие разным альтернативам делят между собой поддеревья.

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

_>А почему не используется сжатие деревьев вывода?
_>Когда деревья соответствующие разным альтернативам делят между собой поддеревья.

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

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

1. ***

Боюсь, что в реальной жизни скорость парсинга может оказаться неприемлемой. В том же Шарпе есть куча мест где при LL()-анализе приходится заглядывать вперед на неопределенную глубину. Что будет в этом случае?

Ну, например, из свежего. В шарпе есть нулбл-типы (добавляющие к вэлью-типам возможность хранить состояние null). Синтаксис описания нулбл-типа упрощенное таков:

NulubleType    :    ID "?";

Между тем еще есть оператор "?:":

Cond : Expr "?" Expr : Expr;

причем есть выражения Expr которые в правой части содержат тип (возможно нулбл).
Естественно и сам Cond может быть выражением (Expr).

Получаем ситуации:

int? i = 0;
Console.WriteLine(i is int ?);
Console.WriteLine(i is int ? "+" : "-");
Console.WriteLine(i is int ? ? "+" : "-");

Первый вариант возвратит True, а остальные "+". То есть в первом "int ?" — это описание типа, во втром тип int и начало оператора "?:", а в третьсем снова тип "int ?".

Предлагаемый твой алгоритм как разрулит пдобную ситуацию?

2. ***

Я поглядел алгоримт. Надо признаться, что столь формальное описание жудко путает и голова начинает резко болеть. Так что полностью я его не понял (пока). Но сразу бросается в глаза, то что не строится никаких автоматов и не генерируется код. Вместо этого происходит интерпретакция. Даже если парсер будет О(n), если он будет интерпретирующим, то скорость по сравнению с классчическим парсером будет в 10 и более раз меньше! Это как ты понимашь точно так же может оказаться аргументов против алгоритма.

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

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


VD>1. ***
VD>Боюсь, что в реальной жизни скорость парсинга может оказаться неприемлемой. В том же Шарпе есть куча мест где при LL()-анализе приходится заглядывать вперед на неопределенную глубину. Что будет в этом случае?

...

VD>Предлагаемый твой алгоритм как разрулит пдобную ситуацию?

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

VD>2. ***

VD>Я поглядел алгоримт. Надо признаться, что столь формальное описание жудко путает и голова начинает резко болеть. Так что полностью я его не понял (пока). Но сразу бросается в глаза, то что не строится никаких автоматов и не генерируется код. Вместо этого происходит интерпретакция. Даже если парсер будет О(n), если он будет интерпретирующим, то скорость по сравнению с классчическим парсером будет в 10 и более раз меньше! Это как ты понимашь точно так же может оказаться аргументов против алгоритма.

Нет, скорость примерно в два раза меньше чем у LR(1)-анализатора, это подтверждено экспериментально. Кроме того, аналогия с интерпретаторами и компиляторами здесь не совсем уместна. Для алгоритма синтаксического анализа есть два параметра: КС-грамматика и входная строка. Так как грамматика обычно не меняется от одного запуска алгоритма синтаксического анализа к другому, то фактически представляет собой постоянную величину. Поэтому, из грамматики можно попытаться еще до первого запуска алгоритма вытащить какую-то информацию о ее внутренней структуре. Какую информацию зависит уже от метода синтаксического анализа. Для LL(k)-анализатора это будет First и Follow множества, для LR(k)-анализатора это будет LR(k)-автомат. Но такая информация не увеличивает скорость анализа, она обычно расширяет множество грамматик, которые данный алгоритм может обрабатывать. Например, LR(1)-анализатор обрабатывает больше грамматик (видов грамматик) чем LR(0)-анализатор. Алгоритм Эрли тоже можно оптимизировать так, чтобы лишнего поиска не делалось. Тогда, лишнее время будет тратиться только на создание ситуаций, т.е. на работу с памятью. Скорость, как я уже говорил, примерно в два раза ниже.

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

Это ведь тоже можно оптимизировать. Я в коде, который прислал, сделал примитивный распределитель памяти, в котором эти самые ситуации кэшируются. Работает достаточно быстро. Я читал сообщение, подобный парсер обрабатывал за секунду примерно 30 тысяч строк си кода, скорость, я считаю, вполне нормальная. Для языка формул Excel, языка с очень сложной и неоднозначной грамматикой, скорость была примерно 20 тысяч знаков в секунду. Самое неприятное — это большой расход памяти, ведь списки ситуаций мы вынуждены хранить все до тех пор, пока все строка не будет прочитана до конца. В общем, единственный способ проверить скорость — это запустить алгоритм на реальной грамматике, напрмиер, для языка си и посмотреть скорость его работы.

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

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

Directly-Executable Earley Parsing

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

_>Directly-Executable Earley Parsing

У этого deep к сожалению очень большие проблемы с построением деревьев для грамматик с эпсилон-правилами. Чтобы правильно деревья строить приходится модифицировать исходную грамматику. Этой теме посвящена вторая часть статьи. По моему мнению, не стоит оно того. Т.е. алгоритм Эрли должен применяться для анализа сложных языков, для которых объе памяти не вопрос по сравнению со временем и удобством компиляции. Большое количество ситуаций и, как следствие, траты памяти — это бич этого метода. Но у каждого метода (как и у каждого человека) имеются свои скелеты в шкафу. Главное, не выходить за нишу его применения. Для алгоритма Эрли эта ниша есть — сложные, неоднозначные языки, открытые языки. Производить синтаксический анализ простого языка с помощью этого алгоритма — все-равно что стрелять из пушки по воробьям.

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

M>Алгоритм разрулит любую ситуацию. Но здесь надо понять, что принцип работы немного другой. При встрече альтернатив алгоритм строит возможные деревья параллельно. Т.е. там где LL(k)-анализатор заглядывает вперед чтобы выбрать ту или иную альтернативу, алгоритм Эрли просто берет и строит все альтернативы одновременно. Затем, на том месте, где выводится только одна альтернатива, т.е. там куда заглядывает LL(k)-анализатор, алгоритм Эрли оставит только одну альтернативу.

Вот меня и интересует во что обойдется этот параллелизм? И не будет ли слишком большого количества разветвлений только потому, что грамматика не написана в лоб?

M>Нет, скорость примерно в два раза меньше чем у LR(1)-анализатора, это подтверждено экспериментально. Кроме того, аналогия с интерпретаторами и компиляторами здесь не совсем уместна. Для алгоритма синтаксического анализа есть два параметра: КС-грамматика и входная строка. Так как грамматика обычно не меняется от одного запуска алгоритма синтаксического анализа к другому, то фактически представляет собой постоянную величину. Поэтому, из грамматики можно попытаться еще до первого запуска алгоритма вытащить какую-то информацию о ее внутренней структуре. Какую информацию зависит уже от метода синтаксического анализа. Для LL(k)-анализатора это будет First и Follow множества, для LR(k)-анализатора это будет LR(k)-автомат. Но такая информация не увеличивает скорость анализа, она обычно расширяет множество грамматик, которые данный алгоритм может обрабатывать. Например, LR(1)-анализатор обрабатывает больше грамматик (видов грамматик) чем LR(0)-анализатор. Алгоритм Эрли тоже можно оптимизировать так, чтобы лишнего поиска не делалось. Тогда, лишнее время будет тратиться только на создание ситуаций, т.е. на работу с памятью. Скорость, как я уже говорил, примерно в два раза ниже.

Хм.
1. В твоей статье описан механизм динамической интерпретации. И ни слова не сказано о том как сделать так чтобы ее избежать.
2. В ходе работы алгоритма создается куча объектов, заполняются массивы и по ним делается поиск пербором. (насколько я смог понять написанное). В LL(1)-анализаторе построеном CocoR (которым я сейчас пользуюсь) у меня вообще не создается динимических объектов и не производится никаких поисков. LALR-построители тоже генерируют автотат на базе свитчей. Так как же тут может быть сравнимая производительность? Это все равно как компилятор и интерпретатор. Для обоих программы будут делать одно и тоже, но скомпилированный код не буедет делать кучи лишних действий и потому будет в 10 раз быстрее.

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

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

Мой парсер C# 2.0 парсит проект содержащий 42 493 C#-файлов (201 279 узлов AST) за 0.32 сек. (на AMD 64 3500+). Причем это время включает чтение данных из файлов.
C# в разы сложнее С. Написан парсер на том же C#. Причем парсер не только разбирает код, но и строит AST. Так что 30000 строк С-кода за секунду — это довольно медленно. Хотя возможет парсер был написан не супер проффесионально.

M> Для языка формул Excel, языка с очень сложной и неоднозначной грамматикой, скорость была примерно 20 тысяч знаков в секунду.

А что же такого сложного в языке формул Excel? Там же одни выражения. Это же сабсэт бэйскика.


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

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

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

Ага. Только для этого нужно сделать парсер.

В принципе если алгоритм не сложный, то можно сделать прототип на C# взяв в качестве лексера лексер от CocoR и на CocoR-е же сделать разбор файла граматики. Тогда может за неделю что-то удастся наваять и можно будет сравнить это дело с моим же парсером С# (скормив новому пасреру граматику шарпа предварительно выкинув из нее все дополнительные проверки).

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

M>У этого deep к сожалению очень большие проблемы с построением деревьев для грамматик с эпсилон-правилами. Чтобы правильно деревья строить приходится модифицировать исходную грамматику. Этой теме посвящена вторая часть статьи. По моему мнению, не стоит оно того. Т.е. алгоритм Эрли должен применяться для анализа сложных языков, для которых объе памяти не вопрос по сравнению со временем и удобством компиляции. Большое количество ситуаций и, как следствие, траты памяти — это бич этого метода. Но у каждого метода (как и у каждого человека) имеются свои скелеты в шкафу. Главное, не выходить за нишу его применения. Для алгоритма Эрли эта ниша есть — сложные, неоднозначные языки, открытые языки. Производить синтаксический анализ простого языка с помощью этого алгоритма — все-равно что стрелять из пушки по воробьям.

А можно примеры простых языков? Вот C++/C# — это простые языки? Если да, то я вообще не вижу необходимости в подобном парсере. Елси нет, то надо понимать, что скорость парсинга для них очень важна.

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

Лично меня удовлетворил бы LL(*)-парсер. Но к сожалению пока я не видел работающих его реализаций.

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

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

_>Directly-Executable Earley Parsing

Забавна строчка там про то как они попытались создать парсер Явы на своем чуде. Получился монстр который еще хрен скомпилируешь. А ведь граматика Явы — это детский сад по сравению с граматикой воторого Шарпа.

В общем, если автоматный вариант так тормозит, то интерпретируемый будет вообще не пригоден для этой жизни.

Вывод не утешительный. Это слишком дорого на сегодня.

Подождем выхода АНТЛР 3. А там видно будет.

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

VD>Хм.
VD>1. В твоей статье описан механизм динамической интерпретации. И ни слова не сказано о том как сделать так чтобы ее избежать.
VD>2. В ходе работы алгоритма создается куча объектов, заполняются массивы и по ним делается поиск пербором. (насколько я смог понять написанное). В LL(1)-анализаторе построеном CocoR (которым я сейчас пользуюсь) у меня вообще не создается динимических объектов и не производится никаких поисков. LALR-построители тоже генерируют автотат на базе свитчей. Так как же тут может быть сравнимая производительность? Это все равно как компилятор и интерпретатор. Для обоих программы будут делать одно и тоже, но скомпилированный код не буедет делать кучи лишних действий и потому будет в 10 раз быстрее.

Ну почему же не создает дополнительных структур? LALR-анализаторы работают с автоматом и автомат этот тем объемнее, чем объемнее грамматика. Кроме того, есть магазин, который может очень много состояний держать, а пользовательских ссылок на узлы. Там тоже создается много чего. И в LL(1)-анализаторах много чего создается, например те же множества First и Follow. Просто там все кодируется вручную, т.е. спрятано в коде. Ведь при вызовах функций точно такой-же магазин создается. Конечно, в алгоритме Эрли таких структур создается больше. Но, как я уже говорил, нельзя эти аллгоритмы сравнивать, они просто разной весовой категории. По определнию, алгоритмы LR и LL анализа будут и быстрее и экономичнее. Поэтому, там где важна скорость в ущерб удобству и естественности необходимо использвать эти алгоритмы. А вот там, где эти алгоритмы неприменимы, где важно оставить грамматику естественной, там можно использовать алгоритм Эрли. Такая у него ниша.

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

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

VD>Мой парсер C# 2.0 парсит проект содержащий 42 493 C#-файлов (201 279 узлов AST) за 0.32 сек. (на AMD 64 3500+). Причем это время включает чтение данных из файлов.
VD>C# в разы сложнее С. Написан парсер на том же C#. Причем парсер не только разбирает код, но и строит AST. Так что 30000 строк С-кода за секунду — это довольно медленно. Хотя возможет парсер был написан не супер проффесионально.

Зря ты сравниваешь эти алгоритмы. Не будет никогда алгоритм Эрли работать так же, как LL-анализатор, не та специфика. Использовать аллгоритм Эрли для анализа языка, синтаксис которого специально проектировался с учетом того, чтобы быть LL(1) совместимым, — напрасная роскошь. Алгоритм Эрли работает там, где линейные анализаторы не применимы.

VD>А что же такого сложного в языке формул Excel? Там же одни выражения. Это же сабсэт бэйскика.

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

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

Нет, к сожалению нельзя, ведь списки строятся не для всех строк языка, а только для данной конкретной входной строки и специфичны именно для нее. Но выделение таких списков при запуске парсера совсем не делает этот парсер более медленным. Мы просто резервируем достаточное количество памяти заранее и затем на выделение памяти не тратится ни милисекунды. В общем, надо просто взять и проверить. В статье Faster Earley parser Хорспул и Эйкок привели экспериментальные данные, в которых их реализация алгоритма Эрли работает примерно в два раза медленнее, чем бизон. Я считаю, что такая скорость более чем достаточная плата за удобство написания парсера.

VD>Ага. Только для этого нужно сделать парсер.

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

VD>В принципе если алгоритм не сложный, то можно сделать прототип на C# взяв в качестве лексера лексер от CocoR и на CocoR-е же сделать разбор файла граматики. Тогда может за неделю что-то удастся наваять и можно будет сравнить это дело с моим же парсером С# (скормив новому пасреру граматику шарпа предварительно выкинув из нее все дополнительные проверки).

Вот-вот, но алгоритм уже есть. Это то, что я присоеденил вместе со статьей.

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

VD>А можно примеры простых языков? Вот C++/C# — это простые языки? Если да, то я вообще не вижу необходимости в подобном парсере. Елси нет, то надо понимать, что скорость парсинга для них очень важна.

Си++ — это не простой язык. Его грамматика полна неоднозначностей и как раз для него не применимы такие алгоритмы, как LR или LL анализаторы. Поэтому, вполне возможно использовать алгоритм Эрли для синтаксического анализа языка си++. Относительно си шарп, так вроде же грамматика этого языка специально спроектирована так, чтобы через LL(1) разбираться? Или я ошибаюсь?

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

Да не бывает так. Это же закон, чем грамматика сложнее, т.е. чем поиск сложнее — тем скорость разбора ниже. И ничего не сделаешь, закон Природы.

VD>Лично меня удовлетворил бы LL(*)-парсер. Но к сожалению пока я не видел работающих его реализаций.

По моему мнению, это все фигня и шарлатанство. LL(*)-алгоритм совершенно ничем по мощности не отличается от LL(k)-анализаторов. Те же проблемы с левой рекурсией. Сам алгоритм, как я уже писал, был придуман Борщевым почти сорок лет назад и известен в науке о синтаксисе естественных языков как сети Вудса. Чудес не бывает.

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

M>Зря ты сравниваешь эти алгоритмы. Не будет никогда алгоритм Эрли работать так же, как LL-анализатор, не та специфика. Использовать аллгоритм Эрли для анализа языка, синтаксис которого специально проектировался с учетом того, чтобы быть LL(1) совместимым, — напрасная роскошь. Алгоритм Эрли работает там, где линейные анализаторы не применимы.

К сожалению LL(1)- и LALR()- парсеры не пригодны для парсинга большинства современных языков. Я уже задолбался писать рукапашные заглядывания вперед для CocoR-парсера C# 2.0. А до этого устал ржать от глупости Яка по поводу граматики C# 1.0. Даже примитивный SQL не является совместимым с LL(1).

Потому мне и интересна эта тема. Мне интересны исследования в языковой области. Но у меня нет возможности убивать по неделе на каждое несоотвествие грамматики LL(1)-ограничениям.

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

Это и в Васике есть. И его парсер считается очень простым.

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

Дык, в приведенной рядом ссылке говорится, что удалось создать автоматный Эрли-парсер. И хотя результаты у них не супер, но хоть что-то. Рядом результаты обычного Эрли-парсера смотрятся намного хуже.

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

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

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

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

К сожалению это груда кода на С++ который не так то просто понять. К тому же он не позволяет взять в качестве входа граматику в виде текстового файла и выдать результат в осмысленном виде.

VD>>В принципе если алгоритм не сложный, то можно сделать прототип на C# взяв в качестве лексера лексер от CocoR и на CocoR-е же сделать разбор файла граматики. Тогда может за неделю что-то удастся наваять и можно будет сравнить это дело с моим же парсером С# (скормив новому пасреру граматику шарпа предварительно выкинув из нее все дополнительные проверки).

M>Вот-вот, но алгоритм уже есть. Это то, что я присоеденил вместе со статьей.

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

Так как я последнее, свободное, время занимался созданием граматики для C# 2.0, то мог бы попробовать, с твоей помощью реализовать алгоритм парсера на C#.

Лексер уже есть. Причем он будет идентичен с лексером для CocoR-овского парсера, так что сравнивать можно будет довольно точно.

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

Только одно но. Быстро восоздать алгоритм по твоей статье и коду на С++ мне явно не удастся. Нужно более простое объяснение. Можно попробывать сделать что-то в интерактивном режиме.

Если есть желание можно попробовать.

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

M>Си++ — это не простой язык. Его грамматика полна неоднозначностей и как раз для него не применимы такие алгоритмы, как LR или LL анализаторы. Поэтому, вполне возможно использовать алгоритм Эрли для синтаксического анализа языка си++. Относительно си шарп, так вроде же грамматика этого языка специально спроектирована так, чтобы через LL(1) разбираться? Или я ошибаюсь?

К сожалению это не так. Начиная с того, что реальная граматика из стандарта праворекурсивна и заканчивая тем, что имеется куча мест где LL(1) никуда не годится.

Вот здесь: http://rsdn.ru/projects/rsharp/svnsnapshot.7z лежит граматика шарпа для CocoR. Реально нужно смотреть файл CS.atg. Погляди сколько в нем конструкций IF() и врукопашную написанных функций заглядывания вперд.

В общем, реальных не однозначностей там почти нет. Но для LL(1)- LALR-парсеров неоднозначностей просто море.

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

M>Да не бывает так. Это же закон, чем грамматика сложнее, т.е. чем поиск сложнее — тем скорость разбора ниже. И ничего не сделаешь, закон Природы.

Ждать милостей от природы не приемлемо!

VD>>Лично меня удовлетворил бы LL(*)-парсер. Но к сожалению пока я не видел работающих его реализаций.

M>По моему мнению, это все фигня и шарлатанство. LL(*)-алгоритм совершенно ничем по мощности не отличается от LL(k)-анализаторов.

Ты сильно ошибашся. LL(k) к сожалению ничего не дает. Приходится использовать все те же рукопашные заглядвания вперед. К тмоу же качественных LL(k)-парсеров тоже нет. Есть LL(1), но это вообще задница. И есть LL(k) где k обеспечивается банальными заглядываниями вперед, что как ты понимашь тормоза еще те.

АНТЛР 3 вроде как должен сделать то что нужно, но его альфы которые я смотрел "вешаются" (уходят в безсконечный цикл или банально вылетают по переполнению стека) на куда более простых вещах нежели граматика Шарпа.

M> Те же проблемы с левой рекурсией.

А это как раз не проблема. Среда для АНТЛР-а обладает средствами ее выяления и рефакторингом который легко переписывает правило устраняя ее.

M>Сам алгоритм, как я уже писал, был придуман Борщевым почти сорок лет назад и известен в науке о синтаксисе естественных языков как сети Вудса. Чудес не бывает.

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