0. so-quest 130 03.12.14 03:08 Сейчас в теме

Разработка синтаксического анализатора языка запросов на языке 1С

Пример разработки генератора для PEG парсера

Перейти к публикации

Комментарии
Избранное Подписка Сортировка: Древо
1. Идальго 120 03.12.14 10:07 Сейчас в теме
Нифига себе генератор синтаксических анализаторов)))
2. Famza 82 03.12.14 11:04 Сейчас в теме
3. so-quest 130 03.12.14 11:18 Сейчас в теме
(2) главное что бы понятно было.
4. SeiOkami 1133 03.12.14 16:43 Сейчас в теме
Плюс однозначно. Хотя описано довольно сложно. Надо будет потом хорошенько повникать, а то так с ходу и не понимаю )
5. so-quest 130 03.12.14 18:40 Сейчас в теме
(4) Ну может в следующей части, на реальном примере разбора текста запроса станет ясно. Хотя старался писать просто и мало. В основном все в коде
6. Ekovichev 626 03.12.14 20:10 Сейчас в теме
Статья интересная. Чем это может быть полезно на практике?
NoRazum; boy13; Evil Beaver; +3 Ответить
8. so-quest 130 04.12.14 11:17 Сейчас в теме
(6) Обычно парсеры для разбора строк используются.
(7) Ну если тебе так сильно нужен будет исходный код - вышлю на мыло. Ну или пожди пока эту идиотскую блокировку снимут
7. webester 29 04.12.14 06:17 Сейчас в теме
Исходный код статьи - здесь

РосПозорНадзор запретил гитхаб в нашей стране, там нашлась статья, как неудачник может прекратить свои страдания.
9. ivanov660 1626 04.12.14 11:17 Сейчас в теме
Что-то уж очень запутано и много кода. К тому же конструктор запросов уже существует для управляемого приложения.
На мой взгляд для решения данной задачи проще использовать конечные автоматы или иерархические конечные автоматы. Из плюсов: алгоритм занимает "десяток" строк кода + таблица правил настраиваемых вручную (есть редакторы), которые можно поменять довольно быстро; графическое представление алгоритма.
10. so-quest 130 04.12.14 11:32 Сейчас в теме
11. AlexanderKai 04.12.14 12:53 Сейчас в теме
Я не понял, а внутри архива есть парсер запроса или только тесты?
12. so-quest 130 04.12.14 13:13 Сейчас в теме
Только тесты к тому что описано.
В следующей публикации будет рассмотрен вопрос как учитывать позицию символов, кэширование работы парсеров и как разработать простой парсер для языка запросов 1С.



13. AlexanderKai 04.12.14 14:38 Сейчас в теме
(12)
А сам парсер будет? :)
Просто тесты бессмысленны без того, что они проверяют :)
14. so-quest 130 04.12.14 15:27 Сейчас в теме
(13) Ну а как же без этого? Будут. Правда сперва будет статья про расчет координат, затем обработка ошибок и восстановление состояния, потом кэширование.
А после - любой сможет написать свой парсер - с девами и вином.
15. AlexanderKai 04.12.14 15:30 Сейчас в теме
(14)
Будет интересно посмотреть на конструирование парсера. Сам сейчас занимаюсь подобным - может чего почерпну.
16. so-quest 130 04.12.14 16:00 Сейчас в теме
Ну коли занимаешься - присоединяйся. Гуртом и батьку бить легче, не то что парсер писать :)

Это, кстати, ко всем желающим относиться - если есть идеи о чем стоит написать - говорите.

17. ADirks 181 05.12.14 07:44 Сейчас в теме
А ещё есть такая интересная штука, как теория формальных языков. Её в институтах изучают.
Также есть и практические инструменты, использующие эту теорию. Например классика - yacc и bison - для C/C++. Или GOLD Parser для всего остального.
18. so-quest 130 05.12.14 08:58 Сейчас в теме
Вот здесь http://infostart.ru/public/239061/ разбор выражения с классической зрения. Для ознакомления.
Второе - формальная грамматика для языка запросов в 1С - отдельная песня. Если посмотришь на реализацию от tormozit - всплакнешь. На остальные - вообще лучше не смотреть, даже моих трех коридоров церковно-приходской школы хватает понять - reduce/reduce конфликт это очень прикольно.
А насчет генераторов парсеров - в прошлом году выкладывал свой шаблон для GoldenParser - позволял по граматике сразу строить код 1С - основной вопрос был "что это и зачем?" Снес нафиг. А ты говоришь FSM, CFG....
19. AlexanderKai 05.12.14 12:43 Сейчас в теме
(18)
Если посмотришь на реализацию от tormozit - всплакнешь.

