Адаптированный алгоритм Эрли - описание - Философия программирования

Здравствуйте, VladD2, Вы писали:

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

Логин/пароль прислал. Давай доступ буду фиксить и рефакторить.

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, VladD2, Вы писали:

VD>>Да, это я конечно лохонулся. И все из-за тог, что пример слишком простой.

WH>

WH>    grammar.AddTerminal("n", Tokens.digitLiteral);
WH>    grammar.AddTerminal("+", Tokens.Plus);
WH>    grammar.AddTerminal("-", Tokens.Minus);
WH>    grammar.AddTerminal("EOF", Tokens.EOF);
    
WH>    grammar.AddRule("S", "n", "+", "S", "+", "n");
WH>    grammar.AddRule("S", "S", "-", "n");
WH>    grammar.AddRule("S", "n");
WH>

WH>Данная грамматика на такой строке "1 + 1 — 1 + 1" не работает.
WH>ИМХО собака порылась в функции Predictor она у тебя както совсем странно реализована.

Нам конечно обещали что парсер крут, но для других парсеро это бред какой-то.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, WolfHound, Вы писали:

WH>Данная грамматика на такой строке "1 + 1 — 1 + 1" не работает.
WH>ИМХО собака порылась в функции Predictor она у тебя както совсем странно реализована.

Вот соотвествующая грамматика:

        grammar.AddTerminal("n", Tokens.digitLiteral);
        grammar.AddTerminal("+", Tokens.Plus);
        grammar.AddTerminal("-", Tokens.Minus);
        grammar.AddTerminal("EOF", Tokens.EOF);

        grammar.AddRule("S", "S", "+", "n");
        grammar.AddRule("S", "n");
        grammar.AddRule("S", "S", "-", "n");

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, WolfHound, Вы писали:

WH>У тебя там косяк на косяке

Да, ладно.

WH> Логин/пароль прислал. Давай доступ буду фиксить и рефакторить.

Добавил. Пробуй.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, VladD2, Вы писали:

AVK>>Или указатель.
VD>На фиг там никакие указатели не уперлись. Еще раз повтояю, ты задолбашся этими указателями ссылаться на разные таблицы. Тут int самое то.

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

Здравствуйте, mefrill, Вы писали:

M>Ну на самом деле и через указатели тоже можно. Есть еще такая идея: завести все помеченные правила посредством перечислений. Т.е. не только правила иметь, а еще и для каждого правила — множество помеченных. Тогда, вместо пары (номер правила, позиция точки) можно просто одно число — номер помеченного правила держать. Правда здесь с увеличением позиции точки гемморой небольшой получается. В общем, экономим память таким образом. Для нескольких миллионов ситуаций — уже экономия. Хотя, лично я, по большому счету здесь выгоды не вижу особой, а только усложнение программной логики.

Память не проблема. Проблема — скорость. Нужно думать как избавиться от переборов. Они самое большое зло.

Ладно. Это все фигня. Давай добъем алгоритм до работоспособного состояния, а там я уже скоростью сам займусь. А вось что и выйдет.

Ты лучше объясни по доходчивее свою идею построения деревьев вывода. И за одно расскажи как создавать понятные сообщения об ошибках. А то пока что мы можетм только сказать выводится строка из грамматики или нет.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, VladD2, Вы писали:

VD>Я долго думал над тем как лучше хранить символы и пришел к мнению, что лучше их хранить в едином массиве со сквозной нумерацией. Это позволяет упростить в некоторых местах алгоритм.
VD>Правила действительно лучше хранить в отдельном массиве. Хоря не факт, что имеет смыслссылаться на правила с помощью индекса. Возможно лучше правда использовать указатели. Для С++ это скорее всего так. А для дотнета с его райт-барьером не факт. В общем, нужно сначала заполучить полноценный парсер, а потом погонять его под профайлером.

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

VD>А зачем state было делать отдельным классом? По-моему это просто вектор.
VD>И почему Ситуация названа item? Бессмыслица полная. Я назвал ее Situation.

В оригинале у Эрли это называется item. Ситуация — это удачный перевод Тихомирова.

VD>origin_
VD>Я назвал это поле CreationState. Я правильно понял суть этого поля?

Ага, верно, но в оригинале origin называется. Я, кстати, хорошего перевода для этого так и не придумал.

Здравствуйте, mefrill, Вы писали:

M>В оригинале у Эрли это называется item. Ситуация — это удачный перевод Тихомирова.

Ну, раз удачный и ты его используешь при объяснении, то и в коде надо так называть.

VD>>origin_
VD>>Я назвал это поле CreationState. Я правильно понял суть этого поля?

M>Ага, верно, но в оригинале origin называется. Я, кстати, хорошего перевода для этого так и не придумал.

Всегда говорил, что у математиков фигово с фонтазией когда речь заходит о именах. Ну, да хорошо, что не X, Y, Z.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, VladD2, Вы писали:

VD>Вот соотвествующая грамматика:
VD>

VD>        grammar.AddTerminal("n", Tokens.digitLiteral);
VD>        grammar.AddTerminal("+", Tokens.Plus);
VD>        grammar.AddTerminal("-", Tokens.Minus);
VD>        grammar.AddTerminal("EOF", Tokens.EOF);

