創建基於自定義語言

考慮語言（Σ,R,S）自上而下的解析器，通過創建基於自定義語言

Σ = { ′(′, ′)′ } 
R = {S → SS, S → (S), S → ϵ }

，這是什麼語言的語法定義？這不僅僅是生產規則的清單，因此R？如果沒有，那麼將語法與生產規則列表區分開來呢？

2.那麼我該如何根據這個語法創建一個自頂向下的解析器？我已經看到它提到了一個堆棧。

我有一個由我的教授提供的tokenizer，但我真的不知道如何去執行代碼（C++）。

編輯：包含現在看起來他們是無關的DFA，引用，所以這是有可能的項目描述的誤解

來源

2014-02-08 Tyler Klement

Re＃1：IIUC你不能，有限狀態自動機不能識別平衡圓括號的語言。 – delnan

如果您被要求爲此語言編寫DFA，則可能會要求您使用抽點引理實際上反駁其在DFA等效常規語言集中的成員資格。如果您不小心引用了DFA，那麼查看遞歸（您可能還想編輯該問題）。 – digenishjkl

語法可以作爲寫：

S = 
    | '(', S, ')', S 
    ;

我添加解析器的一些僞代碼。首先是訪問和操作tokenstream的函數。

IsEof: Bool // checks for end of token stream 
Get: Token // gets next token 
Peek: Token // peeks next token without removing it

然後解析器。 S被識別爲空的標記流，或者paren集其次是另一個S.

Parse_S 
    // If no tokens left, there is a match. 
    if (IsEof) return True // OK 
    // Expect at least one paren set, but possibly more 
    else return (Peek == '(') && (Parse_ParenSet) && (Parse_S)

該paren集合是用括號括起來的S.

Parse_ParenSet 
    // Expect a paren set. 
    if (IsEof) return False // Error 
    // Expect an S enclosed in Parenthesis. 
    else return (Get == '(') && (Parse_S) && (Get == ')')

現在你應該可以繼續分配任務了。

來源

2014-03-10 11:12:52

創建基於自定義語言

回答

相關問題