Pristine Ack-5.5
[Ack-5.5.git] / lang / occam / comp / occam.g
1 /* $Id: occam.g,v 1.12 1994/06/24 12:27:07 ceriel Exp $ */
2 /*
3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
4  * See the copyright notice in the ACK home directory, in the file "Copyright".
5  */
6 /*      OCCAM           */
7 {
8 #include "token.h"
9 #include "symtab.h"
10 #include "expr.h"
11 #include "code.h"
12 #include "sizes.h"
13 #include <system.h>
14 #include <em.h>
15
16 #define MAXERRORS       10      /* Maximum number of insert/delete errors */
17
18 static void nonconst(), nonpositive(), rep_cleanup(), check_assoc();
19 void init_builtins();
20 char *strcpy();
21
22 extern int lineno, LLsymb;
23 union type_info info, none;
24 }
25 %token  AFTER, ALLOCATE, ALT, AND, ANY, BYTE, CHAN, DEF, FALSE, FOR, IF, LOAD;
26 %token  NOT, NOW, OR, PAR, PLACED, PORT, PRI, PROC, SEQ, SKIP, TABLE, TRUE;
27 %token  VALUE, VAR, WAIT, WHILE;
28 %token  IDENTIFIER, NUMBER, CHAR_CONST, STRING;
29 %token  AS, LE, GE, NE, LS, RS, BA, BO, BX, BS;
30
31 %start  occam, program;
32
33 program :                       {       init_builtins();
34                                         header();
35                                 }
36           process
37         ;
38
39 process : primitive
40         | construct
41         |                       {       sym_down(); }
42           declaration ':' process
43                                 {       sym_up(); }
44         ;
45
46 primitive { struct expr *e; } :
47           statement(&e)         {       if (!valueless(e))
48                                                 report("primitive may not have a value");
49                                         code_void(e);
50                                         destroy(e);
51                                 }
52         | WAIT val_expr(&e)     {       int BEGIN=0, END=0, TEST=0;
53                                         check_wait(e);
54                                         no_deadlock();
55                                         branch(&TEST);
56                                         Label(new_label(&BEGIN));
57                                         resumenext();
58                                         Label(TEST);
59                                         code_bool(e, positive, &END, &BEGIN);
60                                         Label(END);
61                                         destroy(e);
62                                 }
63         | SKIP
64         ;
65
66 guard(register *F;)             {       struct expr *e1, *e2;
67                                         register full_guard=0;
68                                         int T=0;
69                 static char EXPECT_INP[]="input process expected as guard";
70                                 } :
71           expression(&e1)
72           [       '&'           {       full_guard=1;
73                                         if (!valued(e1))
74                                                 report("boolean part of guard has no value");
75                                         code_bool(e1, positive, &T, F);
76                                         Label(T);
77                                 }
78                   [       statement(&e2)
79                                 {       if (!input_process(e2))
80                                                 report(EXPECT_INP);
81                                         code_any(e2, F);
82                                         destroy(e2);
83                                 }
84                           | WAIT val_expr(&e2)
85                                 {       check_wait(e2);
86                                         code_bool(e2, positive, &T, F);
87                                         Label(T);
88                                         destroy(e2);
89                                 }
90                           | SKIP
91                   ]
92           ]?
93                                 {       if (!full_guard) {
94                                                 if (!input_process(e1))
95                                                         report(EXPECT_INP);
96                                                 code_any(e1, F);
97                                         }
98                                         destroy(e1);
99                                 }
100         | WAIT val_expr(&e1)
101                                 {       check_wait(e1);
102                                         code_bool(e1, positive, &T, F);
103                                         Label(T);
104                                         destroy(e1);
105                                 }
106         | SKIP
107         ;
108
109 guarded_process(register *END;) {       struct symbol *v;
110                                         struct expr *e1, *e2;
111                                         struct replicator to_test;
112                                         register line, oind;
113                                         int F=0;
114                                 } :
115           guard(&F) process     {       branch(END);
116                                         Label(F);
117                                 }
118         | ALT                   {       line=lineno; oind=ind; }
119           [       %if (line==lineno)
120                   replicator(&v, &e1, &e2)
121                                 {       rep_init(v, e1, e2, &to_test); }
122                   guarded_process(END)
123                                 {       rep_test(v, e1, e2, &to_test);
124                                         rep_cleanup(e1, e2);
125                                 }
126                 |
127                   [ %while (tabulated(oind, ind)) guarded_process(END) ]*
128           ]
129         ;
130
131 conditional(register *END; )    {       struct symbol *v;
132                                         struct expr *e1, *e2;
133                                         struct replicator to_test;
134                                         register line, oind;
135                                         int T=0, F=0;
136                                 } :
137           val_expr(&e1)         {       if (!valued(e1))
138                                                 report("conditional needs valued expression");
139                                         code_bool(e1, positive, &T, &F);
140                                         Label(T);
141                                         destroy(e1);
142                                 }
143           process
144                                 {       branch(END);
145                                         Label(F);
146                                 }
147         | IF                    {       line=lineno; oind=ind; }
148           [       %if (line==lineno)
149                   replicator(&v, &e1, &e2)
150                                 {       rep_init(v, e1, e2, &to_test); }
151                   conditional(END)
152                                 {       rep_test(v, e1, e2, &to_test);
153                                         rep_cleanup(e1, e2);
154                                 }
155                 |
156                   [ %while (tabulated(oind, ind)) conditional(END) ]*
157           ]
158         ;
159
160 replicator(register struct symbol **s; register struct expr **e1; register struct expr **e2; )
161                                 {       register char *index; }:
162           IDENTIFIER            {       index=token.t_sval; }
163           '=' '[' val_expr(e1) FOR val_expr(e2) ']'
164                                 {       if (!valued(*e1) || !valued(*e2))
165                                                 report("replicator needs valued expressions");
166                                         sym_down();
167                                         var_memory(&info, T_VAR, 1);
168                                         *s=insert(index,
169                                         T_VAR|T_REP|T_USED|T_ASSIGNED, 1, &info);
170                                 }
171         ;
172
173 construct                       {       struct symbol *v;
174                                         struct expr *e1, *e2;
175                                         struct replicator to_test;
176                                         register line, oind;
177                                         int BEGIN=0, END=0, NONZERO;
178                                 }:
179           SEQ                   {       line=lineno; oind=ind; }
180           [       %if (line==lineno)
181                   replicator(&v, &e1, &e2)
182                                 {       rep_init(v, e1, e2, &to_test); }
183                   process
184                                 {       rep_test(v, e1, e2, &to_test);
185                                         rep_cleanup(e1, e2);
186                                 }
187                 |
188                   [ %while (tabulated(oind, ind)) process ]*
189           ]
190         | PRI ?
191           [       PAR           {       line=lineno; oind=ind;
192                                         par_begin();
193                                 }
194                   [       %if (line==lineno)
195                           replicator(&v, &e1, &e2)
196                                 {       rep_init(v, e1, e2, &to_test);
197                                         NONZERO=0;
198                                         par_fork(&NONZERO);
199                                 }
200                           process
201                                 {       branch(&END);
202                                         Label(NONZERO);
203                                         rep_test(v, e1, e2, &to_test);
204                                         rep_cleanup(e1, e2);
205                                 }
206                         |
207                           [ %while (tabulated(oind, ind))
208                                 {       NONZERO=0;
209                                         par_fork(&NONZERO);
210                                 }
211                                   process
212                                 {       branch(&END);
213                                         Label(NONZERO);
214                                 }
215                           ]*
216                   ]
217                                 {       Label(END);
218                                         par_end();
219                                 }
220                 | ALT           {       line=lineno; oind=ind;
221                                         no_deadlock();
222                                         Label(new_label(&BEGIN));
223                                 }
224                   [       %if (line==lineno)
225                           replicator(&v, &e1, &e2)
226                                 {       rep_init(v, e1, e2, &to_test); }
227                           guarded_process(&END)
228                                 {       rep_test(v, e1, e2, &to_test);
229                                         rep_cleanup(e1, e2);
230                                 }
231                         |
232                           [ %while (tabulated(oind, ind)) guarded_process(&END)
233                           ]*
234                   ]
235                                 {       resumenext();
236                                         branch(&BEGIN);
237                                         Label(END);
238                                 }
239           ]
240         | IF                    {       line=lineno; oind=ind; }
241           [       %if (line==lineno)
242                   replicator(&v, &e1, &e2)
243                                 {       rep_init(v, e1, e2, &to_test); }
244                   conditional(&END)
245                                 {       rep_test(v, e1, e2, &to_test);
246                                         rep_cleanup(e1, e2);
247                                 }
248                 |
249                   [ %while (tabulated(oind, ind)) conditional(&END) ]*
250           ]
251                                 {       Label(END); }
252         | WHILE val_expr(&e1)   {       if (!valued(e1))
253                                                 report("WHILE needs valued expression");
254                                         branch(&END);
255                                         Label(new_label(&BEGIN));
256                                 }
257           process
258                                 {       int DONE=0;
259                                         Label(END);
260                                         code_bool(e1, negative, &DONE, &BEGIN);
261                                         Label(DONE);
262                                         destroy(e1);
263                                 }
264         ;
265
266 subscript(register *byte; register struct expr **e; )
267                                 {       struct expr *e1;
268                                         register slice=0, err=0;
269                                 } :
270           '['                   {       *byte=0; }
271           [       BYTE          {       *byte=T_BYTE; }
272           ]?
273           val_expr(e)           {       if (!valued(*e))
274                                                 err++;
275                                 }
276           [       FOR expression(&e1)
277                                 {       static char siz[]="slize size";
278                                         if (!constant(e1)) {
279                                                 if (!err)
280                                                         nonconst(siz);
281                                                 destroy(e1);
282                                                 e1=new_const(0L);
283                                         } else
284                                         if (e1->u.cst<=0)
285                                                 nonpositive(siz);
286                                         *e=new_node(FOR, *e, e1, *byte);
287                                         slice=1;
288                                 }
289           ]?
290           ']'
291                                 {       if (err)
292                                                 report(slice ?
293                                 "slice must be '[' value FOR constant ']'" :
294                                 "subscript needs valued expression");
295                                 }
296         ;
297
298 chan    { register type, arr_siz=1; register char *name; struct expr *e; }:
299           IDENTIFIER            {       type=T_CHAN;
300                                         name=token.t_sval;
301                                 }
302           [       '[' expression(&e) ']'
303                                 {       static char siz[]="channel array size";
304                                         if (!constant(e))
305                                                 nonconst(siz);
306                                         else
307                                         if (e->u.cst<0)
308                                                 nonpositive(siz);
309                                         else
310                                                 arr_siz=e->u.cst;
311                                         destroy(e);
312                                         type|=T_ARR;
313                                 }
314           ]?
315                                 {       chan_memory(&info, arr_siz);
316                                         chan_init(&info, arr_siz);
317                                         insert(name, type, arr_siz, &info);
318                                 }
319         ;
320
321 var                             {       register type, byte=0, arr_siz=1;
322                                         register char *name;
323                                         struct expr *e;
324                                 }:
325           IDENTIFIER            {       type=T_VAR; name=token.t_sval; }
326           [       '['
327                   [       BYTE  {       byte=T_BYTE; }
328                   ]?
329                   expression(&e) ']'
330                                 {       static char siz[]="variable array size";
331                                         if (!constant(e))
332                                                 nonconst(siz);
333                                         else
334                                         if (e->u.cst<=0)
335                                                 nonpositive(siz);
336                                         else
337                                                 arr_siz=e->u.cst;
338                                         destroy(e);
339                                         type|=T_ARR|byte;
340                                 }
341           ]?
342                                 {       var_memory(&info, type, arr_siz);
343                                         insert(name, type, arr_siz, &info);
344                                 }
345         ;
346
347 const_def { register char *name; struct expr *e; }:
348           IDENTIFIER            {       name=token.t_sval; }
349           '=' expression(&e)
350                                 {       if (!constant(e) && !arr_constant(e))
351                                                 nonconst("expression in constant definition");
352                                         info.t_const=e;
353                                         insert(name, T_CONST|T_USED, 0, &info);
354                                 }
355         ;
356
357 form_parm(register struct par_list ***aapars; register *g_type;)
358                                 {       register char *name;
359                                         register type= *g_type;
360                                 }:
361           [       VAR           {       type=T_VAR|T_ASSIGNED|T_USED; }
362                 | CHAN          {       type=T_CHAN; }
363                 | VALUE         {       type=T_VALUE|T_ASSIGNED; }
364           ]?
365           IDENTIFIER            {
366                                         if (type<0) {
367                                                 report("VAR, CHAN or VALUE expected");
368                                                 type=T_VAR;
369                                         }
370                                         name=token.t_sval;
371                                         *g_type=type;
372                                 }
373           [       '[' ']'
374                                 {       type|=T_ARR; }
375           ]?
376                                 {       pars_add(aapars, type&(T_TYPE|T_ARR),
377                                           insert(name, type|T_PARAM, 0, &none));
378                                 }
379         ;
380
381 form_parms(struct par_list **apars;) { int type= -1; }:
382           '(' form_parm(&apars, &type)
383           [       ',' form_parm(&apars, &type)
384           ]*
385           ')'
386         ;
387
388 declaration:
389           VAR
390           var [ ',' var ]*
391         | CHAN
392           chan [ ',' chan ]*
393         | DEF
394           const_def [ ',' const_def ]*
395         | proc_declaration
396         ;
397         
398 proc_declaration                {       struct par_list *pars=nil;
399                                         register struct symbol *proc;
400                                         int OVER=0;
401                                         register old_min_offset;
402                                 }:
403           PROC IDENTIFIER       {       branch(&OVER);
404                                         proc=insert(token.t_sval,
405                                                 T_PROC|T_RECURS, 0, &none);
406                                         old_min_offset=min_offset;
407                                         sym_down();
408                                         prologue(proc);
409                                 }
410           form_parms(&pars) ?   {       form_offsets(pars);
411                                         proc->s_info.proc.pars=pars;
412                                 }
413           '=' process           {       epilogue(proc);
414                                         sym_up();
415                                         proc->s_type&= ~T_RECURS;
416                                         min_offset=old_min_offset;
417                                         Label(OVER);
418                                 }
419         ;
420
421 vector_constant(register struct expr **e;)
422                                 {       struct table *pt=nil, **apt= &pt;
423                                         register Tlen=0;
424                                 }:
425           table(e)
426         | STRING                {       register char *ps= token.t_sval;
427                                         register len;
428
429                                         Tlen+= len= (*ps++ & 0377);
430                                         while (--len>=0)
431                                                 table_add(&apt, (long) *ps++);
432                                 }
433           [ %while (1)    STRING
434                                 {       register char *ps= token.t_sval;
435                                         register len;
436
437                                         Tlen+= len= (*ps++ & 0377);
438                                         while (--len>=0)
439                                                 table_add(&apt, (long) *ps++);
440                                 }
441           ]*
442                                 {       apt= &pt;
443                                         table_add(&apt, (long) Tlen);
444                                         *e=new_table(E_BTAB, pt);
445                                 }
446         ;
447
448 item(register struct expr **e;)
449                                 {       struct expr *e1;
450                                         register struct symbol *var;
451                                         struct par_list *pars=nil;
452                                         register line, oind;
453                                         int byte, err=0, subs_call=0;
454                                         struct expr_list *elp=nil, **aelp= &elp;
455                                 }:
456           IDENTIFIER            {       line=lineno;
457                                         oind=ind;
458                                         var=searchall(token.t_sval);
459
460                                         if (var_constant(var))
461                                                 *e=copy_const(var->s_info.t_const);
462                                         else {
463                                                 if (var_proc(var))
464                                                         pars=var->s_info.proc.pars;
465                                                 *e=new_var(var);
466                                         }
467                                 }
468           [ %while (line==lineno || tabulated(oind, ind))
469                   [       subscript(&byte, &e1)
470                                 {       *e=new_node('[', *e, e1, byte); }
471                         | '('   {       if (!var_declared(var)) {
472                                                 var->s_type=T_PROC|T_USED|T_NOTDECL;
473                                                 var->s_info.proc.pars=nil;
474                                                 err=1;
475                                         }
476                                         if (!var_proc(var)) {
477                                                 report("%s is not a named process",
478                                                         var->s_name);
479                                                 err=1;
480                                         }
481                                 }
482                           expression(&e1)
483                                 {       check_param(&pars, e1, &err);
484                                         expr_list_add(&aelp, e1);
485                                 }
486                           [       ',' expression(&e1)
487                                 {       check_param(&pars, e1, &err);
488                                         expr_list_add(&aelp, e1);
489                                 }
490                           ]*
491                                 {
492                                         if (pars!=nil)
493                                                 report("too few actual parameters");
494                                 }
495                           ')'
496                                 {       *e=new_call(*e, elp); }
497                   ]
498                                 {       subs_call=1; }
499           ]?
500                                 {       if (!subs_call && var_proc(var)) {
501                                                 if (pars!=nil)
502                                                         report("no actual parameters");
503                                                 *e=new_call(*e, (char *)nil);
504                                         }
505                                 }
506         | vector_constant(e)
507           [       subscript(&byte, &e1)
508                                 {       *e=new_node('[', *e, e1, byte); }
509           ]?
510         ;
511
512 statement(register struct expr **e;)
513                                 {       struct expr *e1;
514                                         struct expr_list *elp=nil, **aelp= &elp;
515                                         register out;
516                                 }:
517           item(e)
518           [       AS expression(&e1)
519                                 {       *e=new_node(AS, *e, e1, 0); }
520                 | [
521                           '?'   {       out=0; }
522                         | '!'   {       out=1; }
523                   ]
524                   io_arg(&e1)
525                                 {       if (e1!=nil) check_io(out, e1);
526                                         expr_list_add(&aelp, e1);
527                                 }
528                   [ %while (1) ';' io_arg(&e1)
529                                 {       if (e1!=nil) check_io(out, e1);
530                                         expr_list_add(&aelp, e1);
531                                 }
532                   ]*
533                                 {       *e=new_io(out, *e, elp); }
534           ]?
535         ;
536
537 io_arg(struct expr **e; ) :
538           expression(e)
539         | ANY                   {       *e=nil; }
540         ;
541
542 table(register struct expr **e;)        
543                                 {       struct table *pt=nil, **apt= &pt;
544                                         struct expr *e1;
545                                         register type;
546                                 }:
547           TABLE '['             {       type=E_TABLE; }
548           [       BYTE          {       type=E_BTAB; }
549           ]?
550           expression(&e1)       {       if (!constant(e1))
551                                                 nonconst("table element");
552                                         else
553                                                 table_add(&apt, e1->u.cst);
554                                         destroy(e1);
555                                 }
556           [       ',' expression(&e1)
557                                 {       if (!constant(e1))
558                                                 nonconst("table element");
559                                         else
560                                                 table_add(&apt, e1->u.cst);
561                                         destroy(e1);
562                                 }
563           ]*
564                                 {       *e=new_table(type, pt); }
565           ']'
566         ;
567
568 arithmetic_op:  '+' | '-' | '*' | '/' | BS
569         ;
570
571 comparison_op:  '<' | '>' | LE | GE | NE | '=' | AFTER
572         ;
573
574 logical_op:     BA | BO | BX
575         ;
576
577 boolean_op:     AND | OR
578         ;
579
580 shift_op:       LS | RS
581         ;
582
583 monadic_op(register *op;):
584           '-'                   {       *op='~'; }
585         | NOT                   {       *op=NOT; }
586         ;
587
588 operator: arithmetic_op | comparison_op | logical_op | boolean_op | shift_op
589         ;
590
591 element(register struct expr **e;) :
592           %default NUMBER       {       *e=new_const(token.t_lval); }
593         | statement(e)
594         | TRUE                  {       *e=new_const(-1L); }
595         | FALSE                 {       *e=new_const(0L); }
596         | NOW                   {       *e=new_now(); }
597         | CHAR_CONST            {       *e=new_const(token.t_lval); }
598         | '(' expression(e) ')' {       if (valueless(*e))
599                                                 warning("primitive should not be parenthesized");
600                                 }
601         ;
602
603 expression(register struct expr **e;)
604                                 {       int op=0;
605                                         struct expr *e1;
606                                 }:
607           element(e)
608           [ %while (1)          {       if (op!=0) check_assoc(op, LLsymb);
609                                         op=LLsymb;
610                                 }
611                   operator element(&e1)
612                                 {       *e=new_node(op, *e, e1, 0); }
613           ]*
614         | monadic_op(&op) element(&e1)
615                                 {       *e=new_node(op, e1, (char *)nil, 0); }
616         ;
617
618 val_expr(register struct expr **e;) :
619           expression(e)         {       used(*e); }
620         ;
621
622 %lexical scanner;
623 {
624 int err=0;
625
626 main(argc, argv) register argc; register char **argv;
627 {
628         while (argc > 1 && argv[1][0] == '-') {
629                 do_option(&argv[1][1]);
630                 argc--;
631                 argv++;
632         }
633
634         leader();
635         occam();
636         trailer();
637
638         exit(err);
639 }
640
641 do_option(text)
642         char *text;
643 {
644         extern int Lflag;
645
646         switch(*text++) {
647
648         default:
649                 fatal("illegal option: %c", *--text);
650
651         case 'L' :                      /* no fil/lin */
652                 Lflag++;
653                 break;
654         case 'V' :      /* set object sizes and alignment requirements  */
655         {
656                 arith size, align;
657                 char c;
658
659                 while (c = *text++)     {
660                         size = txt2int(&text);
661                         switch (c)      {
662                         case 'w':       /* word         */
663                                 if (size != (arith)0)
664                                         wz = size;
665                                 break;
666                         case 'p':       /* pointer      */
667                                 if (size != (arith)0)
668                                         pz = size;
669                                 break;
670                         case 'l':       /* long         */
671                                 if (size != (arith)0)
672                                         vz = size;
673                                 break;
674                         default:
675                                 fatal("-V: bad type indicator %c\n", c);
676                         }
677                 }
678                 break;
679         }
680         }
681 }
682
683 int
684 txt2int(tp)
685         char **tp;
686 {
687         /*      the integer pointed to by *tp is read, while increasing
688                 *tp; the resulting value is yielded.
689         */
690         register int val = 0, ch;
691         
692         while (ch = **tp, ch >= '0' && ch <= '9')       {
693                 val = val * 10 + ch - '0';
694                 (*tp)++;
695         }
696         return val;
697 }
698
699 LLmessage(tk) register tk;
700 {
701         static errors=0;
702
703         if (tk>0) {
704                 repeat_token(LLsymb);
705                 warning("syntax error: %s expected (inserted)", tokenname(tk, 1));
706         } else
707         if (tk==0)
708                 warning("syntax error: bad token %s (deleted)", tokenname(LLsymb, 0));
709         else { /* tk<0 */
710                 warning("syntax error: garbage at end of program");
711         }
712         if (++errors==MAXERRORS) {
713                 fprint(STDERR, "Too many insert/delete errors. Compiler ends.\n");
714                 err=1; trailer(); exit(1);
715         }
716 }
717
718 static void nonconst(siz) char *siz;
719 {
720         report("%s should be a constant", siz);
721 }
722
723 static void nonpositive(siz) char *siz;
724 {
725         report("%s must be positive", siz);
726 }
727
728 static void rep_cleanup(e1, e2) struct expr *e1, *e2;
729 {
730         destroy(e1);
731         destroy(e2);
732         sym_up();
733 }
734
735 static void check_assoc(prev_op, op) register prev_op, op;
736 {
737         switch (op) {
738                 char prev[5];
739         case '+':       case '*':
740         case AND:       case OR:
741         case BA:        case BO:        case BX:
742                 if (prev_op==op) break;
743         default:
744                 strcpy(prev, tokenname(prev_op, 0));
745
746                 warning("Operators %s and %s don't associate",
747                         prev, tokenname(op, 0)
748                 );
749         }
750 }
751
752 void
753 No_Mem()
754 {
755         fatal("out of memory");
756 }
757 }