VD>        grammar.AddRule("S", "S", "+", "n");
VD>        grammar.AddRule("S", "n");
VD>        grammar.AddRule("S", "S", "-", "n");
VD>

Э нет я хочу чтобы было с переди n-сложений и с зади n-сложений, а по середине опционально вычитание.
А не даботает это по тому что у тебя Completer и Predictor реализованы не правильно. Да и в Parse ты накосячил...
Я это дело у себя пофиксил

Работает

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Здравствуйте, WolfHound, Вы писали:

VD>>Для особо требовательных можно просто константу отплеваывать. А вообще, на фоне тормозов самого алгоритма, думаю, эти вызовы будут незаметны. Меня вообще пока что волнует вопрс будет ли этот алгоритм пригоден для реального использования?
WH>Скорость это деое техники. Я вот чего не понял так это как сообщения об ошибках получать?

Вот здеськое-какие мои мысли по этому поводу.

Еще есть проблема восстановления после ошибок. Там тоже есть свои решения.

Здравствуйте, VladD2, Вы писали:

VD>Добавил. Пробуй.
Ща отрефакторю и залью.
Кстати у тебя там в некоторых местах в качестве отступов пробелы, а в других табы. Как должно быть?

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Здравствуйте, VladD2, Вы писали:

VD>Если учесть, что код слишком большой для стольк простой задачи я бы предпочел бы изучать алгоритм на безе шарповского варианат приведенного мной здесь:
VD>Re: Адаптированный алгоритм Эрли — описание

Нет проблем. Главное — это изучать.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, mefrill, Вы писали:

VD>Похоже несоотвествие:
VD>

Проходим по списку S0:
VD>в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки, поэтому пропускаем эту ситуацию. Следующая ситуация — это [S --> * n, 0]. Вот у нее символ после точки равен n. Поэтому, добавляем эту ситуацию в список S1, сдвинув точку на символ правее, имеем ситуацию [S --> n *, 0] в списке S1.

VD>и:
VD>

S1
VD>[S --> * n, 0]
VD>[S --> S * + n, 0]

VD>Где ошибка?

Конечно, ошибка в [S --> * n, 0], надо чистать так: [S --> n *, 0], т.е. точка на символ правее.

Здравствуйте, WolfHound, Вы писали:

WH>Э нет я хочу чтобы было с переди n-сложений и с зади n-сложений, а по середине опционально вычитание.

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

S : n + n X n + n
X : -
X : +

если под необязательным ты понимашь замену на +.

WH>А не даботает это по тому что у тебя Completer и Predictor реализованы не правильно. Да и в Parse ты накосячил...
WH>Я это дело у себя пофиксил

Работает

Надо еще поглядеть, что ты там наисправлял.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, VladD2, Вы писали:

VD>А что будет если строка не выводится из грамматики?

Тогда сканер не добавит ни одной ситуации в следующее состояние.

VD>Явно прослеживается, что после несовпадения строки парсер начинает работать в холостую. Видимо наличие пустых состояний свидетельсвует о том, что строка не совпала с грамматикой. Так ли это? И если так, то можно ли останавливать парсинг отталкиваясь от того, что новое состояние пусто?

Ага, именно.

Здравствуйте, mefrill, Вы писали:

M>Конечно, ошибка в [S --> * n, 0], надо чистать так: [S --> n *, 0], т.е. точка на символ правее.

У меня так и получилось.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, WolfHound, Вы писали:

WH>Кстати у тебя там в некоторых местах в качестве отступов пробелы, а в других табы. Как должно быть?

Нет. Я просто на ноуте в воескресенье работал, и забыл в начале включить табы. Везде должны быть табы.

... << RSDN@Home 1.2.0 alpha rev. 631>>

Здравствуйте, VladD2, Вы писали:

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

Присоединил здесь статью именно об этом.

Здравствуйте, VladD2, Вы писали:

VD>Нет. Я просто на ноуте в воескресенье работал, и забыл в начале включить табы. Везде должны быть табы.
Ок.

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Здравствуйте, VladD2, Вы писали:

VD>Ты имеешь дело с рекурсивной грамматикой. Правило что я привел описывает любые сочетания сложений и вычитаний. Если тебе нужно именно фиксированное количество сложений и в середине не обязательное вычитание, то это нужно делать как-то так:
1)Ты непровильно преобразовал грамматику.
2)Ты занимаешься подгонкой грамматики под убогие парсеры. Этот и так все сожрет.

VD>Надо еще поглядеть, что ты там наисправлял.
Вобщем залил. Смотри.

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

	От:	WolfHound
	Дата:	23.01.06 18:55
	Оценка:

От:	VladD2	www.nemerle.org
Дата:	23.01.06 18:58
Оценка:

От:	VladD2	www.nemerle.org
Дата:	23.01.06 19:01
Оценка:

От:	VladD2	www.nemerle.org
Дата:	23.01.06 19:04
Оценка:

	От:	mefrill
	Дата:	23.01.06 19:16
	Оценка: