Ресурсы для лексинга, токенизации и разбора в python

Могут ли люди указать мне ресурсы на лексирование, разбор и токенизацию с помощью Python?

Я немного взломал проект с открытым исходным кодом (hotwire) и хотел сделать несколько изменений в коде, который lexes, анализирует и токенизирует команды, введенные в него. Поскольку это настоящий рабочий код, он довольно сложный и немного сложный.

Я раньше не работал над кодом для lex/parse/tokenise, поэтому я думал, что один из подходов будет заключаться в том, чтобы работать через учебник или два по этому аспекту. Я бы хотел научиться достаточно, чтобы перемещаться вокруг кода, который я действительно хочу изменить. Есть ли что-нибудь подходящее там? (В идеале это можно сделать днем, чтобы не покупать и не читать книгу драконов...)

Изменить: (7 октября 2008 г.) Ни один из нижеперечисленных ответов не дает то, что я хочу. С ними я мог генерировать парсеры с нуля, но я хочу научиться писать свой собственный базовый парсер с нуля, не используя lex и yacc или подобные инструменты. Сделав это, я смогу лучше понять существующий код.

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

Ответ 1

Я счастливый пользователь PLY. Это чистая реализация Python для Lex и Yacc, с множеством небольших тонкостей, которые делают ее довольно Pythonic и просты в использовании. Поскольку Lex и Yacc являются наиболее популярными инструментами лексинга и синтаксического анализа и используются для большинства проектов, PLY имеет преимущество стоять на плечах гигантов. Много знаний существует в Интернете на Lex и Yacc, и вы можете свободно применять его к PLY.

PLY также имеет хорошую страницу документации с некоторыми простыми примерами, чтобы вы начали.

Для перечисления множества инструментов анализа Python см. this.

Ответ 2

Для средне-сложных грамматик 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.

Ответ 3

Этот вопрос довольно старый, но, возможно, мой ответ поможет кому-то, кто хочет изучить основы. Я считаю, что этот ресурс очень хорош. Это простой интерпретатор, написанный на питоне без использования каких-либо внешних библиотек. Таким образом, это поможет любому, кто хотел бы понять внутреннюю работу синтаксического анализа, лексинга и токенизации:

"Простой Intepreter от Scratch в Python: Часть 1, Часть 2, часть 3 и часть 4.

Ответ 4

Посмотрите на стандартный модуль shlex и измените одну его копию в соответствии с синтаксисом, который вы используете для своей оболочки. является хорошей отправной точкой

Если вы хотите всю мощь полного решения для лексинга/синтаксического анализа, ANTLR также может генерировать питон.

Ответ 5

pygments - это синтаксис синтаксиса исходного кода, написанный на python. Он имеет лексеры и форматирование, и может быть интересно заглянуть в источник.

Ответ 6

Вот несколько вещей, которые вы можете начать (примерно от простых до самых сложных, наименее-самых-мощных):

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

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

Это не та книга, которую я использовал, но это довольно хорошо: Принципы проектирования компилятора.

Надеюсь, этого достаточно, чтобы вы начали:)

Ответ 7

Я предлагаю http://www.canonware.com/Parsing/, так как это чистый питон, и вам не нужно изучать грамматику, но это не широко используется и имеет сравнительно небольшую документацию. Тяжелый вес - ANTLR и PyParsing. ANTLR также может генерировать парсингеры Java и С++, а также хосты AST, но вам нужно будет узнать, что представляет собой новый язык.