Это про "Подсистема "Инструменты разработчика" v3.20"?
21. AlexanderKai 05.12.14 12:48 Сейчас в теме
(18)
А насчет генераторов парсеров - в прошлом году выкладывал свой шаблон для GoldenParser - позволял по граматике сразу строить код 1С - основной вопрос был "что это и зачем?" Снес нафиг. А ты говоришь FSM, CFG....

Про ГолденПарсер что-то помню такое, что было. Код 1С - всмысле, байт-код?
23. tormozit 5591 05.12.14 13:37 Сейчас в теме
(18) да, в моей грамматике есть ряд кривых моментов, которые появились для обхода reduce/deduce конфликтов. Как говорится красиво сделал до туда, до куда осилил, а дальше залепил бреши. Самое главное, что на основе этой грамматике сейчас работает самый продвинутый из виденных мной конструктор запросов.
24. so-quest 130 05.12.14 13:51 Сейчас в теме
(23) Он не только самый продвинутый, но и единственный которым можно пользоваться. Тебе за него - отдельный респект и уважуха. В принципе если бы не проблемы с комментариями и определением ид это или имя функции - она бы и мне подошла. Но не срослось. Сергей, если обидел тебя своим высказыванием про "плакал" - прошу прощения, но высказывание относилось не к твоему труду, а к gold parser'у - (как к неособо дружелюбной системе разроботки), и КС грамматикам в принципе (перестал их любить)
(21) Нет, в код 1С (текст)
(20) Возьми ты ту же грамматика для языка запросов и попробуй встроить комментарий везде где он может быть - если делать будешь это в GP - то там тебе даже подсветят где происходит конфликт. И подробно разжуют почему. Вообще комментарии в грамматике - отдельная тема.
29. tormozit 5591 05.12.14 18:32 Сейчас в теме
(24) Да, среда разработки GoldParser конечно отвратная. Видимо все потому, что она кроссплатформенная и потому интерфейс пользователя такой корявый и неудобный. Но альтернатив, таких же доступных для применения в 1С, я не видел. Еще есть такая крутая штука ANTLR http://www.antlr.org/ , но для него нет готового COM движка.
Да, в грамматике моей самая большая беда с идентификаторами. Я много времени убил на поиск красивого решения, но так и не нашел. Мне даже кажется, что его там в принципе нельзя сделать красивым.
И по комментариям тоже кривая реализация конечно, из-за чего я ее так долго и не делал, т.к. искал опять же красивое решение. В некоторых местах комментарии вызывают ошибку парсера, т.к. они лексемы рождают, которые несколько правил могут начинать. Но уже мой код в 1С там выдает подсказку пользователю, чтобы он переставил комментарии. И за разбор комментариев таким образом пришлось заплатить некоторым снижением гибкости расположения комментариев в тексте запроса.
20. AlexanderKai 05.12.14 12:46 Сейчас в теме
reduce/reduce конфликт это очень прикольно.

Если в двух словах? :)
22. tormozit 5591 05.12.14 13:30 Сейчас в теме
Правильное название GOLD Parsing System, а не Golden Parser. Грамматика гибридного языка запросов (1с + sql) для этого парсера мной развивается тут http://devtool1c.ucoz.ru/load/grammatika_jazyka_zaprosov_1s_8_2_goldparser/1-1-0-4. Она используется в подсистеме "Инструменты разработчика" при построении дерева запроса в консоли запросов и в собственном конструкторе запроса.
25. AlexanderKai 05.12.14 14:20 Сейчас в теме
Возьми ты ту же грамматика для языка запросов и попробуй встроить комментарий везде где он может быть - если делать будешь это в GP - то там тебе даже подсветят где происходит конфликт. И подробно разжуют почему. Вообще комментарии в грамматике - отдельная тема.

С трудом представляю какие могут быть сложности с комментариями.
26. so-quest 130 05.12.14 15:01 Сейчас в теме
Ссылку на грамматику тебе дали. Скачай и добавь поддержку комментариев. Проблему поймешь легко.
Вот пример

