DelphiAST - каждому по автошеме

← →
Kerk © (2014-09-16 11:39) [0]

Опубликовал на гитхабе проект DelphiAST. Это фрагмент моего проекта, связанного со статическим анализом кода, про который тут некоторые знают и который я никак не могу довести до ума.

DelphiAST умеет взять текст юнита и вернуть его в виде абстрактного синтаксического дерева (примеры по ссылке). Там не все пока идеально, но работает этот код довольно стабильно и он однозначно функциональнее всего, что доступно сейчас для Delphi.

Часть проекта - SimpleParser - это существенно доработанная версия знаменитого CastaliaDelphiParser. В нем были исправлены баги и добавлена поддержка нового синтаксиса Delphi.

Чтобы этот труд не лежал в долгом ящике, я решил поделиться его частью с сообществом. Потребность в подобном проекте есть, судя по периодически возникающим обсуждениям в G+.

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

https://github.com/RomanYankovsky/DelphiAST
http://roman.yankovsky.me/?p=1678

Теперь каждый сможет написать себе автошему :)

← →
Rouse__ (2014-09-17 21:47) [1]

Ром, я слегка поизучал все это дело...
Сразу технический вопрос, из дерева можно сгенерировать код, готовый к компиляции хотябы в виде инклуда?
К примею, имея на руках синтаксическое дерево кода, я захочу морфить именно его, заменяя узел инструкции на дерево, представляющее данный узел.

← →
Rouse__ (2014-09-17 21:54) [2]

Чуть поясню, в дереве мы имеем к примеру inc(var)
Вместо данного чанка я размещаю var-900 первой инструкцией и второй var + 901, развожу их по дереву и по факту получаю тот-же +1 но уже ввиде двух инструкций

← →
Kerk © (2014-09-17 23:15) [3]

Тут стоит упомянуть, что проект находится в довольно стабильном состоянии, но все еще не завершен. Если говорить о возможности в принципе, то когда мы дождемся, скажем так, версии 1.0, то из дерева можно будет сгенерировать полноценный готовый к компиляции юнит.

Пока же в дерево, к сожалению, попадает не вся информация, которая есть в исходнике. Из-за нехватки сил, времени, внимательности и т.д. и т.п. Но постепенно ситуация будет улучшаться.

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

P.S. Если у тебя (или у кого-то из читающих эту ветку) если время и энтузиазм, то могу поделиться задачей, которая никак не связана с самим парсингом и довольно локализована (то есть не придется вникать в кучу кода), но решение которой было бы очень полезно для обработки кода непосредственно в секции implementation. Когда-нибудь у меня самого руки дойдут, но если вдруг кто-то поможет, будет здорово.

← →
ухты (2014-09-17 23:26) [4]

а для чего все это? или опять, нафига пояснять тому кому не надо?

← →
Kerk © (2014-09-18 00:02) [5]

> ухты (17.09.14 23:26) [4]

Анализ кода. Самый разнообразный. Вон Rouse_ только что штуку спросил, которая мне и в голову не приходила. Это тоже ответ на вопрос "для чего". Или автошема знаменитая, не верю, что на этом сайте про нее кто-то не слышал. Я не зря про нее пошутил. Это тоже ответ на вопрос "для чего".

← →
Павиа (2014-09-18 21:45) [6]

> Или автошема знаменитая, не верю, что на этом сайте про
> нее кто-то не слышал.

Слышал на DelphiMaster когда искал что это пришел к выводу что это типо интернет мема?

← →
Павиа (2014-09-18 22:37) [7]

Долго медетируя над компиляторами и парсерами пришел к одному выводу. Любой парсер и генератор это "база знаний". Тут не существует одного простого метода на все случае жизни тут есть куча элементов мозаики которые отработаны годами и работают в узкой области.
Так что если кто-то захочет что-то сделать своё, то совет. Копируйте и ещё раз копируйте то что сделали другие.

Но существующие реализации AST меня не очень устроили.

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

