關於LL1非遞歸語法分析器中的AST構造

我已經使用顯式堆棧以非遞歸方法實現了LL1分析器。關於LL1非遞歸語法分析器中的AST構造

下面的算法是從龍書：

set zp to point to the first symbol of w; 
set X to the top stack symbol; 
while (X != $) { /* stack is not empty */ 
    if (X is a) 
     pop the stack and advance zp; 
    else if (X is a terminal) 
     error(); 
    else if (M[X, a] is an error entry) 
     error(); 
    else if (M[X,a] = X -+ Y1Y2 Yk) { 
     output the production X -+ YlY2 - . Yk; 
     pop the stack; 
     push Yk, Yk-1,. . . , Yl onto the stack, with Yl on top; 

    set X to the top stack symbol; 
}

書中說：

解析器是由認爲X，符號上頂部堆疊的程序控制，和a，當前輸入符號。如果X是非終結符號，則解析器通過查詢條目 M [X，a]的解析表IM來選擇X生產。 （此處可以執行其他代碼，例如，在分析樹中構造節點的代碼）。 否則，它會檢查終端X和當前輸入符號a之間的匹配。

但是我需要更多關於如何在這種方法下構建表達式樹節點的信息。我有UnaryOperator，BinaryOperator等節點層次結構，但不知道在哪裏實例化它。

但我還沒有找到任何簡單的例子（例如算術語言）。

來源

2014-03-01 Wyvern666

我一直在尋找相同的信息 - 如何創建一個LL（1）表驅動的非遞歸解析的分析樹 - 並且發現很少。

剛纔我發現了這些講義：https://parasol.tamu.edu/~rwerger/Courses/434/lec7.pdf，其中提出了對於每個終端或非終端，相應的分析樹節點也被推入堆棧。不過，它確實看起來很浪費。下面是僞代碼中提出的算法：

TOS ← 0 
Stack[tos++] ← eof 
Stack[tos++] ← *root node* 
Stack[tos++] ← *Start Symbol* 
token ← next_token() 
X ← Stack[tos] 
repeat 
    if X is a terminal or eof then 
    if X = token then 
     pop X 
     token ← next_token() 
     *pop and fill in node* 
    else error() 
    else /* X is a non-terminal */ 
    if M[X,token] = X → Y1Y2...Yk then 
     pop X 
     *pop node for X 
     build node for each child and 
     make it a child of node for X* 
     push nk,Yk,nk-1,Yk-1...n1,Y1 
    else error() 
until X = eof

來源

2014-11-29 20:39:22 LHP

關於LL1非遞歸語法分析器中的AST構造

回答

相關問題