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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209 | -- Abstract :
--
-- Types and operations for generating parsers, common to all parser
-- types.
--
-- The wisi* packages deal with reading *.wy files and generating
-- source code files. The wisitoken-generate* packages deal with
-- computing parser properties from the grammar. (For historical
-- reasons, not all packages follow this naming convention yet).
--
-- References :
--
-- See wisitoken.ads
--
-- Copyright (C) 2018 - 2020, 2022 Free Software Foundation, Inc.
--
-- This library is free software; you can redistribute it and/or modify it
-- under terms of the GNU General Public License as published by the Free
-- Software Foundation; either version 3, or (at your option) any later
-- version. This library is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHAN-
-- TABILITY or FITNESS FOR A PARTICULAR PURPOSE.
-- As a special exception under Section 7 of GPL version 3, you are granted
-- additional permissions described in the GCC Runtime Library Exception,
-- version 3.1, as published by the Free Software Foundation.
pragma License (Modified_GPL);
with Ada.Containers.Doubly_Linked_Lists;
with SAL.Ada_Containers.Gen_Doubly_Linked_Lists_Image;
with SAL.Gen_Graphs;
with WisiToken.Productions;
package WisiToken.Generate is
Error : Boolean := False;
Warning : Boolean := False;
-- Set True by errors/warnings during grammar generation
function Error_Message
(File_Name : in String;
File_Line : in WisiToken.Line_Number_Type;
Message : in String;
Warning : in Boolean := False)
return String;
procedure Put_Error (Message : in String);
-- Set Error True, output Message to Standard_Error
procedure Put_Warning (Message : in String);
-- Set Warning True, output Message to Standard_Error
procedure Check_Consistent
(Grammar : in WisiToken.Productions.Prod_Arrays.Vector;
Descriptor : in WisiToken.Descriptor;
Source_File_Name : in String);
-- Check requirements on Descriptor values.
function Check_Unused_Tokens
(Descriptor : in WisiToken.Descriptor;
Grammar : in WisiToken.Productions.Prod_Arrays.Vector)
return Boolean;
-- Return False if there is a terminal or nonterminal that is not
-- used in the grammar.
--
-- Raises Grammar_Error if there is a non-grammar token used in the
-- grammar.
function Nullable (Grammar : in WisiToken.Productions.Prod_Arrays.Vector) return Token_Array_Production_ID;
-- If ID is nullable, Result (ID) is the production that should be
-- reduced to produce the null. Otherwise Result (ID) is
-- Invalid_Production_ID.
function Has_Empty_Production (Nullable : in Token_Array_Production_ID) return Token_ID_Set;
function Has_Empty_Production (Grammar : in WisiToken.Productions.Prod_Arrays.Vector) return Token_ID_Set;
-- Result (ID) is True if any production for ID can be an empty
-- production, recursively.
function First
(Grammar : in WisiToken.Productions.Prod_Arrays.Vector;
Has_Empty_Production : in Token_ID_Set;
First_Terminal : in Token_ID)
return Token_Array_Token_Set;
-- For each nonterminal in Grammar, find the set of tokens
-- (terminal or nonterminal) that any string derived from it can
-- start with. Together with Has_Empty_Production, implements
-- algorithm FIRST from [dragon], augmented with nonterminals.
--
-- LALR, LR1 generate want First as both Token_Sequence_Arrays.Vector
-- and Token_Array_Token_Set, Packrat wants Token_Array_Token_Set,
-- existing tests all use Token_Array_Token_Set. So for LR we use
-- To_Terminal_Sequence_Array.
function To_Terminal_Sequence_Array
(First : in Token_Array_Token_Set;
Descriptor : in WisiToken.Descriptor)
return Token_Sequence_Arrays.Vector;
-- Only includes terminals.
function Follow
(Grammar : in WisiToken.Productions.Prod_Arrays.Vector;
Descriptor : in WisiToken.Descriptor;
First : in Token_Array_Token_Set;
Has_Empty_Production : in Token_ID_Set)
return Token_Array_Token_Set;
-- For each nonterminal in Grammar, find the set of terminal
-- tokens that can follow it. Implements algorithm FOLLOW from
-- [dragon] pg 189.
----------
-- Recursion
-- Recursion is the result of a cycle in the grammar. We can form a
-- graph representing the grammar by taking the nonterminals as the
-- graph vertices, and the occurrence of a nonterminal in a
-- production right hand side as a directed edge from the left hand
-- side of the production to that nonterminal. Then recursion is
-- represented by a cycle in the graph.
type Edge_Data is record
-- The edge leading to this node.
RHS : Natural := Natural'Last;
Token_Index : Positive := Positive'Last;
end record;
function Edge_Image (Edge : in Edge_Data) return String
is (Trimmed_Image (Edge.RHS) & "." & Trimmed_Image (Edge.Token_Index));
type Base_Recursion_Index is range 0 .. Integer'Last;
subtype Recursion_Index is Base_Recursion_Index range 1 .. Base_Recursion_Index'Last;
Invalid_Recursion_Index : constant Base_Recursion_Index := 0;
function Trimmed_Image is new SAL.Gen_Trimmed_Image (Base_Recursion_Index);
package Grammar_Graphs is new SAL.Gen_Graphs
(Edge_Data => Generate.Edge_Data,
Default_Edge_Data => (others => <>),
Vertex_Index => Token_ID,
Invalid_Vertex => Invalid_Token_ID,
Path_Index => Recursion_Index,
Edge_Image => Edge_Image);
subtype Recursion_Cycle is Grammar_Graphs.Path;
-- A recursion, with lowest numbered production first. If there is
-- only one element, the recursion is direct; otherwise indirect.
subtype Recursion_Array is Grammar_Graphs.Path_Arrays.Vector;
-- For the collection of all cycles.
type Recursions is record
Full : Boolean;
Recursions : Recursion_Array;
-- If Full, elements are paths; edges at path (I) are to path (I). If
-- not Full, elements are strongly connected components; edges at
-- path (I) are from path (I).
end record;
Empty_Recursions : constant Recursions := (Full => False, Recursions => <>);
package Recursion_Lists is new Ada.Containers.Doubly_Linked_Lists (Recursion_Index);
function Image is new SAL.Ada_Containers.Gen_Doubly_Linked_Lists_Image
(Recursion_Index, "=", Recursion_Lists, Trimmed_Image);
function To_Graph (Grammar : in WisiToken.Productions.Prod_Arrays.Vector) return Grammar_Graphs.Graph;
function Compute_Full_Recursion
(Grammar : in WisiToken.Productions.Prod_Arrays.Vector;
Descriptor : in WisiToken.Descriptor)
return Recursions;
-- Each element of result is a cycle in the grammar.
function Compute_Partial_Recursion
(Grammar : in WisiToken.Productions.Prod_Arrays.Vector;
Descriptor : in WisiToken.Descriptor)
return Recursions;
-- Each element of the result contains all members of a non-trivial
-- strongly connected component in the grammar, in arbitrary order.
-- This is an approximation to the full recursion, when that is too
-- hard to compute (ie for Java).
procedure Set_Grammar_Recursions
(Recursions : in WisiToken.Generate.Recursions;
Grammar : in out WisiToken.Productions.Prod_Arrays.Vector);
----------
-- Indented text output. Mostly used for code generation in wisi,
-- also used in outputing the parse_table and other debug stuff.
Max_Line_Length : constant := 120;
Indent : Standard.Ada.Text_IO.Positive_Count := 1;
Line_Count : Integer;
procedure Indent_Line (Text : in String);
-- Put Text, indented to Indent, to Current_Output, with newline.
procedure Indent_Start (Text : in String);
-- Put Text indented to Indent to Current_Output, without newline.
-- Should be followed by Put_Line, not Indent_Line.
procedure Indent_Wrap (Text : in String);
-- Put Text, indented to Indent, wrapped at Max_Line_Length, to
-- Current_Output, ending with newline.
procedure Indent_Wrap_Comment (Text : in String; Comment_Syntax : in String);
-- Put Text, prefixed by Comment_Syntax and two spaces, indented to
-- Indent, wrapped at Max_Line_Length, to Current_Output, ending with
-- newline.
end WisiToken.Generate;
|