[PEG] Добавил в сниппеты еще один пример. - Nemerle

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

ВВ>А для ключевых слов тоже ToLower() делать?

В грамматике?

ВВ>Потому что я могу написать типа:

ВВ>

ВВ>Sub = "SUB";
ВВ>

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

ВВ>Вообще идея неплохая, не считая того, что придется держать две копии строки.

Мне кажется в наше время это не проблема. Вторая строка нужна на маленький промежуток времени, так что будет реюзаться одна и та же область LOH-а в GC.

ВВ>Учитывая, что ведь парсер-то, наверное, юникодный?

Да. Точнее он дотнетный и не делающий никаких предположении о типе контента (нет никаких таблиц или еще чего-то что могло бы зависит от размера символов).

ВВ>Т.е. я могу без всякого шаманства написать:

ВВ>

ВВ>Sub = "Процедура";
ВВ>

Можешь конечно. Но ты же хочешь не чувствительный к регистру парсинг? Тогда можно смириться, что в случае не чувствительного к регистру парсера надо писать все слова в нижнем регистре.

ВВ>В противном случае регистронезависимое сравнение весьма тривиально.
ВВ>Кстати, Кокор тоже шаманит каким-то таким образом — т.е. видимо ToLower/ToUpper делает для всей строки, ибо сама логика распознавания никак не меняется при включении этой опции.

Возможно. Думаю, что тут все очень просто. Стоимость регистро-независимого сравнения весьма высока по сравнению с примитивными операциями типа x == 'c'. Потом химии много, а толку мало.

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

ВВ>>>Ignore = "\r\n\t"
ВВ>>>это если через атрибут указывать.
VD>>Это в принципе невозможно.

ВВ>А почему?

Потому что нельзя будет описать очень многих вариантов использования. Скажем как описать идентификатор?
Сейчас это выглядит так:

    letter                    = (['A'..'Z', 'a' .. 'z', 'А' .. 'Я', 'а' .. 'я'] / '_');
    digit                     = ['0'..'9'];
    identifierValue           = '@'? letter (letter / digit)*;
    identifier   : string     = identifierValue spaces;

Если подставлять spaces везде, то у нас получится:

    identifierValue           = '@'? spaces letter spaces (letter spaces / digit spaces)* spaces;

ВВ>Под ignore имеется в виду, что они учитываются как раздилители между токенами, но при этом предполагается любое их количество в любых местах и явно указывать их уже не нужно.

Ага. Только нет самого понятия "токен". Мы описываем парсер строки! Лексера нет как ложку в Матрице.

ВВ>Говоря другим словами, эта настройка не влияет на выделение токенов, она просто означает, что везде по умолчанию стоит spaces. ИМХО вполне возможно должно быть.

Только при условии, что можно указать, что где-то не надо ставить эти самые spaces. Это нужно или задавать для каждого отдельного правила, или нужно вводить nospaces.

А вообще, на практике добавление spaces не взывает никаких проблем. Просто это не привычно для тех кто использовал лексерные парсеры (классно звучит).

VD>>Тут поступило другое предложение. Можно идти от обратного и вместо spaces ввести специализированное правило (предопределенное) "nospaces". Тогда по умолчанию можно будет вставлять spaces между любыми правилами кроме тех случаев когда между ними уже присутствует nospaces.

ВВ>Не до конца ясно, как это должно работать. Т.е. spaces все равно надо описывать явно? Потому что его определение не всегда же одинаково.

Нет. Алгоритм следующий. Все подправила (кроме содержимого литералов) дополняем spaces-ами. Если по логике пробелы не нужны, то мы пишем так:

identifierValue           = '@'? nopace letter nopace (letter nopace / digit nopace)* nopace;

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

VD>>Сейчас есть более приоритетные задачи:
VD>>1. Обработка ошибок.

ВВ>Мне в целом нравится подход того же Кокора. Т.е. к примеру, если я такую продукцию:

Он тут пролетает, так как является LL(1)-автоматом. Ему не сложно самостоятельно определить, что есть ошибка во входной строке. У ПЕГ-а же ошибок в коде просто не бывает. У ПЕГ-а бывают откаты. После того как будет откачено стартовое правило, можно будет сказать, что во входной строке что-то не так, так как она не парсится данным парсером. Но где ошибка понять будет невозможно.

Один из способов понять где же ошибка — это запоминать максимальную позицию в которой был произведен откат и правило которое было откачено. Но это а) не эффективно, б) не всегда дает хороший результат (например, так нельзя указать на то, что некоторая открывающая скобка незакрыта).

ВВ>Т.е. не надо, как ты предлагаешь, делать:

ВВ>Expr = "keyword" ( Foo | Bar | Error ).

