從遞歸下降的語法生成表達式

Question

我有一個簡單的語法。實際上，我使用的語法更復雜，但這是解釋我的問題的最小子集。

Expr ::= Value Suffix 
     | "(" Expr ")" Suffix 

Suffix ::= "->" Expr 
     | "<-" Expr 
     | Expr 
     | epsilon 

Value匹配標識符，字符串，數字等等。 Suffix規則可以消除左遞歸。這個匹配表達式，如：

a -> b (c -> (d) (e)) 

也就是說，在a進入既b和(c -> (d) (e))結果的曲線圖，和c進入d和e。我試圖爲這些表達式產生一個抽象語法樹，但是我遇到了困難，因爲所有的操作符都可以接受任何數量的操作數。我寧願將生成AST的邏輯保留在遞歸下降解析方法中，因爲它避免了必須複製提取表達式的邏輯。我目前的策略如下：

1. 如果出現Value，請將其推送到輸出。

2. 如果From或To出現：

   1. 輸出的分離器。

   2. 獲取下一個Expr。

   3. 創建一個Link節點。

   4. 將第一組操作數從輸出中彈出到Link，直到出現分隔符。

   5. 擦除發現的分隔符。

   6. 將第二組操作數彈入Link直到出現分隔符。

   7. 將Link推送到輸出。

如果我通過運行這個不服從步驟2.3 – 2.7，我得到的價值和分離器的列表。對於上面，a -> b (c -> (d) (e))引述表達，輸出應該是：

A sep_1 B sep_2 C sep_3 D E 

運用To規則將隨後產量：

A sep_1 B sep_2 (link from C to {D, E}) 

而且隨後：

(link from A to {B, (link from C to {D, E})}) 

重要的是要注意是否sep_2（對界定第二個->的左側操作數至關重要）不會出現，所以解析器認爲表達實際寫入：

a -> (b c -> (d) (e)) 

爲了我目前的策略來解決這個問題，我需要一種方法來產生相鄰表達式之間的分隔符，但前提是當前表達式是封閉在一個From或To表達括號。如果可能的話，我只是沒有看到它，答案應該很簡單。但是，如果有更好的方法去解決這個問題，那麼請讓我知道！

Answer 1

我還沒有嘗試分析它的細節，但是：「From或To表達括號括起來」開始聽起來很像「上下文相關的」，這遞歸下降不能直接處理。爲了避免上下文相關，您可能需要單獨製作From或To（括號內），而From或To（不包含偏旁）。

編輯：雖然它可能是來不及做任何好處，如果我對你要配什麼的理解是正確的，我想我會更喜歡這樣寫：

Graph := 
     | List Sep Graph 
     ; 

Sep := "->" 
    | "<-" 
    ; 

List := 
     | Value List 
     ; 

Value := Number 
     | Identifier 
     | String 
     | '(' Graph ')' 
     ; 

很難是肯定的，但我認爲這應該至少接近匹配（只）你想要的輸入，並且應該很容易生成反映正確輸入的AST。