yecc.erl

OTP是开放电信平台的简称

            St#yecc{rules_list = Rules, rules = list_to_tuple(Rules)}
    end.

duplicates(List) ->
    Unique = usort(List),
    {Unique, List -- Unique}.

names(Symbols) ->
    map(fun(Symbol) -> Symbol#symbol.name end, Symbols).

symbol_line(Name, St) ->
    {value, #symbol{line = Line}} = symbol_search(Name, St#yecc.all_symbols),
    Line.

symbol_member(Symbol, Symbols) ->
    symbol_search(Symbol#symbol.name, Symbols) =/= false.

symbol_search(Name, Symbols) ->
    keysearch(Name, #symbol.name, Symbols).

states_and_goto_table(St0) ->
    St1 = create_symbol_table(St0),
    St = compute_states(St1),
    create_precedence_table(St).

parse_actions(St) ->
    erase(), % the pd is used when decoding lookahead sets
    ParseActions = compute_parse_actions(St#yecc.n_states, St, []),
    erase(),
    St#yecc{parse_actions = ParseActions, state_tab = []}.

action_conflicts(St0) ->
    St = find_action_conflicts(St0),
    St#yecc{conflicts_done = true}.

write_file(St) ->
    #yecc{parse_actions = ParseActions, goto_tab = GotoTab} = St,
    Sorted = sort_parse_actions(ParseActions),
    #yecc{infile = Infile, outfile = Outfile,
          inport = Inport, outport = Outport,
          nonterminals = Nonterminals} = St,
    UserCodeActions = find_user_code(Sorted, St),
    {N_lines, LastErlangCodeLine} = 
        output_header(Outport, Inport, St),
    io:nl(Outport),
    output_file_directive(St, Outfile, N_lines+2),
    io:nl(Outport),
    output_actions(Outport, Sorted, St),
    Go0 = [{Symbol,{From,To}} || {{From,Symbol},To} <- ets:tab2list(GotoTab)],
    Go = family_with_domain(Go0, Nonterminals),
    output_goto(Outport, Go),
    output_inlined(St, UserCodeActions, Infile),
    io:nl(Outport),
    case LastErlangCodeLine of
        %% Just in case warnings or errors are emitted after the last
        %% line of the file.
        {last_erlang_code_line, Last_line} ->
            output_file_directive(St, Infile, Last_line);
        no_erlang_code ->
            ok
    end,
    St.

yecc_ret(St0) ->
    St = check_expected(St0),
    report_errors(St),
    report_warnings(St),
    Es = pack_errors(St#yecc.errors),
    Ws = pack_warnings(St#yecc.warnings),
    if 
        Es =:= [] -> 
            case member(return_warnings, St#yecc.options) of
                true -> {ok, St#yecc.outfile, Ws};
                false -> {ok, St#yecc.outfile}
            end;
        true -> 
            case member(return_errors, St#yecc.options) of
                true -> {error, Es, Ws};
                false -> error
            end
    end.

check_expected(St0) ->
    #yecc{shift_reduce = SR, reduce_reduce = RR, expect_shift_reduce = ExpSR,
          n_states = NStates0, expect_n_states = ExpStates,
          conflicts_done = Done} = St0,
    N_RR = length(usort(RR)),
    N_SR = length(usort(SR)),
    St1 = if
              not Done ->
                  St0;
              N_SR =:= ExpSR, N_RR =:= 0 ->
                  St0;
              true ->
                  add_warning(none, {conflicts, N_SR, N_RR}, St0)
          end,
    NStates = NStates0 + 1,
    if
        (not Done) or (ExpStates =:= []) or (NStates =:= ExpStates) ->
            St1;
        true ->
            add_warning(none, {n_states, ExpStates, NStates}, St1)
    end.

pack_errors([{File,_} | _] = Es) ->
    [{File, flatmap(fun({_,E}) -> [E] end, sort(Es))}];
pack_errors([]) ->
    [].
    
pack_warnings([{File,_} | _] = Ws) ->
    [{File, flatmap(fun({_,W}) -> [W] end, sort(Ws))}];
pack_warnings([]) ->
    [].

report_errors(St) ->
    case member(report_errors, St#yecc.options) of
        true ->
            foreach(fun({File,{none,Mod,E}}) -> 
                            io:fwrite("~s: ~s\n", [File,Mod:format_error(E)]);
                       ({File,{Line,Mod,E}}) -> 
                            io:fwrite("~s:~w: ~s\n", 
                                      [File,Line,Mod:format_error(E)])
                    end, sort(St#yecc.errors));
        false -> 
            ok
    end.

report_warnings(St) ->
    case member(report_warnings, St#yecc.options) of
        true ->
            foreach(fun({File,{none,Mod,W}}) -> 
                            io:fwrite("~s: Warning: ~s\n", 
                                      [File,Mod:format_error(W)]);
                       ({File,{Line,Mod,W}}) -> 
                            io:fwrite("~s:~w: Warning: ~s\n", 
                                      [File,Line,Mod:format_error(W)])
                    end, sort(St#yecc.warnings));
        false -> 
            ok
    end.

add_error(E, St) ->
    add_error(none, E, St).

add_error(Line, E, St) ->
    add_error(St#yecc.infile, Line, E, St).

add_error(File, Line, E, St) ->
    St#yecc{errors = [{File,{Line,?MODULE,E}}|St#yecc.errors]}.    

add_errors(SymNames, E0, St0) ->
    foldl(fun(SymName, St) ->
                  add_error(symbol_line(SymName, St), {E0, SymName}, St)
          end, St0, SymNames).

add_warning(Line, W, St) ->
    St#yecc{warnings = [{St#yecc.infile,{Line,?MODULE,W}}|St#yecc.warnings]}.

add_warnings(SymNames, W0, St0) ->
    foldl(fun(SymName, St) ->
                  add_warning(symbol_line(SymName, St), {W0, SymName}, St)
          end, St0, SymNames).

check_rhs([#symbol{name = '$empty'}], St) ->
    St;
check_rhs(Rhs, St0) ->
    case symbol_search('$empty', Rhs) of
        {value, #symbol{line = Line}} ->
            add_error(Line, illegal_empty, St0);
        false ->
            foldl(fun(Sym, St) ->
                          case symbol_member(Sym, St#yecc.all_symbols) of
                              true -> 
                                  St;
                              false -> 
                                  E = {undefined_symbol,Sym#symbol.name},
                                  add_error(Sym#symbol.line, E, St)
                          end
                  end, St0, Rhs)
    end.

%% This is not necessary, but if the compiler finds syntax errors in
%% actions, ugly messages may be given.
check_action(Tokens, St) ->
    case erl_parse:parse_exprs(add_roberts_dot(Tokens, 0)) of
        {error, {ErrorLine, Mod, What}} ->
            add_error(ErrorLine, {error, Mod, What}, St);
        {ok, _Exprs} ->
            St
    end.

add_roberts_dot([], Line) ->
    [{'dot', Line}];
add_roberts_dot([{'dot', Line} | _], _) ->
    [{'dot', Line}];
add_roberts_dot([Token | Tokens], _) ->
    [Token | add_roberts_dot(Tokens, element(2, Token))].

subst_pseudo_vars([], _, St) ->
    {[], St};
subst_pseudo_vars([H0 | T0], NmbrOfDaughters, St0) ->
    {H, St1} = subst_pseudo_vars(H0, NmbrOfDaughters, St0),
    {T, St} = subst_pseudo_vars(T0, NmbrOfDaughters, St1),
    {[H | T], St};
subst_pseudo_vars({atom, Line, Atom}, NmbrOfDaughters, St0) ->
    case atom_to_list(Atom) of
        [$$ | Rest] ->
            try list_to_integer(Rest) of
                N when N > 0, N =< NmbrOfDaughters ->
                    {{var, Line, list_to_atom(append("__", Rest))}, St0};
                _ ->
                    St = add_error(Line, {undefined_pseudo_variable, Atom}, 
                                   St0),
                    {{atom, Line, '$undefined'}, St}
            catch 
                error: _ -> {{atom, Line, Atom}, St0}
            end;
        _ ->
            {{atom, Line, Atom}, St0}
    end;
subst_pseudo_vars(Tuple, NmbrOfDaughters, St0) when is_tuple(Tuple) ->
    {L, St} = subst_pseudo_vars(tuple_to_list(Tuple), NmbrOfDaughters, St0),
    {list_to_tuple(L), St};
subst_pseudo_vars(Something_else, _, St) ->
    {Something_else, St}.

kind_of_symbol(St, SymName) ->
    case member(SymName, St#yecc.nonterminals) of
        false ->
            case member(SymName, St#yecc.terminals) of
                false ->
                    case St#yecc.endsymbol of
                        SymName ->
                            endsymbol;
                        _ ->
                            unknown
                    end;
                true ->
                    terminal
            end;
        true ->
            nonterminal
    end.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Computing parse states and goto table from grammar.
% Start item: {0, [Endsymbol]} <->
% (['ACCEPT' '.', Rootsymbol], {'$'}) in Aho & Johnson
% where '$end' is the default end of input symbol of the
% scanner if no 'Endsymbol' has been declared in the syntax file.

-record(tabs, {
          symbols,      % ETS-set, keypos 1: {SymbolName, SymbolCode}
          inv_symbols,  % ETS-set, keypos 2: {SymbolName, SymbolCode}
          state_id,     % ETS-bag, keypos 1: {StateId, StateNum}
                        % StateId is not unique for a state.
          rp_rhs,       % rule pointer -> the remaining rhs symbols
          rp_info,      % rule pointer -> expanding rules and lookahead
          goto          % ETS-bag, keypos 1: first 
                        % {{FromStateNum, Symbol, ToStateNum}}, then
                        % {{FromStateNum, Symbol}, ToStateNum}
         }).

-record(item, { % what states are made of
          rule_pointer,
          look_ahead,
          rhs
         }).

compute_states(St0) ->
    SymbolTab = St0#yecc.symbol_tab,
    CodedRules = map(fun(#rule{symbols = Syms} = R) ->
                             R#rule{symbols = code_symbols(Syms, SymbolTab)}
                     end, St0#yecc.rules_list),
    CodedNonterminals = code_symbols(St0#yecc.nonterminals, SymbolTab),
    %% Only coded in this phase; StC is thrown away.
    StC = St0#yecc{rules_list = CodedRules, 
                   rules = list_to_tuple(CodedRules),
                   nonterminals = CodedNonterminals},
    {RuleIndex, RulePointer2Rule} = 
        make_rule_index(StC, St0#yecc.rules_list),
    StateTab0 = {},
    StateIdTab = ets:new(yecc_state_id, [set]),
    GotoTab = ets:new(yecc_goto, [bag]),
    RulePointerRhs = make_rhs_index(StC#yecc.rules_list),
    RulePointerInfo = make_rule_pointer_info(StC, RulePointerRhs, RuleIndex),

    Tables = #tabs{symbols = SymbolTab, 
                   state_id = StateIdTab,
                   rp_rhs = RulePointerRhs,
                   rp_info = RulePointerInfo,
                   goto = GotoTab},

    erase(),
    EndsymCode = code_terminal(StC#yecc.endsymbol, StC#yecc.symbol_tab),
    {StateId, State0} = compute_state([{EndsymCode, 1}], Tables),

    StateNum0 = first_state(),
    FirstState = {StateNum0, State0},
    StateTab1 = insert_state(Tables, StateTab0, FirstState, StateId),
    {StateTab, N} = 
        compute_states1([{StateNum0, get_current_symbols(State0)}], 
                        FirstState, StateTab1, Tables),
    true = ets:delete(StateIdTab),
    St = St0#yecc{state_tab = StateTab, goto_tab = GotoTab, n_states = N,
                  rule_pointer2rule = RulePointer2Rule},
    decode_goto(GotoTab, St#yecc.inv_symbol_tab),
    check_usage(St).

first_state() ->
    0.

decode_goto(GotoTab, InvSymTab) ->
    G = ets:tab2list(GotoTab),
    ets:delete_all_objects(GotoTab),
    ets:insert(GotoTab, 
               map(fun({{From, Sym, Next}}) ->
                           {{From, decode_symbol(Sym, InvSymTab)}, Next}
                   end, G)).

check_usage(St0) ->
    SelSyms = ets:fun2ms(fun({{_,Sym},_}) -> Sym end),
    UsedSymbols = ets:select(St0#yecc.goto_tab, SelSyms),
    Syms = ordsets:from_list([?ACCEPT, '$empty' | UsedSymbols]),
    NonTerms = ordsets:from_list(St0#yecc.nonterminals),
    UnusedNonTerms = ordsets:to_list(ordsets:subtract(NonTerms, Syms)),
    St1 = add_warnings(UnusedNonTerms, unused_nonterminal, St0),
    Terms = ordsets:from_list(St0#yecc.terminals),
    St2 = add_warnings(ordsets:to_list(ordsets:subtract(Terms, Syms)),
                       unused_terminal, St1),
    DefinedNonTerminals = map(fun(#rule{symbols = [Name | _]}) -> 
                                            Name
                              end, St2#yecc.rules_list),
    DefNonTerms = ordsets:from_list(DefinedNonTerminals),
    UndefNonTerms = ordsets:subtract(NonTerms, DefNonTerms),
    add_errors(ordsets:to_list(ordsets:subtract(UndefNonTerms, 
                                                UnusedNonTerms)),
               missing_syntax_rule, St2).

%% States are sometimes big, should not be copied to ETS tables.
%% Here an "extendible" tuple is used.
lookup_state(StateTab, N) ->
    element(N+1, StateTab).

insert_state(#tabs{state_id = StateIdTab}, StateTab0, State, StateId) ->
    {N, _Items} = State,
    insert_state_id(StateIdTab, N, StateId),
    StateTab = if 
                   size(StateTab0) > N ->
                       StateTab0;