1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
-------------------------------------------------------------------------------
--
-- Copyright (C) 2002, 2003, 2009, 2010, 2013, 2014 Stephe Leake
-- Copyright (C) 1999 Ted Dennison
--
-- References:
--
-- [dragon] "Compilers Principles, Techniques, and Tools" by Aho,
-- Sethi, and Ullman (aka: "The [Red] Dragon Book").
--
-- This file is part of the OpenToken package.
--
-- The OpenToken package is free software; you can redistribute it and/or
-- modify it under the terms of the GNU General Public License as published
-- by the Free Software Foundation; either version 3, or (at your option)
-- any later version. The OpenToken package is distributed in the hope that
-- it will be useful, but WITHOUT ANY WARRANTY; without even the implied
-- warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-- GNU General Public License for more details. You should have received
-- a copy of the GNU General Public License distributed with the OpenToken
-- package; see file GPL.txt. If not, write to the Free Software Foundation,
-- 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
--
-- As a special exception, if other files instantiate generics from
-- this unit, or you link this unit with other files to produce an
-- executable, this unit does not by itself cause the resulting
-- executable to be covered by the GNU General Public License. This
-- exception does not however invalidate any other reasons why the
-- executable file might be covered by the GNU Public License.
-----------------------------------------------------------------------------
-----------------------------------------------------------------------------
-- This package is the root package of an implementation of a LALR
-- (Look-Ahead Left-to-right scanning Rightmost-deriving) parser for
-- grammars defined by a production list. It contains types shared by
-- the parse table generator in child package generator, and the
-- parser in child package parser. Debug output of structures is in
-- child package Text_IO.
with Ada.Containers.Doubly_Linked_Lists;
generic
First_State_Index : in Natural;
package OpenToken.Production.Parser.LALR is
-- No private types; that would make it too hard to write the unit tests
-- Following are the types used in the parse table. The parse
-- table is an array indexed by parse state that where each state
-- contains a list of parse actions and a list of gotos.
--
-- Parse actions are indexed by the terminal they match and are either
-- o Shift and change to a designated state.
-- o Reduce by the given production
--
-- Gotos are indexed by the nonterminal they match and designate
-- the state the parser need to change to.
type Unknown_State_Index is new Integer range -1 .. Integer'Last;
subtype State_Index is Unknown_State_Index range Unknown_State_Index (First_State_Index) .. Unknown_State_Index'Last;
Unknown_State : constant Unknown_State_Index := -1;
type Parse_Action_Verbs is (Shift, Reduce, Accept_It, Error);
type Parse_Action_Rec (Verb : Parse_Action_Verbs := Shift) is record
case Verb is
when Shift =>
State : State_Index;
when Reduce | Accept_It =>
LHS : Nonterminal.Handle;
Action : Nonterminal.Synthesize;
Index : Integer; -- into rule, for generating action names, debugging.
Token_Count : Natural;
when Error =>
null;
end case;
end record;
subtype Reduce_Action_Rec is Parse_Action_Rec (Reduce);
Null_Reduce_Action_Rec : constant Reduce_Action_Rec := (Reduce, null, null, 0, 0);
type Parse_Action_Node;
type Parse_Action_Node_Ptr is access Parse_Action_Node;
type Parse_Action_Node is record
Item : Parse_Action_Rec;
Next : Parse_Action_Node_Ptr; -- non-null only for conflicts
end record;
type Action_Node;
type Action_Node_Ptr is access Action_Node;
type Action_Node is record
Symbol : Token.Terminal_ID;
Action : Parse_Action_Node_Ptr;
Next : Action_Node_Ptr;
end record;
type Goto_Node;
type Goto_Node_Ptr is access Goto_Node;
type Goto_Node is record
Symbol : Nonterminal_ID;
State : State_Index;
Next : Goto_Node_Ptr;
end record;
type Parse_State is record
Action_List : Action_Node_Ptr;
Goto_List : Goto_Node_Ptr;
end record;
type Parse_Table is array (State_Index range <>) of Parse_State;
type Parse_Table_Ptr is access Parse_Table;
subtype Conflict_Parse_Actions is Parse_Action_Verbs range Shift .. Reduce;
type Conflict is record
-- A typical conflict is:
--
-- SHIFT/REDUCE in state: 11 on token IS
--
-- State numbers change with minor changes in the grammar, so
-- we identify the state by the LHS of the two productions
-- involved. We also store the state number for generated
-- conflicts (not for known conflicts from the grammar
-- definition file), for Text_IO output.
Action_A : Conflict_Parse_Actions;
LHS_A : Token.Token_ID;
Action_B : Conflict_Parse_Actions;
LHS_B : Token.Token_ID;
State_Index : Unknown_State_Index;
On : Token.Token_ID;
end record;
package Conflict_Lists is new Ada.Containers.Doubly_Linked_Lists (Conflict);
----------
-- Useful text output
function State_Image (Item : in State_Index) return String;
-- no leading space
procedure Put (Item : in Parse_Action_Rec);
end OpenToken.Production.Parser.LALR;
|
