Здравствуйте, Damat_AE, Вы писали:
D_A>Насчет наивности — не верю. Если это уже реализовали, то и я смогу, многое считал в свое время заоблачным, а потом чик — и реализовал.
Левша блоху то подковал, но она потом не прыгала
Автодополнение с высказанными выше требованиями, требует знания типа, того что стоит перед точкой.
Для этого нужно провести семантический анализ.
От контекста к корню это можно, если имеешь этот самый корень
От точки влево, это тоже можно, но это разбор справа-налево, скорее всего восходящий. D_A>Если не забегать наперед, то все сложное становится простым — проэктировать надо правильно!!!
Для этого достаточно просто проЕктировать
Re[12]: Универсальный механизм Intellisense (идея)
В корне как раз стоит экземпляр класса — известный тип,
тогда проще узнать что в нем есть, тоесть правильно сформированная грамматика
предполагает, что обход синтаксического дерева от корня к чилдам — даст строковое представление
корень — чилд — чилд чилда итп...
согласен, что не всегда так — даже возвращаемое значение функции — тип, стоит перед именем иной,
что уже нарушает это правило. НО...
парсим исходник мы всеравно от корня к чилдам — нэймспэйс, в нем — тыпы...
собственно в каждом ДОМЕНЕ есть перечень возможных типов ДОМЕНОВ, которые могут быть в нем.
ДОМЕН умеет парсить себя, тоесть в строковом контенте каждый должен узнать себя и подсоединиться
к родителю (дерево). Для специфических случаев ДОМЕН реализует свою собственную стратегию узнавания —
функция нашла свое имя со скобочкой — разбивает строчку на части и отдает на парсинг своим дочерним
доменам — возвращаемому значению и параметрам, телу. Так подходит для всего.
На предыдущей работе я парсил адрес США — 8 составляющих — стратегии и ничего сложного, каждый ДОМЕН
просто реализовывал интерфейс — в итоге: Интерфейс прост и в каждом домене минимум реализации — и
работает естественно
Если что-то не вяжется под схему — оставь возможность реализовать по своему...
И опять. Я предлагаю не думать про парсинг сначала — в отдельном модуле реализовуем грамматику,
добавляем обязательно визитор — обожаю, и потом извне вешаем что угодно — отдельно автодополнение,
ну как захочется.
А с парсингом потом разберемся — это будет своя специфика, а кто сказал, что интелисенс не связан с
редактором диаграмм последовательностей??? ведь тоже самое, тоесть парсинг — это если в текстовом
редакторе сидеть...
И уж если до того дойдет, чтобы уже писать парсинг, то точно придется меньше заморачиваться, чем
если думать о всех его сложностях сразу.
В чем разница наших подходов и точек зрения — я не кричу о возможных проблемах и особо не заморачиваюсь
сейчас в поисках их решения — они еще не требуют от меня решения, следовательно их решение сейчас
требует гораздо больше усилий, чем решать их потом, когда они могут уже и не быть проблемами — естественно
А для достижения же цели надо на даном этапе всего лишь юзе-кейс диаграмку с возможными ситуациями, которые
надо решить — по ним придется строить объектную модель — но не отталкиваясь от типа: БОЖЕ, КАК ЖЕ СЛОЖНО БУДЕТ
ТОЛЬКО ПАРСИТЬ!!! с таким подходом толково писать не получится!!!
Так что давайте уж делать(продумывать), если интересно
Мне — очень!!!
ПС. как сказал мой учитель(гуру внатуре!!!): если до чегото не можешь додуматься сейчас — не спеши лепить код,
отвлекись на время(день, неделя) — пусть оно варится в голове — решение придет само — подсознание тоже шуршит
всегда верно!!!
Здравствуйте, VladD2, Вы писали:
VD>Хочу разочаровать еще одних кремлевских мечтателей. Реализация универсального интелисенса невозможна, так как в интелисенсе главное не клавиатурные шпионы или диковенные окна, а банальные парсеры языков. Сложность их разработки — это главный астонавливающий фактор. Так что для решения описанной задачи на высоком техническом уровне начать нужно с гениального построителя пасреров сопособного по грамматике из описания языка быстренько составить эффективный пасрер. Таких продуктов в в свободном доступе я не видел.
Всё не так уж и сложно. Делаем Инкрементный GLR парсер. (таким образом охватываем все контекстно свободные грамматики, а это уже достаточно) Делаем генератор таблиц к парсесу по файлу грамматики (грамматику можно в расширенной форме Бэкуса Наура задавать + ещё всякие действия IntelliSense).
VD>Более того многие языки так сожны в парсинге (С++, естественные языки) или имеют такие особености (Смолток), что уневирсально решить такую задачу нельзя.
GLR парсер.
Здравствуйте, maggot, Вы писали:
M>Всё не так уж и сложно. Делаем Инкрементный GLR парсер. (таким образом охватываем все контекстно свободные грамматики, а это уже достаточно) Делаем генератор таблиц к парсесу по файлу грамматики (грамматику можно в расширенной форме Бэкуса Наура задавать + ещё всякие действия IntelliSense).
Ага. Ну, эта задача практически элементарна. Желаю удачи тем кто ею займется.
ЗЫ
Кстати, парсера мало. Приличный интеллисенс требует информации о типах и работы при не полных исходниках.
В общем, создать даже частный случай интеллисенса для мощьного языка очень сложно, а универсальный крайне сложно.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>И наблюдаем живое воплощение O(n^3) на больших проектах и файлах.
Откуда там O(n^3) ? Киньте ссылку или хотя бы объясните...
ИМХО У статического(то есть не инкрементного) GLR синтаксического анализатора сложность линейная от размера файла.
И как вы вообще определяете сложность алгоритма, если сначала анализируются полностью исходники, а потом в режиме реального времени при их изменении корректируется дерево разбора и, соответственно, выполняются какие-то действия?
VD>Ага. Ну, эта задача практически элементарна. Желаю удачи тем кто ею займется.
Естественно, это не блокнот создать.
Займусь в ближайшее время. Пока что единственной проблемой является "умная" обработка ошибок и восстановление после них. Я полагаю, некорректные конструкции должны как то выделяться (там подчёркиваться, как, например, в Ворде). Вот, например, с ошибками в выражении IntelliSense могут бороться, а вот с ошибками в открытии/закрытии блока (фигурные скобки в С++/Java) уже нет. По крайней мере я таких не встречал.
Вот, что мне приходит в голову по этому поводу:
Что такое ошибка? Это когда не существует нетерминального символа в данном контексте, в который можно свернуть последовательность символов. Другими словами ни один нетерминальный символ в данном контексте не порождает данную последовательность символов.
Можно продолжить разбор по "нескольким ветвям" (скорее их количество нужно будет ограничивать), свернув последовательность символов в некоторые нетерминалы, которые могут порождать наиболее похожие последовательности символов относительно данной.
Таким образом на разных ветвях разбора будет возникать различное количество синтаксических ошибок (можно сделать ещё обратную связь семантического анализатора с синтаксическим, тогда будет ещё круче ). IntelliSense будет работать ориентируясь по той ветви, в которой количество ошибок наименьшее. Идея отличная, другого варианта сделать универсально нет. Но реализовать это будет довольно сложно.
VD>ЗЫ
VD>Кстати, парсера мало. Приличный интеллисенс требует информации о типах и работы при не полных исходниках.
Конечно, ещё нужен семантический анализатор.
VD>В общем, создать даже частный случай интеллисенса для мощьного языка очень сложно, а универсальный крайне сложно.
Смотря как делать. Если затачивать под конкретный язык, например, С++, то есть, не абстрагируясь от конкретных конструкция языка, задача без ошибок практически не выполнима. Универсальный будет проще, да и качественнее.
PS На данный момент я сделал только GLR парсер(без обработки ошибок) и генератор таблиц к нему. Делаю на С++. Ввиду того что сплошь и рядом использовал контейнеры STL, код ужасно кривой (опять же это относительно) и неэффективный, особенно по использованию памяти, и я решил всё переделать, написав свою библиотеку контейнеров. Вот так вот
When implemented carefully, the GLR algorithm has the same time complexity as the CYK algorithm and Earley algorithm -- O(n3).
Понятно. O(n^3) в худшем случае. Время работы алгоритма зависит от меры недетерменированности грамматики.
In practice, most programming languages are deterministic or "nearly deterministic", meaning that any nondeterminism is usually resolved within a small (though possibly unbounded) number of tokens.
Практически сложности O(n^3) даже на больших проектах не будет.
И вообще, разве GLR анализатор не единственный наиболее оптимальный вариант?
Здравствуйте, maggot, Вы писали:
M>Понятно. O(n^3) в худшем случае. Время работы алгоритма зависит от меры недетерменированности грамматики.
А зачем нужен GLR если грамматика детерминирована?
M>
In practice, most programming languages are deterministic or "nearly deterministic", meaning that any nondeterminism is usually resolved within a small (though possibly unbounded) number of tokens.
M>Практически сложности O(n^3) даже на больших проектах не будет.
M>И вообще, разве GLR анализатор не единственный наиболее оптимальный вариант?
Нет конечно.
... << RSDN@Home 1.2.0 alpha rev. 725 on Windows Vista 6.0.6000.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>А зачем нужен GLR если грамматика детерминирована?
Грамматика почти детерминированна. Можно, конечно, использовать LR(k) анализатор, НО тогда нужно определиться с k. Выберем k=4. А вдруг граммтика конкретного языка такая, что должно быть равно пяти? Всё, она не подходит! IntelliSense не универсален — работает не со всеми контекстно свободными грамматиками.
O(n^3) будет тогда, когда граммтика такая, что LR(k) анализатор для неё будет нужен такой, что k=n.
На одной и той же грамматике GLR анализатор работает не медленнее, чем LR(k).
AVK>Нет конечно.
Здравствуйте, maggot, Вы писали:
M>Смотря как делать. Если затачивать под конкретный язык, например, С++, то есть, не абстрагируясь от конкретных конструкция языка, задача без ошибок практически не выполнима. Универсальный будет проще, да и качественнее.
Елы, паля! Ну, это же базовая жизненная мудрость. Абстрактное решение сделать сложнее чем конкретное.
В общем, когда сделашь, что-то рабочее — свисни. Но я почему-то уверен, что ничего путного не выйдет в принципе.
M>PS На данный момент я сделал только GLR парсер(без обработки ошибок) и генератор таблиц к нему. Делаю на С++. Ввиду того что сплошь и рядом использовал контейнеры STL, код ужасно кривой (опять же это относительно) и неэффективный, особенно по использованию памяти, и я решил всё переделать, написав свою библиотеку контейнеров. Вот так вот
С++ для таких задач вообще еще тот выбор. Задача не подъемная и на более удобных инструментах, а уж на этом это будет просто последним гвоздем в крышку гроба. В прочем, какая разница на чем решать нерешаемые задачи?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
