diff options
Diffstat (limited to 'lib/parsetools/src/yecc.erl')
| -rw-r--r-- | lib/parsetools/src/yecc.erl | 2531 |
1 files changed, 2531 insertions, 0 deletions
diff --git a/lib/parsetools/src/yecc.erl b/lib/parsetools/src/yecc.erl new file mode 100644 index 0000000000..f4d76f471d --- /dev/null +++ b/lib/parsetools/src/yecc.erl @@ -0,0 +1,2531 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 1996-2009. All Rights Reserved. +%% +%% 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 online 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. +%% +%% %CopyrightEnd% +%% +%% 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"). + +-record(yecc, { + infile, + outfile, + includefile, + includefile_version, + module, + options = [], + verbose = false, + file_attrs = true, + errors = [], + warnings = [], + conflicts_done = false, + shift_reduce = [], + reduce_reduce = [], + n_states = 0, + inport, + outport, + line, + + 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 = [], + header = [], + erlang_code = none + }). + +-record(rule, { + n, % rule n in the grammar file + line, + symbols, % the names of symbols + tokens, + is_guard, % the action is a guard (not used) + is_well_formed % can be parsed (without macro expansion) + }). + +-record(reduce, { + rule_nmbr, + head, + nmbr_of_daughters, + prec, + unused % assure that #reduce{} comes before #shift{} when sorting + }). + +-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}; +atom_option(verbose) -> {verbose, true}; +atom_option(Key) -> Key. + +is_filename(T) -> + try filename:flatten(T) of + Filename -> Filename + catch error: _ -> no + end. + +shorten_filename(Name0) -> + {ok,Cwd} = file:get_cwd(), + case lists:prefix(Cwd, Name0) of + false -> Name0; + true -> + case lists:nthtail(length(Cwd), Name0) of + "/"++N -> N; + N -> N + end + end. + +start(Infilex, Options) -> + Infile = assure_extension(Infilex, ".yrl"), + {value, {_, Outfilex0}} = keysearch(parserfile, 1, Options), + {value, {_, Includefilex}} = keysearch(includefile, 1, Options), + Outfilex = case Outfilex0 of + [] -> filename:rootname(Infilex, ".yrl"); + _ -> Outfilex0 + end, + Includefile = case Includefilex of + [] -> []; + _ -> assure_extension(Includefilex,".hrl") + end, + IncludefileVersion = includefile_version(Includefile), + Outfile = assure_extension(Outfilex, ".erl"), + Module = list_to_atom(filename:basename(Outfile, ".erl")), + #yecc{infile = Infile, + outfile = Outfile, + includefile = Includefile, + includefile_version = IncludefileVersion, + module = Module, + options = Options, + verbose = member(verbose, Options), + file_attrs = member(file_attributes, Options)}. + +assure_extension(File, Ext) -> + concat([strip_extension(File, Ext), Ext]). + +%% Assumes File is a filename. +strip_extension(File, Ext) -> + case filename:extension(File) of + Ext -> filename:rootname(File); + _Other -> File + end. + +infile(Parent, Infilex, Options) -> + St0 = start(Infilex, Options), + St = case file:open(St0#yecc.infile, [read, read_ahead]) of + {ok, Inport} -> + try + outfile(St0#yecc{inport = Inport}) + after + ok = file:close(Inport) + end; + {error, Reason} -> + add_error(St0#yecc.infile, none, {file_error, Reason}, St0) + end, + case St#yecc.errors of + [] -> ok; + _ -> _ = file:delete(St#yecc.outfile) + end, + Parent ! {self(), yecc_ret(St)}. + +outfile(St0) -> + case file:open(St0#yecc.outfile, [write, delayed_write]) of + {ok, Outport} -> + try + generate(St0#yecc{outport = Outport, line = 1}) + catch + throw: St1 -> + St1; + exit: Reason -> + add_error({internal_error, Reason}, St0) + after + ok = file:close(Outport) + end; + {error, Reason} -> + add_error(St0#yecc.outfile, none, {file_error, Reason}, St0) + end. + +os_process_size() -> + case os:type() of + {unix, sunos} -> + Size = os:cmd("ps -o vsz -p " ++ os:getpid() ++ " | tail -1"), + list_to_integer(lib:nonl(Size)); + _ -> + 0 + end. + +timeit(Name, Fun, St0) -> + Time = runtime, + %% Time = wall_clock, + {Before, _} = statistics(Time), + St = Fun(St0), + {After, _} = statistics(Time), + Mem0 = erts_debug:flat_size(St)*erlang:system_info(wordsize), + Mem = lists:flatten(io_lib:format("~.1f kB", [Mem0/1024])), + Sz = lists:flatten(io_lib:format("~.1f MB", [os_process_size()/1024])), + io:fwrite(" ~-30w: ~10.2f s ~12s ~10s\n", + [Name, (After-Before)/1000, Mem, Sz]), + St. + +-define(PASS(P), {P, fun P/1}). + +generate(St0) -> + Passes = [?PASS(parse_grammar), ?PASS(check_grammar), + ?PASS(states_and_goto_table), ?PASS(parse_actions), + ?PASS(action_conflicts), ?PASS(write_file)], + F = case member(time, St0#yecc.options) of + true -> + io:fwrite(<<"Generating parser from grammar in ~s\n">>, + [format_filename(St0#yecc.infile)]), + fun timeit/3; + false -> + fun(_Name, Fn, St) -> Fn(St) end + end, + Fun = fun({Name, Fun}, St) -> + St2 = F(Name, Fun, St), + if + St2#yecc.errors =:= [] -> St2; + true -> throw(St2) + end + end, + foldl(Fun, St0, Passes). + +parse_grammar(St) -> + parse_grammar(St#yecc.inport, 1, St). + +parse_grammar(Inport, Line, St) -> + {NextLine, Grammar} = read_grammar(Inport, Line), + parse_grammar(Grammar, Inport, NextLine, St). + +parse_grammar(eof, _Inport, _NextLine, St) -> + St; +parse_grammar({#symbol{name = 'Header'}, Ss}, Inport, NextLine, St0) -> + St1 = St0#yecc{header = [S || {string,_,S} <- Ss]}, + parse_grammar(Inport, NextLine, St1); +parse_grammar({#symbol{name = 'Erlang'}, [#symbol{name = code}]}, _Inport, + NextLine, St) -> + St#yecc{erlang_code = NextLine}; +parse_grammar(Grammar, Inport, NextLine, St0) -> + St = parse_grammar(Grammar, St0), + parse_grammar(Inport, NextLine, St). + +parse_grammar({error,ErrorLine,Error}, St) -> + add_error(ErrorLine, Error, St); +parse_grammar({rule, Rule, Tokens}, St0) -> + NmbrOfDaughters = case Rule of + [_, #symbol{name = '$empty'}] -> 0; + _ -> length(Rule) - 1 + end, + {IsGuard, IsWellFormed} = check_action(Tokens), + {Tokens1, St} = subst_pseudo_vars(Tokens, + NmbrOfDaughters, + St0), + RuleDef = #rule{symbols = Rule, + tokens = Tokens1, + is_guard = IsGuard, + is_well_formed = IsWellFormed}, + St#yecc{rules_list = [RuleDef | St#yecc.rules_list]}; +parse_grammar({prec, Prec}, St) -> + St#yecc{prec = Prec ++ St#yecc.prec}; +parse_grammar({#symbol{line = Line, name = Name}, Symbols}, St) -> + CF = fun(I) -> + case element(I, St) of + [] -> + setelement(I, St, Symbols); + _ -> + add_error(Line, {duplicate_declaration, Name}, St) + end + end, + OneSymbol = length(Symbols) =:= 1, + case Name of + 'Nonterminals' -> CF(#yecc.nonterminals); + 'Terminals' -> CF(#yecc.terminals); + 'Rootsymbol' when OneSymbol -> CF(#yecc.rootsymbol); + 'Endsymbol' when OneSymbol -> CF(#yecc.endsymbol); + 'Expect' when OneSymbol -> CF(#yecc.expect_shift_reduce); + 'States' when OneSymbol -> CF(#yecc.expect_n_states); % undocumented + _ -> add_warning(Line, bad_declaration, St) + end. + +read_grammar(Inport, Line) -> + case yeccscan:scan(Inport, '', Line) of + {eof, NextLine} -> + {NextLine, eof}; + {error, {ErrorLine, Mod, What}, NextLine} -> + {NextLine, {error, ErrorLine, {error, Mod, What}}}; + {ok, Input, NextLine} -> + {NextLine, case yeccparser:parse(Input) of + {error, {ErrorLine, Mod, Message}} -> + {error, ErrorLine, {error, Mod, Message}}; + {ok, {rule, Rule, {erlang_code, Tokens}}} -> + {rule, Rule, Tokens}; + {ok, {#symbol{name=P}, + [#symbol{name=I} | OpL]}=Ss} -> + A = precedence(P), + if + A =/= unknown, + is_integer(I), + OpL =/= [] -> + Ps = [{Op, I , A} || Op <- OpL], + {prec, Ps}; + true -> + Ss + end; + {ok, Ss} -> + Ss + end} + end. + +precedence('Left') -> left; +precedence('Right') -> right; +precedence('Unary') -> unary; +precedence('Nonassoc') -> nonassoc; +precedence(_) -> unknown. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +check_grammar(St0) -> + Empty = #symbol{line = none, name = '$empty'}, + AllSymbols = St0#yecc.nonterminals ++ St0#yecc.terminals ++ [Empty], + St1 = St0#yecc{all_symbols = AllSymbols}, + Cs = [fun check_nonterminals/1, fun check_terminals/1, + fun check_rootsymbol/1, fun check_endsymbol/1, + fun check_expect/1, fun check_states/1, + fun check_precedences/1, fun check_rules/1], + foldl(fun(F, St) -> F(St) end, St1, Cs). + +check_nonterminals(St) -> + case St#yecc.nonterminals of + [] -> + add_error(nonterminals_missing, St); + Nonterminals -> + {Unique, Dups} = duplicates(names(Nonterminals)), + St1 = add_warnings(Dups, duplicate_nonterminal, St), + St2 = check_reserved(Unique, St1), + St2#yecc{nonterminals = [?ACCEPT | Unique]} + end. + +check_terminals(St0) -> + case St0#yecc.terminals of + [] -> + add_error(terminals_missing, St0); + Terminals -> + {Unique, Dups} = duplicates(names(Terminals)), + St1 = add_warnings(Dups, duplicate_terminal, St0), + Common = intersect(St1#yecc.nonterminals, Unique), + St2 = add_errors(Common, symbol_terminal_and_nonterminal, St1), + St3 = check_reserved(Unique, St2), + St3#yecc{terminals = ['$empty' | Unique]} + end. + +check_reserved(Names, St) -> + add_errors(intersect(Names, ['$empty', '$end', '$undefined']), + reserved, St). + +check_rootsymbol(St) -> + case St#yecc.rootsymbol of + [] -> + add_error(rootsymbol_missing, St); + [#symbol{line = Line, name = SymName}] -> + case kind_of_symbol(St, SymName) of + nonterminal -> + St#yecc{rootsymbol = SymName}; + _ -> + add_error(Line, {bad_rootsymbol, SymName}, St) + end + end. + +check_endsymbol(St) -> + case St#yecc.endsymbol of + [] -> + St#yecc{endsymbol = '$end'}; + [#symbol{line = Line, name = SymName}] -> + case kind_of_symbol(St, SymName) of + nonterminal -> + add_error(Line, {endsymbol_is_nonterminal, SymName}, St); + terminal -> + add_error(Line, {endsymbol_is_terminal, SymName}, St); + _ -> + St#yecc{endsymbol = SymName} + end + end. + +check_expect(St0) -> + case St0#yecc.expect_shift_reduce of + [] -> + St0#yecc{expect_shift_reduce = 0}; + [#symbol{name = Expect}] when is_integer(Expect) -> + St0#yecc{expect_shift_reduce = Expect}; + [#symbol{line = Line, name = Name}] -> + St1 = add_error(Line, {bad_expect, Name}, St0), + St1#yecc{expect_shift_reduce = 0} + end. + +check_states(St) -> + case St#yecc.expect_n_states of + [] -> + St; + [#symbol{name = NStates}] when is_integer(NStates) -> + St#yecc{expect_n_states = NStates}; + [#symbol{line = Line, name = Name}] -> + add_error(Line, {bad_states, Name}, St) + end. + +check_precedences(St0) -> + {St1, _} = + foldr(fun({#symbol{line = Line, name = Op},_I,_A}, {St,Ps}) -> + case member(Op, Ps) of + true -> + {add_error(Line, {duplicate_precedence,Op}, St), + Ps}; + false -> + {St, [Op | Ps]} + end + end, {St0,[]}, St0#yecc.prec), + foldl(fun({#symbol{line = Line, name = Op},I,A}, St) -> + case kind_of_symbol(St, Op) of + endsymbol -> + add_error(Line,{precedence_op_is_endsymbol,Op}, St); + unknown -> + add_error(Line, {precedence_op_is_unknown, Op}, St); + _ -> + St#yecc{prec = [{Op,I,A} | St#yecc.prec]} + end + end, St1#yecc{prec = []}, St1#yecc.prec). + +check_rule(Rule0, {St0,Rules}) -> + Symbols = Rule0#rule.symbols, + #symbol{line = HeadLine, name = Head} = hd(Symbols), + case member(Head, St0#yecc.nonterminals) of + false -> + {add_error(HeadLine, {undefined_nonterminal, Head}, St0), Rules}; + true -> + St = check_rhs(tl(Symbols), St0), + Rule = Rule0#rule{line = HeadLine, symbols = names(Symbols)}, + {St, [Rule | Rules]} + end. + +check_rules(St0) -> + {St,Rules0} = foldl(fun check_rule/2, {St0,[]}, St0#yecc.rules_list), + case St#yecc.rules_list of + [] -> + add_error(no_grammar_rules, St); + _ -> + Rule = #rule{line = none, + symbols = [?ACCEPT, St#yecc.rootsymbol], + tokens = []}, + Rules1 = [Rule | Rules0], + Rules = map(fun({R,I}) -> R#rule{n = I} end, count(0, Rules1)), + 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}. + +-record(state_info, {reduce_only, state_repr, comment}). + +write_file(St0) -> + #yecc{parse_actions = ParseActions, goto_tab = GotoTab} = St0, + Sorted = sort_parse_actions(ParseActions), + StateReprs = find_identical_shift_states(Sorted), + StateInfo = collect_some_state_info(Sorted, StateReprs), + StateJumps = find_partial_shift_states(Sorted, StateReprs), + UserCodeActions = find_user_code(Sorted, St0), + #yecc{infile = Infile, outfile = Outfile, + inport = Inport, outport = Outport, + nonterminals = Nonterminals} = St0, + {St10, N_lines, LastErlangCodeLine} = + output_prelude(Outport, Inport, St0), + St20 = St10#yecc{line = St10#yecc.line + N_lines}, + St25 = nl(St20), + St30 = output_file_directive(St25, Outfile, St25#yecc.line), + St40 = nl(St30), + St50 = output_actions(St40, StateJumps, StateInfo), + Go0 = [{Symbol,{From,To}} || {{From,Symbol},To} <- ets:tab2list(GotoTab)], + Go = family_with_domain(Go0, Nonterminals), + St60 = output_goto(St50, Go, StateInfo), + St70 = output_inlined(St60, UserCodeActions, Infile), + St = nl(St70), + 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 -> + St + end. + +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. + +check_action(Tokens) -> + case erl_parse:parse_exprs(add_roberts_dot(Tokens, 0)) of + {error, _Error} -> + {false, false}; + {ok, [Expr | Exprs]} -> + IsGuard = Exprs =:= [] andalso erl_lint:is_guard_test(Expr), + {IsGuard, true} + 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 + tuple_size(StateTab0) > N -> + StateTab0; + 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) -> + {RulesL, _N} = + lists:mapfoldl(fun(#rule{symbols = [Nonterminal | Daughters]}, I) -> + I1 = I + length(Daughters)+1, + {{Nonterminal, I}, I1} + end, 1, RulesList), + IndexedTab = family_with_domain(RulesL, Nonterminals), + + Symbol2Rule = [{Foo,R} || #rule{symbols = Symbols}=R <- RulesListNoCodes, + Foo <- Symbols], + Pointer2Rule = [{I, R} || {{_Foo,R},I} <- count(1, Symbol2Rule)], + {dict:from_list(IndexedTab), dict:from_list(Pointer2Rule)}. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Computing parse action table from list of states and goto table: + +compute_parse_actions(N, St, StateActions) -> + case N < first_state() of + true -> + StateActions; + false -> + {N, StateN} = lookup_state(St#yecc.state_tab, N), + %% There can be duplicates in Actions. + Actions = compute_parse_actions1(StateN, N, St), + compute_parse_actions(N - 1, St, [{N, Actions} | StateActions]) + end. + +compute_parse_actions1([], _, _) -> + []; +compute_parse_actions1([#item{rule_pointer = RulePointer, + look_ahead = Lookahead0, + rhs = Rhs} | Items], N, St) -> + case Rhs of + [] -> + Lookahead = decode_terminals(Lookahead0, St#yecc.inv_symbol_tab), + case rule(RulePointer, St) of + {[?ACCEPT | _], _RuleLine, _} -> + [{Lookahead, accept} + | compute_parse_actions1(Items, N, St)]; + %% Head is placed after the daughters when finding the + %% precedence. This is how giving precedence to + %% non-terminals takes effect. + {[Head | Daughters0], _RuleLine, _} -> + Daughters = delete('$empty', Daughters0), + [{Lookahead, + #reduce{rule_nmbr = RulePointer, head = Head, + nmbr_of_daughters = length(Daughters), + prec = get_prec(Daughters ++ [Head], St)}} + | compute_parse_actions1(Items, N, St)] + end; + [Symbol | Daughters] -> + case is_terminal(St#yecc.symbol_tab, Symbol) of + true -> + DecSymbol = decode_symbol(Symbol, St#yecc.inv_symbol_tab), + {[Head | _], _RuleLine, _} = rule(RulePointer, St), + %% A bogus shift-shift conflict can be introduced + %% here if some terminal occurs in different rules + %% which have been given precedence "one level up". + Prec1 = case Daughters of + [] -> get_prec([DecSymbol, Head], St); + _ -> get_prec([DecSymbol], St) + end, + Pos = case Daughters of + [] -> z; + _ -> a + end, + [{[DecSymbol], + #shift{state = goto(N, DecSymbol, St), + pos = Pos, + prec = Prec1, + rule_nmbr = RulePointer}} + | compute_parse_actions1(Items, N, St)]; + false -> + compute_parse_actions1(Items, N, St) + end + end. + +get_prec(Symbols, St) -> + get_prec1(Symbols, St#yecc.prec_tab, {0, none}). + +get_prec1([], _, P) -> + P; +get_prec1([Symbol | T], PrecTab, P) -> + case ets:lookup(PrecTab, Symbol) of + [] -> + get_prec1(T, PrecTab, P); + [{_, N, Ass}] -> + get_prec1(T, PrecTab, {N, Ass}) + end. + +create_precedence_table(St) -> + PrecTab = ets:new(yecc_precedences, []), + true = ets:insert(PrecTab, St#yecc.prec), + St#yecc{prec_tab = PrecTab}. + +-record(cxt, {terminal, state_n, yecc, res}). + +%% Detects shift-reduce and reduce-reduce conflicts. +%% Also removes all but one conflicting action. As a consequence the +%% lookahead sets for a state are always disjoint. +%% Reduce/reduce conflicts are considered errors. +find_action_conflicts(St0) -> + Cxt0 = #cxt{yecc = St0, res = []}, + {#cxt{yecc = St, res = Res}, NewParseActions0} = + foldl(fun({N, Actions0}, {Cxt1, StateActions}) -> + L = [{Terminal, Act} || {Lookahead, Act} <- Actions0, + Terminal <- Lookahead], + {Cxt, Actions} = + foldl(fun({Terminal, As}, {Cxt2,Acts0}) -> + Cxt3 = Cxt2#cxt{terminal = Terminal, + state_n = N}, + {Action, Cxt} = + find_action_conflicts2(As, Cxt3), + {Cxt,[{Action,Terminal} | Acts0]} + end, {Cxt1,[]}, family(L)), + {Cxt,[{N,inverse(family(Actions))} | StateActions]} + end, {Cxt0, []}, St0#yecc.parse_actions), + if + length(Res) > 0, St#yecc.verbose -> + io:fwrite(<<"\n*** Conflicts resolved by operator " + "precedences:\n\n">>), + foreach(fun({Confl, Name}) -> + report_conflict(Confl, St, Name, prec) + end, reverse(Res)), + io:fwrite(<<"*** End of resolved conflicts\n\n">>); + true -> + ok + end, + NewParseActions = reverse(NewParseActions0), + St#yecc{parse_actions = NewParseActions}. + +find_action_conflicts2([Action], Cxt) -> + {Action, Cxt}; +find_action_conflicts2([#shift{state = St, pos = Pos, prec = Prec}, + #shift{state = St}=S | As], + Cxt) when Pos =:= a; Prec =:= {0,none} -> + %% This is a kludge to remove the bogus shift-shift conflict + %% introduced in compute_parse_actions1(). + find_action_conflicts2([S | As], Cxt); +find_action_conflicts2([#shift{state = NewState, pos = z}=S1, + #shift{state = NewState}=S2 | _], Cxt) -> + %% This is even worse than last clause. Give up. + Confl = conflict(S1, S2, Cxt), + #cxt{yecc = St0} = Cxt, + St = conflict_error(Confl, St0), + {S1, Cxt#cxt{yecc = St}}; % return any action +find_action_conflicts2([#shift{prec = {P1, Ass1}}=S | Rs], Cxt0) -> + {R, Cxt1} = find_reduce_reduce(Rs, Cxt0), + #cxt{res = Res0, yecc = St0} = Cxt1, + #reduce{prec = {P2, Ass2}} = R, + Confl = conflict(R, S, Cxt1), + if + P1 > P2 -> + {S, Cxt1#cxt{res = [{Confl, shift} | Res0]}}; + P2 > P1 -> + {R, Cxt1#cxt{res = [{Confl, reduce} | Res0]}}; + Ass1 =:= left, Ass2 =:= left -> + {R, Cxt1#cxt{res = [{Confl, reduce} | Res0]}}; + Ass1 =:= right, Ass2 =:= right -> + {S, Cxt1#cxt{res = [{Confl, shift} | Res0]}}; + Ass1 =:= nonassoc, Ass2 =:= nonassoc -> + {nonassoc, Cxt1}; + P1 =:= 0, P2 =:= 0 -> + report_conflict(Confl, St0, shift, default), + St = add_conflict(Confl, St0), + {S, Cxt1#cxt{yecc = St}}; + true -> + St = conflict_error(Confl, St0), + {S, Cxt1#cxt{yecc = St}} % return any action + end; +find_action_conflicts2(Rs, Cxt0) -> + find_reduce_reduce(Rs, Cxt0). + +find_reduce_reduce([R], Cxt) -> + {R, Cxt}; +find_reduce_reduce([#reduce{head = Categ1, prec = {P1, _}}=R1, + #reduce{head = Categ2, prec = {P2, _}}=R2 | Rs], Cxt0) -> + #cxt{res = Res0, yecc = St0} = Cxt0, + Confl = conflict(R1, R2, Cxt0), + {R, Res, St} = + if + P1 > P2 -> + {R1, [{Confl, Categ1} | Res0], St0}; + P2 > P1 -> + {R2, [{Confl, Categ2} | Res0], St0}; + true -> + St1 = conflict_error(Confl, St0), + {R1, Res0, St1} + end, + Cxt = Cxt0#cxt{res = Res, yecc = St}, + find_reduce_reduce([R | Rs], Cxt). + +%% Since the lookahead sets are disjoint (assured by +%% find_action_conflicts), the order between actions can be chosen +%% almost arbitrarily. nonassoc has to come last, though (but is later +%% discarded!). And shift has to come before reduce. +sort_parse_actions([]) -> + []; +sort_parse_actions([{N, La_actions} | Tail]) -> + [{N, sort_parse_actions1(La_actions)} | sort_parse_actions(Tail)]. + +sort_parse_actions1(LaActions) -> + As = filter(fun({_LA, A}) -> A =:= accept end, LaActions), + Ss = filter(fun({_LA, A}) -> is_record(A, shift) end, LaActions), + Rs = filter(fun({_LA, A}) -> is_record(A, reduce) end, LaActions), + Ns = filter(fun({_LA, A}) -> A =:= nonassoc end, LaActions), + As ++ Ss ++ Rs ++ Ns. + +%% -> {State, StateRepr}. StateRepr has the same set of shift actions +%% as State. No code will be output for State if State =/= StateRepr. +find_identical_shift_states(StateActions) -> + L1 = [{Actions, State} || {State,Actions} <- StateActions], + {SO, NotSO} = lists:partition(fun({Actions,_States}) -> + shift_actions_only(Actions) + end, family(L1)), + R = [{State, hd(States)} || {_Actions, States} <- SO, State <- States] + ++ + [{State, State} || {_Actions, States} <- NotSO, State <- States], + lists:keysort(1, R). + +-record(part_data, {name, eq_state, actions, n_actions, states}). + +%% Replace {SStates,Actions} with {SStates,{Actions,Jump}} where +%% Jump describes which clauses that have been extracted from shift +%% states so that they can be used from other states. Some space is +%% saved. +find_partial_shift_states(StateActionsL, StateReprs) -> + L = [{State, Actions} || {{State,Actions}, {State,State}} <- + lists:zip(StateActionsL, StateReprs), + shift_actions_only(Actions)], + StateActions = sofs:family(L, [{state,[action]}]), + StateAction = sofs:family_to_relation(StateActions), + + %% Two actions are equal if they occur in the same states: + Parts = sofs:partition(sofs:range(StateActions)), + PartsL = sofs:to_external(Parts), + %% Assign temporary names to the parts of the partition (of actions): + PartNameL = lists:zip(seq1(length(PartsL)), PartsL), + ActPartL = [{Action,PartName} || + {PartName,Actions} <- PartNameL, + Action <- Actions], + ActionPartName = sofs:relation(ActPartL, [{action,partname}]), + StatePartName = sofs:relative_product(StateAction, ActionPartName), + PartInStates = sofs:relation_to_family(sofs:converse(StatePartName)), + + %% Parts that equal all actions of a state: + PartActions = sofs:family(PartNameL, [{partname,[action]}]), + PartState = + sofs:relative_product(PartActions, sofs:converse(StateActions)), + PartStates = sofs_family_with_domain(PartState, sofs:domain(PartActions)), + + PartDataL = [#part_data{name = Nm, eq_state = EqS, actions = P, + n_actions = length(P), + states = ordsets:from_list(S)} || + {{Nm,P}, {Nm,S}, {Nm,EqS}} <- + lists:zip3(PartNameL, + sofs:to_external(PartInStates), + sofs:to_external(PartStates))], + true = length(PartDataL) =:= length(PartNameL), + Ps = select_parts(PartDataL), + + J1 = [{State, Actions, {jump_some,hd(States)}} || + {_W, #part_data{actions = Actions, eq_state = [], + states = States}} <- Ps, + State <- States], + J2 = [{State, Actions, {jump_all,To}} || + {_W, #part_data{actions = Actions, eq_state = EqS, + states = States}} <- Ps, + To <- EqS, + State <- States, + State =/= To], + J = lists:keysort(1, J1 ++ J2), + + JumpStates = ordsets:from_list([S || {S,_,_} <- J]), + {JS, NJS} = + sofs:partition(1, sofs:relation(StateActionsL, [{state, actions}]), + sofs:set(JumpStates, [state])), + R = + [{S, {Actions,jump_none}} || {S,Actions} <- sofs:to_external(NJS)] + ++ + [{S, {Actions--Part, {Tag,ToS,Part}}} || + {{S,Actions}, {S,Part,{Tag,ToS}}} <- + lists:zip(sofs:to_external(JS), J)], + true = length(StateActionsL) =:= length(R), + lists:keysort(1, R). + +%% Very greedy. By no means optimal. +select_parts([]) -> + []; +select_parts(PartDataL) -> + T1 = [{score(PD), PD} || PD <- PartDataL], + [{W, PD} | Ws] = lists:reverse(lists:keysort(1, T1)), + #part_data{n_actions = NActions, states = S} = PD, + if + W < 8 -> % don't bother + []; + true -> + %% Cannot extract more clauses from the chosen part's states: + NL = [D#part_data{states = NewS} || + {W1, #part_data{states = S0}=D} <- Ws, + W1 > 0, + (NewS = ordsets:subtract(S0, S)) =/= []], + if + length(S) =:= 1; NActions =:= 1 -> + select_parts(NL); + true -> + [{W,PD} | select_parts(NL)] + end + end. + +%% Does it pay off to extract clauses into a new function? +%% Assumptions: +%% - a call costs 8 (C = 8); +%% - a clause (per action) costs 20 plus 8 (select) (Cl = 28); +%% - a new function costs 20 (funinfo) plus 16 (select) (F = 36). +%% A is number of actions, S is number of states. +%% Special case (the part equals all actions of some state): +%% C * (S - 1) < (S - 1) * A * Cl +%% Normal case (introduce new function): +%% F + A * Cl + C * S < S * A * Cl +score(#part_data{n_actions = NActions, eq_state = [], states = S}) -> + (length(S) * NActions * 28) - (36 + NActions * 28 + length(S) * 8); +score(#part_data{n_actions = NActions, states = S}) -> + ((length(S) - 1) * NActions * 28) - (8 * (length(S) - 1)). + +shift_actions_only(Actions) -> + length([foo || {_Ts,{shift,_,_,_,_}} <- Actions]) =:= length(Actions). + +collect_some_state_info(StateActions, StateReprs) -> + RF = fun({_LA, A}) -> is_record(A, reduce) end, + L = [{State, + begin + RO = lists:all(RF, LaActions), + %% C is currently always ""; identical states are all shift. + C = [io_lib:fwrite(<<" %% ~w\n">>, [State]) || + true <- [RO], Repr =/= State], + #state_info{reduce_only = RO, state_repr = Repr, comment = C} + end} || + {{State, LaActions}, {State, Repr}} <- + lists:zip(StateActions, StateReprs)], + list_to_tuple(L). + +conflict_error(Conflict, St0) -> + St1 = add_conflict(Conflict, St0), + add_error({conflict, Conflict}, St1). + +report_conflict(Conflict, St, ActionName, How) -> + if + St#yecc.verbose -> + io:fwrite(<<"~s\n">>, [format_conflict(Conflict)]), + Formated = format_symbol(ActionName), + case How of + prec -> + io:fwrite(<<"Resolved in favor of ~s.\n\n">>, [Formated]); + default -> + io:fwrite(<<"Conflict resolved in favor of ~s.\n\n">>, + [Formated]) + end; + true -> + ok + end. + +add_conflict(Conflict, St) -> + case Conflict of + {Symbol, StateN, _, {reduce, _, _, _}} -> + St#yecc{reduce_reduce = [{StateN,Symbol} |St#yecc.reduce_reduce]}; + {Symbol, StateN, _, {shift, _, _}} -> + St#yecc{shift_reduce = [{StateN,Symbol} | St#yecc.shift_reduce]}; + {_Symbol, _StateN, {one_level_up, _, _}, _Confl} -> + St + end. + +conflict(#shift{prec = Prec1, rule_nmbr = RuleNmbr1}, + #shift{prec = Prec2, rule_nmbr = RuleNmbr2}, Cxt) -> + %% Conflict due to precedences "one level up". Kludge. + #cxt{terminal = Symbol, state_n = N, yecc = St} = Cxt, + {_, L1, RuleN1} = rule(RuleNmbr1, St), + {_, L2, RuleN2} = rule(RuleNmbr2, St), + Confl = {one_level_up, {L1, RuleN1, Prec1}, {L2, RuleN2, Prec2}}, + {Symbol, N, Confl, Confl}; +conflict(#reduce{rule_nmbr = RuleNmbr1}, NewAction, Cxt) -> + #cxt{terminal = Symbol, state_n = N, yecc = St} = Cxt, + {R1, RuleLine1, RuleN1} = rule(RuleNmbr1, St), + Confl = case NewAction of + #reduce{rule_nmbr = RuleNmbr2} -> + {R2, RuleLine2, RuleN2} = rule(RuleNmbr2, St), + {reduce, R2, RuleN2, RuleLine2}; + #shift{state = NewState} -> + {shift, NewState, last(R1)} + end, + {Symbol, N, {R1, RuleN1, RuleLine1}, Confl}. + +format_conflict({Symbol, N, _, {one_level_up, + {L1, RuleN1, {P1, Ass1}}, + {L2, RuleN2, {P2, Ass2}}}}) -> + S1 = io_lib:fwrite(<<"Conflicting precedences of symbols when " + "scanning ~s in state ~w:\n">>, + [format_symbol(Symbol), N]), + S2 = io_lib:fwrite(<<" ~s ~w (rule ~w at line ~w)\n" + " vs.\n">>, + [format_assoc(Ass1), P1, RuleN1, L1]), + S3 = io_lib:fwrite(<<" ~s ~w (rule ~w at line ~w)\n">>, + [format_assoc(Ass2), P2, RuleN2, L2]), + [S1, S2, S3]; +format_conflict({Symbol, N, Reduce, Confl}) -> + S1 = io_lib:fwrite(<<"Parse action conflict scanning symbol " + "~s in state ~w:\n">>, [format_symbol(Symbol), N]), + S2 = case Reduce of + {[HR | TR], RuleNmbr, RuleLine} -> + io_lib:fwrite(<<" Reduce to ~s from ~s (rule ~w at " + "line ~w)\n vs.\n">>, + [format_symbol(HR), format_symbols(TR), + RuleNmbr, RuleLine]) + end, + S3 = case Confl of + {reduce, [HR2|TR2], RuleNmbr2, RuleLine2} -> + io_lib:fwrite(<<" reduce to ~s from ~s " + "(rule ~w at line ~w).">>, + [format_symbol(HR2), format_symbols(TR2), + RuleNmbr2, RuleLine2]); + {shift, NewState, Sym} -> + io_lib:fwrite(<<" shift to state ~w, adding right " + "sisters to ~s.">>, + [NewState, format_symbol(Sym)]) + end, + [S1, S2, S3]. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Code generation: + +%% The version up to and including parsetools-1.3 is called "1.0". +%% +%% "1.1", parsetools-1.4: +%% - the prologue file has been updated; +%% - nonassoc is new; +%% - different order of clauses; +%% - never more than one clause matching a given symbol in a given state; +%% - file attributes relate messages to .yrl file; +%% - actions put in inlined functions; +%% - a few other minor fixes. +%% +%% "1.2", parsetools-1.4.2: +%% - the generated code has been changed as follows: +%% - yeccpars2() calls the functions yeccpars2_State(); +%% - several states can share yeccpars2_State(), which reduces code size; +%% - yeccgoto() has been split on one function per nonterminal; +%% - several minor changes have made the loaded code smaller. +%% - the include file yeccpre.hrl has been changed incompatibly. +%% +%% "1.3", parsetools-1.4.4: +%% - the generated code has been changed as follows: +%% - yeccgoto_T() no longer returns the next state, but calls yeccpars_S(); +%% - yeccpars2() is not called when it is known which yeccpars2_S() to call; +%% - "__Stack" has been substituted for "Stack"; +%% - several states can share yeccpars2_S_cont(), which reduces code size; +%% - instead if calling lists:nthtail() matching code is emitted. + +-define(CODE_VERSION, "1.3"). +-define(YECC_BUG(M, A), + iolist_to_binary([" erlang:error({yecc_bug,\"",?CODE_VERSION,"\",", + io_lib:fwrite(M, A), "}).\n\n"])). + +%% Returns number of newlines in included files. +output_prelude(Outport, Inport, St0) when St0#yecc.includefile =:= [] -> + St5 = output_header(St0), + #yecc{infile = Infile, module = Module} = St5, + St10 = fwrite(St5, <<"-module(~w).\n">>, [Module]), + St20 = + fwrite(St10, + <<"-export([parse/1, parse_and_scan/1, format_error/1]).\n">>, + []), + {St25, N_lines_1, LastErlangCodeLine} = + case St20#yecc.erlang_code of + none -> + {St20, 0, no_erlang_code}; + Next_line -> + St_10 = output_file_directive(St20, Infile, Next_line-1), + Nmbr_of_lines = include1([], Inport, Outport), + {St_10, Nmbr_of_lines, + {last_erlang_code_line, Next_line+Nmbr_of_lines}} + end, + St30 = nl(St25), + IncludeFile = + filename:join([code:lib_dir(parsetools), "include","yeccpre.hrl"]), + %% Maybe one could assume there are no warnings in this file. + St = output_file_directive(St30, IncludeFile, 0), + N_lines_2 = include(St, IncludeFile, Outport), + {St, N_lines_1 + N_lines_2, LastErlangCodeLine}; +output_prelude(Outport, Inport, St0) -> + St5 = output_header(St0), + #yecc{infile = Infile, module = Module, includefile = Includefile} = St5, + St10 = fwrite(St5, <<"-module(~w).\n">>, [Module]), + St20 = output_file_directive(St10, Includefile, 0), + N_lines_1 = include(St20, Includefile, Outport), + St30 = nl(St20), + case St30#yecc.erlang_code of + none -> + {St30, N_lines_1, no_erlang_code}; + Next_line -> + St = output_file_directive(St30, Infile, Next_line-1), + Nmbr_of_lines = include1([], Inport, Outport), + {St, Nmbr_of_lines + N_lines_1, + {last_erlang_code_line, Next_line+Nmbr_of_lines}} + end. + +output_header(St0) -> + lists:foldl(fun(Str, St) -> fwrite(St, <<"~s\n">>, [Str]) + end, St0, St0#yecc.header). + +output_goto(St, [{_Nonterminal, []} | Go], StateInfo) -> + output_goto(St, Go, StateInfo); +output_goto(St0, [{Nonterminal, List} | Go], StateInfo) -> + F = function_name(yeccgoto, Nonterminal), + St10 = output_goto1(St0, List, F, StateInfo, true), + St = output_goto_fini(F, Nonterminal, St10), + output_goto(St, Go, StateInfo); +output_goto(St, [], _StateInfo) -> + St. + +output_goto1(St0, [{From, To} | Tail], F, StateInfo, IsFirst) -> + St10 = delim(St0, IsFirst), + {To, ToInfo} = lookup_state(StateInfo, To), + #state_info{reduce_only = RO, state_repr = Repr, comment = C} = ToInfo, + if + RO -> + %% Reduce actions do not use the state, so we just pass + %% the old (now bogus) on: + FromS = io_lib:fwrite("~w=_S", [From]), + ToS = "_S"; + true -> + FromS = io_lib:fwrite("~w", [From]), + ToS = io_lib:fwrite("~w", [To]) + end, + St20 = fwrite(St10, <<"~w(~s, Cat, Ss, Stack, T, Ts, Tzr) ->\n">>, + [F,FromS]), + St30 = fwrite(St20, <<"~s">>, [C]), + %% Short-circuit call to yeccpars2: + St = fwrite(St30, <<" yeccpars2_~w(~s, Cat, Ss, Stack, T, Ts, Tzr)">>, + [Repr, ToS]), + output_goto1(St, Tail, F, StateInfo, false); +output_goto1(St, [], _F, _StateInfo, _IsFirst) -> + St. + +output_goto_fini(F, NT, #yecc{includefile_version = {1,1}}=St0) -> + %% Backward compatibility. + St10 = delim(St0, false), + St = fwrite(St10, <<"~w(State, _Cat, _Ss, _Stack, _T, _Ts, _Tzr) ->\n">>, + [F]), + fwrite(St, + ?YECC_BUG(<<"{~w, State, missing_in_goto_table}">>, [NT]), + []); +output_goto_fini(_F, _NT, St) -> + fwrite(St, <<".\n\n">>, []). + +%% Find actions having user code. +find_user_code(ParseActions, St) -> + [#user_code{state = State, + terminal = Terminal, + funname = inlined_function_name(State, Terminal), + action = Action} || + {State, La_actions} <- ParseActions, + {Action, Terminals, RuleNmbr, NmbrOfDaughters} + <- find_user_code2(La_actions), + case tokens(RuleNmbr, St) of + [{var, _, '__1'}] -> NmbrOfDaughters =/= 1; + _ -> true + end, + Terminal <- Terminals]. + +find_user_code2([]) -> + []; +find_user_code2([{_, #reduce{rule_nmbr = RuleNmbr, + nmbr_of_daughters = NmbrOfDaughters} + =Action}]) -> + %% Same optimization as in output_state_actions. + [{Action, ["Cat"], RuleNmbr, NmbrOfDaughters}]; +find_user_code2([{La, #reduce{rule_nmbr = RuleNmbr, + nmbr_of_daughters = NmbrOfDaughters} + =Action} | T]) -> + [{Action,La, RuleNmbr, NmbrOfDaughters} | find_user_code2(T)]; +find_user_code2([_ | T]) -> + find_user_code2(T). + +output_actions(St0, StateJumps, StateInfo) -> + %% Not all the clauses of the dispatcher function yeccpars2() can + %% be reached. Only when shifting, that is, calling yeccpars1(), + %% will yeccpars2() be called. + Y2CL = [NewState || {_State,{Actions,_J}} <- StateJumps, + {_LA, #shift{state = NewState}} <- Actions], + Y2CS = ordsets:from_list([0 | Y2CL]), + Y2S = ordsets:from_list([S || {S,_} <- StateJumps]), + NY2CS = ordsets:subtract(Y2S, Y2CS), + Sel = [{S,true} || S <- ordsets:to_list(Y2CS)] ++ + [{S,false} || S <- ordsets:to_list(NY2CS)], + + SelS = [{State,Called} || + {{State,_JActions}, {State,Called}} <- + lists:zip(StateJumps, lists:keysort(1, Sel))], + St10 = foldl(fun({State, Called}, St_0) -> + {State, #state_info{state_repr = IState}} = + lookup_state(StateInfo, State), + output_state_selection(St_0, State, IState, Called) + end, St0, SelS), + St20 = fwrite(St10, <<"yeccpars2(Other, _, _, _, _, _, _) ->\n">>, []), + St = fwrite(St20, + ?YECC_BUG(<<"{missing_state_in_action_table, Other}">>, []), + []), + foldl(fun({State, JActions}, St_0) -> + {State, #state_info{state_repr = IState}} = + lookup_state(StateInfo, State), + output_state_actions(St_0, State, IState, + JActions, StateInfo) + end, St, StateJumps). + +output_state_selection(St0, State, IState, Called) -> + Comment = [<<"%% ">> || false <- [Called]], + St = fwrite(St0, <<"~syeccpars2(~w=S, Cat, Ss, Stack, T, Ts, Tzr) ->\n">>, + [Comment, State]), + fwrite(St, + <<"~s yeccpars2_~w(S, Cat, Ss, Stack, T, Ts, Tzr);\n">>, + [Comment, IState]). + +output_state_actions(St, State, State, {Actions,jump_none}, SI) -> + output_state_actions1(St, State, Actions, true, normal, SI); +output_state_actions(St0, State, State, {Actions, Jump}, SI) -> + {Tag, To, Common} = Jump, + CS = case Tag of + jump_some -> list_to_atom(lists:concat([cont_, To])); + jump_all -> To + end, + St = output_state_actions1(St0, State, Actions, true, {to, CS}, SI), + if + To =:= State -> + output_state_actions1(St, CS, Common, true, normal, SI); + true -> + St + end; +output_state_actions(St, State, JState, _XActions, _SI) -> + fwrite(St, <<"%% yeccpars2_~w: see yeccpars2_~w\n\n">>, [State, JState]). + +output_state_actions1(St, State, [], _IsFirst, normal, _SI) -> + output_state_actions_fini(State, St); +output_state_actions1(St0, State, [], IsFirst, {to, ToS}, _SI) -> + St = delim(St0, IsFirst), + fwrite(St, + <<"yeccpars2_~w(S, Cat, Ss, Stack, T, Ts, Tzr) ->\n" + " yeccpars2_~w(S, Cat, Ss, Stack, T, Ts, Tzr).\n\n">>, + [State, ToS]); +output_state_actions1(St0, State, [{_, #reduce{}=Action}], + IsFirst, _End, SI) -> + St = output_reduce(St0, State, "Cat", Action, IsFirst, SI), + fwrite(St, <<".\n\n">>, []); +output_state_actions1(St0, State, [{Lookahead,Action} | Tail], + IsFirst, End, SI) -> + {_, St} = + foldl(fun(Terminal, {IsFst,St_0}) -> + {false, + output_action(St_0, State, Terminal, Action, IsFst,SI)} + end, {IsFirst,St0}, Lookahead), + output_state_actions1(St, State, Tail, false, End, SI). + +output_action(St, State, Terminal, #reduce{}=Action, IsFirst, SI) -> + output_reduce(St, State, Terminal, Action, IsFirst, SI); +output_action(St0, State, Terminal, #shift{state = NewState}, IsFirst, _SI) -> + St10 = delim(St0, IsFirst), + St = fwrite(St10, <<"yeccpars2_~w(S, ~s, Ss, Stack, T, Ts, Tzr) ->\n">>, + [State, quoted_atom(Terminal)]), + output_call_to_includefile(NewState, St); +output_action(St0, State, Terminal, accept, IsFirst, _SI) -> + St10 = delim(St0, IsFirst), + St = fwrite(St10, + <<"yeccpars2_~w(_S, ~s, _Ss, Stack, _T, _Ts, _Tzr) ->\n">>, + [State, quoted_atom(Terminal)]), + fwrite(St, <<" {ok, hd(Stack)}">>, []); +output_action(St, _State, _Terminal, nonassoc, _IsFirst, _SI) -> + St. + +output_call_to_includefile(NewState, #yecc{includefile_version = {1,1}}=St) -> + %% Backward compatibility. + fwrite(St, <<" yeccpars1(Ts, Tzr, ~w, [S | Ss], [T | Stack])">>, + [NewState]); +output_call_to_includefile(NewState, St) -> + fwrite(St, <<" yeccpars1(S, ~w, Ss, Stack, T, Ts, Tzr)">>, + [NewState]). + +output_state_actions_fini(State, #yecc{includefile_version = {1,1}}=St0) -> + %% Backward compatibility. + St10 = delim(St0, false), + St = fwrite(St10, <<"yeccpars2_~w(_, _, _, _, T, _, _) ->\n">>, [State]), + fwrite(St, <<" yeccerror(T).\n\n">>, []); +output_state_actions_fini(_State, St) -> + fwrite(St, <<".\n\n">>, []). + +output_reduce(St0, State, Terminal0, + #reduce{rule_nmbr = RuleNmbr, + head = Head, + nmbr_of_daughters = NmbrOfDaughters}, + IsFirst, StateInfo) -> + St10 = delim(St0, IsFirst), + Terminal = if + is_atom(Terminal0) -> quoted_atom(Terminal0); + true -> Terminal0 + end, + St20 = fwrite(St10, + <<"yeccpars2_~w(_S, ~s, Ss, Stack, T, Ts, Tzr) ->\n">>, + [State, Terminal]), + St30 = + if + NmbrOfDaughters < 2 -> + Ns = "Ss", + St20; + true -> + Ns = "Nss", + Tmp = string:join(lists:duplicate(NmbrOfDaughters - 1, "_"), + ","), + fwrite(St20, <<" [~s|Nss] = Ss,\n">>, [Tmp]) + end, + St40 = case tokens(RuleNmbr, St30) of + [{var, _, '__1'}] when NmbrOfDaughters =:= 1 -> + NewStack = "Stack", + St30; + _ -> + NewStack = "NewStack", + fwrite(St30, <<" NewStack = ~w(Stack),\n">>, + [inlined_function_name(State, Terminal0)]) + end, + if + NmbrOfDaughters =:= 0 -> + NextState = goto(State, Head, St40), + {NextState, I} = lookup_state(StateInfo, NextState), + #state_info{reduce_only = RO, state_repr = Repr, comment = C} = I, + %% Reduce actions do not use the state, so we just pass + %% the old (now bogus) on: + if + RO -> NextS = "_S"; + true -> NextS = io_lib:fwrite("~w", [NextState]) + end, + St = fwrite(St40, <<"~s">>, [C]), + %% Short-circuit call to yeccpars2: + fwrite(St, + <<" yeccpars2_~w(~s, ~s, [~w | Ss], ~s, T, Ts, Tzr)">>, + [Repr, NextS, Terminal, State, NewStack]); + true -> + fwrite(St40, + <<" ~w(hd(~s), ~s, ~s, ~s, T, Ts, Tzr)">>, + [function_name(yeccgoto, Head), Ns, + Terminal, Ns, NewStack]) + end. + +delim(St, true) -> + St; +delim(St, false) -> + fwrite(St, <<";\n">>, []). + +quoted_atom(Atom) -> + io_lib:fwrite(<<"~w">>, [Atom]). + +output_inlined(St, UserCodeActions, Infile) -> + foldl(fun(#user_code{funname = InlinedFunctionName, + action = Action}, St_0) -> + output_inlined(St_0, InlinedFunctionName, + Action, Infile) + end, St, UserCodeActions). + +%% Each action with user code is placed in a separate inlined function. +%% The purpose is to be able to pinpoint errors and warnings correctly. +output_inlined(St0, FunctionName, Reduce, Infile) -> + #reduce{rule_nmbr = RuleNmbr, nmbr_of_daughters = N_daughters} = Reduce, + #rule{tokens = Tokens, is_well_formed = WF} = get_rule(RuleNmbr, St0), + Line0 = first_line(Tokens), + NLines = last_line(Tokens) - Line0, + + St5 = if + WF -> + St0; + not WF -> + %% The compiler will generate an error message for + %% the inlined function (unless the reason that yecc + %% failed to parse the action was some macro). The + %% line number of the message will be correct since + %% we are keeping track of the current line of the + %% output file... + #yecc{outfile = Outfile, line = CurLine} = St0, + output_file_directive(St0, Outfile, CurLine) + end, + + CodeStartLine = lists:max([0, Line0 - 4]), + St10 = fwrite(St5, <<"-compile({inline,~w/1}).\n">>, [FunctionName]), + St20 = output_file_directive(St10, Infile, CodeStartLine), + St30 = fwrite(St20, <<"~w(__Stack0) ->\n">>, [FunctionName]), + %% Currently the (old) inliner emits less code if matching the + %% stack inside the body rather than in the head... + St40 = case N_daughters of + 0 -> + Stack = "__Stack0", + St30; + _ -> + Stack = "__Stack", + A = concat(flatmap(fun(I) -> [",__",I] end, + lists:seq(N_daughters, 1, -1))), + fwrite(St30, <<" ~s = __Stack0,\n">>, + [append(["[", tl(A), " | __Stack]"])]) + end, + St = St40#yecc{line = St40#yecc.line + NLines}, + fwrite(St, <<" [begin\n ~s\n end | ~s].\n\n">>, + [pp_tokens(Tokens, Line0), Stack]). + +inlined_function_name(State, "Cat") -> + inlined_function_name(State, ""); +inlined_function_name(State, Terminal) -> + list_to_atom(concat([yeccpars2_, State, '_', Terminal])). + +-compile({nowarn_unused_function,function_name/2}). +function_name(Name, Suf) -> + list_to_atom(concat([Name, '_' | quoted_atom(Suf)])). + +rule(RulePointer, St) -> + #rule{n = N, line = Line, symbols = Symbols} = + dict:fetch(RulePointer, St#yecc.rule_pointer2rule), + {Symbols, Line, N}. + +get_rule(RuleNmbr, St) -> + dict:fetch(RuleNmbr, St#yecc.rule_pointer2rule). + +tokens(RuleNmbr, St) -> + Rule = dict:fetch(RuleNmbr, St#yecc.rule_pointer2rule), + Rule#rule.tokens. + +goto(From, Symbol, St) -> + case ets:lookup(St#yecc.goto_tab, {From, Symbol}) of + [{_, To}] -> + To; + [] -> + erlang:error({error_in_goto_table, From, Symbol}) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Auxiliaries: + +-ifdef(SYMBOLS_AS_CODES). + +%%% Bit mask operations. + +-compile({inline,[set_empty/0]}). +set_empty() -> + 0. + +set_add(I, BM) -> + (1 bsl I) bor BM. + +-compile({inline,[set_member/2]}). +set_member(I, BM) -> + ((1 bsl I) band BM) =/= 0. + +%% Assumes I is a member... +-compile({inline,[set_delete/2]}). +set_delete(I, BM) -> + (1 bsl I) bxor BM. + +-compile({inline,[set_union/2]}). +set_union(BM1, BM2) -> + BM1 bor BM2. + +-compile({inline,[set_is_subset/2]}). +set_is_subset(BM1, BM2) -> + (BM1 band BM2) =:= BM1. + +empty_member(BM) -> + set_member(0, BM). + +empty_delete(BM) -> + set_delete(0, BM). + +code_symbols(Ss, SymbolTable) -> + map(fun(S) -> ets:lookup_element(SymbolTable, S, 2) end, Ss). + +decode_symbol(C, InvSymbolTable) -> + ets:lookup_element(InvSymbolTable, C, 1). + +code_terminal(T, SymbolTab) -> + set_add(ets:lookup_element(SymbolTab, T, 2), 0). + +decode_terminals(BM, InvSymbolTab) -> + case get(BM) of + undefined -> + Symbols = decode_terminals(BM, 0, InvSymbolTab), + put(BM, Symbols), + Symbols; + Symbols -> + Symbols + end. + +decode_terminals(0, _I, _InvSymbolTab) -> + []; +decode_terminals(BM, I, InvSymbolTab) -> + case set_member(I, BM) of + true -> + [ets:lookup_element(InvSymbolTab, I, 1) + | decode_terminals(set_delete(I, BM), I+1, InvSymbolTab)]; + false -> + decode_terminals(BM, I+1, InvSymbolTab) + end. + +set_add_terminal({_Symbol, TerminalNum}, BM) -> + set_add(TerminalNum, BM). + +-compile({inline,[is_terminal/2]}). +is_terminal(_Tab, SymbolCode) -> + SymbolCode >= 0. + +left_corner_symbol_table(St) -> + St#yecc.inv_symbol_tab. + +-else. + +set_empty() -> + []. + +set_add(Symbol, L) -> + ordsets:union([Symbol], L). + +set_union(Es1, Es2) -> + ordsets:union(Es1, Es2). + +set_is_subset(Es1, Es2) -> + ordsets:is_subset(Es1, Es2). + +code_symbols(Ss, _SymbolTab) -> + Ss. + +decode_symbol(S, _InvSymbolTab) -> + S. + +code_terminal(T, _SymbolTab) -> + [T]. + +decode_terminals(Ts, _InvSymbolTab) -> + Ts. + +empty_member(['$empty' | _]) -> + true; +empty_member(_) -> + false. + +empty_delete(['$empty' | Terminals]) -> + Terminals. + +set_add_terminal({Symbol, _TerminalNum}, L) -> + set_add(Symbol, L). + +is_terminal(Tab, SymbolName) -> + ets:lookup_element(Tab, SymbolName, 2) >= 0. + +left_corner_symbol_table(St) -> + St#yecc.symbol_tab. + +-endif. % SYMBOLS_AS_CODES + +intersect(L1, L2) -> + ordsets:to_list(ordsets:intersection(ordsets:from_list(L1), + ordsets:from_list(L2))). + +format_symbols([Sym | Syms]) -> + concat([format_symbol(Sym) | format_symbols1(Syms)]). + +format_symbols1([]) -> + []; +format_symbols1([H | T]) -> + [" ", format_symbol(H) | format_symbols1(T)]. + +include(St, File, Outport) -> + case file:open(File, [read]) of + {error, Reason} -> + throw(add_error(File, none, {file_error, Reason}, St)); + {ok, Inport} -> + Line = io:get_line(Inport, ''), + N_lines = include1(Line, Inport, Outport), + file:close(Inport), + N_lines + end. + +include1(Line, Inport, Outport) -> + include1(Line, Inport, Outport, 0). + +include1(eof, _, _, Nmbr_of_lines) -> + Nmbr_of_lines; +include1(Line, Inport, Outport, Nmbr_of_lines) -> + Incr = case member($\n, Line) of + true -> 1; + false -> 0 + end, + io:put_chars(Outport, Line), + include1(io:get_line(Inport, ''), Inport, Outport, Nmbr_of_lines + Incr). + +includefile_version([]) -> + {1,2}; +includefile_version(Includefile) -> + case epp:open(Includefile, []) of + {ok, Epp} -> + try + parse_file(Epp) + after + epp:close(Epp) + end; + {error, _Error} -> + {1,1} + end. + +parse_file(Epp) -> + case epp:parse_erl_form(Epp) of + {ok, {function,_Line,yeccpars1,7,_Clauses}} -> + {1,2}; + {eof,_Line} -> + {1,1}; + _Form -> + parse_file(Epp) + end. + +%% Keeps the line breaks of the original code. +pp_tokens(Tokens, Line0) -> + concat(pp_tokens1(Tokens, Line0, [])). + +pp_tokens1([], _Line0, _T0) -> + []; +pp_tokens1([T | Ts], Line0, T0) -> + Line = element(2, T), + [pp_sep(Line, Line0, T0), pp_symbol(T) | pp_tokens1(Ts, Line, T)]. + +pp_symbol({var,_,Var}) -> Var; +pp_symbol({_,_,Symbol}) -> io_lib:fwrite(<<"~p">>, [Symbol]); +pp_symbol({Symbol, _}) -> Symbol. + +pp_sep(Line, Line0, T0) when Line > Line0 -> + ["\n " | pp_sep(Line - 1, Line0, T0)]; +pp_sep(_Line, _Line0, {'.',_}) -> + ""; +pp_sep(_Line, _Line0, _T0) -> + " ". + +output_file_directive(St, Filename, Line) when St#yecc.file_attrs -> + fwrite(St, <<"-file(~s, ~w).\n">>, + [format_filename(Filename), Line]); +output_file_directive(St, _Filename, _Line) -> + St. + +first_line(Tokens) -> + element(2, hd(Tokens)). + +last_line(Tokens) -> + element(2, lists:last(Tokens)). + +%% Keep track of the current line in the generated file. +fwrite(#yecc{outport = Outport, line = Line}=St, Format, Args) -> + NLines = count_nl(Format), + io:fwrite(Outport, Format, Args), + St#yecc{line = Line + NLines}. + +%% Assumes \n is used, and never ~n. +count_nl(<<$\n,Rest/binary>>) -> + 1 + count_nl(Rest); +count_nl(<<_,Rest/binary>>) -> + count_nl(Rest); +count_nl(<<>>) -> + 0. + +nl(#yecc{outport = Outport, line = Line}=St) -> + io:nl(Outport), + St#yecc{line = Line + 1}. + +format_filename(Filename) -> + io_lib:write_string(filename:flatten(Filename)). + +format_assoc(left) -> + "Left"; +format_assoc(right) -> + "Right"; +format_assoc(unary) -> + "Unary"; +format_assoc(nonassoc) -> + "Nonassoc". + +format_symbol(Symbol) -> + String = concat([Symbol]), + case erl_scan:string(String) of + {ok, [{atom, _, _}], _} -> + io_lib:fwrite(<<"~w">>, [Symbol]); + {ok, [{Word, _}], _} when Word =/= ':', Word =/= '->' -> + case erl_scan:reserved_word(Word) of + true -> + String; + false -> + io_lib:fwrite(<<"~w">>, [Symbol]) + end; + {ok, [{var, _, _}], _} -> + String; + _ -> + io_lib:fwrite(<<"~w">>, [Symbol]) + end. + +inverse(L) -> + sort([{A,B} || {B,A} <- L]). + +family(L) -> + sofs:to_external(sofs:relation_to_family(sofs:relation(L))). + +seq1(To) when To < 1 -> + []; +seq1(To) -> + lists:seq(1, To). + +count(From, L) -> + lists:zip(L, lists:seq(From, length(L)-1+From)). + +family_with_domain(L, DL) -> + sofs:to_external(sofs_family_with_domain(sofs:relation(L), sofs:set(DL))). + +sofs_family_with_domain(R0, D) -> + R = sofs:restriction(R0, D), + F = sofs:relation_to_family(R), + FD = sofs:constant_function(D, sofs:from_term([])), + sofs:family_union(F, FD). |