"ВЫБРАТЬ // хитрый комментарий 1
| 1 // хитрый комментарий 2
| КАК // хитрый комментарий 3
|Поле1 // хитрый комментарий 4
|// хитрый комментарий 5
|ОБЪЕДИНИТЬ // хитрый комментарий 6
| // хитрый комментарий
|ВСЕ // хитрый комментарий 7
|
|ВЫБРАТЬ // хитрый комментарий 8
| // хитрый комментарий 9
|2"

Если сделаешь - тебе спасибо очень многие скажут. :)

27. AlexanderKai 05.12.14 15:34 Сейчас в теме
(26)
Я грамматиками не балуюсь - просто беру и пишу :) Как-то пробовал вникнуть в него(голден парсер) - но что-то у нас характеры не сошлись.
Возможно это архитектурные ограничения Голден Парсера и там действительно это проблема. В моей текущей версии парсера комментарии легко обрабатываются. До запроса еще не дошел, но не думаю, что там возникнут проблемы.
30. tormozit 5591 05.12.14 18:39 Сейчас в теме
(27) AlexanderKai,
В моей текущей версии парсера комментарии легко обрабатываются.
Грамматика языка запросов 1с в несколько раз сложнее грамматики встроенного языка 1с и соответственно неоднозначных переходов к правилам при встрече лексемы комментария будет намного меньше.
43. orefkov 1974 26.12.14 12:10 Сейчас в теме
(26)
А зачем комментарии встраивать в грамматику? Может я что-то не понимаю? Но обычно комментарии еще на этапе лексического разбора убираются.
void ModuleParser::nextLexem()
{
	for(;;)
	{
		m_source.nextLexemWithKeyword(lastLexem);
		if(lexRemark == lastLexem.type)
			continue;
...

Показать
44. so-quest 130 26.12.14 12:34 Сейчас в теме
(43) orefkov, глянь на инструменты разработчика - по AST восстанавливается текст запроса.
45. orefkov 1974 26.12.14 13:09 Сейчас в теме
(44)
А, я так понимаю это задача о "конструкторе запросов, оставляющем комментарии" ?
То есть залили текст, поредактировали дерево, вылили текст?
Имхо, это уже не задача грамматики.
Вернее, в терминах одной лишь грамматики строго не реализуема. Ибо грамматика - это прежде всего формальный подход, регламентирование, строгость и однозначность.
А какие формальные правила есть при написании комментариев? Нет, и быть не может. К примеру, стоит комментарий перед первым полем в списке полей. Он к чему относится? К конкретному полю:
"-- Тут поле Товара"
А может ко всему списку полей:
"-- Начинаем поля выборки"
А может просто
"-- Вася 10.10.10 был и правил"
Поле "Товар" удалили - оставлять комментарий или нет?

Я бы все-таки и для этой задачи не вносил комментарии в грамматику. А сделал бы комментарий просто атрибутом узла AST. На этапе лексического разбора комментарий бы просто привязывал к ближайшей последующей/предыдущей значащей лексеме. В-принципе, при желании, после построения дерева (уже после парсера грамматики) можно было бы по нему пройтись и выделить комментарии в отдельные узлы. Но так и так - это уже задача семантики, а не грамматики - следующее звено цепочки "лексика-грамматика-семантика". Грамматика - не серебрянная пуля, и не надо стараться только на ней одной выехать.
Для того же телепата и снегопата ряд моментов мной был вынесен из грамматики на уровень семантики - ибо на уровне грамматики они решались сложно, а на уровне семантики - легко. К примеру "Возврат Выражение" - то, что это допустимо только в функции, но не в процедуре, что Прервать/Продолжить допустимо только в циклах, те же ключевые слова как имена свойств/методов - это уже делалось либо пост-парсером, либо хаком разбора.
46. tormozit 5591 26.12.14 13:25 Сейчас в теме
(45) +1
В (29) я этой проблемы касался относительно комментариев. Была бы возможность (в COM-реализации парсера GoldParser), я бы ни за что не стал осквернять грамматику комментариями. Но кроме бесспорных минусов у варианта обозначения комментариев в грамматике есть и свои плюсы, которые конечно же не смогут перевесить минусы.
47. so-quest 130 27.12.14 18:16 Сейчас в теме
(46) tormozit, Была бы возможность (в COM-реализации парсера GoldParser), я бы ни за что не стал осквернять грамматику комментариями. - там же вроде в зависимости от того что вернет Parse() можно определить токен это или комментарий. могу ошибаться - сто лет туда не смотрел
48. tormozit 5591 27.12.14 21:54 Сейчас в теме
(47) определять что лексер вернул комментарий, можно, но прикреплять к узлам синтаксического дерева эти комментарии напрямую нельзя. Дерево все полностью только для чтения.
28. so-quest 130 05.12.14 15:52 Сейчас в теме
Другими словами - ты пишешь то же самое что и я - нисходящий разбор. Интересно посмотреть - как без баловства с грамматиками можно что-то сделать.
> До запроса еще не дошел, но не думаю, что там возникнут проблемы.
При ручном разборе - нет. Не возникнут. Как впрочем и проблем с "|" не будет - у тебя оператор выбора - упорядоченный получается.
> Возможно это архитектурные ограничения Голден Парсера и там действительно это проблема.
Нет. В GP - не проблема, в общем случае для КС это сложно.
31. so-quest 130 05.12.14 19:09 Сейчас в теме
> Мне даже кажется, что его там в принципе нельзя сделать красивым.
В той постановке задачи которую принял ты - да, лучше чем у тебя сделано - никак. Повторюсь - это проблема всех КС грамматик - прочитан символ и надо определиться куда дальше идти - если сверток больше 2 - конфликт. В PEG этого нет, так как оператор альтернативы - упорядочен. Кстати, если упростить твою грамматику до одного id, а выяснение роли этого идентификатора (идентификатор ил имя функции) вынести в интерпретатор - то грамматика упрощается.


Проблема с комментариями решается просто на уровне GP. Но тогда тебе придется очень много кода перекроить. При чтении комментария генерируется токен с типом комментарий (даже 2 - что бы различать многострочные и однострочные комментарии). Можно на это завязаться - но повторюсь - много переписывать придется.


>Грамматика языка запросов 1с в несколько раз сложнее грамматики встроенного языка 1с
Ну не сказал бы. В инете валяется грамматика которую еще MMF (по моему он, могу ошибаться) делал. Посложнее языка запросов будет.
32. tormozit 5591 05.12.14 20:04 Сейчас в теме
(31)
При чтении комментария генерируется токен с типом комментарий
Это я в первую очередь пробовал, но COM-объекты неизменяемые, т.е. я не могу в них вставлять свои дополнения (прилепить комментарий к текущему правилу). Поэтому такой способ кажется все очень усложнит.

Под сложностью грамматики имею ввиду некую функцию от количества правил и средней степени вложений правил. Мне кажется грамматика встроенного языка тут явно проще будет.
33. alexinzaz 08.12.14 14:56 Сейчас в теме
Мне чет институтские лекции по основам трансляторов вспомнились:) Автору респект.
34. so-quest 130 15.12.14 21:06 Сейчас в теме
Ищу соавтора на вторую часть статьи. Будут описано построение парсера для арифметических выражений, построение генератора парсера и в качестве примера использования - описана грамматика markdown-разметки для комментариев в коде. Желающие - отметьтесь в личке.
35. brr 176 19.12.14 15:58 Сейчас в теме
(34) не могу написать вам личное сообщение, потому что у меня менее 1 стратмани :))). Готов поучаствовать.
36. orefkov 1974 25.12.14 11:30 Сейчас в теме
В снегопате процедура парсинга языка 1С состоит из 3 тысяч строк, в которых 1300 "goto" и ни одного "for" :)
37. so-quest 130 25.12.14 11:51 Сейчас в теме
38. orefkov 1974 25.12.14 11:52 Сейчас в теме
(37)
Нет конечно. Сначала bison, а потом мой скрипт по его результатам.
39. so-quest 130 25.12.14 11:54 Сейчас в теме
Косяк с х.Возврат обошел так же как и в 77?
40. orefkov 1974 25.12.14 12:34 Сейчас в теме
(39)
Немного недопонял, какой именно косяк и как я его обошел в 77?
41. so-quest 130 25.12.14 12:40 Сейчас в теме
Использование ключевых слов в имени полей. В грамматике для 77 ты ввел отдельное правило, а здесь как сделал?
42. orefkov 1974 26.12.14 09:54 Сейчас в теме
(41)
int ModuleParser::onError()
{
    if ((stack->state == 73 || stack->state == 75 || stack->state == 149) && lastTokenType > lexName) {
        // Имена после точки могут совпадать с ключевыми словами
        lastTokenType = lexName;
        return 1;
    }
    return 0;
}
Показать
49. Makushimo 154 30.12.14 06:02 Сейчас в теме
Как использовать эти алгоритмы?
Это вот что?
Проверим работоспособность парсера последовательности на следующей грамматике
‹тест1› ::= ‹м› ‹а› ‹м› ‹а›
‹м› ::= м
‹а› ::= а

