Да запутано все. Нетерминал "любой символ" определен, а ни где не используется. Должен быть только один нетерминал используемый только в левой части правил — нетерминал самого языка. Типа: C#:=> ....
Программа – это мысли спрессованные в код
Re[2]: контекстно-свободная самоописывающаяся грамматика
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>Здравствуйте, Qulac, Вы писали:
Q>>Да запутано все. Нетерминал "любой символ" определен, а ни где не используется.
AS>в правиле "Т"
Q>>Должен быть только один нетерминал используемый только в левой части правил
AS>стартовый нетерминал — "файл". А насчёт того, что он должен быть один — это вызывающе неверное утверждение. Поясни, пожалуйста, что ты хотел сказать.
Нет, он должен быть частью другого правила, более высокого порядка. Типа X:= "любой символ" | тут что-то еще.
Программа – это мысли спрессованные в код
Re[4]: контекстно-свободная самоописывающаяся грамматика
AS>(*Ю*) повторение = [ количество повторений , гм ] , "{" , гм , выражение , гм , "}" ;
AS>(*Я*) количество повторений = ( не менее , гм , "*" , гм , не более ) | десятичное число ;
Нет красивого способа задавать "не менее N повторений": N{expr}{expr}. Можно было использовать полуинтервал: N*{expr}
Нет пояснения, что без чисел — {expr} — означает от нуля до бесконечности.
(*4*) исключение = выражение , гм , "-" , гм , выражение ;
Плохая семантика, negative lookahead в общем случае. На ровном месте получаем из контекстно-свободной грамматики контекстно-зависимую. Хотя подразумевалась чисто регулярная фишка — классы символов.
Пример:
привет = "п" , "р" , "и" , "в" , "е" , "т" ;
мир = "м" , "и" , "р" ;
любое слово = буква { буква } ;
любые слова = любое слово , { обм , любое слово } ;
привет но не мир = ( привет , обм , любые слова ) - ( любые слова , обм , мир ) ;
Перекуём баги на фичи!
Re[2]: контекстно-свободная самоописывающаяся грамматика
некий фрагмент = произвольный текст - многосимвольный маркер окончания фрагмента ;
я бы даже сказал:
строковая константа = начало строковой константы, тело строковой константы , конец строковой константы ;
начало строковой константы = двойная кавычка ;
тело строковой константы = [ { символ в строке } ] - конец строковой константы ;
(* тело строковой константы не должно содержать "конец строковой константы" *)
символ в строке = значимый символ в строке | { бэкслеш , новая строка } ;
значимый символ в строке = . - бэкслеш ;
(* бекслеши, которые в строке, должны вырезаться, а не превращаться в пробел *)
конец строковой константы = двойная кавычка ;
комментарий = начало комментария, тело комментария , конец комментария ;
начало комментария = [ тп ] , "#" ;
тело комментария = [ { символ комментария } ] - новая строка ;
символ комментария = . ;
(* бекслеши в комментариях не обрабатываются *)
конец комментария = ; (* пустые правила элиминируются при анализе грамматики *)
(* далее определения пробелов определены таким образом,
чтобы перенос строки (бекслеш перед концом строки) превращался в пробел *)
ябм = { тп | новая строка | бэкслеш , новая строка } ;
бэкслеш = "\" ;
К>Хотя подразумевалась чисто регулярная фишка — классы символов.
в этой грамматике действительно окончание комментария вида "*)" может быть записано классами символов, да.
А вообще, чем длинее маркер, тем тяжелее писать формулу.
К>Пример: К>
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>у меня большое желание сделать от 1 до бесконечности, чтобы можно было писать AS>[{ . }] вместо 1… { . } AS>UPD: переделал, теперь от 1 до бесконечности
Вот это ещё осталось
(*А*) файл = [ маркер ] , гм , правило , { гм , правило } , гм ;
К>>Плохая семантика, negative lookahead в общем случае. AS>Чем она плохая? регэкспы же: AS>http://www.regular-expressions.info/lookaround.html
К>> На ровном месте получаем из контекстно-свободной грамматики контекстно-зависимую.
Плохая только тем, что парсер более тяжеловесный.
Кстати, а без lookahead'а не регулярная ли вообще грамматика получается? В данном конкретном случае, разумеется.
Так-то, понятное дело, у тебя просто альтернативная запись старой доброй БНФ, которая, в общем случае, описывает контекстно-свободные грамматики.
AS>Это специально. я хочу примерно как тут — http://stackoverflow.com/questions/406230/regular-expression-to-match-a-line-that-doesnt-contain-a-word
Ну, если ты знаешь, куда применить лукохеды, то конечно.
Но тогда уж комментарий
комментарий = "(*", [{ . - "*)" }], "*)" ;
Кстати, интересный момент, про исключение. Его можно двояко трактовать:
— сопоставить от текущей позиции левую (положительную) часть и сопоставить её с правой (отрицательной) — в данном случае, очевидно, исключение не произойдёт, т.к. один символ (.) не сопоставится с двумя ("*)")
— сопоставить от текущей позиции правую (отрицательную) часть, и если не сопоставилось, — сопоставить от текущей позиции левую (положительную)
И ещё. Не хватает политики жадности-ленивости. Тот же комментарий на ленивом сопоставлении:
комментарий = "(*", [{ . }~], "*)" ;
расширение текстореза = "?", [{ знак }~], "?"
Не понял, что такое расширение текстореза, в твоей грамматике оно не используется, но раз "?" задействован, то для ленивости можно припахать суффикс "~" вместо классического "?".
А делать суффикс или префикс, тут я в задумчивости. Это надо смотреть, что удобнее для разбора и интерпретации.
Ну и если отрицательный лукохед есть, то почему бы и остальные не припахать? Сгорел сарай, гори и хата!
К>>Пример: К>>
Ничего не делать. Просто знать о том, что лукохеды могут очень жёстко просадить производительность.
Сделать квадратичную — легко. Сделать кубическую — чуть сложнее (двойное отрицание). Экспоненту или факториал — тут помощник нужен (надо подумать, возможно ли вообще).
AS>Ещё есть засада в том, что буква с ударением — это не один символ, а двусимвольная строка из основного символа и модификатора.
Вот поэтому движки регекспов особым образом поддерживают юникод.
Тем более, что там бывают и мультибайтные кодировки, и композитные символы, набранные из основного символа и пачки модификаторов.
Перекуём баги на фичи!
Re[4]: контекстно-свободная самоописывающаяся грамматика
там же.
К> лукохеды могут очень жёстко просадить производительность. Сделать квадратичную — легко. Сделать кубическую — чуть сложнее (двойное отрицание).
нет. при ненаивной реализации можно обеспечить линейную. И ненадо меня убеждать, что нельзя.
Re[4]: контекстно-свободная самоописывающаяся грамматика
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>>у меня большое желание сделать от 1 до бесконечности, чтобы можно было писать AS>>[{ . }] вместо 1… { . } AS>>UPD: переделал, теперь от 1 до бесконечности
Перечитал исходный стандарт. Понял, что моя семантика операции "-" отличается от той, которая в стандарте.
Делать [{}] было не обязательно, потому что уже есть эквивалент
{.}-,
(т.е. от нуля до бесконечности, но без нуля)
поэтому я лучше минус сделаю как в стандарте (точное несовпадение правой части), а для своей операции буду вместо минуса использовать ~(не должно содержать правой части).
Про ленивость я не осознаю на данный момент.
Re[4]: контекстно-свободная самоописывающаяся грамматика
Образ я бы тоже хотел обсудить. Только не юникод, а директивы Include.
Получается, что с одной стороны, сама директива описывается КС-грамматикой (в частном случае регэкспом),
а с другой стороны, она вытягивает целое AST-дерево из другого файла.
Когда я об этом думаю, меню клинит (неясно, как это оформить кодом C#).
Мне тут подсказывают: "паттерн, паттерн используй". Компоновщик, итератор. Но клинит всё равно.
Re[5]: контекстно-свободная самоописывающаяся грамматика
Здравствуйте, Arsen.Shnurkov, Вы писали:
К>> Не понял, что такое расширение текстореза AS>там
Оригинально перевёл special sequence!
К>> Чем "оператор пробел" не нравится?
AS>там же.
То есть, выбирая между слитно_записываемыми_идентификаторами и , идентификаторами с пробелами внутри , и , явной , разбивкой , на , лексемы , — был сделан выбор в пользу второго. Ну хозяин барин.
К>> лукохеды могут очень жёстко просадить производительность. Сделать квадратичную — легко. Сделать кубическую — чуть сложнее (двойное отрицание). AS>нет. при ненаивной реализации можно обеспечить линейную. И ненадо меня убеждать, что нельзя.
Есть что почитать на эту тему? Или на пальцах объяснить?
Перекуём баги на фичи!
Re[5]: контекстно-свободная самоописывающаяся грамматика
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>Про ленивость я не осознаю на данный момент.
Ну, можно просто задекларировать, что все операции повторения ленивые.
С жадностью придётся реализовывать ленивость вручную. По сути, ленивость — это такой неявный негативный лукохед: "если можешь сматчить следующий за квантификатором кусок, то всё, стоп!"
А если нет произвольного негативного лукохеда, а только строгое неравенство (классы символов — это частный случай), то ещё и его придётся руками расписать:
Здравствуйте, Arsen.Shnurkov, Вы писали:
К>> особым образом поддерживают
AS>Образ я бы тоже хотел обсудить. Только не юникод, а директивы Include. AS>Получается, что с одной стороны, сама директива описывается КС-грамматикой (в частном случае регэкспом), AS>а с другой стороны, она вытягивает целое AST-дерево из другого файла. AS>Когда я об этом думаю, меню клинит (неясно, как это оформить кодом C#).
AS>Мне тут подсказывают: "паттерн, паттерн используй". Компоновщик, итератор. Но клинит всё равно.
Какие директивы Include? Это ты про что?
Перекуём баги на фичи!
Re[4]: контекстно-свободная самоописывающаяся грамматика
Как, по-твоему, описать любую другую директиву, отличную от директивы Include ?
Если расписывать по буквам вручную, как ты выше предлагаешь,
то во что превратится этот процесс, если станет две директивы типа "include"? а если семь?
К> То есть, выбирая между слитно_записываемыми_идентификаторами и , идентификаторами с пробелами внутри , и , явной , разбивкой , на , лексемы , — был сделан выбор в пользу второго. Ну хозяин барин.
Вариант синтаксиса без запятых — это ABNF из rfc 5234:
3.1. Concatenation: Rule1 Rule2
Если EBNF, то по стандарту только с запятыми.
название EBNF является более распиаренным, поэтому я выбрал вариант с запятыми.
рассмотрим класс Apache2 с двумя статическими методами
class Apache2 {
public static string LoadConfig (string filename)
{
// парсим файл и ищем маски
// вызываем LoadConfigsByMask()
// вставляем строки вместо интервалов с директивами
// возвращаем итоговую строку
}
public static string LoadConfigsByMask(string filemask)
{
// ищем файлы по маске
// каждый файл читаем функцией LoadConfig()
// склеиваем строки
// результат возвращаем
}
}
Тут плохо то, что:
1) потом после получения сконкатенированного контента парсить прийдётся ещё раз (по другой грамматике);
2) теряется информация про исходное положение символов в разных файлах (нужно не строки возвращать, а что-то более сложное).
Хотелось бы как-то учитывать результаты первого парсинга во время второго, чтобы повысить эффективность.
Допустим, что изменим прототипы методов, чтобы они возвращали узлы деревьев:
public static Pair<FileInfo,Node> LoadConfig (string filename)
public static List<Pair<FileInfo,Node>> LoadConfigsByMask (string filename)
Но тогда не ясно, что делать с узлами, описывающими директивы Include. Заменять их непосредственно нежелательно (потеряется информация о текстовом представлении директивы Include), значит список надо записывать в атрибут (аттрибутированная грамматика) узла Include.
но тогда, получается, что нужен какой-то дополнительный итератор, который учитывал бы, что могут существовать директивы Include.
Либо можно поступить наоборот — заменить узлы, а информацию об Include переместить в атрибут...
Или построить второе дерево из узлов типа MetaNode, каждый из которых будет ссылаться на свой Node, и работать уже с тем новым деревом.
Отдельная идея — не очень здо́рово хранить всё целиком в памяти, если можно обрабатывать по частям (DOM vs SAX). То есть, это неправильно, возвращать все узлы. Вместо этого надо возвращать итератор.
Здравствуйте, Arsen.Shnurkov, Вы писали:
AS>Как, по-твоему, описать любую другую директиву, отличную от директивы Include ?
AS>Если расписывать по буквам вручную, как ты выше предлагаешь, AS>то во что превратится этот процесс, если станет две директивы типа "include'? а если семь?
Тут проще ввести фактор приоритетности, — жадность/ленивость и отсечки.
Не знаю, как это на БНФ записать, — на регекспах это атомарные группы (?>blablabla)
Ну как-то так будет
directive = some_include | some_exclude | everything_else;
some_include = good_include | bad_include;
good_include = include_keyword, space, valid_path;
bad_include = include_keyword, ERROR_BEGINS_HERE, bullshit_till_end_of_sentence, ERROR_ENDS_HERE;
(* или так *)
some_include = include_keyword,
( space, valid_path, {space}, [ unexpected ]
| unexpected
),
LOOKAHEAD_end_of_sentence; (* сопоставляется, но не съедает, признак конца *)
unexpected = ERROR_BEGINS_HERE, (* сопоставляется с пустой строкой, служит признаком для парсера *)
bullshit_till_the_end_of_sentence,
ERROR_ENDS_HERE; (* то же самое *)
bullshit_till_the_end_of_sentence = {.}, LOOKAHEAD_end_of_sentence;
(* или в более сложных случаях, может проглатывать парные скобки, если признак конца фразы может встретиться внутри фразы, под скобками) *)
Заодно научишь парсер восстанавливаться после ошибок.
Перекуём баги на фичи!
Re[6]: контекстно-свободная самоописывающаяся грамматика
К>Ну, можно просто задекларировать, что все операции повторения ленивые. К>С жадностью придётся реализовывать ленивость вручную. По сути, ленивость — это такой неявный негативный лукохед: "если можешь сматчить следующий за квантификатором кусок, то всё, стоп!"
Ленивость, negative/positive lookahead, и то что мне нужно — это три разные вещи.
вот это то что мне надо (только мне надо без расписывания):
К> если нет произвольного негативного лукохеда, а только строгое неравенство (классы символов — это частный случай), то ещё и его придётся руками расписать: К>
Т.е. прийдётся определить дополнительный синтаксис специально под мою операцию, а потом думать, как её разворачивать "как руками".
Это проблема, потому что неразрешима задача определения того, является ли КС-грамматика регулярной.
Перекуём баги на фичи!
