如何解析lambda項

我想解析一個lambda微積分。我不知道如何解析這個詞並尊重括號的優先級。例如：如何解析lambda項

(lx ly (x(xy)))(lx ly xxxy)

我無法找到這樣做的好方法。我只是看不到適應的算法。術語由具有類型（APPLICATION，ABSTRACTION，VARIABLE）和類型爲「struc term」的右側和左側組件的結構表示。

任何想法如何做到這一點？

編輯

不好意思打擾你，但我真的想了解。你可以檢查函數「表達式（）」讓我知道我是否正確。

Term* expression(){ 
    if(current==LINKER){ 
     Term* t = create_node(ABSTRACTION); 
     get_next_symbol(); 
     t->right = create_node_variable(); 
     get_next_symbol(); 
     t->left = expression(); 
    } 

    else if(current==OPEN_PARENTHESIS){ 
     application(); 
     get_next_symbol(); 
     if(current != CLOSE_PARENTHESIS){ 
      printf("Error\n"); 
      exit(1); 
     } 
    } 
    else if(current==VARIABLE){ 
     return create_node_variable(); 
    } 
    else if(current==END_OF_TERM) 
    { 
     printf("Error"); 
     exit(1); 
    } 
}

感謝

來源

2010-12-11 Mac Fly

的可以通過分離從其他表達式的應用程序簡化爲：

EXPR -> l{v} APPL  "abstraction" 
    -> (APPL)  "brackets" 
    -> {v}   "variable" 

APPL -> EXPR +  "application"

你的方法唯一不同的是，應用程序被表示爲表達式的列表，因爲abcd可以隱式讀爲(((ab)c)d)，因此您可以在解析時將其妥善保存爲abcd。

基於該語法，一個簡單的遞歸下降語法分析器可與先行的單個字符創建：

EXPR: 'l' // read character, then APPL, return as abstraction 
     '(' // read APPL, read ')', return as-is 
     any // read character, return as variable 
     eof // fail 

APPL: ')' // unread character, return as application 
     any // read EXPR, append to list, loop 
     eof // return as application

根符號是APPL，當然。作爲解析後的步驟，您可以將您的APPL = EXPR列表變爲應用程序樹。遞歸下降如此簡單，以至於如果您願意，您可以使用明確的堆棧輕鬆轉變爲一種迫切的解決方案。

來源

2010-12-11 20:25:18

+1：遞歸是這裏的訣竅。 – Puppy 2010-12-11 20:38:42

好的，但我真的看不到這個訣竅。你可以給我一個例子嗎。請。 – 2010-12-11 22:04:23

給出一個更詳細的例子幾乎等於編寫代碼。是否有一個特定的部分導致你的麻煩？ – 2010-12-11 22:13:35

如何解析lambda項

回答

相關問題