с этим что делать?

Красиво изложенная теория не укладывается в голове.ни вдоль ни поперек.

Как подать на вход некий текст? Пример кода
Что будет на выходе?
Отсюда должно появиться понимание - Для чего все это?

Помню летал в вышмате в институте, но уже тогда кроме игр разума, не видел практической ценности этих знаний. Не показали, блин -)))

50. so-quest 130 30.12.14 10:14 Сейчас в теме
(49) Makushimo, вот буквально после грамматики ниже - процедура Тест_Последовательно() - в ней пример вызова для анализа строки и анализ полученного результата.
Практическая ценность - конечно никакой. Одна игра разума. Возможно во второй части будет понятней - https://github.com/wwall/report-1/blob/master/md/part2.md - но опять же, повторюсь, для написания печатных форм и при подготовке к экзамену в 1С - никак не поможет.



51. Makushimo 154 30.12.14 14:31 Сейчас в теме
(50)
тю на вас -))
я изучаю всякие подходы к реализации разного рода анализаторов/парсеров текстов
думал можт у вас научусь чему нибудь.
А тут ничего не понятно-)))
52. Makushimo 154 30.12.14 14:44 Сейчас в теме
(50)
почему тест грамматики написан именно таким "убеймозг"-образом ??
это строка, которую можно подать на вход процедуре/функции?

