Чтобы стать миллиардером, нужна прежде всего удача, значительная доза знаний, огромная работоспособность, но самое главное – вы должны иметь менталитет миллиардера. Менталитет миллиардера – это такое состояние ума, при котором вы сосредотачиваете все свои знания, все свои умения, все свои навыки на достижении поставленной цели.  Пол Гетти

I, krvss

  1. граматика мови
  2. Основні поняття graph-talk
  3. Моделювання процесу інтерпретації

Хочу розповісти про те, як зробити інтерпретатор за допомогою бібліотеки Graph-talk. В якості прикладу візьмемо чудова мова Brainfuck .

граматика мови

Всього в мові є 8 команд:

  • «>» - перехід до наступної комірки пам'яті;
  • «<» - перехід до попередньої комірки пам'яті;
  • «+» - збільшити значення в поточному осередку на 1;
  • «-» - зменшити значення в поточній комірці на 1;
  • «.» - вивести значення поточної комірки;
  • «,» - ввести значення ззовні в поточну комірку
  • «[» - початок циклу, виконати вміст всередині циклу, якщо в поточній осередку не 0;
  • «]» - кінець циклу, повернутися на початок з урахуванням вкладеності.

Власне, це все. Спочатку є 30 000 осередків пам'яті. «Hello, World!» На цьому мілейшем мовою виглядає так:

++++++++++ [> +++++++> ++++++++++> +++> + <<<< -]> ++
.> +. +++++++ .. +++.> ++. << +++++++++++++++.>. +++.
--.---.> +.>.

Основні поняття graph-talk

Graph-talk спочатку проектувалася як бібліотека для операцій розбиття на лексеми, парсинга і інтерпретації текстів, написаних на формальних мовах.

Формальні мови та процеси обробки в ній подаються у вигляді графів, які, в свою чергу, складаються з вершин (понять) і дуг (зв'язків або відносин між ними).

Є 4 типи понять:

  1. Просте поняття - лист дерева з деяким назвою (клас Notion);
  2. Активне поняття - просте поняття, яке викликає деяку функцію при його обробці (ActionNotion);
  3. Складений поняття - містить в собі кілька інших понять в зазначеному порядку (ComplexNotion);
  4. Вибіркове поняття - аналог оператора «select», складене поняття, яке містить в собі одне з декількох понять (SelectiveNotion).

Поняття пов'язані між собою відносинами 4-х типів:

  1. Проста зв'язок - з'єднує разом два поняття, одне з яких називається Subject, а інше - Object (клас Relation);
  2. Спрямована зв'язок - дозволяє переходити від одного поняття до іншого, якщо виконується задана умова (NextRelation);
  3. Активна зв'язок - спрямована зв'язок, яка викликає функцію при її обробці (ActionRelation);
  4. Розпізнає зв'язок - спрямована зв'язок, яка «поглинає» оброблений текст, якщо він збігається з її умовою (ParsingRelation);
  5. Циклічна зв'язок - спрямована зв'язок, яка повторює вбрання поняття вказане число раз (LoopRelation);

Для обробки використовується кілька типів процесів (Process) з різними можливостями. Для даного прикладу нам буде потрібен процес розпізнавання (ParsingProcess). ParsingProcess отримує на вхід текст і стартову вершину графа для обробки. Потім він починає обхід графа, передаючи наявну у нього інформацію про текст елементам графа. Залежно від типу елемента він отримує «відповіді» з вказівками щодо подальших дій, наприклад: перейти до наступного елементу, виконати функцію, обробити шматок тексту і так далі. В кінцевому підсумку весь вхідний текст виявляється оброблений за допомогою розпізнають зв'язків.

Моделювання процесу інтерпретації

Програма представляє собою набір команд. За допомогою графа можна уявити це в такий спосіб:
Програма представляє собою набір команд
Програма - це складене поняття, яке буде складатися з декількох активних понять в тому порядку, в якому вони зустрічаються в програмі.

Для того щоб реалізувати цикл, його тіло поміщається всередину відповідного складеного поняття, яке буде повторювати вміст до тих пір, поки значення поточної комірки буде не 0. Це реалізується за допомогою циклічної зв'язку (LoopRelation). На малюнку внизу показаний цикл, який буде друкувати вміст поточної комірки до тих пір, поки воно більше нуля:

На малюнку внизу показаний цикл, який буде друкувати вміст поточної комірки до тих пір, поки воно більше нуля:

Для безпосереднього виконання команд реалізуються відповідні функції, які будуть потім виконуватися віртуальною машиною Brainfuck. Після розпізнавання команди виклик функції міститься в граф програми як активне поняття. Коли вхідний текст повністю оброблений, процес обходу переходить на граф програми і починає його виконання. Ось як буде виглядати граф програми «, ​​[-.]» - введення і друку вмісту комірки, поки воно більше 0:

]» - введення і друку вмісту комірки, поки воно більше 0:

Як видно з малюнка, сам процес інтерпретації ( «Interpreter») складається з обробки вихідного коду ( «Source», буде однаковим для всіх програм на мові Brainfuck) і результуючої програми ( «Program»).

Вихідний код складається з команд ( «Commands»), яких може бути скільки завгодно і які ми будемо продовжувати шукати до тих пір, поки текст не скінчиться. Кожна команда може бути однією з 8 команд мови, прогалиною або чимось іншим (тобто помилкою). Вибір команди здійснюється за допомогою вибіркового поняття ( «Command») і розпізнають зв'язків (ParsingRelation), кожна з яких «з'їдає» відповідний текст при збігу умови. Розпізнають зв'язку ведуть до активних поняттям, функції яких поміщають нові активні поняття, які будуть виконувати функції мови, в граф результуючої програми.

Кілька цікавих моментів:

  1. Зв'язок «пробіл» у якості умови використовує регулярний вираз. При наявності символів пробілу все вони будуть видалені з тексту.
  2. Зв'язок «помилка» позначена як зв'язок за замовчуванням ( «default») для поняття «Command». Це означає, що процес перейде на неї тільки в тому випадку, якщо всі інші зв'язку не спрацюють.
  3. Для підтримки вкладеності циклів необхідно «прикріплювати» нові команди не до самого верхнього поняттю програми, а до поняття «Top», яке залежить від рівня циклу. Для цього використовується стек понять «Top», при створенні нового циклу в нього поміщається новий елемент, а при закінченні циклу елемент витягується і нові команди починають підключатися на рівень вище.

Повний код прикладу знаходиться тут .

Крім інтерпретатора, в ньому наводиться модель процесу перетворення коду на Brainfuck в код на Python, що значно спрощує читання текстів на цьому езотеричному мовою.

 

Календарь

Реклама

Цитата дня

Я никогда ничего не покупаю, если не могу на одной бумаге описать мои объяснения и причины. Я могу ошибаться, но я буду знать ответ этому. «Я плачу 32 миллиарда долларов за компанию Coca-Cola, потому что…» И если вы не можете ответить на этот вопрос, вам не стоит покупать эти акции. Но если вы ответите на этот вопрос и сделаете это несколько раз, вы заработаете много денег.   Уоррен Баффетт