程序化語法的解析算法是什麼？

Question

我想知道用於解析程序化語法的解析算法是什麼。任何鏈接，博客或任何可以閱讀有關程序化語法的文章，以及除IEEE研究論文之外的解析算法？

Answer 1

我認爲這很好地解釋在The power of programmed grammars with graphs from various classes：

上下文無關文法指定爲四G = (N, T, S, P)，其中N 被稱爲非終結字母表有限非空集，T是有限的非空集稱爲終端字母表(N ∩ T = ∅), S ∈ N是開始符號，而P 是稱爲規則集的有限子集N × (N ∪ T)∗。規則也被命名爲 作爲生產。

編程的語法（無外觀檢查）是六元組G = (N, T, S, Lab, P, PG)其中N , T and S被指定爲在一個上下文無關文法，Lab是字母表（標籤），P是一個有限集的上下文規則稱爲 設定芯製作，和PG是一個有限三元組集合r = (q, p, σ)，其中 q ∈ Lab是r, p ∈ P標籤的被稱爲核心 生產r上下文無關的生產，和σ是Lab一個子集，被稱爲成功字段r。 PG的元素被稱爲G的規則。

由指定爲上述 編程的語法G產生的語言L(G)被定義爲一組所有字w ∈ T∗使得存在一個推導 S = w0 =⇒r1 w1 =⇒r2 w2 =⇒r3 . . . =⇒rk wk = w, 其中k ≥ 1並且對於1 ≤ i ≤ k, wi−1 = wi−1 Ai wi−1和wi = wi−1 vi wi−1 對於一些單詞wi−1 , wi−1 ∈ (N ∪ T)∗ , ri = (qi , Ai → vi , σi)和，爲i < k, qi+1 ∈ σi。

對不起LaTeX。

以類似的方式Ogden's Lemma is stronger than the Pumping Lemma（由於標記），程序語法的概念比上下文更加嚴格，因爲這些標點符號。