EBNF中的大綱模式

我正在嘗試使用instaparse庫爲組織模式文件編寫解析器。該庫使用EBNF表示法並將其轉換爲解析函數。組織模式的文件使用線與星開始做大綱的頭條新聞，其中數星星設置在大綱樹的水平，這樣EBNF中的大綱模式

* 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中傳達這一點？

來源

2013-12-21 snowape

你在這個項目中有多遠？我正在考慮爲組織模式文件編寫一個Instaparse解析器，似乎我必須自己編寫EBNF規範，因爲我無法爲組織模式找到一個。如果你已經開始了，我會很樂意爲你的項目做貢獻或者以其他方式爲你的項目做貢獻。 –

我不認爲這是可能的。下推式自動機可以精確識別上下文無關的語言。但想想下推式自動機將如何操作來確定示例中標題的級別。

下推自動機具有一組有限的狀態。所以如果我們要允許深度層次的話，它不能使用狀態來跟蹤標題的級別。所以它必須使用它的堆棧。計數使用堆棧的唯一方法是每次讀取一個堆棧符號（也有一定數量的堆棧符號）時，它會讀取一個*。假設它在某些* s的開始處的輸入字符串中。它通過推動每個*的堆棧符號來繼續。但是當涉及輸入字符串中的* s的末尾時，自動機可以用來決定其動作的唯一事情是：輸入字符串中的符號，其狀態以及堆棧中的頂部符號。我們「已經」知道輸入符號不是*，所以這沒有幫助。我們知道堆棧的頂部是我們每*推送一次的符號，所以這也沒有幫助。如前所述，這組狀態是有限的，所以我們不能以某種方式使用這些狀態來計算堆棧上符號的數量。

來源

2013-12-22 04:58:37 oskarkv

EBNF中的大綱模式

回答

相關問題