Здравствуйте, night beast, Вы писали:
NB>Интересуют последние достижения. NB>И еще попутно вопрос: NB>понадобилось динамически добавлять/удалять правила грамматики. NB>как лучше это реализовать?
Это смотри в сторону грамматик ВанВейгартена. Тот который занимался Алголом-68.
Называется Двухуровневые грамматики ВанВейнгартена.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
NB>>Интересуют последние достижения. NB>>И еще попутно вопрос: NB>>понадобилось динамически добавлять/удалять правила грамматики. NB>>как лучше это реализовать? LVV>Это смотри в сторону грамматик ВанВейгартена. Тот который занимался Алголом-68. LVV>Называется Двухуровневые грамматики ВанВейнгартена.
извини за наглость, а нет ссылки на почитать?
а то что-то гугл ничего конкретного не дает
NB>И еще попутно вопрос: NB>понадобилось динамически добавлять/удалять правила грамматики. NB>как лучше это реализовать?
Чтобы ответить на этот вопрос, надо сначала знать, как правила хранятся. Вообще, некоторые алгоритмы требуют предварительной обработки грамматики для своей работы, другие не требуют. Вот тот же bison по грамматике строит автомат специального вида, поэтому пробразует грамматику в такой автомат. Грамматик подает программе на вход, из нее генерится автомат, который представляет собой просто набор функций на Си. Можно сделать к этому делу дополнительный модуль хранения правил грамматики и при ее модификации вызывать bison для генерации нового автомата. Конечно, тогда надо будет и сишный код заново компилировать. Другие алгоритмы не требуют предварительной обработки, для них правила даются как есть. Это, например, алгоритм Эрли.
В любом случае, модуль хранения грамматики ты должен будешь написать сам, а алгоритм синтаксического анализа использовать для этого модуля отдельно.
Здравствуйте, mefrill, Вы писали:
NB>>И еще попутно вопрос: NB>>понадобилось динамически добавлять/удалять правила грамматики. NB>>как лучше это реализовать?
M>Чтобы ответить на этот вопрос, надо сначала знать, как правила хранятся. Вообще, некоторые алгоритмы требуют предварительной обработки грамматики для своей работы, другие не требуют. Вот тот же bison по грамматике строит автомат специального вида, поэтому пробразует грамматику в такой автомат. Грамматик подает программе на вход, из нее генерится автомат, который представляет собой просто набор функций на Си. Можно сделать к этому делу дополнительный модуль хранения правил грамматики и при ее модификации вызывать bison для генерации нового автомата. Конечно, тогда надо будет и сишный код заново компилировать. Другие алгоритмы не требуют предварительной обработки, для них правила даются как есть. Это, например, алгоритм Эрли.
алгоритм Эрли — сложность О(n^3) (это очень много)
bison при построении строит таблицу. то есть все правила должны быть известны.
Здравствуйте, night beast, Вы писали:
NB>понадобилось динамически добавлять/удалять правила грамматики. NB>как лучше это реализовать?
Смотри PEG. В отличии от BNF этот формализм описывает как разбирать, а не генерировать текст.
Расширяемая динамически реализация Katahdin. Он конечно тормоз но это проблемы реализации.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, night beast, Вы писали:
NB>Что можно почитать по теории синтаксического анализа?
NB>Интересуют последние достижения.
NB>И еще попутно вопрос: NB>понадобилось динамически добавлять/удалять правила грамматики. NB>как лучше это реализовать?
Классическими работами по синтаксическому анализу являются "Компиляторы. Принципы, технологии, инструменты .Ахо, Сети,Ульман" и "Теория синтаксического анализа, перевода и компиляции. Ахо, Ульман Т.1 и Т.2"
Занимался этими проблемами. Есть интересные наработки. Получается просто. Но для этой простоты нужно сделать сложные вещи. А именно, новый язык представления синтаксиса. Чуть сложнее БНФ. Если сделать транслятор задуманой системы, то решаются практически все проблемы. И эффективности и динамического изменения грамматики.. Фактически с этого языка получаем непосредственно транслятор
нового языка. Правила в кратце следующие.
Введение. Правила описания грамматик.
Система Lada имеет собственные средства описания грамматики, поэтому в тексте использована именно эта нотация, краткое описание которой ниже.
1. Понятие определяется оператором Determination, за которым следует имя определяемого понятия и далее определяющая последовательность понятий в скобках. При необходимости определить сразу несколько понятий они заключаются в фигурные скобки (либо в круглые скобки через запятую) после оператора Determination. Раздел 2.1. Объекты, заключенные в скобки будем называть группой.
2. Имя определяемого понятия может содержать не больше сорока букв, либо любые знаки, заключенные в именные скобки «"». Более подробно смотри правила именования (Раздел 1).
3. Последовательность знаков непосредственно участвующая в разборе выделяется текстовыми кавычками ««» и «»».
4. Последовательность определений в квадратных скобках (группа), и знаком «|» после открывающей скобки обозначает выбор одного варианта из этой последовательности.
5. Надстрочное значение, после закрывающей скобки определяет максимальное количество допустимых повторений понятий объединенных группой, которую закрывает эта скобка.
6. Подстрочное значение после группы понятий указывает минимальное количество вхождений данного понятия в определение. Значение 0 допускает отсутствие группы понятий в разборе.
7. Знак «¬» перед понятием (или группой понятий) означает, что в разборе допустимо все что угодно кроме этого понятия (или группы понятий).
Полное описание языка могу прислать. Тут его кто-то выставил старую версию без моего ведома.А потом мне сообщил. Так я попал на этот сайт)
Теоретические проработки можем обсудить.
Здравствуйте, night beast, Вы писали:
NB>алгоритм Эрли — сложность О(n^3) (это очень много)
Такая сложность только для неоднозначных грамматик. Для LR-грамматик сложность линейная, только константа там побольше, чем в LR-автоматах.
NB>bison при построении строит таблицу, то есть все правила должны быть известны.
Ну так в чем проблема, я же писал: при изменении грамматики заново генеришь автомат. Только бизон это еще и компилирует, что совсем необязательно.
NB>хочется в интерпретаторе определять грамматики на подобии tex макросов: NB>\def \expr \expr "+" \term | \term NB>\def \term \term "*" \factor | \factor NB>\def \factor \@id | "(" \expr ")"
NB>и использовать: \expr a + b; NB>вот такая вот задача
Здесь сложность в том, что такие грамматики могут не укладываться в LR-автоматы и даже не быть однозначными. Надо применять алгоритм Томиты или Эрли. Вопрос только, как семантику к ним определять будешь?
Здравствуйте, mefrill, Вы писали:
NB>>bison при построении строит таблицу, то есть все правила должны быть известны.
M>Ну так в чем проблема, я же писал: при изменении грамматики заново генеришь автомат. Только бизон это еще и компилирует, что совсем необязательно.
NB>>хочется в интерпретаторе определять грамматики на подобии tex макросов: NB>>\def \expr \expr "+" \term | \term NB>>\def \term \term "*" \factor | \factor NB>>\def \factor \@id | "(" \expr ")"
NB>>и использовать: \expr a + b; NB>>вот такая вот задача
M>Здесь сложность в том, что такие грамматики могут не укладываться в LR-автоматы и даже не быть однозначными. Надо применять алгоритм Томиты или Эрли.
думаю, класса SLR-грамматик должно хватить
M>Вопрос только, как семантику к ним определять будешь?
Здравствуйте, batu, Вы писали:
NB>>Что можно почитать по теории синтаксического анализа?
NB>>Интересуют последние достижения.
NB>>И еще попутно вопрос: NB>>понадобилось динамически добавлять/удалять правила грамматики. NB>>как лучше это реализовать? B>Классическими работами по синтаксическому анализу являются "Компиляторы. Принципы, технологии, инструменты .Ахо, Сети,Ульман" и "Теория синтаксического анализа, перевода и компиляции. Ахо, Ульман Т.1 и Т.2"
угу. читал.
только книги старые. вот и интересно, что нового в области...
B>Занимался этими проблемами. Есть интересные наработки. Получается просто. Но для этой простоты нужно сделать сложные вещи. А именно, новый язык представления синтаксиса. Чуть сложнее БНФ. Если сделать транслятор задуманой системы, то решаются практически все проблемы. И эффективности и динамического изменения грамматики.. Фактически с этого языка получаем непосредственно транслятор B>нового языка. Правила в кратце следующие.
B>Введение. Правила описания грамматик.
B>Система Lada имеет собственные средства описания грамматики, поэтому в тексте использована именно эта нотация, краткое описание которой ниже.
B> Полное описание языка могу прислать. Тут его кто-то выставил старую версию без моего ведома.А потом мне сообщил. Так я попал на этот сайт)
просматривал по диагонали.
без обид, не зацепило что-то.
зачем вводить свои определения, когда уже есть устоявшаяся терминология?
B>Теоретические проработки можем обсудить.
N NB>просматривал по диагонали. NB>без обид, не зацепило что-то. NB>зачем вводить свои определения, когда уже есть устоявшаяся терминология?
NB>какой класс грамматик описывается?
Не от хорошей жизни пришлось переделывать. В классическом варианте строится дерево из описания граммантики, и идет анализ этого дерева. У меня можно в описание синтаксиса добавлять функциональную часть. И операторы тоже. Потому класс грамматик шире. И алгоритм разбора не всегда возвращается в случае неудачи в начало ветки, а может перебрать варианты в средине и продолжить. Получается как в фунциональном программировании. Только возможности еще шире.
Можно, например, разобрать грамматику, порождающую язык.. Сори, не знаю как тут степень писать.. напишу как смогу. na^nb^nc^n. И есть еще нюансы.В классическом определении грамматик нет четкого разделения где рекурсия, а где цикл. Все определяется как рекурсия. Разница в эффективности реализации разбора очевидна. Еще один момент, нетерминальные символы приходится вводить по мере необходимости самой грамматики, а не в терминах логики создаваемого языка. У меня нет необходимости создавать промежуточные нетерминальные символы. Вкратце где-то так..Я б прикрепил файл с примерчиком. Но здесь недавно. И не знаю как это сделать.
Здравствуйте, batu, Вы писали:
NB>>просматривал по диагонали. NB>>без обид, не зацепило что-то. NB>>зачем вводить свои определения, когда уже есть устоявшаяся терминология?
NB>>какой класс грамматик описывается? B>Не от хорошей жизни пришлось переделывать. В классическом варианте строится дерево из описания граммантики, и идет анализ этого дерева. У меня можно в описание синтаксиса добавлять функциональную часть. И операторы тоже. Потому класс грамматик шире. И алгоритм разбора не всегда возвращается в случае неудачи в начало ветки, а может перебрать варианты в средине и продолжить. Получается как в фунциональном программировании. Только возможности еще шире. B>Можно, например, разобрать грамматику, порождающую язык.. Сори, не знаю как тут степень писать.. напишу как смогу. na^nb^nc^n. И есть еще нюансы.
а оно точно надо? вроде существующие грамматики нормально с описанием языков справляются..
B>В классическом определении грамматик нет четкого разделения где рекурсия, а где цикл. Все определяется как рекурсия. Разница в эффективности реализации разбора очевидна.
LR анализаторы работают по таблице без рекурсивных вызовов.
B>Еще один момент, нетерминальные символы приходится вводить по мере необходимости самой грамматики, а не в терминах логики создаваемого языка. У меня нет необходимости создавать промежуточные нетерминальные символы.
на самом деле это не критично.
какая сложность разбора твоих определений (линейная/квадратичная)?
B>Вкратце где-то так..Я б прикрепил файл с примерчиком. Но здесь недавно. И не знаю как это сделать.
зайди в свой профиль. там есть вкладка Файл. можно загрузить файл на сайт. получившуюся ссылку можно вставить в сообщение через тег [url]
Здравствуйте, batu, Вы писали:
B>Кстати, понятия "нетерминальные символы" у меня нет. Так как в них нет необходимости. Грамматика описывается в терминах создаваемого языка.
ну, как минимум цифры и буквы являются терминалами.
в КС грамматиках правила тоже можно описать без них. они нужны чтобы упростить разбор.
Из приведенного примера и правил совершенно непонятно, можно ли справа в группах определителей задавать имена понятий или нет. Если нет, то это просто определений некоего подмножества класса регулярных языков (учитывая, что итерации там вроде нет). Если можно, то это контекстно-свободный язык, но тоже с ограничениями.
Имена понятий и есть нетерминалы в терминологии Хомского.
Здравствуйте, mefrill, Вы писали:
M>Здравствуйте, batu, Вы писали:
M>Из приведенного примера и правил совершенно непонятно, можно ли справа в группах определителей задавать имена понятий или нет. Если нет, то это просто определений некоего подмножества класса регулярных языков (учитывая, что итерации там вроде нет). Если можно, то это контекстно-свободный язык, но тоже с ограничениями.
M>Имена понятий и есть нетерминалы в терминологии Хомского.
С определением нетерминалов все понятно. А вот насчет можно ли справа... Ничего не понял.. Какие имена, где справа? Можно еще раз?
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, batu, Вы писали:
B>>Кстати, понятия "нетерминальные символы" у меня нет. Так как в них нет необходимости. Грамматика описывается в терминах создаваемого языка.
NB>ну, как минимум цифры и буквы являются терминалами. NB>в КС грамматиках правила тоже можно описать без них. они нужны чтобы упростить разбор.
Речь идет о нетреминалах. Т.е. о понятиях которые определяються только с целью форулирования грамматики. Т.е. некие промежуточные понятия которые вводяться с одной целью описания самой грамматики.
Вот, например, понятие группа в языке Lada. Подсточное значение выделил тегом i, а надстрочное Bold. Извинюсь, не знаю как здесь отредактировать.
Determination Группа (Determination: Понятие)
{
Switch Скобка
{
Case Круглая «(»
Case Фигурная «{»
Case Квадратная «[»}
Else {Result=False Exit Determination: Группа}
}
ExecuteOnSwitch Скобка
{
Круглая { Понятие {«,» Понятие}0255 «)»}
Фигурная {{Понятие}255 «}»}
Квадратная {«|»{Значение}0}0 {{Понятие}255 «]»}
}
[| "Подстрочное значение", "Надстрочное значение"]02 Формула 16.
}
В обычном описании пришлось бы определить как минимум три нетерминальных символа "Группа с круглыми скобками" "Квадратными", и "фигурными". Да еще и среди них пришлось бы что-то переопределять. А понятие группа, не просто "Не терминальный симовол" а понятие самого определяемого языка.
Ну, и понятно, что если выражение необходимо повторить, то оно определяется в группе с надстрочным значением количества повторений, Т.е. организует цикл. В классическом определении повторение необходимо было бы определить его как рекурсию. Ну, и выполняемый оператор Switch позволяет между ним и ExecuteOnSwitch вставить общую часть, конечно, если она понадобится. И вообще, это не описание грамматики будет, а непосредственно программа создающая транслятор с этого языка. Надо только добавить еще так называемую "реализацию". Но, это другая тема. Подскажите как здесь ставить надстрочные и подстрочные значения.
Здравствуйте, night beast, Вы писали:
NB>Здравствуйте, batu, Вы писали:
NB>>>просматривал по диагонали. NB>>>без обид, не зацепило что-то. NB>>>зачем вводить свои определения, когда уже есть устоявшаяся терминология?
NB>>>какой класс грамматик описывается? B>>Не от хорошей жизни пришлось переделывать. В классическом варианте строится дерево из описания граммантики, и идет анализ этого дерева. У меня можно в описание синтаксиса добавлять функциональную часть. И операторы тоже. Потому класс грамматик шире. И алгоритм разбора не всегда возвращается в случае неудачи в начало ветки, а может перебрать варианты в средине и продолжить. Получается как в фунциональном программировании. Только возможности еще шире. B>>Можно, например, разобрать грамматику, порождающую язык.. Сори, не знаю как тут степень писать.. напишу как смогу. na^nb^nc^n. И есть еще нюансы.
NB>а оно точно надо? вроде существующие грамматики нормально с описанием языков справляются..
B>>В классическом определении грамматик нет четкого разделения где рекурсия, а где цикл. Все определяется как рекурсия. Разница в эффективности реализации разбора очевидна.
NB>LR анализаторы работают по таблице без рекурсивных вызовов.
B>>Еще один момент, нетерминальные символы приходится вводить по мере необходимости самой грамматики, а не в терминах логики создаваемого языка. У меня нет необходимости создавать промежуточные нетерминальные символы.
NB>на самом деле это не критично. NB>какая сложность разбора твоих определений (линейная/квадратичная)?
Со всем согласен. На вопрос о сложности, сложность разбора зависит от сложности грамматики. Если ее природа рекурсивна, то никуда от рекурсии не денешься, со всеми вытекающими следствиями по сложности. (замечание. Некоторые рекурсии можно развернуть в цикл). Потому сочинитель языка должен иметь ввиду будущую сложность разбора. Ну, а дело языка для записи грамматик, сделать наглядной эту сложность, ну и дать инструмент для выхода из положения.
