寫代碼來生成解析樹

Question

這個問題被要求我在面試問題：

寫代碼來生成解析樹一樣的編譯器對於任何給定的表達式內部完成。例如：

a+(b+c*(e/f)+d)*g 

Answer 1

我從一個簡單的語法開始，就像ANTLR和JavaCC使用的語法。

Answer 2

每當你打算寫一個解析器，要問的主要問題是，如果你想要做手工，或使用一個解析器生成器框架。

在這種情況下，我會說，這是一個很好的鍛鍊給它的所有寫自己。

開始與樹本身良好的代表性。這將是你的算法的輸出。例如，這可能是一個對象集合，其中一個對象類型可能代表「標籤」，如a,b和c。其他人可以代表數字。然後，您可以定義運算符的表示形式，例如+是一個二元運算符，它將有兩個子對象，分別代表左側和右側子表達式。

下一步是實際的解析器，我會建議一個經典的遞歸體面解析器。一文描述了這一點，並提供了一個標準的僞代碼實現是本文由Theodore Norvell

Answer 3

簡單的辦法就是你的表達轉化爲後綴符號（ABCEF/* ++）&則指的是這個問題的答案（ http://stackoverflow.com/questions/423898/postfix-notation-to-expression-tree）用於將後綴表達式轉換爲樹。

這是面試官的期望:)

Answer 4

從定義語言開始。沒有人可以將語法分析器或編譯器實現爲定義不明確的語言。你舉一個例子： 'A +（B + C *（E/F）+ d）* G'，它應觸發了以下問題：

1. 是對語言的單個表達，或者可以有多個語句（由「;」分隔？？？？也許
2. 什麼是「A」，「b」，......「G」標記是它的變量什麼是變量的語法是它類似C語言的變量，或它是一個單個字母數字字符作爲你的例子可能意味着
3. 有在你的榜樣3二進制表達式是所有有沒有語言也支持。？「 - 」嗎？您的語言支持邏輯和位運算符
4. 語言支持數字文字S'只有整數？雙？該語言是否支持字符串文字？你引用字符串文字嗎？
5. 評論的語法？
6. 哪個運算符優先？例如，'*'運算符是否優先於'+'？操作數是從右向左評估還是從左向右評估？
7. 任何預處理？

一旦您配備了良好的語言語法定義，就可以從實施標記器開始。令牌生成器獲取一串字符並生成一個令牌列表。在上面的示例中，每個字符都是一個標記，但在var * 12（var power 12）中，有3個標記：'var'，' *'和'12'。如果允許使用正則表達式，則可以使用正則表達式執行此部分解析。

接下來，有一個按類型標識每個標記的函數：它是一個運算符，它是一個變量，數字文字，字符串文字等等。將所有包裝在名爲NextToken的方法中，該方法返回一個標記及其類型。

最後，開始解析。在上面的示例中，解析樹的根將是具有「+」運算符的節點（其優先級高於「」）。左邊的孩子是一個變量標記'a'，右邊的孩子是一棵具有根元素''標記的樹。以遞歸方式工作。