yecc.erl

OTP是开放电信平台的简称

                   true ->
                       list_to_tuple(tuple_to_list(StateTab0) ++
                                     lists:duplicate(round(1 + N * 1.5), []))
               end,
    setelement(N+1, StateTab, State).

insert_state_id(StateIdTab, N, StateId) ->
    true = ets:insert(StateIdTab, {StateId, N}).

compute_states1([], {N, _}=_CurrState, StateTab0, _Tables) ->
    {StateTab0, N};
compute_states1([{N, Symbols} | Try], CurrState, StateTab, Tables) ->
    {_N, S} = lookup_state(StateTab, N),
    Seeds = state_seeds(S, Symbols),
    compute_states2(Seeds, N, Try, CurrState, StateTab, Tables).

compute_states2([], _N, Try, CurrState, StateTab, Tables) ->
    compute_states1(Try, CurrState, StateTab, Tables);
compute_states2([{Sym,Seed} | Seeds], N, Try, CurrState, StateTab, Tables) ->
    {StateId, NewState} = compute_state(Seed, Tables),
    case check_states(NewState, StateId, StateTab, Tables) of
        add ->
            {M, _} = CurrState,
            %% io:fwrite("Adding state ~w\n", [M + 1]),
            CurrentSymbols = get_current_symbols(NewState),
            Next = M + 1,
            NextState = {Next, NewState},
            NewStateTab = insert_state(Tables, StateTab, NextState, StateId),
            insert_goto(Tables, N, Sym, Next),
            compute_states2(Seeds, N, [{Next, CurrentSymbols} | Try],
                            NextState, NewStateTab, Tables);
        {old, M} ->
            %% io:fwrite("Identical to old state ~w\n", [M]),
            insert_goto(Tables, N, Sym, M),
            compute_states2(Seeds, N, Try, CurrState, StateTab, Tables);
        {merge, M, NewCurrent} ->
            %% io:fwrite("Merging with state ~w\n", [M]),
            Try1 = case keysearch(M, 1, Try) of
                       false ->
                           [{M, NewCurrent} | Try];
                       {value, {_, OldCurrent}} ->
                           case ordsets:is_subset(NewCurrent, OldCurrent) of
                               true ->
                                   Try;
                               false ->
                                   [{M, ordsets:union(NewCurrent, OldCurrent)}
                                    | keydelete(M, 1, Try)]
                           end
                   end,
            NewStateTab = merge_states(NewState, StateTab, Tables, M,StateId),
            insert_goto(Tables, N, Sym, M),
            compute_states2(Seeds, N, Try1, CurrState, NewStateTab, Tables)
    end.

