Парсинг PHP-кода

← →
ProgRAMmer Dimonych © (2013-04-14 22:47) [0]

Нужны подсказки старших товарищей, коллег и сочувствующих. Пишу программу, которая должна брать исходники сайта на PHP, анализировать их и извлекать кое-какую информацию о взаимосвязях между отдельными процедурами/методами, выдавая в итоге определённые оценки. Детали не столь важны.

Хочу сделать всё «руками», без Lex"ов и Yacc"ов — разобраться. Литературу по теме покопал: Ахо, Ульман, Сети; Грис; Креншоу; Вирт — но кое-какие вопросы и сомнения остались. Разумеется, предполагается поддержка только какого-то подмножества языка.

[Очень много букв]

На младших курсах писал за одну ночь простенький парсер, в котором для каждой лексемы и синтаксической конструкции была отдельная процедура и код процедуры определял ожидаемый синтаксис. Сейчас хочется попробовать более цивилизованно: с автоматом в табличном представлении и описанием грамматики, скажем, в (Р)БНФ.

(Р)БНФ придётся тоже парсить :( А потом ещё мучительно строить автоматы для каждой продукции, объединять, превращать НКА в ДКА.

1. Есть ли какие-то хорошие статьи, посвящённые построению ДКА по нотации в (Р)БНФ? Отдельные этапы представляю себе, но хочется в результате получить велосипед, а не БелАЗ.

← →
Pit (2013-04-15 01:55) [1]

по-моему, ты форумом ошибся. Слишком уж специфичная задача, тебе не на дельфи нужно, а какой-то искать алгоритмический форум или типа того...

← →
Dimka Maslov © (2013-04-15 10:48) [2]

Вроде как PHP опенсорсный? Или я ошибаюсь?

← →
Дмитрий С © (2013-04-15 11:47) [3]

> Вроде как PHP опенсорсный? Или я ошибаюсь?

Есть такое, но мне кажется там черт ногу сломит.

← →
Dimka Maslov © (2013-04-15 11:56) [4]

> Есть такое, но мне кажется там черт ногу сломит.

А никто не обещал, что будет легко.

← →
antonn © (2013-04-15 11:58) [5]

но не ковырять же такой проект ради автоматов...

← →
ProgRAMmer Dimonych © (2013-04-15 12:41) [6]

Да, опенсорсный. И даже в исходниках есть описание yaccоподобное. А добрые люди даже сконвертировали это дело в РБНФ. Просто не хочется выпиливать оттуда 90% кода, чтобы посчитать пару-тройку характеристик по исходнику. Да и «самодокументируемый код» не очень-то способствует разбирательству с теорией компиляторов на практике.

← →
Kerk © (2013-04-15 12:55) [7]

Если я ничего не путаю, то в общем случае из БНФ у тебя получится не ДКА, а НДКА. То есть у тебя на самом деле будет два шага: БНФ->НДКА->ДКА.

Получить НДКА из БФН достаточно просто. Преобразовать НДКА в ДКА несколько сложнее, можно начать отсюда: http://www.rsdn.ru/article/alg/nka.xml

← →
Kerk © (2013-04-15 12:56) [8]

Но я бы не мучался и взял lex/yacc :)

← →
Павиа (2013-04-15 13:45) [9]

> БНФ->НДКА->ДКА.

Что-то мне говорит, что не всё так просто. Не всякую "конструкцию" можно передать из 1 в 2 и из 2 в 3 поэтому в БНФ и НДКА применяются костыли.
Правда php язык простой.

> Но я бы не мучался и взял lex/yacc :)

Написать 3-5 функций не сложно, тем более когда есть теория.
Это при условии простого языка. Для сложного придётся вникать в сложности.

> Сейчас хочется попробовать более цивилизованно: с автоматом
> в табличном представлении и описанием грамматики, скажем,
> в (Р)БНФ.

И кто придумал что это цивилизованный способ? Это же типичная оптимизация по скорости выполнения. Которая как и любая оптимизация носит негативный характер в плане понимания.

← →
ProgRAMmer Dimonych © (2013-04-15 14:45) [10]

> [9] Павиа (15.04.13 13:45)
И кто придумал что это цивилизованный способ? Это же типичная оптимизация по скорости выполнения. Которая как и любая оптимизация носит негативный характер в плане понимания.

Виноват, это моя косая формулировка. Идея в том, чтобы логика управления состояниями была максимально централизована, чтобы проще генерировать код лексера/парсера. А генерировать его надо затем, чтобы по мере необходимости расширять поддерживаемое подмножество языка. Меньше логических ошибок наляпаю :)

> [7] Kerk © (15.04.13 12:55)

Спасибо, ссылка выглядит многообещающе. В принципе, в том же Драконе или у Гриса НКА -> ДКА достаточно подробно описано, но несколько оторванно от практики (тонкостей реализации уже в коде).

Но (Р)БНФ -> НКА — не менее больной для меня вопрос. Там никаких скрытых хитростей нет, чтобы проще разобрать? Только свой парсер для (Р)БНФ с лексемами и и логикой?

← →
TUser © (2013-04-15 17:13) [11]

М.В. Мозговой. Алгоритмы, языки, автоматы, компиляторы.

Там примеры на С#, но алгоритмы изложены вполне четко.

можно пойти другим путём

- читаем http://www.php.net/manual/en/tokenizer.examples.php;
- качаем сборку PHP для виндовс;
- пишем скрипт на PHP на пару десятков строк; на входе скрипта - исходный файл на PHP, на выходе - набор лексем;
- разбираем строго структурированные лексемы и радуемся жизни

> [12] wicked © (15.04.13 18:11)

Не-не, такого софта тысячи уже, да и к тому же:

> [0] ProgRAMmer Dimonych © (14.04.13 22:47)
Хочу сделать всё «руками», без Lex"ов и Yacc"ов — разобраться.

> [11] TUser © (15.04.13 17:13)

Благодарю, стиль изложения автора приятен, хотя и C# :)

https://www.coursera.org/course/compilers

Позволю себе продолжить эту тему, не создавая новую. Назрело два новых вопроса, для успокоения своей совести.

Исхожу из того, что лексер — это табличный ДКА. Пусть в языке есть ключевое слово, например, PROCEDURE.

2. Верно ли, что каждая буква ключевого слова будет приводить к созданию в ДКА лексера нового состояния?
3. Верно ли, что для ключевых слов с общим префиксом (например, PROGRAM и PROCEDURE) некоторые состояния будут общими?

Или правильнее всё же делать автомат, для которого ключевое слово не отличается от идентификатора, и выделять ключевые слова на втором шаге, поиском по таблицам символов?

P.S.

> [14] Kerk © (15.04.13 18:58)

Спасибо, нагло пионерю видео. Отвечают не на все вопросы, но воспринимается намного легче, чем в книгах.

Парсинг PHP-кода Найти похожие ветки