Хорош ли мой подход к созданию своего алгоритма движка разбора JSON, XML, HTML, CSS? А что насчет разбора кода на ЯП?
Не то чтобы он даже мой, просто никаких иных решений мне не доводилось где-то встречать. И в голову не лезут.
В общем, мы берем исходный код (в виде строки) и просто в цикле обходим все ее символы, if'ами проверяя что за символ, и принимая соответствующее решение (для HTML: если "<", то создать ветвь, далее парсим тэг и аттрибуты; если ">", то далее парсим содержимое, также закрытие ветви и т.д.; всем этим вспомогательным stuffом - то есть созданием, закрытием и т.д. - заняты отдельные функции, дабы не загромождать сам код парсинга)
Ну а чтобы на каждом символе помнить, где именно мы находимся и каких символов должны ожидать (находимся ли мы внутри аттрибута с кавычками, или внутри аттрибута без кавычек, или мы находимся после "<" и должны ожидать ">", или внутри ветви, и т.д.) для этого есть переменная-перечисление (вариантов местонахождения) + еще переменные.
Вопросы:
1) Хорош ли такой подход для JSON, XML/HTML, CSS?
2) Как его назвать, чтоб "по-научному" и понятно было?
3) А оправдано ли его применение для парсинга не языка разметки, а реального ЯП, скажем JS?
Или для этой задачи это слишком "велосипедно"?
4) Ничего лучше в голову не лезет, ни для ЯП, ни тем более для JSON, XML/HTML, CSS...
Может, регулярки в прямых руках будут лучше? Почему тогда их не применяют в подобных движках?
То что вы описали называется state_machine и это обычный подход для парсинга xml. Тьюринг полный ЯП так не распарсить, например не распарсить goto. ЯП описываются EBNF или другими достаточно варазительными грамматиками и парсятся в абстрактное_синтаксическое_дерево. Парсеры EBNF могут к примеру подсматривать вперед или назад.
Спс, видимо, вы разбираетесь)
Я знаю, что такое BNF. Но это, так сказать, теория.
А на практике-то какой алгоритм применять для такого и в чем отличие от описанного? Только обход в разные стороны?
И почему так не распарсить goto? Я не вижу проблем.
"Абстрактное синтаксическое дерево" тоже ничего для меня не значит. В дерево бинарное - парсятся и JSON и XML. Дерево и дерево.
VZVZ: Забудьте про goto, попробуйте хотя бы рекурсивные определения шаблонов в С++ распарсить в один проход. Да хоть и простейшие обявления классов, где член к которому обращаются находится дальше по тексту, а нужно определить, существует ли он, прямо сейчас.
MiiNiPaa: непонятно одно: зачем "прямо сейчас"?
Да, если не "прямо сейчас", то будет серьезный недостаток: такое будет тормозить, если его применить в штуках вроде IntelliSense (кстати, как такие штуки назвать "по-научному"?)
Но что если мы не собираемся пока делать такое? Если просто для компиляции-интерпретации, то сойдет и не "прямо сейчас", ИМХО
BNF грамматики рекурсивны. Finite State Machine (конечный автомат) не рекурсивен и не полон по Тьюрингу. Что бы распарсить < <><> > вам уже понадобится хотя бы автомат со стеком. Полноценные парсеры что бы получить лексему пробуют по очереди правила грамматики(которые могут быть рекурсивными) выбирают самое подходящее, могут строить гипотезы о дальнейшем вводе имеют память и имеют право подглядывать вперед. А заканчивают разбор не конечным состоянием, а деревом.
VZVZ: Прямо сейчас надо потому что от этого смысл может поменяться. Например есть у нас глобальная переменная foo. Если члена с таким именем нет, то всё ок, обращаемся по адресу этой переменной. Если есть, то надо взять смещение от this, а какое, можно узнать только прочитав всё определение класса. А если это функция-член, то нужно взять её адрес. А если она виртуальная, то надо ковыряться в vtable, в зависимости от её устройства.
MiiNiPaa: давайте упростим задачу. Вернемся к goto.
Итак, у нас есть goto к метке, которая несколькими строчками ниже.
И нам, допустим, надо сразу все писать непосредственно в EXE-файл (допустим так адски важно быстродействие и простота)
Что мы делаем?
Распарсив goto, в EXE-файл пишем jmp 0; (пока что 0), при этом запомнив в коллекцию, что есть такой оператор goto, как называется метка и где именно в EXE-файле он находится.
А потом увидев эту метку, просто находим тот goto в коллекции и в соответствующий адрес EXE-файла ставим адрес метки.
Problems?
VZVZ: Ну например в зависимости от цели прыжка нужны разные опкоды. Причём разной длины. Причём иногда прыжок нелегален и совершать его нельзя. Например если между прыжком и целью объявляется и не уничтожается переменная.
uvelichitel:
> Что бы распарсить < <><> > вам уже понадобится хотя бы автомат со стеком
Хм... Кажется на это уже напоролся. А что это за стек, если по-простому? Типа сек открытых скобок "<", чтобы не запустаться какая ">" для какой "<"?
Rsa97: спасибо и на том, конечно, прежде всего спасибо за "val3", но не понимаю, что вы хотите доказать. Библиотеки, написанные на таком принципе, уже ведь есть.
Получается, как про суслика, только наоборот: Суслика видишь? Да! А его нет!
VZVZ: Я скорее хочу не доказать, а показать то, с чем вы столкнётесь. В JSON синтаксис строгий, поэтому его реализация достаточно простая, по EBNF создаётся автомат с магазинной памятью.
А вот для HTML нужна ещё обработка кучи исключений, его синтаксис не строгий и комбинация тегов не всегда однозначно раскладывается в дерево.
1) Нет, плох. Ничего у вас с этим подходом хорошего не выйдет.
2) Конкретно этот подход - детерминированный конечный автомат
3) Нет, не оправдано. Не получится.
4) Почитайте что-нибудь на тему теории формальных языков и грамматик. Конструирование компиляторов. Теория интерпретации компьютерных программ.
Регулярное выражение эквивалентно детерминированному конечному автомату, так что не выйдет.
VZVZ: конечный-то автомат? Вы мне лучше покажите, где их не используют;) но проблема в том, что им можно распарсить весьма ограниченный круг грамматик.
VZVZ: человек, прочитайте пожалуйста книги Колмогорова Андрея Николаевича по математической логике, а также труды Чёрча по лямбда-вычислениям, а затем Интерпретация Лисп(Lisp) и Ским(scheme). Потом уже переходите к алгоритмам. Как Вам правильно посоветовали: "Изучите ТО что было ДО ..."
VZVZ: к сожалению, это слишком большой объем информации. Теория алгоритмов целиком и полностью базируется на мат логике (не только на ней, но это неотъемлемая часть). Крепитесь!
Алексей П: ну конечный автомат вроде уже понял. Сейчас попробую реализовать для JSON)) Уже могу считать себя специалистом по формальной грамматике, низшего ранга?
Denis Zagayevskiy: а почему вы так думаете? Мне кажется, что человек, который не знаком с мат логикой, будет не до конца понимать принципы формализации языков. Тем более, что в самом начале мат логики излагается понятие терма и лексической формы.
Поэтому, ваш ответ на данный вопрос, я считаю не полным, и ведущим мукам, в дальнейшем. Особенно п 4) - про формальные языки, грамматики и компиляторы.
Т.к. эти понятия подразумевают формальное подтверждение конструкции. К тому же, что такое компилятор? Лексический анализатор + синтакцический анализатор + транслятор + комановщик. Или вы думаете по-другому?
Алексей П: не то, чтобы вы не правы, матлог - штука полезная. Но, извините, советовать это (да ещё плюс нумералы Чёрча) человеку, который рвётся в бой.. Ему надо взять и почитать основы того, чем он сейчас интересуется. Как правильно Д/Н КА представлять, как они с регулярными выражениями связаны, какие грамматики можно ими обработать, какие грамматики вообще существуют, какие есть способы парсинга, как сделать синтаксический анализатор (а того, что придумал автор, без костылей хватит максимум для лексического). Что такое AST - а автор сказал, что ему это ничего не говорит, ну так надо, что говорило. И прочее, и прочее. И для всего этого матлог не нужен. А вы ему Лисп предлагаете интерпретировать. Думаете, он знает, что такое лисп и функциональное программирование? А нафига интерпретировать то, что ты в принципе не понимаешь?
Denis Zagayevskiy: что такое функциональное программирование, я знаю примерно.
Насчет основ - вы правы, но также параллельно им изучаю и готовые решения, в данном случае это Irony.NET (где, к слову, встретил и термин "AST"). То есть иду от примитивного к сложному, и параллельно от сложного к примитивному. Всегда так делал, и получалось, так я сети освоил, например. Что я делал не так?
VZVZ: у каждого свой метод познания того или иного знания. Мне кажется, что если Вам так удобно, тогда так и поступайте. Я привык есть "слона" по частям.
Добавлю про интерпретацию лиспа и ским, Вам выше посоветовали книгу Красного дракона, насколько я помню, она посвящена algol-подобным языкам. Разбор такого языка проблематичнее разбора лиспа, json и т.п.
Местоположения мало.
Взять к примеру json - {"name": "value"}
Если обрабатываешь символ "n", то находишься в документ/обьект/наименование атрибута обьекта/текст
А если символ "v", то документ/обьект/значение атрибута обьекта/текст
И таких тонкостей много.
Это тоже подходит под мою "теорию" "местоположения".
Перечисление (enum) будет выглядеть как-то так:
1) вне элемента
2) в элементе
3) в ключе
4) после ключа (здесь ищем ":")
5) в значении
6) после значения (ищем "," либо "}")
Это как минимум.
Разумеется, для полноценной поддержки JSON и enum будет длиннее и алгоритм "раскидистее", и вообще все сложнее.
Используется принцип флагов, т.е. как только прошли "{" или """, то в переменной меняется значение из enum и начиная со следующего символа мы его учитываем.
Denis Zagayevskiy: почему? Именно ЭТУ - уже распарсил. Есть метод ParseObject(string), вот для каждого такого { "name1" : "value1" } он и вызывается рекурсивно. Правда, на настоящей рекурсии (хотя бы в 2 уровня, а не 1) сразу глюк. Но теоретически вполне можно сделать, и я сделаю. Правда, здесь уже начинаются проблемы при моем сонной башке, ибо сложновато, но ничего, на свежую голову продолжу.
Denis Zagayevskiy: похоже, рекурсии тоже не будет. Петр прав.
Будет другое: нарвавшись на "{" в value, мы создаем новый Object и далее ведем себя с ним так же, как и с коренным ("внешним") объектом, а при "}" закрываем этот объект и снова возвращаемся к "внешнему".
Так должно получиться без рекурсии.
Denis Zagayevskiy: ну, если вам нечего сказать, то как пожелаете. А если вам есть что сказать по подходу "без рекурсии", или хотя бы знаете, как такое называется общепринято, чтобы вбить в гугл и что-то найти, то зря удаляетесь, ИМХО.
Средний
