Erlangの再帰的降下パーサー

Question

私はErlangでRDPを構築しようとしています。これまで私は、トークンのファイルを読み込んで処理しました。このファイルは、[2,6,3,7,3,2,4,6,3,2,4,4,99]（サンプル入力する必要があります）、すべての文字（またはセット）がデフォルトルール[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 

がところでtrueは、入力が解析されたことを意味し、false：それはこのような入力を解析しますので、それが正常に動作しているようです。