Пока что черновик.
// Нижней уровень абстрактного синтаксического дерева. type TASTNode=class private FNodeName:String; Fperant: TASTNode; function GetNodeName: String; procedure PutNodeName(const Value: String); procedure Setperant(const Value: TASTNode); protected public constructor Create; override; destructor Destroy; override; property perant:TASTNode read Fperant write Setperant; property NodeName:String read GetNodeName write PutNodeName; published end; TASTArray=Class(TASTNode) private function GetItem(index: integer): TASTNode; procedure PutItem(index: integer; const Value: TASTNode); function GetCount: Integer; procedure PutCount(const Value: Integer); FItems:array of TASTNode; protected property Items[index:integer]:TASTNode read GetItem write PutItem; default; property Count:Integer read GetCount write PutCount; public constructor Create; override; destructor Destroy; override; published end;

Далее. В виду того что в мире существуют триграммы, двуграммы однограммы.
TASTNil=Class(TASTArray)
TASTOne=Class(TASTArray)
TASTTwo=Class(TASTArray)
TASTThree=Class(TASTArray)
TASTNodeLexeme=class(TASTNil)
ДА немного избыточно. Но это абстрактное дерево и ему присуще избыточность.

Чего тут не хватает и чего планирую сделать в низкий уровень добавить 2 функции для обхода дерева в глубину и ширину. Вверх и вниз по дереву.

Далее идут классы для элементов грамматики.
Думаю всю грамматику поделить на 4-7 групп как это принято в других языках и раскидать по юнитам: идентификаторы, декларация, реализация.

Во вторых как я уже говорил не существует одного метода на все случае жизни. Лично я предполагаю использовать ООП, а именно полиморфизм. На основе полиморфизма добавить в грамматическое дерево семантическое которое будет реализовывать провереку семантических правил. Таких как соотвествие типов, проверку дублирование и наличие имен переменных.

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

По мимо семантического дерева ещё надо добавить морферы. Морферы тоже планирую разделить на низкоуровненые и высокоуровневые. К низкоуровневым планирую отнесу те, без которых нельзя сделать парсер. К примеру морферы нужны для разбора логических вырожений и просто вырожений. Тут ещё конь не волялся. К высокоуровневым отнести те которые наиболее востребованы, но до этого не дошел надо смотреть у кого что есть и тащить к себе. У морферов есть проблемма то, что задачи им приходится решать разные.

← →
Kerk © (2014-09-19 09:10) [8]

> Павиа (18.09.14 21:45) [6]
>
> > Или автошема знаменитая, не верю, что на этом сайте про
> > нее кто-то не слышал.
>
> Слышал на DelphiMaster когда искал что это пришел к выводу
> что это типо интернет мема?

Это вроде локального интернет мема.

Был здесь когда-то такой парень - ДмитрийО. Очень активный. И написал он "автосхему". Это такая программа, которая берет паскалевский модуль и рисует по нему блоксхему. В этом не было бы ничего особенного, если бы ДимаО не был так активен, а программа такой странной и немного смешной. Так что "автошема" вошла в аналлы.

Вот тут это и другое его творчество доступны:
http://dmitriyo.narod.ru/

← →
Ega23 © (2014-09-19 10:49) [9]

Не совсем понятно, как можно построить AST, не используя стек.

← →
Павиа (2014-09-19 11:13) [10]

> Не совсем понятно, как можно построить AST, не используя
> стек.

Имелось в виду то что я не хочу в водить методы push и pop в класс объекта.
А так да в не явной форме стек будет использоваться. Парсер будет строиться по принципу рекурсии когда функия вызывает для разбора другую функцию. Так проще поддерживать парсер. И только для разбора вырождений в явной форме требуется обращение к стеку, правда тут я хочу перейти на морферы и работать с деревом.
А так для паскаля стек не нужен. Это же LR(1) граматика. Весь стек ограничивается 1 элементом. Остальное можно сделать деревом. Просто придется ползать в верх по дереву(в место стека) и применять морферы вместо свёртки.

← →
Ega23 © (2014-09-19 11:16) [11]

А зачем их туда вводить? Они в парсере должны быть, а не в нодах AST.

← →
Kerk © (2014-09-19 11:27) [12]

> Павиа (19.09.14 11:13) [10]
>
> Парсер будет строиться по принципу рекурсии когда функия
> вызывает для разбора другую функцию.