ВВ>Грамматика распухнет конкретно от таких вещей.

LL(1)-грамматики в сотни раз проще чем PEG-овские. И вся эта мощь определяется операторами приоритетного выбора которые предоставляют ограниченный откат. Мы просто не можем вставлять Error в конец всех операторах приоритетного выбора. Это не позволит откатиться правилу которое вызвало данное.

VD>>2. То же игнорирование регистра.
VD>>3. Оптимизации.

ВВ>А тут мы, боюсь, опять приходим к CIL Switch.

Ну, это отдельный вопрос.

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

VD>>>2. То же игнорирование регистра.
VD>>>3. Оптимизации.

ВВ>>А тут мы, боюсь, опять приходим к CIL Switch.

VD>Ну, это отдельный вопрос.

Я это все перечислял чтобы объяснить, что "есть у нас и другие дела" (с). И это только с ПЕГ-ом. А еще есть компилятор, интеграция и т.п.

Лучше бы присоединился и помог бы.

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

VD>Нет. Алгоритм следующий. Все подправила (кроме содержимого литералов) дополняем spaces-ами. Если по логике пробелы не нужны, то мы пишем так:
VD>

VD>identifierValue           = '@'? nopace letter nopace (letter nopace / digit nopace)* nopace;
VD>

nopace это таки кривь.
Ибо в подавляющем большенстве случаев у нас для всего правила либо нужно игнорировать пробелы либо нет.
Так что лучше raw syntax.

... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>

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

ВВ>Ну можно и так. ИМХО важнее как раз возможность полного игнора регистров. А вот фишку с избирательным игнором я бы вообще делал только по факту фич-реквеста. Многие генераторы это не умеют и ничего. Да и сам я не припомню случаев, когда реально требовался бы избирательный игнор. Для таких сценариев уже не грех и свой хелпер для ключевых слов написать.

Как раз в случае с отсутствием лексера, частичный игнор очень важен. Допустим, для языка, у которого регистр кейвордов не важен, но строковые литералы зависят от регистра (а большинство языков "нечуствительных к регистру" именно такие).

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

C>Как раз в случае с отсутствием лексера, частичный игнор очень важен. Допустим, для языка, у которого регистр кейвордов не важен, но строковые литералы зависят от регистра (а большинство языков "нечуствительных к регистру" именно такие).

Честно говоря, не понимаю, как это связано со строками. Парсеру вообще нет дело до того, что содержится внутри "".

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

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

H>>x = y.z = t ? a : 0x23 * 7 + 1;
H>>

H>>На выходе он в презентабельном виде отображает AST:
H>>

H>>x = y.z = (t ? a : (0x23 * (7 + 1)));;
H>>

VD>Кстати — это ошибка. У умножения приоритет должен быть выше. Так что скобки не верно выведены или распознавание не верное.

Я знаю. Мне просто было лень писать правила. Сейчас добавил операторы в соответствии с вот этой древней докой.

Теперь компиляция проекта длится несколько долгих-долгих минут.

Там полиномиальная сложность что ли с какой-то дикой степенью?

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

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

VD>А почему JSParser.GUI на Шарпе? За одно WinForms постестировал бы.

Я так и не научил SharpDevelop рисовать формы на Nemerle.

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

H>Теперь компиляция проекта длится несколько долгих-долгих минут.

Там полиномиальная сложность что ли с какой-то дикой степенью?

Исправил еще ошибки в 8985.
Компиляция проекта занимает порядка 10 минут.

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

H>Я знаю. Мне просто было лень писать правила. Сейчас добавил операторы в соответствии с вот этой древней докой.

H>Теперь компиляция проекта длится несколько долгих-долгих минут.

Там полиномиальная сложность что ли с какой-то дикой степенью?

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

Скорее всего ты добавил нечто другое, но тоже не очень хорошее (экспонентное).

Грамматика для бинарных операторов должна быть примерно такая:

mayBeInfixExpression    : Expression = multiplicativeExpr (('+' / '-') multiplicativeExpr)*;
multiplicativeExpr      : Expression = expression (('*' / '/' / '%') expression)*

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

H>Я так и не научил SharpDevelop рисовать формы на Nemerle.

Дык воспользовался бы студией. А результат уже можно было бы компилировать и SharpDevelop-ом.

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

C>Как раз в случае с отсутствием лексера, частичный игнор очень важен. Допустим, для языка, у которого регистр кейвордов не важен, но строковые литералы зависят от регистра (а большинство языков "нечуствительных к регистру" именно такие).

Я же сказал "Ну, а значения для токенов добывать из оригинальной строки.". То есть парсер работает с копией строки в приведенной к нижнему или верхнему регистру, а функция GetText() работает с оригиналом и добывает исходные значения.

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

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