например
СтрокаНаАнализ = "‹тест1› ::= ‹м› ‹а› ‹м› ‹а›
| ‹м› ::= м
| ‹а› ::= а";
Результат = Тест_Последовательно(СтрокаНаАнализ);

Но в тексте статьи "вот буквально после грамматики ниже" ничего такого нету.
Там прямо в процедуре что-то происходит -))
ну то есть понять что с объектами происходит можно, но что это в итоге означает - нет.
Например, Образец получает результат разбора части строки.
а нечто с именем юТест имеет метод ПроверитьРавенство() который что-то делает.
и т.д.
53. so-quest 130 30.12.14 14:51 Сейчас в теме
(52) Makushimo, Там прямо в процедуре что-то происходит -))
Вы попутно с " всякими подходами к реализации разного рода анализаторов/парсеров текстов" язык программирования 1С еще изучите. Станет понятно что там происходит, почему и как.
И очень рекомендую прочитать часть озаглавленную "Необязательные инструменты использованные в процессе разработки" - станет ясно откуда берется юТест и почему код построен таким образом.
54. Makushimo 154 31.12.14 05:27 Сейчас в теме
(53)
О, так еще и язык 1С учить надо? -)))
е-мае, куда я попал. -)))

короче на вас надежды нет, придется идти тем же, что и вы или другим путем.

и да, вы нереально круты раз написали такую непонятную крутую штуку. -))
55. so-quest 130 31.12.14 12:02 Сейчас в теме
За разрешение двигаться - тебе конечно спасибо. Я то думал что же меня так на месте держит?

Вот объясни что тебе не понятно??? Это же заготовка под PEG генератор. Что может быть проще??? Все ссылки объясняющие для чего это делается есть. Как это делается - в коде написано. Что будет сделано дальше - также написано.

А насчет непонятности - ты первый на 3 ресурсах кто об сказал. Может действительно стоит переписать.

