把節點到解析樹這不應該是有

Question

我寫一個解析器的語言，而掃描儀的設計

1. 要麼也返回不需要的終端（例如whitespacing）OR
2. 不這樣做

基於布爾標誌。

現在，在解析器中，我不想讓語法與所有終端混在一起，它們應該被我正在構建的解析樹以某種方式「自動地」吞下。爲了做到這一點「魔術」，我想我會鏈接終端（簡單地連接循環列表），所以我可以迭代它們並在發生縮減時「填空」（我正在使用LALR（1 ）解析器生成器）。

這聽起來像一個理智的想法，雖然有一個問題。記得我說過「要麼退還要麼沒有」？在情景（2）中，我會釋放終端，因爲誰知道接下來會發生什麼？我不想要任何內存泄漏。

但是在場景（1）中，我不能釋放終端，因爲根據他們我會決定進一步減少「填空」過程應該停止的地方。

由於相同的原因，我無法有條件地釋放它，我不知道接下來會發生什麼。如果沒有任何「填充空白」過程觸發？如果根本沒有進一步減少會怎樣？

你有類似的問題嗎？你是如何解決它的？

注意：這一切都在我的腦海裏，我可能沒有足夠清楚地解釋它，請問，我會編輯我的問題。這個場景實際上有點複雜，我不是從頭開始寫的，我可以利用我的想象力，我將它融入其他東西，所以很可能我會回答「我做不到這一點由於環境的限制「。

---

附錄

的只是在我腦海中真正的好想法是叉子和提高解析器生成，我已經在這裏和那裏的一些細微的地方已經完成，克服一些那些我上面提到的限制。

Answer 1

你的詞彙有點奇怪。大多數解析器旨在識別語言的語法。通常語言定義定義了終端的一些概念，並且明確地排除了「空白」，其包括終端文本之間無意義的文本序列，通常包括空白，標籤和各種獨立評論。所以解析中使用的「終端」這個詞通常意味着「那些不是空白的語言原子」。你已經明確地將其定義爲包含空格，並且我認爲這會導致你的悲傷。

從這個角度來看，避免使用空格解析器所使用的語法定義的最簡單方法是簡單地讓詞法分析器不將空白傳遞給解析器。那麼你的語法不需要指出它們是如何處理的（是的，這樣做的語法真的很混亂），解析器不必擔心它們，它們也不會出現在樹中。

如果您正在構建編譯器或解釋器，那麼忽略空白是最簡單的。

如果你正在建設一個重新設計解析器（查看我們的DMS Software Reengineering Toolkit，然後捕捉評論（至少）在AST是很重要的，因爲最終 一個要重新生成從consturcted AST的文本，它是有益的，如果再生文本也包含註釋[你可以通過其他方式做到這一點，但它們並不那麼容易]

DMS詞法分析器生成「微型」標記，這是您內部語言標記，空白和註釋的概念。它拋出了空白微型令牌，因爲它們根本不會添加任何東西（參見上面的討論）。它將常規令牌傳遞給解析器，如您所期望的那樣。它將註釋令牌粘貼到前面或後面的語言令牌，具體取決於令牌類型和其他遇到;對於C，a/* ... * /在將令牌附加到它之前看到，並且// ...註釋附加到前一個令牌（具有一些更細微的細節，這裏未討論）。然後，解析仍然只能看到語言標記，所以語法不是不必要的複雜，並且如果附加到標記的所有信息都放置在樹中，則評論會繼續進行。

現在，人們經常要「抽象」語法樹;他們想要拋棄諸如「（」和「）」之類的東西。我上面描述的方案附加了對這些甚至具體的令牌的評論。現在有一個複雜的問題：如果你將（..）令牌從樹中移出，附加的評論就會消失。哎呀。 因此DMS解析器做了一件複雜的事情：附加到在樹中具有邏輯位置但實際上並不存在的令牌（「被淘汰的終端」）的註釋被提升到父樹節點並帶有註釋，表明它們屬於丟失的子令牌。是的，實施這個確實是一個PITA。 好消息是，我們只需要在DMS的一般解析機器中執行一次，並且它適用於許多種語言。但這意味着您必須願意構建一個不尋常的（「重構」）解析器，並且我們有商業動機來這樣做。

編輯：目前尚不清楚爲什麼OP要這樣做，但他堅持要在樹中捕獲空白。由於他沒有告訴我們爲什麼，我會猜測：他想要令牌/樹節點的精確列信息。這並不困難：教授詞法分析器跟蹤位置（行/列），並將每個標記（例如註釋等微型標記）與開始/結束位置貼在一起，並讓解析存儲該信息那個樹。這樣避免了在樹中留下空白。 （DMS也是這樣做的，因爲在報告問題時，精確的信息是有用的，並且在重新生成代碼時，通常需要將代碼放回原始位置（至少是同一列）。

編輯2：如果OP堅持捕獲空白，他可能會考慮探索scannerless GLR parsing。這會在輸入流中每隔字符保留，包括空格。