Тема синтаксического анализа...

В русской научной литературе тема синтаксического анализа раскрыта крайне плохо. В русском интернете статей и книг почти нет, есть только забугорные платные сайты где сожержаться сканы из книг, датированных 70ми годами. А ведь на самом деле она имеет место при создании различных компиляторов, трансляторов, редакторов кода и тд.
Так вот я предлагаю реализовать не которые алгоритмы и написать статьи, выложить потом это на исходниках.ру
Во первых это хорошая возможнось изучить эту тему, во вторых попрактиковаться в написании статей.
Одному человеку это достаточно сложно сделать, поэтому я собираю команду.
Думаю следует делать это как несколько последовательных статей, где постепенно реализовывать более сложные методы.
Конкретно собираюсь написать и реализовать:
1) Введение. Способы описывания грамматик.
2) Всё про конечные детерменированные аппараты, их генерация и тд. (ктати на codeproject.net (как то так сайт пишется) была одна статья, её можно будет перевести)
3) LL и LR парсеры. Про LL можно написать кратко, в основном рассмотреть LR парсеры. Так же описать все ограничение накладываемые на грамматику при использовании LR.
4) Различные "навороты" LR парсера такие как, поддержка правосторонней регулярной грамматики (например P -> QAAA+) (реализуется это с помощью "Обратного ДКА", который читает стек и снимает с него определённое количество состояний), восстановление после ошибок и тд.
5) Tomita parser. Алгоритм анализа по LR таблице имеющей "эпсилон" переходы (вобщем по одмному символу в несколько состояний) (состояния имеющие переходы по одному символу в несколько других называются "неадекватными")
6) Incremental Parsing Моментально внесение изменений в дерево разбора при изменении входного потока символов. Это нужно для создания всяческих подсветок синтаксиса, IntelliSense'ов и прочего. Можно ещё сделать инкрементную компиляцию, вобщем чего угодно можно придумать.
7) И потом собрать всё это вместе и представить библиотку алгоритмов, где будут реализованы все эти методы.
8) Сделать демонстрационное приложение, где можно будет ввести грамматику, а потом вводить тестовый текст, который будет анализироваться. И вся работа алгоритмов должна будет в виде графов красиво отображаться.
PS Пока я смог реализовать только Tomita LR парсер с поддержкой правосторонней регулярной грамматики.
Как сделать incremental и с восстановлением после ошибок я пока не знаю. Поэтому и ищу команду.
PPS Сам программирую на C++ но если кто то хочет делать на Делфи то пожалуйста. Это можно будет ещё перевести на C++ и будет два варианта.
PPPS И ещё, хочу что бы потом показывать это в инсте или ещё где (многие делают всякие курсовые работы на эту тему, но они много не затрагивают) имели право только участники проэкта. Остальным нужно будет писать откуда они взяли инфу.

http://www.ozon.ru/context/detail/id/146264/

Обработка текста

ЗЫ Материал на Python в Си конвертировать при желании не вопрос!

sploid Я эту книгу давно прочитал. И там ОЧЕНЬ многого не написано. Я прочитал ещё несколько книг на английском (на русском их нет) Это так, если самые азы хочется изучить.
best_lamer Это тоже все не серьезно.
В этом я не уверен, но как я думаю, в YACC можно делать синтаксические LALR(1) анализатры, Tomita парсер yacc генерировать не может, поддержки правосторонней регулярной грамматики (например P -> QAAA+) думаю тоже нет. И тем более Incremental parser тоже не создать.

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

Сообщение отредактировано: maggot - 18.01.07, 12:56

Цитата maggot @ 18.01.07, 12:56

best_lamer Это тоже все не серьезно.

Python parsing tools
А это все тоже?

Ну как это плохо раскрыта? Есть книга "Компиляторы - принципы, технологии, инструменты" Альфред Ахо на русском. У меня она в электронном и бумажном виде и, по-моему, тема синтаксического анализа там изложена на уровне. Я в свое время сливал с глобальной сети всё, что касается компиляторов - в итоге насобирал около 100Mb в формате pdf и пару книг в формате djvu на английском и русском, что мне, в принципе, хватает. А идея неплохая, но для чисто образовательных целей я бы использовал Common Lisp.

Зверуга
Плохо раскрыта по сравнению с иностранной литературой. Соглашусь, что ифнормации в книге "Компиляторы - принципы, технологии, инструменты" Альфред Ахо достаточно для создания промышленного компилятора (можно сказать, решения типовой задачи). С другой стороны, если дальше углублятся в эту тему, прийдётся копаться в какой нибудь редкой иностанной литературе.
Я не считаю, что эта тема настолько сложная и большая, что бы не пытаться изучить её всю. Следовательно, она должно быть полностью и доступно представленна на русском языке в интернете.

А С++ имеет перед Lisp'ом преимущество в том, что он более популярен, и на нём можно решать реальные задачи (не буду говорить про лисп, тк не знаю его).

Цитата maggot @ 18.01.07, 12:56

В этом я не уверен, но как я думаю, в YACC можно делать синтаксические LALR(1) анализатры,

Цитата

Bison is a general-purpose parser generator that converts a grammar description for an LALR(1) context-free grammar into a C program to parse that grammar.
...
Bison is upward compatible with Yacc: all properly-written Yacc grammars ought to work with Bison with no change.

Цитата maggot @ 20.01.07, 19:45

что информации в книге "Компиляторы - принципы, технологии, инструменты" Альфред Ахо достаточно для создания промышленного компилятора (можно сказать, решения типовой задачи)

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

Oleg2004
И где эту книгу взять можно? В интернете не могу найти.
trainer
Я ошибся, хотел написать только LALR(1). Впрочем не важно.
Зверуга
Можешь дать мне какие нибудь книги по "восстановлению после ошибок", и "инкрементному анализу"?

Цитата maggot @ 23.01.07, 21:01

В интернете не могу найти.

Увы это так.
У меня есть только в бумажном виде - английский оригинал и русский перевод
А сканировать так там 500 страниц

У Гриса методик разбора рассмотрено побольше, хотя каких-то методов поновее и нет (да и откуда им там взяться). Хотя объем книги все же поменьше, чем у двухтомника А.Х.У. Лучше все же изучать и ту и ту.

YACC (авторства последник, кажется) собственно и предназначен для LALR(1)-грамматик. С небольшими дополнениями, вроде автоматического разрешения некоторых неоднозначностей, и приоритетов.

Цитата maggot @ 23.01.07, 21:01

Я ошибся, хотел написать только LALR(1).

Цитата

With the proper declarations, Bison is also able to parse these more general context-free grammars, using a technique known as GLR parsing (for Generalized LR). Bison's GLR parsers are able to handle any context-free grammar for which the number of possible parses of any given string is finite.

Цитата Oleg2004 @ 23.01.07, 21:10

Цитата maggot @ 23.01.07, 21:01

В интернете не могу найти.

Увы это так.
У меня есть только в бумажном виде - английский оригинал и русский перевод
А сканировать так там 500 страниц

А где эти книги можно купить?
ЗЫ Живу в Москве.

maggot
А где можно взять твой парсер?
Сам я в этом деле новичок, но могу воспользоваться твоими текстами для реализации своего языка, а потом высказать свои впечатления.