我在大學有一個實驗室。但我不明白我該怎麼做。 我有一些語言的語法（例如算術表達式語法）。我必須構建這個語法樹（我不知道如何）。那麼我必須確定，輸入句子是否是這種語言的句子？我該怎麼做？ P.S.我讀過龍書的幾章，但我沒有找到任何我需要的東西。 P.P.S.我不能使用lex/flex和yacc/bison。語法樹
編輯對不起！我會更加細心。真的，我有一個語法，我必須使用這個語法和輸入句子（我知道如何去做）來構建樹，如果可能的話（在另一種情況下，我必須顯示關於它的消息）。有沒有簡單的理解它的算法？我可以使用像算術表達式這樣的簡單語言的語法。
我假設這是理論上的，因爲它是作業，而不是你實際需要在這一點上編碼的東西。 （肯德里克的回答涵蓋了代碼方法）
基本思想是從你的BNF開始變量開始，並試圖找出如何擴展它，一次應用一個規則，看看你是否可以提出你的輸入序列。
對於像下面這樣的規則集：
(1) start: expression
(2) expression: expression '+' term
(3) | expression '-' term
(4) | term
(5) term: 'a'
(6) | 'b'
鑑於表達a + b - a，你會去是這樣的：
一個。 start（給出）
b。 expression（1）
c。 expression '-' term（3）
d。 expression '-' 'a'（5）
e。 （2）
f。 （4）
g。 h。'a' '+' term '-' 'a'（5）
h。所以這就是你如何做到這一步一次...現在的技巧是，你需要找出你所有的規則調用。所以，你真正的樹會是這個樣子：
start
| (b)
expression
/ | \ (c)
expression '-' term
/| \ (e) | (d)
expression '+' term 'a'
| (f) | (h)
term 'b'
| (g)
'a'
這是起初有點複雜，但一旦你真正看到它是如何做，這不是太硬回暖。
注意：有些人發現向後倒退比較容易，從輸入開始，然後反向應用規則以找到開始表達式。當你編寫一個解析器時，你將不可避免地需要在某個級別上遵循這條路線。
編輯：我列出了所有使用上述小寫字母的表達式步驟，然後顯示樹中的每組分支實際上與規則應用程序之一相對應。可能或不會幫助。
我已經做了很長時間了，所以我會給你簡短的理論答案。我相信別人會有更深入的解釋。
由於你沒有說過你已經做了什麼（並且你將來應該作爲你的問題的一部分），所以第一步是標記輸入。
擁有令牌後，您可以構建一個狀態機來行使令牌並將其推送到所需的樹結構中。這應該包括在你的書中（我還沒有讀過），但是你可能想要先在紙上（或電子版）建立一個模型，並考慮每一步的有效輸入。平等聲明的左邊有效值是多少？如果樹上有令牌x，你可以從哪裏出發？
如果您無法根據當前狀態確定下一步要做什麼，那麼您可能需要在狀態機中實現預測（這是否需要取決於您的語言的複雜性）。
再一次，我在10多年沒有這樣做，所以我的回憶是模糊的。希望我已經給了你足夠的框架來優化你的答案，或者讓那些對這個主題更有見識的人烤我因爲錯誤或過時（並且因此得到你想要作爲一個羣體的答案） ）。
不 - 不 - 不。我必須建立完全的語法樹，即我用BNF符號（http：//en.wikipedia。org/wiki/Backus％E2％80％93Naur_Form），我必須構建這個語法的樹。語法可以修復。 – 2010-12-07 18:18:53
+1爲高級別的高級技術概述。不知道你的方法或我的原始海報是在這裏做什麼。 – 2010-12-07 18:44:00
我想回答這個問題，但沒有真的夠材料工作 - 我留下了這樣的問題：
編輯：考慮評論和更新的問題：我認爲最直接的方法是遞歸下降解析器，它在輸入匹配時構建樹。查找Niklaus Wirth的「編譯器結構」一書，該書已在網上以PDF形式提供，並描述了一種簡單語言的RDP。
遞歸下降解析器的基本思想是，語法中的每個規則對應一個函數，每個函數檢查下一個標記並調用相應的next-lower解析函數。例如，如果你的語法有一個規則
expression : constant '+' constant
相關的分析方法是這樣的：
void parseExpression() {
parseConstant();
Token token = peek_at_next_token();
if (token == '+') {
parseConstant();
... tree building code here ...
}
else
throw ParseException("Expected '+', found "+token);
}
還能看到其他回答這個問題。
我對如何用一個遞歸規則構建* tree *節點感到困惑，像` :: = | `，除非使用標識符來指示遞歸。你能在教科書中找到任何例子嗎？ –
2010-12-07 18:25:20
好的，編輯你想用肯德里克的答案。你有什麼問題？ （按照他所說的順序，忽略你所說的你知道並且不知道的事情。） – 2010-12-07 20:06:42