Комментарии 19
Устремление хорошее, но нужно начинать с теории. Dragon book, возможно, будет сложновата для основ — но я ничего лучше не знаю :). А то, что пока у вас сделано — несерьезно, увы.
Для интереса, можете посмотреть как сделаны различные генераторы — lex / yacc, ANTlr, Coco/R или даже PEG в Nemerle
Для интереса, можете посмотреть как сделаны различные генераторы — lex / yacc, ANTlr, Coco/R или даже PEG в Nemerle
Ну это «любительская работа», так сказать, и я не претендую на серьёзность. Оно работает, и это главное, можно использовать в своих каких-то программах.
Есть очень хорошая книга, называется «Языки программирования и методы трансляции» Сергея Свердлова — там очень просто и доходчиво представлена реализация небольшого языка на паскале. Имхо перед драгонбуком лучше ее читать, чтобы хоть что-то понять, а потом уже углублять знания.
Для 14 лет неплохо (если в профиле все верно указано), даже очень неплохо.
Рекомендую глубже изучить теорию по построению компиляторов.
И несколько замечаний:
1) Построение универсального синтаксического анализатора невозможно в принципе, даже теоретически.
2) Опасаться присвоения кода несколько преждевременно, вряд ли там будет что-либо уникальное — множество людей создавали нечто подобное при обучении в институте, не говоря уже, что множество полноценных компиляторов доступны в исходниках.
Рекомендую глубже изучить теорию по построению компиляторов.
И несколько замечаний:
1) Построение универсального синтаксического анализатора невозможно в принципе, даже теоретически.
2) Опасаться присвоения кода несколько преждевременно, вряд ли там будет что-либо уникальное — множество людей создавали нечто подобное при обучении в институте, не говоря уже, что множество полноценных компиляторов доступны в исходниках.
>> Для 14 лет неплохо
Ну… гмм… вообще-то 13 (если я родился позже июня)
>> Построение универсального синтаксического анализатора невозможно в принципе
С чего это? Приведите аргументы, пожалуйста…
>> 2)
Хорошо, скоро обновлю архив.
Ну… гмм… вообще-то 13 (если я родился позже июня)
>> Построение универсального синтаксического анализатора невозможно в принципе
С чего это? Приведите аргументы, пожалуйста…
>> 2)
Хорошо, скоро обновлю архив.
С чего это? Приведите аргументы, пожалуйста…Если честно, на этот вопрос отвечает теория.
Попробую немного по памяти восстановить.
Для построения анализатора необходимо привести формальную грамматику языка к определенному виду, после чего можно создавать синтаксический анализатор языка по определенному методу (восходящий / нисходящий парсер, каждый метод требует свой вид грамматики).
Но не все грамматики возможно привести к указанным правилам. Если не ошибаюсь, грамматика типа 0 не поддается и, возможно, типа 1 (или не все 1го типа поддаются).
Оу… Даже не пробовал читать об этом статьи Википедии…
Оказывается, я изобрёл велосипед (литерал = терминал, реферал = нетерминал, а любой синтаксис = только контекстно-свободная грамматика)… Ужас какой. Придется статью переправить немного.
Оказывается, я изобрёл велосипед (
Статью и рисунок я поправил, спасибо за информацию (за ссылку на статью о формальных грамматиках (!)).
> 1) Построение универсального синтаксического анализатора невозможно в принципе, даже теоретически.
Неверно. Построение универсального синтаксического анализатора с приемлемой вычислительной сложностью… — вот так.
Неверно. Построение универсального синтаксического анализатора с приемлемой вычислительной сложностью… — вот так.
Что Вы понимаете под вычислительной сложностью?
Да, это известный метод анализа КС-грамматик. Если я правильно понял псевдокод, то это очень похоже на анализатор методом рекурсивного спуска (нисходящий). Но если Вы это придумали сами — то, по-моему, это замечательно!
2SabMaks: в статье говорится про синтаксический анализ именно для КС-языков. Грамматики типа 0 и типа 1 задают более широкий класс языков. Построение универсального анализатора для КС-языков — вещь и теоретически и практически осуществимая. Возьмите, например, алгоритм Кока-Янгера-Касами.
2gribozavr: всё-таки, скорее всего приемлемой сложностью здесь разумно считать линейное время.
Так как
1)за полином (от размера грамматики) можно привести любую КС-грамматику к форме Хомского,
2)а за куб времени и квадрат памяти можно запустить Кока-Янгера-Касами для любой КС-грамматики в форме Хомского,
то эта задача лежит в P. Однако, интересны как раз те случаи, когда работают линейные по времени анализаторы (LL, SLR, LR, операторные и.т.д).
2SabMaks: в статье говорится про синтаксический анализ именно для КС-языков. Грамматики типа 0 и типа 1 задают более широкий класс языков. Построение универсального анализатора для КС-языков — вещь и теоретически и практически осуществимая. Возьмите, например, алгоритм Кока-Янгера-Касами.
2gribozavr: всё-таки, скорее всего приемлемой сложностью здесь разумно считать линейное время.
Так как
1)за полином (от размера грамматики) можно привести любую КС-грамматику к форме Хомского,
2)а за куб времени и квадрат памяти можно запустить Кока-Янгера-Касами для любой КС-грамматики в форме Хомского,
то эта задача лежит в P. Однако, интересны как раз те случаи, когда работают линейные по времени анализаторы (LL, SLR, LR, операторные и.т.д).
Лет 10 назад на билдере писали синтаксический анализатор (если не путаю) контекстно свободных грамматик, там было несколько алгоритмов реализовано, мне почему-то запомнился Кока-Янгера-Касами. Если интересно, попробую поискать.
А что за формат синтаксиса? Почему не БНФ? :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Создание синтаксического анализатора (парсера) по контекстно-свободным грамматикам