Вход | Регистрация
 

РВ-грамматиками кто занимался?

РВ-грамматиками кто занимался?
Я
   Garykom
 
21.08.16 - 10:58
Это такое нечто вроде РБНФ но другое https://ru.wikipedia.org/wiki/Грамматика,_разбирающая_выражение.

Показалось весьма интересным благо для JS нашелся удобный http://pegjs.org/ и даже с онлайн тестером http://pegjs.org/online.
   Garykom
 
1 - 21.08.16 - 11:00
(0)+ Вот если в http://pegjs.org/online слева грамматику заменить на то что ваяю:
// РВ грамматика 1С


Модуль
  = expr:СтрокаМодуля+ {
      return expr;
  }

СтрокаМодуля
  = Пробелы expr: (Подвыражение / Операция) Пробелы ";" Пробелы {
      return expr + ";";
  } 

ОперацияСложенияВычитания
  = head:ОперацияУноженияДеления tail:(Пробелы ("+" / "-") Пробелы ОперацияУноженияДеления)* {
      var result = head, i;
      for (i = 0; i < tail.length; i++) {
        if (tail[i][1] === "+") {
          result = "" + result + "+" + tail[i][3]; 
        }
        if (tail[i][1] === "-") {
          result = "" + result + "-" + tail[i][3]; 
        }
      }
      return result;
    }

ОперацияУноженияДеления
  = head:Подвыражение tail:(Пробелы ("*" / "/") Пробелы Подвыражение)* {
      var result = head, i;
      for (i = 0; i < tail.length; i++) {
        if (tail[i][1] === "*") { 
          result = "" + result + "/" + tail[i][3]; 
        }
        if (tail[i][1] === "/") {
          result = "" + result + "/" + tail[i][3]; 
        }
      }
      return result;
    }

ФункцияМин
  = Пробелы "Мин(" Пробелы head:Подвыражение tail:(Пробелы (",") Пробелы Подвыражение Пробелы)* ")" { 
    var result = head, i;
    for (i = 0; i < tail.length; i++) {
      result = result + "," + tail[i][3];
    }
    return "Math.min(" + result+")"; 
  }

ФункцияМакс
  = Пробелы "Макс(" Пробелы head:Подвыражение tail:(Пробелы (",") Пробелы Подвыражение Пробелы)* ")" { 
    var result = head, i;
    for (i = 0; i < tail.length; i++) {
      result = result + "," + tail[i][3];
    }
    return "Math.max(" + result+")"; 
  }

ФункцияСообщить
  = Пробелы "Сообщить(" Пробелы expr:Подвыражение Пробелы ")" { 
    return "alert(" + expr+")"; 
  }

Операция
  = ОперацияСложенияВычитания / Подвыражение {
  
  }

ПроверкаУсловия
  = Пробелы expr1:(ОперацияСложенияВычитания / Подвыражение) Пробелы "=" Пробелы expr2:(ОперацияСложенияВычитания / Подвыражение) Пробелы {
    return "" + expr1+"==="+expr2; 
  } / ОперацияСложенияВычитания / Подвыражение

УсловиеЕсли
  = Пробелы "Если" Пробелы expr1:ПроверкаУсловия Пробелы 
  "Тогда" Пробелы expr2:(СтрокаМодуля)* Пробелы 
  expr3:("Иначе" Пробелы СтрокаМодуля Пробелы)*
  "КонецЕсли"  {
    var result = "if(" + expr1+"){";
    var i;
    for (i = 0; i < expr2.length; i++) {
      result = result + expr2[i];
    }
    if (expr3.length===1){
      result = result + "}else{"+ expr3[0][2];
    }
    result = result + "}";
    return result; 
  }

Подвыражение "подвыражение"
  = "(" Пробелы expr:ОперацияСложенияВычитания Пробелы ")" { return expr; }
  / Число / ФункцияМин / ФункцияМакс / ФункцияСообщить / УсловиеЕсли

Число "число"
  = [0-9]+ { 
    //return parseInt(text(), 10);

    return text(); 
  }