H>>Я знаю. Мне просто было лень писать правила. Сейчас добавил операторы в соответствии с вот этой древней докой.

H>>Теперь компиляция проекта длится несколько долгих-долгих минут.

Там полиномиальная сложность что ли с какой-то дикой степенью?

VD>Если бы ты добавил правила из этой доки, то парсинг вообще никогда не завершился бы (если конечно переполнения стека не случилось бы). Там описана лево-рекурсивная грамматика. Он с помощью нисходящего спуска вообще не парсится.

Я в курсе. Меня интересовал набор и приоритет операций.

VD>Скорее всего ты добавил нечто другое, но тоже не очень хорошее (экспонентное).

VD>Грамматика для бинарных операторов должна быть примерно такая:
VD>

VD>mayBeInfixExpression    : Expression = multiplicativeExpr (('+' / '-') multiplicativeExpr)*;
VD>multiplicativeExpr      : Expression = expression (('*' / '/' / '%') expression)*
VD>

Так оно и есть:

multiplicativeExpression    : Expression = prefixExpression (('*' / '/' / '%') spaces           prefixExpression)*;
additiveExpression          : Expression = multiplicativeExpression (('+' / '-' ) spaces        multiplicativeExpression)*;
shiftExpression             : Expression = additiveExpression ((">>>" / ">>" / "<<") spaces     additiveExpression)*;
relationalExpression        : Expression = shiftExpression (("<=" / ">=" / '<' / '>') spaces    shiftExpression)*;
equalityExpression          : Expression = relationalExpression (("===" / "==" / "!=") spaces   relationalExpression)*;
andExpression               : Expression = equalityExpression ('&' spaces                       equalityExpression)*;
exclusiveOrExpression       : Expression = andExpression ('^' spaces                            andExpression)*;
inclusiveOrExpression       : Expression = exclusiveOrExpression ('|' spaces                    exclusiveOrExpression)*;
conditionalAndExpression    : Expression = inclusiveOrExpression ("&&" spaces                   inclusiveOrExpression)*;
conditionalOrExpression     : Expression = conditionalAndExpression ("||" spaces                conditionalAndExpression)*;
conditionalExpression       : Expression = conditionalOrExpression (QUEST expression COLON conditionalExpression)?; //right assoc

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

H>Исправил еще ошибки в 8985.
H>Компиляция проекта занимает порядка 10 минут.

Погоди. "Компиляция проекта" в смысле немерлового проекта содержащего грамматику? Или речь о работе самого парсера получаемого по этой грамматике?

Если первое, то нужно искать баг. Такого точно не должно быть.

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

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

H>>Исправил еще ошибки в 8985.
H>>Компиляция проекта занимает порядка 10 минут.

VD>Погоди. "Компиляция проекта" в смысле немерлового проекта содержащего грамматику? Или речь о работе самого парсера получаемого по этой грамматике?

VD>Если первое, то нужно искать баг. Такого точно не должно быть.

Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).

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

H>Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).

А не смотрел профайлером что занимает основное время?

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

Кстати еще смущает размер кода. Теперь сборка с парсером стремится к 400КБ.

Это нормально?

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

H>Кстати еще смущает размер кода. Теперь сборка с парсером стремится к 400КБ.

Это нормально?

К сожалению — да. Без специальных оптимизаций там генерирутся слишком много млекого кода. Плюс Вольфхаунд наладил там инлайнинг который приводит к дублированию массы мелких правил. С одной стороны это повышает скорость (теоретически), с другой приводит к разбуханию кода. Тут тоже надо еще покумекать как лучше поступать.

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

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

H>>Да. Компиляция парсера этой грамматики в которую я добавил весь этот красивый спектр операторов теперь занимает чуть больше 10 минут (дома машинка пошустрее и считает за 7 минут).

VD>А не смотрел профайлером что занимает основное время?

Судя по тому, что я увидел в профайлере, все время времени компилятор проводит в OptimizeRule, а имеенно в CanInline, которая похоже имеет жуткую полиномиальную сложность.

От:	VladD2	www.nemerle.org
Дата:	08.07.10 18:31
Оценка:

От:	VladD2	www.nemerle.org
Дата:	08.07.10 18:43
Оценка:

От:	VladD2	www.nemerle.org
Дата:	08.07.10 18:53
Оценка:

От:	VladD2	www.nemerle.org
Дата:	08.07.10 18:55
Оценка:

	От:	WolfHound
	Дата:	08.07.10 21:19
	Оценка:

	От:	Воронков Василий
	Дата:	08.07.10 22:21
	Оценка:

От:	hardcase	http://nemerle.org
Дата:	09.07.10 08:14
Оценка: