Erlang中的遞歸下降解析器

Question

我試圖在Erlang中構建一個RDP。到目前爲止，我已經閱讀並處理了一個令牌文件，我將把它傳遞給函數，例如[2,6,3,7,3,2,4,6,3,2,4,4,99]（sample輸入應該工作），我需要確保每個字符（或一組）可以通過從默認規則[bexp0]轉換成一些匹配的終端列表來派生。

get_terminal_list() -> 
    [1,2,3,4,5,6,7,8,9,10,11,12,99]. 

get_prod_list() -> 
[bexp0,bexp,bexp1,bterm]. 

get_sym_list(Prod) -> 
    case Prod of 
     bexp0 -> [[bexp,99]]; 
     bexp -> [[bterm,bexp1]]; 
     bexp1 -> [[5,bexp,bexp1],[6,bexp,bexp1]]; 
     bterm -> [[3,bexp,4],[2],[8],[9],[2,10,1],[2,12,1],[2,11,1],[7,bterm]] 
    end. 

get_sym_list顯示使用中的語法 - 其中每個INT代表一個終端字符，並且每個子列表是一組，即bterm-> [[7，BTERM]]意味着BTERM可以變成終端「7」其次是非終端'bterm'。

現在我的工作在某種程度上實現這一：

Check if first set of rule has some terminal 
if so, check which side, reduce list of tokens from same side until first occurrence of this token, 
    parse this new list (w/o token) with rest of the set of this rule (also without the matched terminal). 
     return {success|failure, list_of_tokens, list_of_rules} 
    if success -> check with new list_of_tokens, default_rule 
    if failure, check with old list_of_tokens, and new list_of_rules. 

我假設的最終狀態將達到如果規則列表是空的 - 因此，我們已經用盡了一切可能的生產，因此無效，或令牌
列表是空的，所以我們有充分的令牌/令牌集相匹配的一些規則

Answer 1

也許這會做你想要什麼：

-module(parse). 
-export([parse1/0, parse1/1, parse2/0, parse2/1]). 

parse1() -> 
    parse([bexp], [2,6,3,7,3,2,4,6,3,2,4,4,99], fun get_sym_list1/1). 

parse1(Input) -> 
    parse([bexp], Input, fun get_sym_list1/1). 


parse2() -> 
    parse([bexp0], [2,6,3,7,3,2,4,6,3,2,4,4,99], fun get_sym_list2/1). 

parse2(Input) -> 
    parse([bexp0], Input, fun get_sym_list2/1). 


parse([], [], _) -> 
    true; 
parse([], _, _) -> 
    false; 
parse([X | TX], [X | TY], Fun) -> 
    io:format("+ Current:~w\tTokens:~w Input:~w~n", [X, TX, TY]), 
    parse(TX, TY, Fun); 
parse([X | TX], Input, Fun) -> 
    io:format(" Current:~w\tTokens:~w Input:~w~n", [X, TX, Input]), 
    case lists:member(X, get_terminal_list()) of 
     true -> false; 
     false -> lists:any(fun(T) -> parse(T ++ TX, Input, Fun) end, Fun(X)) 
    end. 

get_terminal_list() -> 
    [1,2,3,4,5,6,7,8,9,10,11,12,99]. 

get_sym_list1(Prod) -> 
    case Prod of 
     bexp -> [[bexp1],[bterm],[bterm,bexp2]]; 
     bexp1 -> [[99]]; 
     bexp2 -> [[5,bterm,bexp2],[6,bterm,bexp2]]; 
     bterm -> [[bfactor],[7,bterm]]; 
     bfactor -> [[3,bexp,4],[bconst],[2,10,1],[2,12,1],[2,11,1],[2]]; 
     bconst -> [[8],[9]] 
    end. 

get_sym_list2(Prod) -> 
    case Prod of 
     bexp0 -> [[bterm,bexp1]]; 
     bexp -> [[bterm,bexp1]]; 
     bexp1 -> [[5,u1],[6,bexp,bexp1],[99]]; 
     bterm -> [[u1,4],[2],[8],[9],[2,10,1],[2,12,1],[2,11,1],[7,bterm]]; 
     u1 -> [[3,bexp]] 
    end. 

