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 //////////////////////////////////////////////////////////////////////////////
25 #ifndef LR1_parser_driver_h
26 #define LR1_parser_driver_h
29 #include <AD/automata/lr1.h> // LR driver basics
30 #include <AD/contain/stack.h> // generic stacks
32 //////////////////////////////////////////////////////////////////////////////
33 // Class LR1ParserDriver is used to implement a LR(1) style
34 // parser driver with automatic semantic stack manipulation.
35 // The class is parametrized with the type of the semantic stack
36 // element(the semantic stack is current implemented as an array).
38 // We assume the user will derive a subclass using this driver
39 // as one of the superclass. The following methods should be provided
42 // Terminal get_token() --- this method retrieved the next token
43 // from the input stream.
44 // void act (Action) --- this method should be used to execute
45 // the semantic actions.
46 //////////////////////////////////////////////////////////////////////////////
48 class LR1ParserDriver
: public LR1
{
50 LR1ParserDriver(const LR1ParserDriver
&); // no copy constructor
51 void operator = (const LR1ParserDriver
&); // no assignment
55 ////////////////////////////////////////////////////////////////////////
56 // Make inherited types visible
57 ////////////////////////////////////////////////////////////////////////
59 typedef Super::Symbol Symbol
;
60 typedef Super::State State
;
61 typedef Super::Offset Offset
;
62 typedef Super::Rule Rule
;
63 typedef Super::ProductionLength ProductionLength
;
67 ////////////////////////////////////////////////////////////////////////
68 // Constructor and destructor
69 ////////////////////////////////////////////////////////////////////////
71 LR1ParserDriver( const Offset base_table
[],
72 const State check_table
[],
73 const State defact_table
[],
74 const State next_table
[],
75 const ProductionLength len_table
[],
76 const unsigned short equiv_table
[]
79 virtual ~LR1ParserDriver();
81 ////////////////////////////////////////////////////////////////////////
83 ////////////////////////////////////////////////////////////////////////
84 virtual void parse ();
87 ////////////////////////////////////////////////////////////////////////
88 // Tokenizer (must be implemented in derived class)
89 ////////////////////////////////////////////////////////////////////////
90 virtual Terminal
get_token() = 0;
92 ////////////////////////////////////////////////////////////////////////
94 // open() -- prelude routine, redefinable by client.
95 // close() -- post processing routine, redefinable by client.
96 // act() -- action routine, redefinable by client.
97 // init_stack_size() -- stack size, redefinable by client.
98 // Notice that the stack is automatically
99 // adjusted by the driver.
100 // stack_overflow() -- handler for stack overflow.
101 ////////////////////////////////////////////////////////////////////////
102 virtual void open () {}
103 virtual void close () {}
104 virtual void act (Action A
) {}
105 virtual int init_stack_size() const { return 4096; }
106 virtual void stack_overflow() {}
109 ///////////////////////////////////////////////////////////////////////////////
110 // Parser driver for LR(1) style parser tables.
111 ///////////////////////////////////////////////////////////////////////////////
113 void LR1ParserDriver::parse()
114 { int size
= init_stack_size();
115 Stack
<State
> S(size
); // the parse stack
116 Stack
<T
> V(size
); // the semantic value stack
120 S
.push(start_state
); // push start state
121 T
= get_token(); // get next token
129 if (isError(n
)) { // parse error
130 } else if (isShift(n
)) { // shift action
131 s
= n
; T
= get_token();
132 } else { // reduce action
133 Rule r
= reduceRule(n
); // reduction rule
134 act(r
); // execute the action
135 S
.pop(reduceLen(r
)); // pop the parse stack
136 S
.push(go(s
= S
.top(),T
));