Контурный режим в EBNF

Question

Я пытаюсь написать парсер для файлов режима org, используя библиотеку instaparse. Эта библиотека принимает нотацию EBNF и превращает ее в функцию синтаксического анализа. Файлы Org-режим использует строки, начинающиеся со звездами, чтобы сделать заголовки контурные, где число звезд установить уровень в дереве набросков, как этот

* Headline 
** Sub headline1 
** Sub headline2 

Моя первая попытка должна поставить все заголовки на том же уровне в полученное дерево:

(def outline 
    (insta/parser 
    "<S> = Headline-node * 
    Headline-node = Level <' '> Headline 
    Level = #'^\\*+' 
    Headline = #'\\S'+ <'\n'>")) 
(outline "* Headline\n** Subheadline\n") 
;=> 
([:Headline-node [:Level "*"] [:Headline "H" "e" "a" "d" "l" "i" "n" "e"]] 
[:Headline-node [:Level "**"] [:Headline "S" "u" "b" "h" "e" "a" "d" "l" "i" "n" "e"]]) 

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

(def outline 
    (insta/parser 
    "<S> = Headline-node1 * 
    Headline-node1 = <#'^\\* '> Headline (Headline-node2)* 
    Headline-node2 = <#'^\\*\\* '> Headline 
    Headline = #'\\S'+ <'\n'>")) 
(outline "* Headline\n** Subheadline\n") 
;=> 
([:Headline-node1 [:Headline "H" "e" "a" "d" "l" "i" "n" "e"] 
        [:Headline-node2 [:Headline "S" "u" "b" "h" "e" "a" "d" "l" "i" "n" "e"]]]) 

Но я хотел бы создать бесконечные уровни заголовков. Есть ли способ передать это в EBNF?

Answer 1

Не думаю, что это возможно. Автоматы Pushdown могут распознавать точно контекстно-свободные языки. Но подумайте о том, как автомат pushdown должен будет действовать, чтобы определить уровень заголовка в вашем примере.

Пускай автомат имеет конечный набор состояний. Таким образом, он не может использовать состояния для отслеживания уровня заголовка, если мы хотим разрешить арбитально глубокие уровни. Поэтому он должен использовать свой стек. Единственный способ подсчета с использованием стека - нажать символ стека (также есть конечное число символов стека) каждый раз, когда он читает *. Скажем, что это где-то во входной строке в начале некоторого * s. Он продолжается путем нажатия символа стека для каждого *. Но когда дело доходит до конца * s во входной строке, единственными вещами, которые автомат может использовать для определения своего действия, являются: символ во входной строке, ее состояние и верхний символ в стеке. Мы «уже» знали, что входной символ не является *, так что это не помогает. Мы знаем, что верхняя часть стека является символом, который мы нажимаем один раз для каждого *, так что это тоже не помогает. И, как ранее отмечалось, множество состояний конечно, поэтому мы не можем каким-то образом использовать состояния для подсчета количества символов в стеке.