Итаак, для того, чтобы что-нибудь навычислять, надо сначала описать анализируемую грамматику. Тут есть два варианта:
1) описать её при помощи английской грамматики и собрать генератором парсеров с поддержкой Unicode, получится сгенерированный парсер который сможет читать русскую грамматику и создавать объектную модель для анализа по вышеприведённому алгоритму.
2) можно описать грамматику кодом (насоздавать объекты по одному для каждого правила, нетерминала и терминала). Для этого хорошо бы иметь язык с динамическим распределением памяти, но не обязательно. Можно создать массивы массивов на любом языке, например на КуМире, или сплошной массив с телами правил и массивы-индексы с началами/длинами.
Как представлять грамматику в тексте программы
Страница: 1
Сообщений 1 страница 10 из 10
Поделиться12017-10-24 16:56:37
Поделиться22017-10-24 17:14:54
Есть третий путь. Как то сделано в интерпретаторе Форта, так называемый шитый-код.
Поделиться32017-10-24 18:05:25
Павиа, ну ты как всегда со своими размышлениями...
Подозреваю, что чтобы кого-нибудь сподвигнуть это написать прийдётся оформить ТЗ чуть ли не по ГОСТ 19...
Итак:
допустим, что есть некая BNF-грамматика, которая записана в виде символов на листе бумаги при помощи гелевой ручки.
Нужно написать такой минимальный текст программы, чтобы предьявив его можно было сказать - вот, этот код описывает эту грамматику.
Как это сделать проще всего:
1) взять пример "здравствуй мир"
2) заменить фразу "здравствуй мир" на текст грамматики (программа будет выводить текст грамматики, а значит она грамматику в себе содержит).
3) подумать над рефакторингом, позволяющим выполнять операции с грамматикой (такие как "добавление правила", "удаление правила"), это должно привести к мысли что можно использовать более удобный набор структур данных, не единственную строку, а
например тройку-четвёрку массивов:
- строковый массив имён символов (терминалов и нетерминалов),
- массив с телами (правыми частями) правил
- массив индексов начал правил (длины можно вычислять каждый раз, а можно тоже хранить)
- как-нибудь учесть, что у одного символа может быть несколько правых частей-альтернатив (например завести массив количеств альтернатив в правилах, он будет состоять в основном из единичек)
4) такую структуру данных можно описать средствами языка, потом распечатать её и претендовать на то, что программа описывает грамматику.
Обрати внимание, что АПИ для работы с этой структурой данных пока не нужно, поэтому и форт тут как собаке пятая нога.
Где, кстати, почитать про русский синтаксис для форта и будет ли это работать под linux?
Ладно, допустим даже, что как-нибудь можно написать то же самое на форте, будет ли оно от этого понятнее (мне как школьнику)? Сомневаюсь...
Отредактировано Лис (2017-10-25 00:15:34)
Поделиться42017-10-24 19:21:49
Ладно, допустим даже, что как-нибудь можно написать то же самое на форте, будет ли оно от этого понятнее (мне как школьнику)? Сомневаюсь...
Устал повторять корень зла не в сложности программы, а в сложности теории описывающей все эти грамматики. Дело не в Форте.
2) можно описать грамматику кодом (насоздавать объекты по одному для каждого правила, нетерминала и терминала). Для этого хорошо бы иметь язык с динамическим распределением памяти, но не обязательно. Можно создать массивы массивов на любом языке, например на КуМире, или сплошной массив с телами правил и массивы-индексы с началами/длинами.
А можно придумать свой формат файлов и хранить грамматику (по-крайней мере большую ее часть) в отдельном файле и позволить языку иметь кучу синтаксисов 
А чтобы Лис не придирался взять и все иностранные Remark переименовать в русские слова
- строковый массив имён символов (терминалов и нетерминалов),
- массив с телами (правыми частями) правил
Первые частный случай второго. Незачем городить лишний огород.
массив индексов начал правил (длины можно вычислять каждый раз, а можно тоже хранить)
Где там в БНФ индексы начала правил? Чего то Вы переусложнили.
- как-нибудь учесть, что у одного символа может быть несколько правых частей-альтернатив (например завести массив количеств альтернатив в правилах, он будет состоять в основном из единичек)
Так, давай же, ну. Еще пару шажков до дерева осталось... Все эти терминалы, нетерминалы это частный случай правил, которые описываются рекурсивно. Разворачивая рекурсию получаем классическое дерево .
Пример:
IF <выражение>
|
THEN <Оператор>
|
ELSE <Оператор>
Здесь только нужно правила правильно помечать или упростить до
IF <выражение> THEN <Оператор>
|
ELSE <Оператор>
Валентина в синтаксической фазе упаковывает все конструкции (то есть все строки программы имеющие смысл) в структуры вида:
ID
Param1
Param2
Param3
Param4
То есть изначально избавляемся от кучи лишних правил (такое вот тупое ассемблерное представление). ID - это код семантики (что нужно делать), Param - это параметры (то есть как нужно делать). В дальнейшем в ходе выполнения программы параметры могут уточняться (а могут нет, так как модель динамическая). Для компиляторов параметры естественно можно уточнить гораздо раньше.
Отредактировано utkin (2017-10-24 20:08:34)
Поделиться52017-10-24 23:38:57
utkin написал(а):
Первые частный случай второго.
нет.
Допустим есть грамматика
Код:
файл → строка файл строка → СИМВОЛ строка
здесь три символа: "СИМВОЛ", "файл", "строка".
Грамматика не очень удачная (неоднозначная, т.к. не описаны концы строк), но для примера это неважно.
в массиве имён мы будем хранить эти названия символов:
Код:
лит таб названия_символов [1:3]
названия_символов[1]="СИМВОЛ"
названия_символов[2]="файл"
названия_символов[3]="строка"
цел первый_нетерминал=2
цел таб правые_части[1:4]
правые_части[1]=3
правые_части[2]=2
правые_части[3]=1
правые_части[4]=3
цел таб начала_правил[1:2]={1,3}
цел таб правил_на_нетерминал[1:2]={1,1} utkin написал(а):
Лис написал(а):массив индексов начал правил (длины можно вычислять каждый раз, а можно тоже хранить)
Где там в БНФ индексы начала правил? Чего то Вы переусложнили.
Я сделал так, потому что в Кумире нет вложенных массивов или "разноразмерных массивов" (jagged array)
Делать прямоугольную матрицу с пустыми ячейками было бы излишним расходом памяти.
utkin написал(а):
Так, давай же, ну. Еще пару шажков до дерева осталось... Все эти терминалы, нетерминалы это частный случай правил, которые описываются рекурсивно. Разворачивая рекурсию получаем классическое дерево
Вы говорите правильно, но то что Вы это говорите показывает, что Вы не понимаете, что я хочу сделать.
Отредактировано Лис (2017-10-25 00:31:27)
Поделиться62017-10-25 01:17:33
Лис написал(а):
1: for every nonterminal C do
2: Compute all nonterminals A satisfying C →rm∗ A...
3: Compute all nonterminals B satisfying C →rm∗ B
4: end for
русскими словами
1: цикл для каждого нетерминала К
2: вычислить все нетерминалы Л удовлетворяющие условию К →пв∗ Л...
3: вычислить все нетерминалы М удовлетворяющие условию К →пв∗ М
4: конец цикла
для того, чтобы реализовать вычисление этих четырёх строчек, нужно описать куда будем складывать результаты вычислений.
Можно сделать две квадратные таблицы с логическими ячейками (если не заботится об экономии памяти).
Нетерминал либо не выводится из другого нетерминала, либо в принципе выводится. И это наш первый квадратный массив с логическими значениями.
Точно так же, нетерминал либо не выводится из другого нетерминала являясь последним в правиле, либо выводится являясь последним в правиле. И это второй квадратный массив с логическими значениями.
После этого каждый читатель легко сможет написать программы на КуМир-е, заполняющие эти две таблицы по исходным данным описанным выше по топику. Размеры массивов известны заранее, так что проблем никаких.
Продвинутые читатели могут подумать - не являются ли массивы треугольными массивами (после топологической сортировки) и нельзя ли свести их в один квадратный массив, храня одну часть сверху диагонали, другую снизу. А так же повысит или понизит это общую производительность процесса преобразования грамматики с учётом промахов мимо кешей процессоров.
Так же стоит статистически обосновать - при каких размерах грамматики использовать (сильно разреженные) матрицы, а при каких переходить на списки.
Многопоточная реализация на GPU оставляется в качестве упражнения
Отредактировано Лис (2017-10-25 02:53:47)
Поделиться72017-10-25 06:53:50
названия_символов[1]="СИМВОЛ"
названия_символов[2]="файл"
названия_символов[3]="строка"
Зачем их хранить? Это нужно для работы программы или для Вашего представления алгоритма?
Я сделал так, потому что в Кумире нет вложенных массивов или "разноразмерных массивов" (jagged array)
Делать прямоугольную матрицу с пустыми ячейками было бы излишним расходом памяти.
Использовать устаревшие элементы порочный путь. Кумир не отвечает современным требованиям. Соответственно только усложняется реализация, отсюда куча проблем.
Вы говорите правильно, но то что Вы это говорите показывает, что Вы не понимаете, что я хочу сделать.
Потому что есть более простые решения . Но Вам надо через задницу .
для того, чтобы реализовать вычисление этих четырёх строчек, нужно описать куда будем складывать результаты вычислений.
Если это организовано рекурсивно в этом нет необходимости. Зачем его складывать куда-то? Вы берете строку программы и методично применяете к ней те правила, которым она должна удовлетворять. Если все ОК, значит это то, о чем мы думаем (утиная типизация). Если строка не удовлетворяет набору правил (например условного оператора), значит перед нами что-то другое. И нужно брать набор правил для описания иного оператора (допустим проверять цикл перед нами или что-то еще). И дерево здесь прямо вот просится, потому что все компьютерные языки они примитивные. По сути подавляющее большинство операторов (за исключением например выражений) определяются первым символом (ну то есть первой лексемой).
Ну например, нет смысл полного разбора условного выражения. Достаточно сначала проверить, что перед нами IF. Если не IF, то нет смысла искать THEN. Это простая функция, созданная набором логических выражений И (AND).
Как осуществляется проверка операнд1 AND операнд2? Если первый операнд ложен (не IF, а что-то другое), то нет смысла смотреть дальше, результат операции известен.
И вот перед нами простая функция IF AND <условие> AND THEN AND <действие> или IF --> <условие> --> THEN ---> <действие>. Вот и все правила.
По такому принципу делаются все остальные операторы (так как еще раз - компьютерные языки имеют примитивные правила образования синтаксиса). Единственно, Вы должны однозначно определять, что перед Вами действительно оператор, а не выражение (там уже другие правила используются - но тоже классическое дерево, где промежуточные узлы определяются операциями и их приоритетами)
Многопоточная реализация на GPU оставляется в качестве упражнения
Зачем стрелять из пушки по воробьям? Сколько правил в современном языке? Тысяча? Десть тысяч? Обсчет меньше секунды на среднем компьютере.
Отредактировано utkin (2017-10-25 08:12:55)
Поделиться82017-10-25 14:15:01
utkin написал(а):
Зачем стрелять из пушки по воробьям? Сколько правил в современном языке? Тысяча? Десть тысяч? Обсчет меньше секунды на среднем компьютере.
100-1000. Так в том и беда Лис вместо того что-бы упрощать усложнил всё до безобразия. Вместо регулярной граматике он использует контексно свободную.
1) 97-99% правил это регулярные граматики
2) пользователи такое будут осваивать с большим трудом.
3) разработчики компиляторов будут её осваивать с нименьшим трудом. Лис её сам освоить несумел.
4) Скорость O(1) против O(N^3).
Если парсер для регулярной обрабатывает 10 000 строк в секунду. То для КС это будет 1 строчка в 100 секунд. И да GPU тут непоможет, так как всё упрётся в память.
4) про таблицы их трудно поддерживать тем более у вас в алгоритме ошибка - для КС они бесконечные.
Поделиться92017-10-25 15:01:15
Вот там второй пост с рисунком... Там рисунок относится к разбору выражения, а не к построению грамматике вообще. Разбор выражений это маленькая подзадача и как его разбирать слева направо или по арабски справа налево вообще пофиг. Разбор выражений давно расжеванная тема - либо высокоуровнево через деревья (там уже всяческие оптимизации проводить можно) либо узкоспецифично для компиляторов в обратную польскую нотацию (для того чтобы загонять вычисления в стек), что по сути тоже дерево только в иной форме.
Поделиться102017-10-25 15:10:13
Павиа написал(а):
таблицы ... у вас в алгоритме ошибка - для КС они бесконечные.
Павиа, второе китайское предупреждение!
Страница: 1