С наступающим. Всех благ в новом году!
56. Dethmontt 09.01.15 03:23 Сейчас в теме
(55) ну когда уже ждать оформленного "тут" продолжения?
57. sashocq 191 02.02.15 11:37 Сейчас в теме
Тут действительно очень нелегко разобраться что к чему. Описания принципов сильно переплетено с деталями реализации. Описаны кирпичи, но нет какого-нибудь сарая, который можно из них построить. Примеры как разложить строку в массив символов и обратно или как "1234" преобразовать в 1234 мне совершенно не интересны. Мне интересно как из строки "128 + -65" получить число 63. При чем, желательно видеть где начало, а где конец. У вас же в тестах сложно увидеть вход и выход, они где-то в середине:
    цифра = ПостроитьПарсер("range",Новый Структура("Минимум,Максимум","0","9"));
    число = ПостроитьПарсер("+",цифра);
    Преобразователь = ПостроитьПарсер("fn",Новый Структура("Парсер,Функция",число,"РезультатВЧисло"));
    Результат = ПрименитьПарсер(Преобразователь,"1234");
    Образец = РазобраноУспешно(1234,"");
    юТест.ПроверитьРавенство(Результат.Тип, образец.Тип);
    юТест.ПроверитьРавенство(Остаток(Результат), Остаток(образец));
    юТест.ПроверитьРавенство(Значение(Результат), Значение(образец));
Показать

Где тут видно, что вход - "1234", а выход - 1234???
58. so-quest 130 02.02.15 13:10 Сейчас в теме
(57) sashocq, насчет такого сравнения прав - тут не очевидно, но в следующей версии поправлено.
Код
цифра = ПостроитьПарсер("range",Новый Структура("Минимум,Максимум","0","9"));
    число = ПостроитьПарсер("+",цифра);
    Преобразователь = ПостроитьПарсер("fn",Новый Структура("Парсер,Функция",число,"РезультатВЧисло"));
    Результат = ПрименитьПарсер(Преобразователь,"1234");
    Образец = РазобраноУспешно(1234,"");
    юТест.ПроверитьРавенствоРекурсивно(Результат образец);

будет думаю более читаемым (но опять же - для этого придется взять мой правленый xUnit, с поддержкой этой функции).
>>> Мне интересно как из строки "128 + -65" получить число 63.
Пишу, вот честно - пишу продолжение, но сейчас увы времени мало. Да и отзывов на бета версию второй части тоже немного, что не добавляет оптимизма. :)
59. baton_pk 392 17.02.15 22:07 Сейчас в теме
вселенская несправедливость, что тут до сих пор не было моего плюса.

Код большими кусками плохо воспринимается.

    МассивРезультата = Новый Массив;
    МассивРезультата.Добавить("м");
    МассивРезультата.Добавить("а");
    МассивРезультата.Добавить("м");
    МассивРезультата.Добавить("а");

Делайте на такие вещи всё-таки функцию какую-нибудь, чтобы тут в статьях это была одна строчка, а не 5.

(Ушёл внимательно читать ещё разок...)
60. artamir 8 08.12.16 16:57 Сейчас в теме
Нашел очепятку в параграфе 3.1 в пункте 1. прочатнный = прочитанный
61. artamir 8 08.12.16 18:11 Сейчас в теме
В параграфе 4.4 исчезло окончание кода:
Функция Интервал(Парсер,СтрокаАнализа)
    мин = Парсер.Парсер.Минимум;
    макс = Парсер.Парсер.Максимум;
    символ = Сред(СтрокаАнализа,1,1);
    Если мин
62. so-quest 130 08.12.16 23:14 Сейчас в теме
Спасибо за комментарии. В следующей версии будет все поправлено.
63. kote 499 12.03.17 19:29 Сейчас в теме
64. tsukanov 57 13.08.17 16:28 Сейчас в теме
Фигасе ты заморочился )))
65. so-quest 130 14.08.17 08:55 Сейчас в теме
Давно это было. Сейчас бы делал совсем по другому.
Оставьте свое сообщение
Новые вопросы с вознаграждением
Автор темы объявил вознаграждение за найденный ответ, его получит тот, кто первый поможет автору.

Вакансии

Программист 1С
Москва
зарплата от 120 000 руб. до 150 000 руб.
Полный день


Программист 1С
Санкт-Петербург
зарплата от 80 000 руб. до 120 000 руб.
Полный день

Архитектор 1С
Санкт-Петербург
зарплата от 150 000 руб.
Полный день

Программист 1С (Оперативный учет)
Санкт-Петербург
зарплата от 120 000 руб.
Полный день