yecc.erl

OTP是开放电信平台的简称

%% ``The contents of this file are subject to the Erlang Public License,
%% Version 1.1, (the "License"); you may not use this file except in
%% compliance with the License. You should have received a copy of the
%% Erlang Public License along with this software. If not, it can be
%% retrieved via the world wide web at http://www.erlang.org/.
%% 
%% Software distributed under the License is distributed on an "AS IS"
%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
%% the License for the specific language governing rights and limitations
%% under the License.
%% 
%% The Initial Developer of the Original Code is Ericsson Utvecklings AB.
%% Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
%% AB. All Rights Reserved.''
%% 
%%     $Id $
%%
%% Yacc like LALR-1 parser generator for Erlang.
%% Ref: Aho & Johnson: "LR Parsing", ACM Computing Surveys, vol. 6:2, 1974.
%% Auxiliary files: yeccgramm.yrl, yeccparser.erl, yeccpre.hrl, yeccscan.erl.
%%

-module(yecc).

-export([compile/3, file/1, file/2, format_error/1]).

%% Kept for compatibility with R10B.
-export([yecc/2, yecc/3, yecc/4]).

-import(lists, [append/1, append/2, concat/1, delete/2, filter/2,
                flatmap/2, foldl/3, foldr/3, foreach/2, keydelete/3,
                keysearch/3, keysort/2, last/1, map/2, member/2,
                reverse/1, sort/1, usort/1]).

-include("erl_compile.hrl").
-include("ms_transform.hrl").

%% By default one function, yeccgoto/2, is generated. It is possible
%% to split this (often huge) function into several functions. The
%% effect is however not measurable.
-define(pre_ets, 1).
-ifdef(pre_ets).
  -define(select(Old, New), Old).
-else.
  -define(select(Old, New), New).
-endif.    

-record(yecc, {
          infile,
          outfile,
          includefile,
          module,
          options = [],
          verbose = false,
          file_attrs = true,
          errors = [],
          warnings = [],
          conflicts_done = false,
          shift_reduce = [],
          reduce_reduce = [],
          n_states = 0,
          inport,
          outport,

          parse_actions,
          symbol_tab,
          inv_symbol_tab,
          state_tab,
          prec_tab,
          goto_tab,

          terminals = [],
          nonterminals = [],
          all_symbols = [],
          prec = [],
          rules_list = [],
          rules, % a tuple of rules_list
          rule_pointer2rule,
          rootsymbol = [],
          endsymbol = [],
          expect_shift_reduce = [],
          expect_n_states = [],
          erlang_code = none
         }).

-record(rule, {
          n,       % rule n in the grammar file
          line,
          symbols, % the names of symbols
          tokens
         }).

-record(reduce, {
          rule_nmbr,
          head,
          nmbr_of_daughters,
          prec,
          unused % assure that #reduce{} comes before #shift{} when soring
         }).

-record(shift, {
          state,
          pos,
          prec,
          rule_nmbr
         }).

-record(user_code, {state, terminal, funname, action}).

-record(symbol, {line = none, name}).

%% ACCEPT is neither an atom nor a non-terminal.
-define(ACCEPT, {}).

%% During the phase 'compute_states' terminals in lookahead sets are
%% coded as integers; sets of terminals are integer bit masks. This is
%% for efficiency only. '$empty' is always given the mask 1. The
%% behaviour can be turned off by un-defining SYMBOLS_AS_CODES (useful
%% when debugging).

%% Non-terminals are also given integer codes, starting with -1. The
%% absolut value of the code is used for indexing a tuple of lists of
%% rules.

-define(SYMBOLS_AS_CODES, true).

-ifdef(SYMBOLS_AS_CODES).
-define(EMPTY, 0).
-else.
-define(EMPTY, '$empty').
-endif.

%%%
%%% Exported functions
%%%

%%% Interface to erl_compile.