insert_goto(Tables, From, Sym, To) ->
    true = ets:insert(Tables#tabs.goto, {{From, Sym, To}}).

%% Create an ets table for faster lookups.
create_symbol_table(St) ->
    #yecc{terminals = Terminals, endsymbol = Endsymbol} = St,
    SymbolTab = ets:new(yecc_symbols, [{keypos,1}]),
    %% '$empty' is always assigned 0
    Ts = ['$empty', Endsymbol | delete('$empty', Terminals)],
    TsC = count(0, Ts),
    NTsC = map(fun({NT,I}) -> {NT,-I} end, count(1, St#yecc.nonterminals)),
    Cs = TsC++NTsC,
    true = ets:insert(SymbolTab, Cs),

    InvSymTable = ets:new(yecc_inverted_terminals, [{keypos,2}]),
    true = ets:insert(InvSymTable, Cs),

    St#yecc{symbol_tab = SymbolTab, inv_symbol_tab = InvSymTable}.

get_current_symbols(State) ->
    usort(get_current_symbols1(State, [])).

get_current_symbols1([], Syms) ->
    Syms;
get_current_symbols1([#item{rhs = Rhs} | Items], Syms) ->
    case Rhs of
        [] ->
            get_current_symbols1(Items, Syms);
        [Symbol | _] ->
            get_current_symbols1(Items, [Symbol | Syms])
    end.

state_seeds(Items, Symbols) ->
    L = [{S,{LA,RP + 1}} || #item{rule_pointer = RP, look_ahead = LA, 
                                  rhs = [S | _]} <- Items],
    state_seeds1(keysort(1, L), Symbols).

state_seeds1(_L, []) ->
    [];
state_seeds1(L, [Symbol | Symbols]) ->
    state_seeds(L, Symbol, Symbols, []).

state_seeds([{Symbol, Item} | L], Symbol, Symbols, Is) ->
    state_seeds(L, Symbol, Symbols, [Item | Is]);
state_seeds([{S, _Item} | L], Symbol, Symbols, Is) when S < Symbol ->
    state_seeds(L, Symbol, Symbols, Is);
state_seeds(L, Symbol, Symbols, Is) ->
    [{Symbol, Is} | state_seeds1(L, Symbols)].

compute_state(Seed, Tables) ->
    RpInfo = Tables#tabs.rp_info,
    foreach(fun({LA, RulePointer}) -> put(RulePointer, LA) end, Seed),
    foreach(fun({LA, RP}) -> compute_closure(LA, RP, RpInfo) end, Seed),
    Closure = keysort(1, erase()),
    state_items(Closure, [], [], Tables#tabs.rp_rhs).

%% Collects a uniqe id for the state (all rule pointers). 
state_items([{RP, LA} | L], Is, Id, RpRhs) ->
    I = #item{rule_pointer = RP, look_ahead = LA, rhs = element(RP, RpRhs)},
    state_items(L, [I | Is], [RP | Id], RpRhs);
state_items(_, Is, Id, _RpRhs) ->
    {Id, Is}.

-compile({inline,[{compute_closure,3}]}).
compute_closure(Lookahead, RulePointer, RpInfo) ->
    case element(RulePointer, RpInfo) of
        []=Void -> % no followers, or terminal
            Void;
        {no_union, ExpandingRules, NewLookahead} ->
            compute_closure1(ExpandingRules, NewLookahead, RpInfo);
        {union, ExpandingRules, Lookahead0} ->
            NewLookahead = set_union(Lookahead0, Lookahead),
            compute_closure1(ExpandingRules, NewLookahead, RpInfo);
        ExpandingRules ->
            compute_closure1(ExpandingRules, Lookahead, RpInfo)
    end.
    
compute_closure1([RulePointer | Tail], NewLookahead, RpInfo) ->
    compute_closure1(Tail, NewLookahead, RpInfo),
    case get(RulePointer) of
        undefined -> % New
            put(RulePointer, NewLookahead),
            compute_closure(NewLookahead, RulePointer, RpInfo);
        Lookahead2 ->
            Lookahead = set_union(Lookahead2, NewLookahead),
            if 
                Lookahead =:= Lookahead2 -> % Old
                    Lookahead2; % void()
                true -> % Merge
                    put(RulePointer, Lookahead),
                    compute_closure(NewLookahead, RulePointer, RpInfo)
            end
    end;
compute_closure1(Nil, _, _RpInfo) ->
    Nil.

%% Check if some old state is a superset of our NewState
check_states(NewState, StateId, StateTab, #tabs{state_id = StateIdTab}) ->
    try ets:lookup_element(StateIdTab, StateId, 2) of
        N ->
            {_N, OldState} = lookup_state(StateTab, N),
            check_state1(NewState, OldState, [], N)
    catch error:_ -> add
    end.

check_state1([#item{look_ahead = Lookahead1, rhs = Rhs} | Items1],
             [#item{look_ahead = Lookahead2} | Items2], Symbols, N) ->
    case set_is_subset(Lookahead1, Lookahead2) of
        true ->
            check_state1(Items1, Items2, Symbols, N);
        false ->
            case Rhs of
                [] ->
                    check_state2(Items1, Items2, Symbols, N);
                [Symbol | _] ->
                    check_state2(Items1, Items2, [Symbol | Symbols], N)
            end
    end;
check_state1([], [], _Symbols, N) ->
    {old, N}.

check_state2([#item{look_ahead = Lookahead1, rhs = Rhs} | Items1],
             [#item{look_ahead = Lookahead2} | Items2], Symbols, N) ->
    case set_is_subset(Lookahead1, Lookahead2) of
        true ->
            check_state2(Items1, Items2, Symbols, N);
        false ->
            case Rhs of
                [] ->
                    check_state2(Items1, Items2, Symbols, N);
                [Symbol | _] ->
                    check_state2(Items1, Items2, [Symbol | Symbols], N)
            end
    end;
check_state2([], [], Symbols, N) ->
    {merge, N, usort(Symbols)}.

merge_states(NewState, StateTab, Tables, M, StateId) ->
    {_M, Old_state} = lookup_state(StateTab, M),
    MergedState = merge_states1(NewState, Old_state),
    insert_state(Tables, StateTab, {M, MergedState}, StateId).

merge_states1([Item1 | Items1], [Item2 | Items2]) ->
    LA1 = Item1#item.look_ahead,
    LA2 = Item2#item.look_ahead,
    if
        LA1 =:= LA2 ->
            [Item1 | merge_states1(Items1, Items2)];
        true ->
            [Item1#item{look_ahead = set_union(LA1, LA2)}
             | merge_states1(Items1, Items2)]
    end;
merge_states1(_, _) ->
    [].

%% RulePointer -> Rhs. Every position Rhs in has its unique "rule pointer".
make_rhs_index(RulesList) ->
    Index = flatmap(fun(#rule{symbols = [_Non | Daughters]}) ->
                            suffixes0(Daughters)
                    end, RulesList),
    list_to_tuple(Index).

suffixes0([?EMPTY]) ->
    [[], []];
suffixes0(L) ->
    suffixes(L).

suffixes([]=L) ->
    [L];
suffixes([_ | T]=L) ->
    [L | suffixes(T)].

%% Setup info about lookahead and expanding rules for each point
%% ("rule pointer") in the grammar. 
make_rule_pointer_info(StC, RpRhs, RuleIndex) ->
    SymbolTab = StC#yecc.symbol_tab,
    LcTab = make_left_corner_table(StC),
    LA_index = map(fun(Syms) ->
                           rp_info(Syms, SymbolTab, LcTab, RuleIndex)
                   end, tuple_to_list(RpRhs)),
    list_to_tuple(LA_index).

rp_info([], _SymbolTab, _LcTab, _RuleIndex) ->
    [];
rp_info([Category | Followers], SymbolTab, LcTab, RuleIndex) ->
    case dict:find(Category, RuleIndex) of
        error -> % terminal
            [];
        {ok, ExpandingRules} when Followers =:= [] ->
            ExpandingRules;
        {ok, ExpandingRules} ->
            case make_lookahead(Followers, SymbolTab, LcTab, set_empty()) of
                {empty, LA} ->
                    {union, ExpandingRules, LA};
                LA ->
                    {no_union, ExpandingRules, LA}
            end
    end.

%% Lookahead computation is complicated by the possible existence
%% of null string rewriting rules, such as A -> '$empty'.
make_lookahead([], _, _, LA) ->
    {empty, LA};
make_lookahead([Symbol | Symbols], SymbolTab, LcTab, LA) ->
    case dict:find(Symbol, LcTab) of
        {ok, LeftCorner} -> % nonterminal
            case empty_member(LeftCorner) of
                true ->
                    make_lookahead(Symbols, SymbolTab, LcTab,
                                   set_union(empty_delete(LeftCorner), LA));
                false ->
                    set_union(LeftCorner, LA)
            end;
        error -> % terminal
            set_add(Symbol, LA)
    end.

%% -> dict-of({Nonterminal, [Terminal]}).
%% The algorithm FIRST/1 from the Dragon Book.
%% Left corner table, all terminals (including '$empty') that can
%% begin strings generated by Nonterminal.
make_left_corner_table(#yecc{rules_list = RulesList} = St) ->
    SymbolTab = left_corner_symbol_table(St),
    Rules = map(fun(#rule{symbols = [Lhs | Rhs]}) ->
                        {Lhs,{Lhs, Rhs}}
                end, RulesList),
    LeftHandTab = dict:from_list(family(Rules)),
    X0 = [{S,H} || {H,{H,Rhs}} <- Rules, 
                   S <- Rhs, 
                   not is_terminal(SymbolTab, S)],
    XL = family_with_domain(X0, St#yecc.nonterminals),
    X = dict:from_list(XL),
    Xref = fun(NT) -> dict:fetch(NT, X) end,
    E = set_empty(),
    LC0 = dict:from_list([{H, E} || {H,_} <- XL]),
    %% Handle H -> a S, where a is a terminal ('$empty' inclusive).
    {Q, LC1} =
        foldl(fun({H,{H,[S | _]}}, {Q0, LC}) ->
                      case ets:lookup(SymbolTab, S) of
                          [{_,Num}=SymbolAndNum] when Num >= 0 ->
                              F = set_add_terminal(SymbolAndNum, E),
                              {[Xref(H) | Q0], upd_first(H, F, LC)};
                          _ ->
                              {Q0, LC}
                      end
              end, {[], LC0}, Rules),
    left_corners(Q, LC1, LeftHandTab, SymbolTab, Xref).

left_corners(Q0, LC0, LeftHandTab, SymbolTab, Xref) ->
    case usort(append(Q0)) of
        [] -> 
            LC0;
        Q1 -> 
            Rs = flatmap(fun(NT) -> dict:fetch(NT, LeftHandTab) end, Q1),
            {LC, Q} = left_corners2(Rs, LC0, [], SymbolTab, Xref),
            left_corners(Q, LC, LeftHandTab, SymbolTab, Xref)
    end.
    
left_corners2([], LC, Q, _SymbolTab, _Xref) ->
    {LC, Q};
left_corners2([{Head,Rhs} | Rs], LC, Q0, SymbolTab, Xref) ->
    Ts = left_corner_rhs(Rhs, Head, LC, set_empty(), SymbolTab),
    First0 = dict:fetch(Head, LC),
    case set_is_subset(Ts, First0) of
        true ->
            left_corners2(Rs, LC, Q0, SymbolTab, Xref);
        false ->
            LC1 = upd_first(Head, Ts, LC),
            left_corners2(Rs, LC1, [Xref(Head) | Q0], SymbolTab, Xref)
    end.

upd_first(NT, Ts, LC) ->
    dict:update(NT, fun(First) -> set_union(First, Ts) end, LC).

left_corner_rhs([S | Ss], Head, LC, Ts, SymbolTab) ->
    case ets:lookup(SymbolTab, S) of
        [{_,Num}=SymbolAndNum] when Num >= 0 ->
            set_add_terminal(SymbolAndNum, Ts);
        [_NonTerminalSymbol] ->
            First = dict:fetch(S, LC),
            case empty_member(First) of
                true ->
                    NTs = set_union(empty_delete(First), Ts),
                    left_corner_rhs(Ss, Head, LC, NTs, SymbolTab);
                false ->
                    set_union(First, Ts)
            end
    end;
left_corner_rhs([], _Head, _LC, Ts, _SymbolTab) ->
    set_add(?EMPTY, Ts).

%% For every non-terminal return a list of "rule pointers" for rules
%% expanding the non-terminal.
%% Also assigns a unique number to each point in the grammar, "rule pointer".
make_rule_index(#yecc{nonterminals = Nonterminals, 
                      rules_list = RulesList}, RulesListNoCodes) ->