Как отображаются графики на SQLite?

Question

Можно создать дубликат:
Tool for generating railroad diagram used on json.org

SQLite имеет некоторые удивительные графики, показывающие грамматику языка на своем веб-сайте, кто-нибудь знает, как они сделаны?

Есть инструмент для создания графики из grammas?

Answer 1

Этот пример очень похож на конечный автомат - т. Е. Эквивалент графа регулярного выражения. Если вы можете представить свою грамматику в RE (естественно, не все грамматики будут представлены как REs!), Вы можете использовать Kleene's theorem, чтобы перевести его в граф FA.

Обратите внимание, что данный алфавит для REs - это не отдельные буквы, а слова и жетоны. В приведенном выше примере соответствующий RE выглядит следующим образом:

DELETE FROM qualified-table-name 
(WHERE expr|()) /* "WHERE expr" is optional; the alternative branch is the empty expression "()" */ 
(
    (ORDER BY ordering-term (, ordering-term)*|()) /* ", ordering-term" may be repeated */ 
    LIMIT expr ((OFFSET|,) expr|()) /* can use "OFFSET" or "," */ 
|() 
) 

Это означает, что FA очень похож на вашу диаграмму. GraphViz выполнит непростую работу по разметке чертежа.

Однако это не совсем так же, как оригинал, так? Представлять это красиво - следующая задача. Я бы предложил взять вложенные выражения RE и рендерировать их рекурсивно, начиная с листьев.

Например, для визуализации (WHERE expr|()):

1. два альтернативных пути. Рендер каждый в отдельности:
   1. Рендер WHERE expr:
      1. Рендер WHERE как поле.
      2. Затем стрелка.
      3. Затем рендер expr как коробка.
   2. Render () как отдельная стрелка.
2. Найти самый длинный (первый) и растянуть остальные, чтобы соответствовать ему.
3. Создайте начальные и конечные узлы на каждом конце.
4. Нарисуйте соединительные края от начального узла к каждой подчасти, затем от каждой подчасти к конечному узлу.

Выполнение этого графически означает отслеживание размеров и положений коробки, в том числе невидимых. На каждом подчастике есть невидимая коробка. Есть три вещи, чтобы отметить о рекурсивной структуры:

1. размер компонента зависит от размеров его детей.
2. местоположение подчасти зависит от местоположения его родителя.
3. Местоположение всего (может) зависит от размеров всего остального.

Это означает, что вы должны сначала рассчитать размеры каждой детали, начиная с нижней. Затем, как только вы знаете размер корня, вы можете начать позиционирование частей сверху вниз.