一个Erlang写的算术表达式解析器

最近在学Erlang，就使用Erlang写了个算数表达式的解析器，该解析器仅支持加减乘除和括号运算，下面为几个表达式对应的输出。

1 -> {num,1}
1+2 -> {plus,{num,1},{num,2}}
1+2*3 -> {plus,{num,1},{multi,{num,2},{num,3}}
(1+2)*3-> {multi,{plus,{num,1},{num,2}},{num,3}}
3/3/3->{div,{num,3},{div,{num,3},{num,3}}}

从某本编译器上的书上得到表达式的语法规则如下：

expr -> term | term addop expr
addop -> + | -
term -> factor | factor mulop term
mulop -> * | /
factor -> NUM | (expr)

根据语法规则很容易使用递归下降分析法写出解析器，程序代码如下：

-module(ex08b).

-export([parse/1]).

%% Syntax Grammer

%% expr -> term | term + expr | term - expr

%% term -> factor | factor * term | factor / term

%% factor -> NUM | (expr)

parse(Tokens) ->

    element(1, expr(Tokens)).

expr(Tokens) ->

    {LeftTree, RestTokens} = term(Tokens),

    if 

length(RestTokens) == 0 -> 

   {LeftTree, []};

true -> 

   [Head | Tail] = RestTokens,

   {Lt, Rt} = expr(Tail),

   case Head of

$+ -> {{plus, LeftTree, Lt}, Rt};

$- -> {{sub, LeftTree, Lt}, Rt};

_Other -> {LeftTree, RestTokens}

   end

    end.

term(Tokens) ->

    {LeftTree, RestTokens} = factor(Tokens),

    if 

length(RestTokens) == 0 ->

   {LeftTree, []};

true -> [Head | Tail] = RestTokens,

{LT, Rt} = term(Tail),

case Head of

    $* -> {{multi, LeftTree, LT}, Rt};

    $/ -> {{divide, LeftTree, LT}, Rt};

    _Other -> {LeftTree, RestTokens}

end

    end.

factor([]) ->

    {{}, []};

factor([Head | Tail]) ->

    if 

Head >= $0, Head =< $9 -> 

   {Int, Rest} = string:to_integer([Head | Tail]),

   {{num, Int}, Rest};

Head == $( -> 

   {Lt, Rt} = expr(Tail),

   is_match(Rt, $)),

   [_ | T] = Rt,

   {Lt, T};

true ->

   {{}, [Head | Tail]}

    end.

    

is_match([Token | _], Token) ->

    ok;

is_match(_, _) ->

    throw ({'EXIT', "unexpected token"}).

问题一：该语法规则怎么体现运算符的优先级的，如为什么乘除的优先级高于加减？

expr->term addop expr

term->factor mulop term

addop对应的规则在mulop前面。根据语法规则，在expr函数内部首先会调用term，然后调用factor，当碰到终结符时，函数调用回回溯到factor。此时会判断当前token是否为mulop，只有当前token不是为mulop，才会向上再回溯到expr，然后判断是否为addop。因此，乘除的优先级就高于加减。

问题二：运算符的结合性（向左结合/向右结合）是如何体现的。

term->factor mulop term，这是个递归调用，只有当term解析完毕后，才回回到factor mulop term的解析过程中，而term已经分析完成一部分代码了，因此3/3/3会得到{div,{num,3},{div,{num,3},{num,3}}}，也就是乘除运算符是向右结合。