但是，它看起來像語法或輸入列表是不正確的，因爲據我可以看到舊的和新的語法都不能解析輸入。它似乎是工作的罰款，因爲它會解析這樣一個輸入：

41> parse:parse2([2,6,8,5,3,bterm,5,3,9,99,99]). 
    Current:bexp0 Tokens:[] Input:[2,6,8,5,3,bterm,5,3,9,99,99] 
    Current:bterm Tokens:[bexp1] Input:[2,6,8,5,3,bterm,5,3,9,99,99] 
    Current:u1 Tokens:[4,bexp1] Input:[2,6,8,5,3,bterm,5,3,9,99,99] 
    Current:3  Tokens:[bexp,4,bexp1] Input:[2,6,8,5,3,bterm,5,3,9,99,99] 
+ Current:2  Tokens:[bexp1] Input:[6,8,5,3,bterm,5,3,9,99,99] 
    Current:bexp1 Tokens:[] Input:[6,8,5,3,bterm,5,3,9,99,99] 
    Current:5  Tokens:[u1] Input:[6,8,5,3,bterm,5,3,9,99,99] 
+ Current:6  Tokens:[bexp,bexp1] Input:[8,5,3,bterm,5,3,9,99,99] 
    Current:bexp Tokens:[bexp1] Input:[8,5,3,bterm,5,3,9,99,99] 
    Current:bterm Tokens:[bexp1,bexp1] Input:[8,5,3,bterm,5,3,9,99,99] 
    Current:u1 Tokens:[4,bexp1,bexp1] Input:[8,5,3,bterm,5,3,9,99,99] 
    Current:3  Tokens:[bexp,4,bexp1,bexp1] Input:[8,5,3,bterm,5,3,9,99,99] 
    Current:2  Tokens:[bexp1,bexp1] Input:[8,5,3,bterm,5,3,9,99,99] 
+ Current:8  Tokens:[bexp1,bexp1] Input:[5,3,bterm,5,3,9,99,99] 
    Current:bexp1 Tokens:[bexp1] Input:[5,3,bterm,5,3,9,99,99] 
+ Current:5  Tokens:[u1,bexp1] Input:[3,bterm,5,3,9,99,99] 
    Current:u1 Tokens:[bexp1] Input:[3,bterm,5,3,9,99,99] 
+ Current:3  Tokens:[bexp,bexp1] Input:[bterm,5,3,9,99,99] 
    Current:bexp Tokens:[bexp1] Input:[bterm,5,3,9,99,99] 
+ Current:bterm Tokens:[bexp1,bexp1] Input:[5,3,9,99,99] 
    Current:bexp1 Tokens:[bexp1] Input:[5,3,9,99,99] 
+ Current:5  Tokens:[u1,bexp1] Input:[3,9,99,99] 
    Current:u1 Tokens:[bexp1] Input:[3,9,99,99] 
+ Current:3  Tokens:[bexp,bexp1] Input:[9,99,99] 
    Current:bexp Tokens:[bexp1] Input:[9,99,99] 
    Current:bterm Tokens:[bexp1,bexp1] Input:[9,99,99] 
    Current:u1 Tokens:[4,bexp1,bexp1] Input:[9,99,99] 
    Current:3  Tokens:[bexp,4,bexp1,bexp1] Input:[9,99,99] 
    Current:2  Tokens:[bexp1,bexp1] Input:[9,99,99] 
    Current:8  Tokens:[bexp1,bexp1] Input:[9,99,99] 
+ Current:9  Tokens:[bexp1,bexp1] Input:[99,99] 
    Current:bexp1 Tokens:[bexp1] Input:[99,99] 
    Current:5  Tokens:[u1,bexp1] Input:[99,99] 
    Current:6  Tokens:[bexp,bexp1,bexp1] Input:[99,99] 
+ Current:99 Tokens:[bexp1] Input:[99] 
    Current:bexp1 Tokens:[] Input:[99] 
    Current:5  Tokens:[u1] Input:[99] 
    Current:6  Tokens:[bexp,bexp1] Input:[99] 
+ Current:99 Tokens:[] Input:[] 
true 

BTW true意味着輸入已被解析並false，它也沒有。