LL解析器和AST之間的區別

Question

我正在嘗試創建LL解析器。 但是我已經有了我的BNF語法，但是我必須在AST之前創建並且我有幾個問題。

• AST和LL解析器有什麼區別？ （因爲它們都是二叉樹）
• 如何從BNF語法創建AST？ （ http://mariusbancila.ro/blog/2009/02/05/evaluating-expressions-part-3-building-the-ast/

我對谷歌發現了這個教程，講解了很多關於建立一個AST否則，他們沒有解釋如何知道有沒有采取正確的分支或左分支）。

感謝的

Answer 1

AST是一種抽象語法樹 - 它是一種樹，它編碼作爲輸入提供給編譯器的程序的邏輯結構。通常，編譯器前端的工作是爲輸入程序構建一個AST，並使用有用的信息爲其註釋，然後優化器和代碼生成器可以使用該信息生成輸出程序。

通常，實際生成AST的編譯器部分稱爲解析器。有許多不同的解析器類別，其中解析器是一個流行的家族。 LL解析器通常可以手寫，但它們通常使用編譯器生成工具自動生成。

換句話說，AST和LL解析器之間差異的主要問題的答案是「LL解析器是一種解析器，而解析器是生成AST的東西。」

您的下一個問題是您如何從BNF語法構建AST。通常，您不會爲BNF語法本身構建AST。相反，語法會指導解析器的構建，然後解析器將構建AST。實際上，構建解析器通常是標準編譯器課程中的一個主題。如果您有興趣，I have a set of lecture slides available from the last time I taught a compilers class以及02,03和04講座將介紹語法分析以及如何設計和構建LL解析器。希望他們給你一個正確的方向！