Пробелы "whitespace"
  = [ \t\n\r]*


А справа вставить пример "кода 1С":
Если 1 Тогда 
  2;
  22;
Иначе
  3;
КонецЕсли;
Макс( Мин(1, 2), 3);
Сообщить( Мин(1, 2) );

То будет некий результат ))
   quest
 
2 - 22.08.16 - 07:00
баловался когда-то. Но нормальную грамматику которая бы не тормозила - собрать трудно.
   Garykom
 
3 - 22.08.16 - 07:03
(2) Да есть такой момент, что это разбор всегда одинаковый в РВ-грамматике, а вот сами "правила" могут быть кучей вариантов.
   quest
 
4 - 22.08.16 - 07:07
для эксперимента - напиши грамматику которая бы разобрала модуль на 10 000 строк, сделай замер. Потом тоже самое сделай на бизоне/яке и замерь.
Результат будет не в пользу peg. А если все это еще на 1С написать - вообще задница. Прозводительность в разы отличается. Если тебе так хочется что-то поразбирать - возьми sableСС или Coco/R
   Garykom
 
5 - 22.08.16 - 07:11
(4) Чем то напоминает сравнение 1С и C++, типа C++ быстрее же зачем вам 1С ))

В данном случае скорость не важна совершенно и PEG (как и прочие парсеры РВ-грамматик) намного быстрее разбирает чем парсеры КС-грамматик классических на РБНФ/БНФ.

Да сам js не сильно шустрый по сравнению с C++ и реализация PEG.js не факт что самая оптимальная, но в данном случае это не важно совершенно.
   quest
 
6 - 22.08.16 - 07:13
(5) Тут чисто алгоритмический затык.  За счет чего быстрее разбирает? Какой механизм лежит внутри и чем за это приходиться платить?
   Garykom
 
7 - 22.08.16 - 07:16
(6) Два минуса у РВ:
1. Жрут много памяти за счет сохранения всех шагов.
2. "РВ-грамматики не могут содержать леворекурсивных правил, которые содержат вызов самих себя без продвижения по строке."

Но глобальный плюсы:
1. Шустрые.
2. Разбор всегда одинаковый в отличие от КС-грамматик, где могут быть разные варианты разбора.
   quest
 
8 - 22.08.16 - 09:17
Что значит разбор всегда одинаковый? Текст меняется, а разбор нет? Или что ты имеешь в виду?
   Garykom
 
9 - 22.08.16 - 09:38
(8) С РБНФ и другими КС-грамматиками разные деревья разбора возможно построить которые типа все правильные, с РВ-грамматиками для одного текста всегда одно дерево выйдет.
   quest
 
10 - 22.08.16 - 10:02
в общем есть желание - бейся об эту стену. Для меня это пройденный этап. peg - для прототипирования хорошо, для промышленной разработки, где тебе надо по сотни килобайт разбирать - жесть просто.
   Garykom
 
11 - 22.08.16 - 10:21
(10) Ну PEG моложе BNF как минимум в 2 раза, пока еще мало откатано.

Насчет "надо по сотни килобайт разбирать" не поняло совершенно, в теории PEG шустрее но жрет больше ресурсов (в основном памяти) и не требует предварительную обработку/анализ.
   quest
 
12 - 22.08.16 - 10:31
Если у тебя текст для разбора маленький и грамматика простая - то проблем нет. Ты как-то просто относишься к выделению памяти. peg хорошо в хаскеле - но там и gc покруче чем в js.

Как следствие -
Если текст для разбора от полумегабайта, грамматика сложнее чем калькулятор - возникнет много разочарования от использования.
А уж если активно используются правила с ! и & - то много-много попоболи гарантировано.


Но для самообучения - peg стоит покрутить. когда-то даже для 1с реализовывал что-то похожее.
   Garykom
 
13 - 22.08.16 - 10:35
(12) Гм у меня транслятор, а не интерпретатор.
Суть что парсер юзается один раз на нормальной машине и выдает готовый js код.

А этот js код уже выполняется обычным образом в браузере/nodejs без левых парсеров.

Список тем форума
 
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.