compile(Input0, Output0, 
        #options{warning = WarnLevel, verbose=Verbose, includes=Includes}) ->
    Input = shorten_filename(Input0),
    Output = shorten_filename(Output0),
    Includefile = lists:sublist(Includes, 1),
    Opts = [{parserfile,Output}, {includefile,Includefile}, {verbose,Verbose},
            {report_errors, true}, {report_warnings, WarnLevel > 0}],
    case file(Input, Opts) of
        {ok, _OutFile} ->
            ok;
        error ->
            error
    end.

format_error(bad_declaration) ->
    io_lib:fwrite("unknown or bad declaration, ignored", []);
format_error({bad_expect, SymName}) ->
    io_lib:fwrite("argument ~s of Expect is not an integer", 
                  [format_symbol(SymName)]);
format_error({bad_rootsymbol, SymName}) ->
    io_lib:fwrite("rootsymbol ~s is not a nonterminal", 
                  [format_symbol(SymName)]);
format_error({bad_states, SymName}) ->
    io_lib:fwrite("argument ~s of States is not an integer", 
                  [format_symbol(SymName)]);
format_error({conflict, Conflict}) ->
    format_conflict(Conflict);
format_error({conflicts, SR, RR}) ->
    io_lib:fwrite("conflicts: ~w shift/reduce, ~w reduce/reduce", [SR, RR]);
format_error({duplicate_declaration, Tag}) ->
    io_lib:fwrite("duplicate declaration of ~s", [atom_to_list(Tag)]);
format_error({duplicate_nonterminal, Nonterminal}) ->
    io_lib:fwrite("duplicate non-terminals ~s", 
                  [format_symbol(Nonterminal)]);
format_error({duplicate_precedence, Op}) ->
    io_lib:fwrite("duplicate precedence operator ~s", 
                  [format_symbol(Op)]);
format_error({duplicate_terminal, Terminal}) ->
    io_lib:fwrite("duplicate terminal ~s", 
                  [format_symbol(Terminal)]);
format_error({endsymbol_is_nonterminal, Symbol}) ->
    io_lib:fwrite("endsymbol ~s is a nonterminal", 
                  [format_symbol(Symbol)]);
format_error({endsymbol_is_terminal, Symbol}) ->
    io_lib:fwrite("endsymbol ~s is a terminal", 
                  [format_symbol(Symbol)]);
format_error({error, Module, Error}) ->
    Module:format_error(Error);
format_error({file_error, Reason}) ->
    io_lib:fwrite("~s",[file:format_error(Reason)]);
format_error(illegal_empty) ->
    io_lib:fwrite("illegal use of empty symbol", []);
format_error({internal_error, Error}) ->
    io_lib:fwrite("internal yecc error: ~w", [Error]);
format_error({missing_syntax_rule, Nonterminal}) ->
    io_lib:fwrite("no syntax rule for non-terminal symbol ~s",
                  [format_symbol(Nonterminal)]);
format_error({n_states, Exp, N}) ->
    io_lib:fwrite("expected ~w states, but got ~p states", [Exp, N]);
format_error(no_grammar_rules) ->
    io_lib:fwrite("grammar rules are missing", []);
format_error(nonterminals_missing) ->
    io_lib:fwrite("Nonterminals is missing", []);
format_error({precedence_op_is_endsymbol, SymName}) ->
    io_lib:fwrite("precedence operator ~s is endsymbol",
                  [format_symbol(SymName)]);
format_error({precedence_op_is_unknown, SymName}) ->
    io_lib:fwrite("unknown precedence operator ~s",
                  [format_symbol(SymName)]);
format_error({reserved, N}) ->
    io_lib:fwrite("the use of ~w should be avoided", [N]);
format_error({symbol_terminal_and_nonterminal, SymName}) ->
    io_lib:fwrite("symbol ~s is both a terminal and nonterminal",
                  [format_symbol(SymName)]);
format_error(rootsymbol_missing) ->
    io_lib:fwrite("Rootsymbol is missing", []);
format_error(terminals_missing) ->
    io_lib:fwrite("Terminals is missing", []);
format_error({undefined_nonterminal, Symbol}) ->
    io_lib:fwrite("undefined nonterminal: ~s", [format_symbol(Symbol)]);
format_error({undefined_pseudo_variable, Atom}) ->
    io_lib:fwrite("undefined pseudo variable ~w", [Atom]);
format_error({undefined_symbol, SymName}) ->
    io_lib:fwrite("undefined rhs symbol ~s", [format_symbol(SymName)]);
format_error({unused_nonterminal, Nonterminal}) ->
    io_lib:fwrite("non-terminal symbol ~s not used", 
                  [format_symbol(Nonterminal)]);
format_error({unused_terminal, Terminal}) ->
    io_lib:fwrite("terminal symbol ~s not used", 
                  [format_symbol(Terminal)]).

file(File) ->
    file(File, [report_errors, report_warnings]).

file(File, Options) ->
    case is_filename(File) of
        no -> erlang:error(badarg, [File, Options]);
        _ -> ok
    end,
    case options(Options) of
        badarg ->
            erlang:error(badarg, [File, Options]);
        OptionValues ->
            Self = self(),
            Flag = process_flag(trap_exit, false),
            Pid = spawn_link(fun() -> infile(Self, File, OptionValues) end),
            receive
                {Pid, Rep} -> 
                    receive after 1 -> ok end,
                    process_flag(trap_exit, Flag),
                    Rep
            end
    end.

%% Kept for backward compatibility.
yecc(Infile, Outfile) ->
    yecc(Infile, Outfile, false, []).

yecc(Infile, Outfile, Verbose) ->
    yecc(Infile, Outfile, Verbose, []).

yecc(Infilex, Outfilex, Verbose, Includefilex) ->
    statistics(runtime),
    case file(Infilex, [{parserfile, Outfilex}, 
                        {verbose, Verbose}, 
                        {report, true},
                        {includefile, Includefilex}]) of
        {ok, _File} ->
            statistics(runtime);
        error ->
            exit(error)
    end.

%%%
%%% Local functions
%%%

options(Options0) when is_list(Options0) ->
    try 
        Options = flatmap(fun(return) -> short_option(return, true);
                             (report) -> short_option(report, true);
                             ({return,T}) -> short_option(return, T);
                             ({report,T}) -> short_option(report, T);
                             (T) -> [T]
                          end, Options0),
        options(Options, [file_attributes, includefile, parserfile, 
                          report_errors, report_warnings, return_errors, 
                          return_warnings, time, verbose], [])
    catch error: _ -> badarg
    end;
options(Option) ->
    options([Option]).

short_option(return, T) ->
    [{return_errors,T}, {return_warnings,T}];
short_option(report, T) ->
    [{report_errors,T}, {report_warnings,T}].

options(Options0, [Key | Keys], L) when is_list(Options0) ->
    Options = case member(Key, Options0) of
                  true -> 
                      [atom_option(Key) | delete(Key, Options0)];
                  false ->
                      Options0
              end,
    V = case keysearch(Key, 1, Options) of
            {value, {Key, Filename0}} when Key =:= includefile; 
                                           Key =:= parserfile ->
                case is_filename(Filename0) of
                    no -> 
                        badarg;
                    Filename -> 
                        {ok, [{Key, Filename}]}
                end;
            {value, {Key, Bool}} when Bool =:= true; Bool =:= false ->
                {ok, [{Key, Bool}]};
            {value, {Key, _}} ->
                badarg;
            false ->
                {ok, [{Key, default_option(Key)}]}
        end,
    case V of
        badarg ->
            badarg;
        {ok, KeyValueL} ->
            NewOptions = keydelete(Key, 1, Options),
            options(NewOptions, Keys, KeyValueL ++ L)
    end;
options([], [], L) ->
    foldl(fun({_,false}, A) -> A;
             ({Tag,true}, A) -> [Tag | A];
             (F, A) -> [F | A]
          end, [], L);
options(_Options, _, _L) ->
    badarg.

default_option(file_attributes) -> true;
default_option(includefile) -> [];
default_option(parserfile) -> [];
default_option(report_errors) -> true;
default_option(report_warnings) -> true;
default_option(return_errors) -> false;
default_option(return_warnings) -> false;
default_option(time) -> false;
default_option(verbose) -> false.

atom_option(file_attributes) -> {file_attributes, true};
atom_option(report_errors) -> {report_errors, true};
atom_option(report_warnings) -> {report_warnings, true};
atom_option(return_errors) -> {return_errors, true};
atom_option(return_warnings) -> {return_warnings, true};
atom_option(time) -> {time, true};