source: devel-tools/trunk/LL1GrammarAnalyzers/LLAnalyzerInRfp2k9/src/GrAnal.rf @ 4103

Last change on this file since 4103 was 4103, checked in by yura, 11 years ago
  • Copy from LLAnalyzerInRfp2k7.
  • Property svn:eol-style set to native
File size: 10.0 KB
Line 
1//
2// File GRANAL.RF
3//
4// Project: GR
5//
6
7$use Access;
8$use Arithm;
9$use Compare;
10$use Dos;
11$use StdIO;
12
13$use GrPrn;
14
15$func  NTWithout  (e.NTL) (e.Rules) = e.Dead;
16$func  EnvWith    (e.NTL) (e.Env) = e.Env;
17$func  FindAlive  e.Rules = e.Alive;
18$func  IterAlive  (e.Alive) (e.Rules) = e.Alive;
19$func  NextAlive  (e.Alive) (e.Rules) = e.NextAlive;
20$func  FindReachable  e.Rules = e.Reachable;
21$func  IterReachable  (e.Reachable) (e.Rules) = e.Reachable;
22$func  NextReachable  (e.Reachable) (e.Rules) = e.NextReachable;
23$func  FindNullable  e.Rules = e.Nullable;
24$func  IterNullable  (e.Nullable) (e.Rules) = e.Nullable;
25$func  NextNullable  (e.Nullable) (e.Rules) = e.NextNullable;
26$func? IsNullableRhs  (e.Nullable) (e.Rhs) = ;
27$func  FindStarters  (e.Nullable) (e.Rules) = e.SEnv;
28$func  IterStarters  (e.Nullable) (e.SEnv) (e.Rules) = e.SEnv;
29$func  NextStarters  (e.Nullable) (e.SEnv) (e.Rules) = e.SEnv;
30$func  RhsListStarters (e.Nullable) (e.SEnv) (e.L) = e.Starters;
31$func  RhsStarters   (e.Nullable) (e.SEnv) (eR) = e.Starters;
32$func  FindFollowers (e.Nullable) (e.SEnv) (e.Rules) = e.FEnv;
33$func  IterFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules) = e.SEnv;
34$func  NextFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules) = e.SEnv;
35$func  RhsListFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (e.L) = e.FEnv;
36$func  RhsFollowers  sN (e.Nullable) (e.SEnv) (e.FEnv) (eR) = e.FEnv;
37$func  UpdateFollowers sN (e.Nullable) (e.SEnv) (e.FEnv) sX (e.Rest) = e.FEnv;
38$func  PrintAnnGrammar (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules) = ;
39$func  PrintAnnRules sC (e.Nullable) (e.SEnv) (e.FEnv) (e.S) sN (eL) = ;
40$func  SetUnion   (eX) (eY) = eU;
41$func  MkSet      e.List = e.Set;
42$func  ExtractNT      e.RhsList = e.NTList;
43$func  ExtractNTRhs  e.Rhs = e.NTList;
44$func  RulesToEnv    e.Rules = e.Env;
45$func  LookupEnv      sN (e.Env) = eV;
46$func  UpdateEnv      sN (eV) (e.Env) = e.Env;
47
48Analyze (e.Tokens) (e.Rules) =
49// <PrintGrammar (e.Tokens) (e.Rules)>,
50  <FindAlive e.Rules> :: e.Alive,
51  <NTWithout (e.Alive) (e.Rules)> :: e.Dead,
52  {
53  e.Dead : ;
54  <Print "\nDead nonterminals:\n\n  ">,
55    <PrintSet e.Dead>,<PrintLn "\n">,
56    <Exit 1>;
57  },
58  <FindReachable e.Rules> :: e.Reachable,
59  <NTWithout (e.Reachable) (e.Rules)> :: e.Unreachable,
60  {
61  e.Unreachable : ;
62  <Print "\nUnreachable nonterminals:\n\n  ">,
63    <PrintSet e.Unreachable>,<PrintLn "\n">,
64    <Exit 1>;
65  },
66  <FindNullable e.Rules> :: e.Nullable,
67  {
68  e.Nullable : ;
69  <Print "\nNullable nonterminals:\n\n  ">,
70    <PrintSet e.Nullable>,<PrintLn "\n">;
71  },
72  e.Rules : (s.Start e) e,
73  ("$START" ( (N s.Start) (T "$END") )) e.Rules :: e.Rules_,
74  <FindStarters (e.Nullable) (e.Rules_)> :: e.SEnv,
75  <PrintLn "\nThe starters of nonterminals:">,
76  e.SEnv : t e.SEnv1,
77  <PrintEnv e.SEnv1>,<PrintLn>,
78  <FindFollowers (e.Nullable) (e.SEnv) (e.Rules_)> :: e.FEnv,
79  <PrintLn "\nThe followers of nullable nonterminals:">,
80  e.FEnv : t e.FEnv1,
81  <EnvWith (e.Nullable) (e.FEnv1)> :: e.FEnv1,
82  <PrintEnv e.FEnv1>,<PrintLn>,
83  <Print "\n*** Annotated grammar ***\n\n">,
84  <PrintAnnGrammar (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules)>
85  ;
86
87NTWithout (e.NTL) (e.Rules) =
88  e.Rules :
89  {
90  = ;
91  (s.N e) e.Rest =
92    {
93    e.NTL : e s.N e,
94      = <NTWithout (e.NTL) (e.Rest)>;
95      = s.N <NTWithout (e.NTL) (e.Rest)>;
96    };
97  };
98
99EnvWith (e.NTL) (e.Env) =
100  e.Env :
101  {
102  = ;
103  (sN (eV)) e.Rest =
104    {
105    e.NTL : e sN e
106      = (sN (eV)) <EnvWith (e.NTL) (e.Rest)>;
107      = <EnvWith (e.NTL) (e.Rest)>;
108    };
109  };
110
111FindAlive e.Rules =
112  <IterAlive () (e.Rules)>;
113
114IterAlive (e.Alive) (e.Rules) =
115  <PrintLnCh &StdErr "Alive iteration ...">,
116  <NextAlive (e.Alive) (e.Rules)> :: e.NextAlive,
117  {
118  e.Alive : e.NextAlive,
119    = e.Alive;
120    = <IterAlive (e.NextAlive) (e.Rules)>;
121  };
122
123NextAlive (e.Alive) (e.Rules) =
124  e.Rules :
125  {
126  = e.Alive;
127  (s.N e.L) e.Rest =
128    {
129    e.L : e (eR) e,
130      # \{ eR : e (N sX) e, # \{ e.Alive : e sX e; }; },
131      = <NextAlive (<SetUnion (e.Alive) (sN)>) (e.Rest)>;
132    = <NextAlive (e.Alive) (e.Rest)>;
133    };
134  };
135
136FindReachable e.Rules =
137  e.Rules : (s.Start e) e,
138  <IterReachable (s.Start) (e.Rules)>;
139
140IterReachable (e.Reachable) (e.Rules) =
141  <PrintLnCh &StdErr "Reachable iteration ...">,
142  <NextReachable (e.Reachable) (e.Rules)> :: e.NextReachable,
143  {
144  e.Reachable : e.NextReachable,
145    = e.Reachable;
146    = <IterReachable (e.NextReachable) (e.Rules)>;
147  };
148
149NextReachable (e.Reachable) (e.Rules) =
150  e.Rules :
151  {
152  = e.Reachable;
153  (s.N e.L) e.Rest =
154    {
155    e.Reachable : e s.N e =
156      <MkSet <ExtractNT e.L>> :: e.NewReachable,
157      <SetUnion (e.Reachable) (e.NewReachable)> :: e.Reachable,
158      = <NextReachable (e.Reachable) (e.Rest)>;
159    = <NextReachable (e.Reachable) (e.Rest)>;
160    };
161  };
162
163FindNullable e.Rules =
164  <IterNullable () (e.Rules)>;
165
166IterNullable (e.Nullable) (e.Rules) =
167  <PrintLnCh &StdErr "Nullable iteration ...">,
168  <NextNullable (e.Nullable) (e.Rules)> :: e.NextNullable,
169  {
170  e.Nullable : e.NextNullable,
171    = e.Nullable;
172    = <IterNullable (e.NextNullable) (e.Rules)>;
173  };
174
175NextNullable (e.Nullable) (e.Rules) =
176  e.Rules :
177  {
178  = e.Nullable;
179  (s.N e.L) e.Rest =
180    {
181    e.L : e (eR) e,
182      <IsNullableRhs (e.Nullable) (eR)>,
183      <SetUnion (e.Nullable) (s.N)> :: e.Nullable,
184      = <NextNullable (e.Nullable) (e.Rest)>;
185    = <NextNullable (e.Nullable) (e.Rest)>;
186    };
187  };
188
189IsNullableRhs (e.Nullable) (eR) =
190  # \{
191  eR : e (T sX) e;
192  eR : e (N sX) e, # \{ e.Nullable : e sX e; };
193  };
194
195FindStarters (e.Nullable) (e.Rules) =
196  <RulesToEnv e.Rules> :: e.SEnv,
197  <IterStarters (e.Nullable) (e.SEnv) (e.Rules)>;
198
199IterStarters (e.Nullable) (e.SEnv) (e.Rules) =
200  <PrintLnCh &StdErr "Starters iteration ...">,
201  <NextStarters (e.Nullable) (e.SEnv) (e.Rules)> :: e.NextSEnv,
202  {
203  e.SEnv : e.NextSEnv,
204    = e.SEnv;
205    = <IterStarters (e.Nullable) (e.NextSEnv) (e.Rules)>;
206  };
207
208NextStarters (e.Nullable) (e.SEnv) (e.Rules) =
209  e.Rules :
210  {
211  = e.SEnv;
212  (s.N e.L) e.Rest =
213    <RhsListStarters (e.Nullable) (e.SEnv) (e.L)> :: e.NewStarters,
214    <LookupEnv s.N (e.SEnv)> :: e.OldStarters,
215    <SetUnion (e.OldStarters) (e.NewStarters)> :: e.NewStarters,
216    <UpdateEnv s.N (e.NewStarters) (e.SEnv)> :: e.SEnv,
217      = <NextStarters (e.Nullable)(e.SEnv) (e.Rest)>;
218  };
219
220RhsListStarters (e.Nullable) (e.SEnv) (e.L) =
221  e.L :
222  {
223  = ;
224  (eR) e.Rest =
225    <SetUnion ( <RhsStarters (e.Nullable) (e.SEnv) (eR)> )
226               ( <RhsListStarters (e.Nullable) (e.SEnv) (e.Rest)> )>;
227  };
228
229RhsStarters (e.Nullable) (e.SEnv) (eR) =
230  eR :
231  {
232  = ;
233  (T sX) e.Rest = sX;
234  (N sX) e.Rest =
235    <LookupEnv sX (e.SEnv)> :: e.XStarters,
236    {
237    e.Nullable : e sX e =
238      <SetUnion (e.XStarters)
239                 ( <RhsStarters (e.Nullable) (e.SEnv) (e.Rest)> )>;
240    = e.XStarters;
241    };
242  };
243
244FindFollowers (e.Nullable) (e.SEnv) (e.Rules) =
245  <RulesToEnv e.Rules> :: e.FEnv,
246  <IterFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules)>;
247
248IterFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules) =
249  <PrintLnCh &StdErr "Followers iteration ...">,
250  <NextFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules)> :: e.NextFEnv,
251  {
252  e.FEnv : e.NextFEnv,
253    = e.FEnv;
254    = <IterFollowers (e.Nullable) (e.SEnv) (e.NextFEnv) (e.Rules)>;
255  };
256
257NextFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules) =
258  e.Rules :
259  {
260  = e.FEnv;
261  (s.N e.L) e.Rest =
262    <RhsListFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (e.L)> :: e.FEnv,
263      = <NextFollowers (e.Nullable) (e.SEnv) (e.FEnv) (e.Rest)>;
264  };
265
266RhsListFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (e.L) =
267  e.L :
268  {
269  = e.FEnv;
270  (eR) e.Rest =
271    <RhsFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (eR)> :: e.FEnv,
272    <RhsListFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (e.Rest)>;
273  };
274
275RhsFollowers sN (e.Nullable) (e.SEnv) (e.FEnv) (eR) =
276  eR :
277  {
278  = e.FEnv;
279  (T sX) e.Rest
280    = <RhsFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (e.Rest)>;
281  (N sX) e.Rest,
282    <UpdateFollowers sN (e.Nullable) (e.SEnv) (e.FEnv) sX (e.Rest)>
283      :: e.FEnv,
284    = <RhsFollowers s.N (e.Nullable) (e.SEnv) (e.FEnv) (e.Rest)>;
285  };
286
287UpdateFollowers sN (e.Nullable) (e.SEnv) (e.FEnv) sX (e.Rest) =
288  <LookupEnv sX (e.FEnv)> :: e.OldFollowers,
289  <RhsStarters (e.Nullable) (e.SEnv) (e.Rest)> :: e.NewFollowers,
290  <SetUnion (e.OldFollowers) (e.NewFollowers)> :: e.NewFollowers,
291  {
292  <IsNullableRhs (e.Nullable) (e.Rest)>
293    = <SetUnion ( e.NewFollowers ) ( <LookupEnv sN (e.FEnv)> )>;
294    = e.NewFollowers;
295  } :: e.NewFollowers,
296  <UpdateEnv sX (e.NewFollowers) (e.FEnv)>;
297
298PrintAnnGrammar (e.Nullable) (e.SEnv) (e.FEnv) (e.Rules) =
299  e.Rules :
300  {
301  = ;
302  (sN eL) e.Rest =
303    <PrintAnnSym (e.Nullable) sN><PrintLn>
304    <PrintAnnRules ":" (e.Nullable) (e.SEnv) (e.FEnv) () sN (eL)>
305    <PrintAnnGrammar (e.Nullable) (e.SEnv) (e.FEnv) (e.Rest)>;
306  };
307
308PrintAnnRules sC (e.Nullable) (e.SEnv) (e.FEnv) (e.S) sN (eL) =
309  eL :
310  {
311  = <PrintLn ";\n">;
312  (eR) e.Rest =
313    <RhsStarters (e.Nullable) (e.SEnv) (eR)> :: e.Sel,
314    {
315    <IsNullableRhs (e.Nullable) (eR)>
316      = <SetUnion (e.Sel) ( <LookupEnv sN (e.FEnv)> )>;
317      = e.Sel;
318    } :: e.Sel,
319    <Print sC><Print " "><PrintSet e.Sel><PrintLn>,
320    {
321    e.S : e s0 e, e.Sel : e s0 e =
322      <PrintLnCh &StdErr "*** Conflict !!! ***">,
323      <PrintLn "*** Conflict !!! ***">;
324      = ;
325    },
326    <SetUnion (e.S) (e.Sel)> :: e.S,
327    <Print "     "><PrintAnnRhs (e.Nullable) (eR)><PrintLn>,
328    = <PrintAnnRules "|" (e.Nullable) (e.SEnv) (e.FEnv) (e.S) sN (e.Rest)>;
329  };
330
331SetUnion
332  {
333  () (eY) = eY;
334  (eX) () = eX;
335  (eX) (eY), eX : sA eX1, eY : sB eY1 =
336    {
337    <Lt (sA)(sB)> = sA <SetUnion (eX1) (eY)>;
338    <Gt (sA)(sB)> = sB <SetUnion (eX)  (eY1)>;
339                   = sA <SetUnion (eX1) (eY1)>;
340    };
341  };
342
343MkSet  eS =
344  <Length eS> :: sLen,
345  {
346  <Le (sLen) (1)>
347    = eS;
348    = <Div sLen 2> :: sK,
349      <Left 0 sK eS> :: eS1,
350      <Middle sK 0 eS> :: eS2,
351        <SetUnion ( <MkSet eS1> )( <MkSet eS2> )>;
352  };
353
354ExtractNT
355  {
356  = ;
357  (eR) e.Rest =
358    <ExtractNTRhs eR> <ExtractNT e.Rest>;
359  };
360
361ExtractNTRhs
362  {
363  e (N s.N) e.Rest
364    = s.N <ExtractNTRhs e.Rest>;
365  e.Rest = ;
366  };
367
368RulesToEnv
369  {
370  = ;
371  (sN e) e.Rest
372    = (sN ()) <RulesToEnv e.Rest>;
373  };
374
375LookupEnv
376  sN (e (sN (eV)) e) = eV;
377
378UpdateEnv
379  sN (eV) (e1 (sN (e)) e2) = e1 (sN (eV)) e2;
Note: See TracBrowser for help on using the repository browser.