遞歸下降解析和抽象語法樹

Question

我對遞歸裁剪解析器進行了硬編碼，主要用於學習目的，並且遇到了一些麻煩。

我會用這短短摘自CSS3語法爲例：

simple_selector = type_selector | universal; 
type_selector = [ namespace_prefix ]? element_name; 
namespace_prefix = [ IDENT | '*' ]? '|'; 
element_name = IDENT; 
universal = [ namespace_prefix ]? '*'; 

首先，我並沒有意識到，namespace_prefix同時是type_selector和universal內的可選部分。這導致type_selector總是失敗時，像*|*饋電輸入，因爲它被盲目地考慮任何輸入匹配namespace_prefix生產。

遞歸下降很簡單，但我的理解是，我需要做大量的工作（缺少更好的單詞）探索性遞歸，然後再決定生產。所以我改變了我的作品的簽名以返回布爾值。通過這種方式，我可以輕鬆判斷某個特定的生產是否成功。

我使用鏈表數據結構來支持任意先行，並且可以很容易地切片這個列表來嘗試一個生產，然後返回到我的起點，如果生產不成功。但是，在嘗試生產時，我正在傳遞可變狀態，試圖構造一個文檔對象模型。這實際上並不奏效，因爲我無法知道生產是否成功。如果生產不成功，我需要以某種方式撤消所做的任何更改。

我的問題是這樣的。我應該使用抽象語法樹作爲中間表示，然後從那裏出發？這是你通常會解決這個問題的方法嗎？因爲這個問題似乎主要與文檔對象模型不適合遞歸合適的樹數據結構有關。

Answer 1

我並不十分熟悉CSS，但總的來說，您要做的就是重構語法以儘可能消除歧義。在你的情況在這裏，即可以在兩個type_selector和普及的開始namespace_prefix生產可以在前面拉出作爲一個單獨的可選產品：

simple_selector = [ namespace_prefix ]? (type_selector | universal); 
type_selector = element_name; 
namespace_prefix = [ IDENT | '*' ]? '|'; 
element_name = IDENT; 
universal = '*'; 

不是所有的語法可以簡化爲喜歡簡單前瞻儘管如此，對於那些可以使用更復雜的shift-reduce分析器的人，或者如你所建議的那樣使用backtracking。對於回溯，通常只是試圖解析產品並通過語法記錄路徑。一旦您的產品與輸入相匹配，您就可以使用記錄的路徑來實際執行該產品的語義操作。