Это очень точное описание парсера, который у меня используется :)
А вот уже для построения AST используется стек.

← →
Павиа (2014-09-19 11:45) [13]

Само по себе AST не очень интересно. Нужна ещё и семантика. Определение класса лексемы. Для лексем которые являются операторами интересно получить их приоритеты. Для описателей типов интересно прикрутить JSON. И тому подобное. Причем как правило вся семантика нужна.

Поэтому было решено не разделять данные и код, а использовать объекты ООП. В принципе так поступают все. Так что парсер думаю как раз и разместить в узлах АСТ. Хотя что-то мне говорит что это не есть правильно.

Как вы уже писали стек нужен. push и pop очень частые операции и их желательно видеть, но в определение дерева таких нет.

Для одного языка наверно стоит тащить в дерево парсер. А вот для нескольких нет. Но я пошел по другому пути. Я разделил дерево на низкий уровень и высокий. Низкий уровень присущ любому языку. А высокий как раз и реализует конкретный язык.

← →
Ega23 © (2014-09-19 12:10) [14]

> Поэтому было решено не разделять данные и код, а использовать
> объекты ООП. В принципе так поступают все. Так что парсер
> думаю как раз и разместить в узлах АСТ. Хотя что-то мне
> говорит что это не есть правильно.

Есть дерево. Есть парсер. Парсеров может быть Over9000. Зачем дереву знать о каком-то своём персере - мне совершенно неясно.

← →
Kerk © (2014-09-19 14:00) [15]

> Павиа (19.09.14 11:45) [13]

Я, честно говоря, не понял о парсинге какого языка речь. Если о Delphi, то зачем еще одно AST-дерево, если уже есть мое? :)

← →
Игорь Шевченко © (2014-09-19 18:08) [16]

Что-то я не понял, как это забрать по указанной ссылке.

В примерах дерево представлено в виде XML - интересует XSD с подробными комментариями ну и вообще документация интересует.

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

← →
Павиа (2014-09-19 18:15) [17]

> Я не понял, как по твоему представлению дерева выполнить
> задачу, о которой большевики твердили уже давно - поиск
> дублирующихся частей дерева.

А что это за задача? Впервые слышу.

> Игорь Шевченко © (19.09.14 18:08) [16]
>
> Что-то я не понял, как это забрать по указанной ссылке.

Там есть кнопка "Download ZIP" справа, например.
Вот прямая ссылка: https://github.com/RomanYankovsky/DelphiAST/archive/master.zip

> Я не понял, как по твоему представлению дерева выполнить
> задачу, о которой большевики твердили уже давно - поиск
> дублирующихся частей дерева.

Ну это ведь дерево. Структура данных. Она не может что-то искать по определению.

А документация нужна, да.

Kerk © (19.09.14 18:24) [18]

От дерева я поиска не требую :) Но искать-то хочется. Потому твое дерево надо во что-то преобразовать, например, в набор классов.

За ссылку спасибо, скачал, посмотрю. В D2006 скомпилировать можно ?

> Игорь Шевченко © (19.09.14 19:09) [19]

Так дерево изначально и состоит из классов. В XML его превращает специальная преобразовалка, но это совершенно не обязательный шаг. Это дерево есть куда улучшать, добавить всяких наследований и полиморфизмов. Но пока все просто, уж как успел :)

> В D2006 скомпилировать можно ?

Там дженерики используются, так что, к сожалению, нет :(

Пара ссылок на другие обсуждения

http://github.com/RomanYankovsky/DelphiAST/issues/3

http://plus.google.com/u/0/+RomanYankovsky/posts/cRdGjS2sqHx

Еще один проект использующий DelphiAST
https://plus.google.com/+StefanGlienke/posts/GHdiFs2LHf1
(эксперт, позволяющий запускать юнит-тесты прямо из IDE)

Роман, привет. :)
Когда будет поиск синтаксически эквивалентных конструкций? :)
Очень ждем :)

Еще один проект использующий DelphiAST
https://plus.google.com/+StefanGlienke/posts/CFLZZvTuUxb

Пользуясь случаем, передаю привет всем, спрашивающим "а нафига оно надо" :)

DelphiAST - каждому по автошеме Найти похожие ветки