Ресурсы для лексирования, токенизации и синтаксического анализа в Python
Могут ли люди указать мне ресурсы по лексированию, синтаксическому анализу и токенизации с помощью Python?
Я немного взламываю проект с открытым исходным кодом (горячий провод) и хотел внести несколько изменений в код, который лексы, синтаксический анализ и токенизация вводил в него команды. Поскольку это настоящий рабочий код, он довольно сложен и труден для работы.
Я раньше не работал над кодом для lex / parse / tokenise, поэтому я подумал, что одним из подходов будет проработка одного или двух руководств по этому аспекту. Я надеюсь узнать достаточно, чтобы ориентироваться в коде, который я действительно хочу изменить. Есть ли там что-нибудь подходящее? (В идеале это можно было бы сделать днем, не покупая и не читая сначала книгу о драконах ...)
Редактировать: (7 октября 2008 г.) Ни один из приведенных ниже ответов не дает того, что я хочу. С их помощью я мог бы генерировать синтаксические анализаторы с нуля, но я хочу научиться писать свой собственный базовый синтаксический анализатор с нуля, не используя lex и yacc или аналогичные инструменты. Сделав это, я смогу лучше понять существующий код.
Так может ли кто-нибудь указать мне на учебник, в котором я могу создать базовый синтаксический анализатор с нуля, используя только python?
Ответы 8
Я предлагаю http://www.canonware.com/Parsing/, поскольку это чистый питон, и вам не нужно изучать грамматику, но он широко не используется и имеет сравнительно мало документации. Наиболее тяжеловесными являются ANTLR и PyParsing. ANTLR также может генерировать синтаксические анализаторы Java и C++ и обходчики AST, но вам придется узнать, что составляет новый язык.
Не могу открыть ссылку.
Я счастливый пользователь PLY. Это реализация Lex & Yacc на чистом Python с множеством мелких тонкостей, которые делают его довольно Pythonic и простым в использовании. Поскольку Lex и Yacc являются наиболее популярными инструментами лексического анализа и синтаксического анализа и используются в большинстве проектов, PLY имеет то преимущество, что стоит на плечах гигантов. В Интернете существует много знаний о Lex & Yacc, и вы можете свободно применять их к PLY.
В PLY также есть хороший страница документации с несколькими простыми примерами для начала.
Список множества инструментов синтаксического анализа Python см. В это.
Я поддерживаю рекомендацию для PLY, это здорово.
пигменты - это подсветка синтаксиса исходного кода, написанная на Python. В нем есть лексеры и средства форматирования, и может быть интересно взглянуть на источник.
Для грамматик средней сложности PyParsing отлично подходит. Вы можете определять грамматики непосредственно в коде Python, без необходимости генерации кода:
>>> from pyparsing import Word, alphas
>>> greet = Word( alphas ) + "," + Word( alphas ) + "!" # <-- grammar defined here
>>> hello = "Hello, World!"
>>>> print hello, "->", greet.parseString( hello )
Hello, World! -> ['Hello', ',', 'World', '!']
(Пример взят с домашней страницы PyParsing).
С помощью действий синтаксического анализа (функций, которые вызываются при срабатывании определенного правила грамматики) вы можете преобразовать синтаксический анализ непосредственно в абстрактные синтаксические деревья или любое другое представление.
Существует множество вспомогательных функций, которые инкапсулируют повторяющиеся шаблоны, такие как иерархии операторов, строки в кавычках, вложение или комментарии в стиле C.
Как бы то ни было, у меня всегда были проблемы с PyParsing. Я пытался использовать его несколько раз и никогда не был полностью удовлетворен результатом (например, это заняло много времени, было трудно отлаживать, требовалось больше кода, чем я ожидал, и т. д.). Я не могу сказать, связано ли это с моим невежеством или сбоем в PyParsing, хотя ...
Ссылка мертва, было бы здорово, если бы вы могли ее обновить.
Вот несколько вещей, с которых вы можете начать (примерно от простого к самому сложному, от наименее к наиболее мощному):
http://en.wikipedia.org/wiki/Recursive_descent_parser
http://en.wikipedia.org/wiki/Top-down_parsing
http://en.wikipedia.org/wiki/LL_parser
http://effbot.org/zone/simple-top-down-parsing.htm
http://en.wikipedia.org/wiki/Bottom-up_parsing
http://en.wikipedia.org/wiki/LR_parser
http://en.wikipedia.org/wiki/GLR_parser
Когда я узнал об этом, это было на семестровом курсе университета с 400 уровнями. Мы выполнили ряд заданий, в которых выполняли синтаксический анализ вручную; если вы хотите действительно понять, что происходит под капотом, я бы порекомендовал тот же подход.
Это не та книга, которую я использовал, но она довольно хорошая: Принципы построения компилятора.
Надеюсь, этого достаточно, чтобы вы начали :)
Как это может помочь кому-то, кто знает все это, но ищет реализации на Python ??
Это довольно старый вопрос, но, возможно, мой ответ поможет тому, кто хочет изучить основы. Я считаю этот ресурс очень хорошим. Это простой интерпретатор, написанный на Python без использования каких-либо внешних библиотек. Это поможет любому, кто хочет понять внутреннюю работу синтаксического анализа, лексирования и токенизации:
«Простой интерпретатор с нуля на Python:» Часть 1, Часть 2, Часть 3. и Часть 4.
Очень хорошая серия статей с акцентом на цель, а не на инструменты!
Фредерико Томассетти хорошо (но коротко) изложил все, что связано с BNF и двоичным дешифрованием:
- лексический
- парсер
- дерево абстрактного синтаксиса (AST) и
- Конструктор / код-генератор.
Он даже упомянул новую грамматику Parsing Expression Grammar (PEG).
Ссылка ANTLR мертва.