1 //////////////////////////////////////////////////////////////////////////////
4 // ADLib, Prop and their related set of tools and documentation are in the
5 // public domain. The author(s) of this software reserve no copyrights on
6 // the source code and any code generated using the tools. You are encouraged
7 // to use ADLib and Prop to develop software, in both academic and commercial
8 // settings, and are free to incorporate any part of ADLib and Prop into
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
14 // We also ask that credit be given to us when ADLib and/or Prop are used in
15 // your programs, and that this notice be preserved intact in all the source
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
27 #include <AD/automata/ll1gen.h> // LL(1) parser generator
28 #include <AD/automata/follow.h> // Follow set computation
29 #include <AD/memory/mempool.h> // Memory pool
31 /////////////////////////////////////////////////////////////////////////
32 // Constructor and destructor
33 /////////////////////////////////////////////////////////////////////////
34 LL1Gen::LL1Gen() {} // nothing to add
35 LL1Gen::~LL1Gen() {} // nothing to add
37 /////////////////////////////////////////////////////////////////////////
38 // Entry point of the compiler
39 /////////////////////////////////////////////////////////////////////////
40 void LL1Gen::compile(const Grammar
& G
)
42 MemPool
mem(4096); // memory pool
43 FollowSet
F(G
,mem
); // compute the follow set
45 //////////////////////////////////////////////////////////////////////
46 // Allocate the dfa tables
47 //////////////////////////////////////////////////////////////////////
48 create_tables( G
.number_of_terminals() * 3, G
.number_of_non_terminals(),
49 G
.min_terminal(), G
.max_terminal() );
51 //////////////////////////////////////////////////////////////////////
52 // Allocate a mapping from non-terminals A to sets of terminals
54 //////////////////////////////////////////////////////////////////////
55 BitSet
** predict_set
= new BitSet
* [ G
.max_non_terminal() + 1 ];
56 { for (Symbol A
= G
.min_non_terminal(); A
<= G
.max_non_terminal(); A
++) {
57 predict_set
[A
] = new (mem
, G
.max_terminal() + 1) BitSet
;
61 //////////////////////////////////////////////////////////////////////
62 // Allocate temporary buffers
63 //////////////////////////////////////////////////////////////////////
64 Symbol
* symbols
= new Symbol
[ G
.number_of_terminals() ];
65 State
* delta
= new State
[ G
.number_of_terminals() ];
66 //int fan_out; // fan out of a state
68 //////////////////////////////////////////////////////////////////////
69 // Now compute the predict sets.
71 // predict(A -> XYZ) = first(XYZ) if ! nullable(XYZ)
72 // first(XYZ) U follow(A) if nullable(XYZ)
73 // predict_set(A) = U predict(A->XYZ)
74 //////////////////////////////////////////////////////////////////////
75 BitSet
* predict
= new (mem
, G
.max_terminal() + 1) BitSet
;
76 { for (int i
= 0; i
< G
.size(); i
++) {
78 Production P
= G
.rhs(i
);
80 if (F
.first(*predict
,P
)) predict
->Union(F
.follow(A
));
84 //////////////////////////////////////////////////////////////////////
86 //////////////////////////////////////////////////////////////////////
88 //////////////////////////////////////////////////////////////////////
90 //////////////////////////////////////////////////////////////////////
93 delete [] predict_set
;
96 /////////////////////////////////////////////////////////////////////////
98 /////////////////////////////////////////////////////////////////////////
99 std::ostream
& LL1Gen::gen_code (std::ostream
& out
, const char name
[]) const
100 { return Super::gen_code(out
,name
);