Создание синтаксического анализатора (парсера) по контекстно-свободным грамматикам

[alek_sys]

Устремление хорошее, но нужно начинать с теории. Dragon book, возможно, будет сложновата для основ — но я ничего лучше не знаю :). А то, что пока у вас сделано — несерьезно, увы.

Для интереса, можете посмотреть как сделаны различные генераторы — lex / yacc, ANTlr, Coco/R или даже PEG в Nemerle

[brainworm]

Ну это «любительская работа», так сказать, и я не претендую на серьёзность. Оно работает, и это главное, можно использовать в своих каких-то программах.

[impwx]

Есть очень хорошая книга, называется «Языки программирования и методы трансляции» Сергея Свердлова — там очень просто и доходчиво представлена реализация небольшого языка на паскале. Имхо перед драгонбуком лучше ее читать, чтобы хоть что-то понять, а потом уже углублять знания.

[SabMakc]

Для 14 лет неплохо (если в профиле все верно указано), даже очень неплохо.
Рекомендую глубже изучить теорию по построению компиляторов.

И несколько замечаний:
1) Построение универсального синтаксического анализатора невозможно в принципе, даже теоретически.
2) Опасаться присвоения кода несколько преждевременно, вряд ли там будет что-либо уникальное — множество людей создавали нечто подобное при обучении в институте, не говоря уже, что множество полноценных компиляторов доступны в исходниках.

[brainworm]

>> Для 14 лет неплохо
Ну… гмм… вообще-то 13 (если я родился позже июня)

>> Построение универсального синтаксического анализатора невозможно в принципе
С чего это? Приведите аргументы, пожалуйста…

>> 2)
Хорошо, скоро обновлю архив.

[SabMakc]

С чего это? Приведите аргументы, пожалуйста…

Если честно, на этот вопрос отвечает теория.

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

Но не все грамматики возможно привести к указанным правилам. Если не ошибаюсь, грамматика типа 0 не поддается и, возможно, типа 1 (или не все 1го типа поддаются).

[brainworm]

Оу… Даже не пробовал читать об этом статьи Википедии…
Оказывается, я изобрёл велосипед (литерал = терминал, реферал = нетерминал, а любой синтаксис = только контекстно-свободная грамматика)… Ужас какой. Придется статью переправить немного.

[SabMakc]

Велосипед, изобретенный собственноручно — гораздо полезнее прочитанной заранее книги.
Главное — вовремя перейти от велосипеда к чтению книги нужной тематики (или от собственного велосипеда — к аналогичному общеиспользуемому).

[brainworm]

Статью и рисунок я поправил, спасибо за информацию (за ссылку на статью о формальных грамматиках (!)).

[gribozavr]

> 1) Построение универсального синтаксического анализатора невозможно в принципе, даже теоретически.
Неверно. Построение универсального синтаксического анализатора с приемлемой вычислительной сложностью… — вот так.

[brainworm]

Что Вы понимаете под вычислительной сложностью?

[gribozavr]

То же, что и все: ru.wikipedia.org/wiki/Теория_сложности_вычислений

Приемлемая сложность — класс P.

[AlexGl]

Да, это известный метод анализа КС-грамматик. Если я правильно понял псевдокод, то это очень похоже на анализатор методом рекурсивного спуска (нисходящий). Но если Вы это придумали сами — то, по-моему, это замечательно!

2SabMaks: в статье говорится про синтаксический анализ именно для КС-языков. Грамматики типа 0 и типа 1 задают более широкий класс языков. Построение универсального анализатора для КС-языков — вещь и теоретически и практически осуществимая. Возьмите, например, алгоритм Кока-Янгера-Касами.

2gribozavr: всё-таки, скорее всего приемлемой сложностью здесь разумно считать линейное время.
Так как
1)за полином (от размера грамматики) можно привести любую КС-грамматику к форме Хомского,
2)а за куб времени и квадрат памяти можно запустить Кока-Янгера-Касами для любой КС-грамматики в форме Хомского,
то эта задача лежит в P. Однако, интересны как раз те случаи, когда работают линейные по времени анализаторы (LL, SLR, LR, операторные и.т.д).

[gribozavr]

Линейная сложность — частный случай полиномиальной :)

[AlexGl]

Да, но я имел в виду то, что
>>Построение универсального синтаксического анализатора с приемлемой вычислительной сложностью
вполне возможно для КС-грамматик, если говорить о классе P.

[SabMakc]

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

[Laplace]

Лет 10 назад на билдере писали синтаксический анализатор (если не путаю) контекстно свободных грамматик, там было несколько алгоритмов реализовано, мне почему-то запомнился Кока-Янгера-Касами. Если интересно, попробую поискать.

[impwx]

А что за формат синтаксиса? Почему не БНФ? :)

[brainworm]

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