Здравствуйте, Damat, Вы писали:
D>согласен, что не просто, но интересен тот факт, он и есть факт, что ошибка внешнего контекста обрывает парсинг внутрености, по крайней мере так часто бывает, что при исправлении в коде 1-й потом начинают вылазить уже другие.
На то есть целая теория о востановлении после сбоя. Для языков типа С зачастую просто пропускают лексемы пока не найдут ключевую, например, ";".
D>Вообще-то, реализация даной штуковины должна быть — элегантный рекурсивный алгоритм и красиво заданная грамматика.
Рекурсивный алгоритм == LL(1) парсеру. Или LL(k) — если с откатами. К сожалению большинство языков с не являются LL(k) и приходится то и дело вставлять ручные заглядывания в перед на непоределенное "к". В итоге код получается страшненьким. И вообще для таких задач нужно использовать построители парсеров.
Вопрос в том, что даже с построителями парсеров задача не становится тривильной и остается огромной для многих ЯП.
D>Смысл даного проэкта(я так думаю) — это реализация его не в коде, а в диаграммах, проработка понятной и расширяемой архитектуры без единого кусочка жвачки
А расширяемую архитектуру чего нужно описывать? Выподающего списка? Дык я тебе его на коленке за день сварганю. А расширяемый парсер — это уже задача небуручка. Вон Мамут очень правильно ссылку дал: Re: Универсальный механизм Intellisense (идея)
D>Есть смысл придумать еще одно колесо — подарок своему самолюбию
Могу только еще раз повторить, что задача создания интерфейса для автодополнения не стоит и выеденного яйца, а задача создания универсального парсера жрущего удобную граматику слишком сложна и сама по себе может потешить любое самолюбие.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Универсальный механизм Intellisense (идея)
Вот понаблюдал еще немножко — набралось аргументов.
Вообщето механизм автодополнения можна делать вообще без парсинга — тк парсинг — это уже разбор представления
синтаксического дерева в текстовом редакторе. Если отбросить все это(пока, зачем париться над логикой свыше),
то можна определить четкий механизм автодополнения — предлагаем от контекста — поиск к корню дерева, хотя и не всегда, но это меня не сильно расстраивает — возможно.
Потом подойдем к отображеню дерева в текст и обратно — сдесь сложнее, но уже попроще, чем париться об этом сразу.
уже сдесь при готовой функциональности определения валидности синтаксического дерева легче реализовывать, тк
решение о правильности — реализовано в библиотеке.
для каждого елемента реализовываются операции превращения в строку и парсинга (интерпритатор)
вообще — отличная задача чтобы использовать практически все паттерны(основные).
Вообще парсить можна по-разному — признаки — парность скобок и т п.
А варианты с заглядыванием наперед — не про SQL запрос ли спрашивалось
Грамматика должна быть по максимуму правильной, иначе — вручную реализован механизм парсинга.
Насчет наивности — не верю. Если это уже реализовали, то и я смогу, многое считал в свое время заоблачным, а потом чик — и реализовал.
Если не забегать наперед, то все сложное становится простым — проэктировать надо правильно!!!
Хочу разочаровать еще одних кремлевских мечтателей. Реализация универсального интелисенса невозможна, так как в интелисенсе главное не клавиатурные шпионы или диковенные окна, а банальные парсеры языков. Сложность их разработки — это главный астонавливающий фактор. Так что для решения описанной задачи на высоком техническом уровне начать нужно с гениального построителя пасреров сопособного по грамматике из описания языка быстренько составить эффективный пасрер. Таких продуктов в в свободном доступе я не видел.
Более того многие языки так сожны в парсинге (С++, естественные языки) или имеют такие особености (Смолток), что уневирсально решить такую задачу нельзя.
Ну, а окошки и шпионы имеются в любой среде вроде Студии или ИДЕИ.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Хочу разочаровать еще одних кремлевских мечтателей.
Думаю, реализация идеи не настолько сложна, как может показаться на первый взгляд. Вопрос лишь в том, насколько "крут" будет такой интеллисенс (меня порадовал бы даже просто IntelliType, то есть автодополнение). Простое автодополнение — это вообще просто и уже сделано, кстати: IntelliComplete, но за деньги Хотелось бы иметь подобный проект, но открытый (свободный) + несколько более функциональный.
Согласен, что автодополнение после точки сделать несколько сложнее, но уверен, что возможно. А вообще, по этой ссылке по-моему, достаточно аргументов сказано по поводу осуществимости...
Кстати, не понял, а зачем вообще парсить естественные языки? Вышеупомянутый шароварный IntelliComplete имеет словарь для русского (!) языка, который работает очень даже здорово.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Silvester, Вы писали:
S>>Есть вот такая идея: S>>http://forum.script-coding.info/topic.php?topic=68 S>>Требуются энтузиасты
VD>Хочу разочаровать еще одних кремлевских мечтателей. Реализация универсального интелисенса невозможна, так как в интелисенсе главное не клавиатурные шпионы или диковенные окна, а банальные парсеры языков. Сложность их разработки — это главный астонавливающий фактор. Так что для решения описанной задачи на высоком техническом уровне начать нужно с гениального построителя пасреров сопособного по грамматике из описания языка быстренько составить эффективный пасрер. Таких продуктов в в свободном доступе я не видел.
VD>Более того многие языки так сожны в парсинге (С++, естественные языки) или имеют такие особености (Смолток), что уневирсально решить такую задачу нельзя.
VD>Ну, а окошки и шпионы имеются в любой среде вроде Студии или ИДЕИ.
Привет.
Вообщето парсинг левосторонней грамматики- тривиальная задача, тоесть один раз пишешь, а потом подкидываешь правила и радуешься. Собственно, на основе даной грамматики можно(даже нужно) строить работу автокомплита ала live templates. Было бы не плохо составить юзе-кейс диаграмму, отображающую то, чего все-таки хоцца, тогда и будет смысл говорить (Влад, это к тебе — сюда было бы не плохо иметь возможность ложить хоть графику — проффесиональнее).
Здравствуйте, Damat, Вы писали:
D>...Было бы не плохо составить юзе-кейс диаграмму, отображающую то, чего все-таки хоцца, тогда и будет смысл говорить...
Может, что-то типа техзадания написать и опубликовать? Я мог бы попробовать.
Здравствуйте, Silvester, Вы писали:
S>Здравствуйте, Damat, Вы писали:
D>>...Было бы не плохо составить юзе-кейс диаграмму, отображающую то, чего все-таки хоцца, тогда и будет смысл говорить...
S>Может, что-то типа техзадания написать и опубликовать? Я мог бы попробовать.
Вообще задачка прикольная, глядя на то, что етсь требования и к скорости, и к функционалу...
Но думать можно начинать тогда, когда четко очерчен объем работ, его же можно и обсудить итеративно
Даного рода задачки прикольные тем, что организация даных принимает вид дерева, что способствует рассматривать
возможные варианты выбора из контекста, в котором ты находишься — типа, сначала неймспейс и ничего другого,
внытри него — классы, структуры, интерфейсы.
Моя идея — как это все задавать — взять за МЕТАФОРУ обычный XSD файл — очень схоже
Но там в основном все статическое, здесь же понадобится абстрагтроваться(выделять интерфейсы).
По крайней мере XML сериализатор, умеющий сохранять и загружать объекты с интерфейсными свойствами у меня уже есть
А еще чего не хватало, например. Рисуеш ты в Визио(ужас!!!) диаграмму последовательности, а на ней тоже нужен интелисенс, такого я покачто не видел. Тоетсь в нашем случае не стоит привязываться к текстовому представлению кода, можна от него абстрагироваться — это как вью
В общем, поучиться есть чему, не уверен, что это реально стартанет, да и стартовать ему нельзя до проработки архитектуры в ЮМЛ — сдесь — СТРУКТУРА — ГЛАВНОЕ
D>Вообщето парсинг левосторонней грамматики- тривиальная задача, тоесть один раз пишешь, а потом подкидываешь правила и радуешься. Собственно, на основе даной грамматики можно(даже нужно) строить работу автокомплита ала live templates. Было бы не плохо составить юзе-кейс диаграмму, отображающую то, чего все-таки хоцца, тогда и будет смысл говорить
На словах все просто. Создай хотя бы один парсер для современного языка тогда поговорим. К тому же парсер для комплита еще должен уметь жить в условиях когда в коде куча ошибок.
D>(Влад, это к тебе — сюда было бы не плохо иметь возможность ложить хоть графику — проффесиональнее).
Клади ее в список своих файлов и давай ссылку. У каждого зарегестрированного посетителя форума в профиле есть список файлов который можно пополнять. Жмешь на свой ник в правом верхнем углу. Жмешь на ссылку "Файлы" и вперед...
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Silvester, Вы писали:
S>Здравствуйте, VladD2, Вы писали:
VD>>Хочу разочаровать еще одних кремлевских мечтателей.
S>Думаю, реализация идеи не настолько сложна, как может показаться на первый взгляд. Вопрос лишь в том, насколько "крут" будет такой интеллисенс (меня порадовал бы даже просто IntelliType, то есть автодополнение). Простое автодополнение — это вообще просто и уже сделано, кстати: IntelliComplete, но за деньги Хотелось бы иметь подобный проект, но открытый (свободный) + несколько более функциональный.
Автодополнение по заранее готовому списку и делать нечего. Это работа на день для любого толкового программиста. А автодополнение для языков программирования требует наличия нехилого парсера для каждого из них... Собственно я уже повторяюсь.
S>Согласен, что автодополнение после точки сделать несколько сложнее, но уверен, что возможно.
Что там быть уверенным? Конечно возможно. Почти любая уважающая себя IDE это делает. Правда, хорошо это удается сделать только для модульных языков хорошо подготовленных для парсинга. Например, нормального автодополнения для С++ я пока что вообще не видел. Везде глюки. Ну, да не о том речь. Создание таких парсерво архи сложный процесс.
S>А вообще, по этой ссылке по-моему, достаточно аргументов сказано по поводу осуществимости...
Извини, но это не серьезно.
S>Кстати, не понял, а зачем вообще парсить естественные языки? Вышеупомянутый шароварный IntelliComplete имеет словарь для русского (!) языка, который работает очень даже здорово.
Комплит по славорю сделать не трудно. В прочем как и не особо нужно. Вот ради хохмы ракропал простенький комплит для текстбокса. В нем конечно половина всего не реализовано, и вообще поделка наколеночная, но за то убил на это дело пол часа всего (C# 2.0):
using System;
using System.Drawing;
using System.Windows.Forms;
public class MainForm : Form
{
[STAThread]
static void Main()
{
Application.EnableVisualStyles();
Application.Run(new MainForm());
}
TextBox _textBox = new TextBox();
ComboBox _comboBox = new ComboBox();
public MainForm()
{
Text = "Пример реализации автодополнения.";
_textBox.Dock = DockStyle.Fill;
_textBox.Multiline = true;
_textBox.KeyDown += textBox1_KeyDown;
_comboBox.DropDownWidth = 200;
_comboBox.DropDownHeight = 150;
_comboBox.DropDownStyle = ComboBoxStyle.DropDownList;
_comboBox.SelectionChangeCommitted += _comboBox_SelectionChangeCommitted;
_comboBox.DropDownClosed += _comboBox_DropDownClosed;
string[] words = @"Мама мыла раму Папу дядю вообще все это фигня".Split(' ');
Array.Sort(words);
_comboBox.Items.AddRange(words);
_comboBox.Visible = false;
Controls.AddRange(new Control[]{_textBox, _comboBox});
}
void ShowComboBox(Point location)
{
_comboBox.Size = new Size(0, 0);
_comboBox.Visible = true;
_comboBox.Focus();
_comboBox.Location = location;
_comboBox.DroppedDown = true;
}
static bool IsIdent(char ch) { return char.IsLetterOrDigit(ch) || ch == '_'; }
Point PickUpWord()
{
string text = _textBox.Text;
int start = _textBox.SelectionStart - 1;
for (; start >= 0 && IsIdent(text[start]); start--)
;
int end = ++start;
for (; end < text.Length && IsIdent(text[end]); end++)
;
return new Point(start, end);
}
private void textBox1_KeyDown(object sender, KeyEventArgs e)
{
if (e.Control && e.KeyCode == Keys.Space)
{
int chPos = _textBox.SelectionStart >= _textBox.Text.Length
? _textBox.SelectionStart - 1 : _textBox.SelectionStart;
Point pos = PointToClient(_textBox.PointToScreen(
_textBox.GetPositionFromCharIndex(chPos)));
ShowComboBox(pos);
Point txtLoc = PickUpWord();
string word = _textBox.Text.Substring(txtLoc.X, txtLoc.Y - txtLoc.X);
_textBox.SelectionStart = txtLoc.X;
int index = _comboBox.FindString(word);
if (index >= 0)
_comboBox.SelectedIndex = index;
e.SuppressKeyPress = true;
}
}
private void _comboBox_DropDownClosed(object sender, EventArgs e)
{
_comboBox.Visible = false;
}
private void _comboBox_SelectionChangeCommitted(object sender, EventArgs e)
{
Point txtLoc = PickUpWord();
_textBox.SelectionStart = txtLoc.X;
_textBox.SelectionLength = txtLoc.Y - txtLoc.X;
_textBox.SelectedText = (string)_comboBox.SelectedItem;
}
}
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
согласен, что не просто, но интересен тот факт, он и есть факт, что ошибка внешнего контекста обрывает парсинг внутрености, по крайней мере так часто бывает, что при исправлении в коде 1-й потом начинают вылазить уже другие.
Вообще-то, реализация даной штуковины должна быть — элегантный рекурсивный алгоритм и красиво заданная грамматика.
Ну там еще контексты, всякие правила...
Смысл даного проэкта(я так думаю) — это реализация его не в коде, а в диаграммах, проработка понятной и расширяемой архитектуры без единого кусочка жвачки
Есть смысл придумать еще одно колесо — подарок своему самолюбию
Здравствуйте, VladD2, Вы писали:
VD>Могу только еще раз повторить, что задача создания интерфейса для автодополнения не стоит и выеденного яйца, а задача создания универсального парсера жрущего удобную граматику слишком сложна и сама по себе может потешить любое самолюбие.
Думаю парсером не отделаться, как минимум нужна типизация. Скорее решение всех задачь фазы анализа при трансляции.
При реализации автодополнения во Флоре поступил очень просто: транслирую до нужной позиции, смотрю состояние стека времени трансляции, и по верхнему элементу делаю автодополнения.
Для естественных языков предлагаю в автодополнении ввести режимы ХОРЕЙ и ЯМБ
Здравствуйте, Lever, Вы писали:
L>Думаю парсером не отделаться, как минимум нужна типизация. Скорее решение всех задачь фазы анализа при трансляции.
Парсер — это общее название. Конечно для комплита нужно делать парсер с семантическим анализом.
L>При реализации автодополнения во Флоре поступил очень просто: транслирую до нужной позиции, смотрю состояние стека времени трансляции, и по верхнему элементу делаю автодополнения.
А если код не корректный? Ктому же не все языки можно транслироват частично. Например в C# обявления не обязаны быть перед исползованием. Так что нужно практически полностью скомпилровать проект, чтобы заработало автодополение.
L>Для естественных языков предлагаю в автодополнении ввести режимы ХОРЕЙ и ЯМБ
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>Парсер — это общее название. Конечно для комплита нужно делать парсер с семантическим анализом.
L>>При реализации автодополнения во Флоре поступил очень просто: транслирую до нужной позиции, смотрю состояние стека времени трансляции, и по верхнему элементу делаю автодополнения.
VD>А если код не корректный? Ктому же не все языки можно транслироват частично. Например в C# обявления не обязаны быть перед исползованием. Так что нужно практически полностью скомпилровать проект, чтобы заработало автодополение.
А еще есть хитрые синтаксические сахара и подсказки для компилятора — от define'ов в С/С++ до import в java до using в C# до compile(export_all), export([myfun/2, myfun/3, myfun2/0]), behavior(gen_server), import в Эрланге
Здравствуйте, VladD2, Вы писали:
VD>А если код не корректный?
Облом. VD>Ктому же не все языки можно транслироват частично. Например в C# обявления не обязаны быть перед исползованием.
Поэтому приветтствуется разбиение на части partial и есть связка CodeUnit <-> текст. VD>Так что нужно практически полностью скомпилровать проект, чтобы заработало автодополение.
А нужно ли оно тогда будет
В данной теме я с Вами полностью согласен. Меня просто удивили наивные попытки требования такой универсальности.
Здравствуйте, Lever, Вы писали:
L>Поэтому приветтствуется разбиение на части partial и есть связка CodeUnit <-> текст.
Не. Я к тому, что парсер для автодополнения должен быть круче чем просто парсер компилятора. Должна быть возможность его локального применения и он должен лучше переносить ошибки в коде. Насколько я знаю те же ДжетБрэйновцы парся Шарп сначала по скобкам обнаруживают функцию, а потом перепарсивают только ее. Это дает возможность быстро обновлять изменения и при этом забивать на многоие ошибки.
VD>>Так что нужно практически полностью скомпилровать проект, чтобы заработало автодополение. L>А нужно ли оно тогда будет
Как видишь, от ДжетБрэйновской ИДЕИ и РеШарпера многие писают кипятком. Так что точно нужно.
L>В данной теме я с Вами полностью согласен. Меня просто удивили наивные попытки требования такой универсальности.
Да, нет. Требования то очень хорошие. Вот только действительно слишком наивные. Люди даже не понимают где реальные сложности. Они думают, что сложно создать механизм комплита. А тем временем основаная сложность это парсеры и логика их точечного применения.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Универсальный механизм Intellisense (идея)
Здравствуйте, VladD2, Вы писали:
VD>Как видишь, от ДжетБрэйновской ИДЕИ и РеШарпера многие писают кипятком. Так что точно нужно.
Что за звери: ДжетБрэйновская ИДЕЯ и РеШарпер?
Если порусски РеШарпер это R#? L>>В данной теме я с Вами полностью согласен. Меня просто удивили наивные попытки требования такой универсальности. VD>Да, нет. Требования то очень хорошие. Вот только действительно слишком наивные.
Я упор делал на наивность.
Re[11]: Универсальный механизм Intellisense (идея)
Здравствуйте, Lever, Вы писали:
L>Здравствуйте, VladD2, Вы писали:
VD>>Как видишь, от ДжетБрэйновской ИДЕИ и РеШарпера многие писают кипятком. Так что точно нужно. L>Что за звери: ДжетБрэйновская ИДЕЯ и РеШарпер?
Здравствуйте, 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>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
