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

Question

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

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

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

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

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

Answer 1

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

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

Список множества инструментов разбора Python см. this .

Answer 2

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

"Простой интерпретатор с нуля в Python:" Часть 1 , Часть 2 , Часть 3 и Часть 4 .

Answer 3

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

Answer 4

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

Answer 5

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

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 уровнями. Мы выполнили несколько заданий, где мы выполняли синтаксический анализ вручную; если вы действительно хотите понять, что происходит под капотом, я бы порекомендовал такой же подход.

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

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

Answer 6

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

Если вам нужны все возможности комплексного решения для лексирования / разбора, ANTLR может также генерировать python.

Answer 7

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

Answer 8

У Фредерико Томассетти была хорошая (но короткая) краткая переписка по всем вещам, связанным с BNF и двоичным расшифровкой:

• лексический,
• парсер,
• абстрактно-синтаксическое дерево (AST) и
• Построить / код-генератор.

Он даже упомянул новую грамматику выражения синтаксического анализа (PEG).

https://tomassetti.me/parsing-in-python/