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

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

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

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

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

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


python parsing resources lex
person Hamish Downer    schedule 31.08.2008    source источник

Ответы (8)


arrow_upward
38
arrow_downward

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

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

Список множества инструментов синтаксического анализа Python см. В this.

person Eli Bendersky    schedule 20.09.2008
comment
Я поддерживаю рекомендацию для PLY, это здорово. - person mipadi; 11.11.2008

arrow_upward
29
arrow_downward

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

«Простой Intepreter с нуля на Python:» Часть 1, Часть 2, Часть 3 и Часть 4.

person Saad    schedule 14.01.2013
comment
Очень хорошая серия статей, посвященных цели, а не инструментам! - person Janus; 24.09.2013

arrow_upward
17
arrow_downward

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

person Torsten Marek    schedule 26.09.2008
comment
Как бы то ни было, у меня всегда были проблемы с PyParsing. Я пытался использовать его несколько раз и никогда не был полностью удовлетворен результатом (например, это заняло много времени, было трудно отлаживать, требовалось больше кода, чем я ожидал, и т. Д.). Я не могу сказать, связано ли это с моим невежеством или сбоем в PyParsing, хотя ... - person David Wolever; 10.09.2010
comment
Ссылка мертвая, было бы здорово, если бы вы могли ее обновить. - person luator; 08.10.2018

arrow_upward
6
arrow_downward

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

person nilamo    schedule 20.09.2008

arrow_upward
5
arrow_downward

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

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

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

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

person Tony Arkles    schedule 11.11.2008
comment
Как это может помочь кому-то, кто знает все это, но ищет реализации на Python ?? - person Alexander Oh; 25.03.2013

arrow_upward
5
arrow_downward

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

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

person PW.    schedule 31.08.2008
comment
Ссылка ANTLR мертва. - person Ekrem Dinçel; 06.05.2020

arrow_upward
3
arrow_downward

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

person nimish    schedule 31.08.2008
comment
Не могу открыть ссылку. - person Ekrem Dinçel; 06.05.2020

arrow_upward
2
arrow_downward

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

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

Он даже упомянул новую грамматику Parsing Expression Grammar (PEG).

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

person John Greene    schedule 05.01.2019