doc/occam/p2

   1 .NH
   2 The Compiler
   3 .PP
   4 The compiler is written in \fBC\fP using LLgen and Lex and compiles
   5 Occam programs to EM code, using the procedural interface as defined for EM.
   6 In the following sub-sections we describe the LLgen parser generator and
   7 the aspect of indentation.
   8 .NH 2
   9 The LLgen Parser Generator
  10 .PP
  11 LLgen accepts a Context Free syntax extended with the operators `\f(CW*\fP', `\f(CW?\fP' and `\f(CW+\fP'
  12 that have effects similar to those in regular expressions.
  13 The `\f(CW*\fP' is the closure set operator without an upperbound; `\f(CW+\fP' is the positive
  14 closure operator without an upperbound; `\f(CW?\fP' is the optional operator;
  15 `\f(CW[\fP' and `\f(CW]\fP' can be used for grouping.
  16 For example, a comma-separated list of expressions can be described as:
  17 .DS
  18 .ft CW
  19         expression_list:
  20                   expression [ ',' expression ]*
  21                 ;
  22 .ft
  23 .DE
  24 .LP
  25 Alternatives must be separated by `\f(CW|\fP'.
  26 C code (``actions'') can be inserted at all points between the colon and the
  27 semicolon.
  28 Variables global to the complete rule can be declared just in front of the
  29 colon enclosed in the brackets `\f(CW{\fP' and `\f(CW}\fP'.  All other declarations are local to
  30 their actions.
  31 Nonterminals can have parameters to pass information.
  32 A more mature version of the above example would be:
  33 .DS
  34 .ft CW
  35        expression_list(expr *e;)       {        expr e1, e2;    } :
  36                 expression(&e1)
  37                 [ ',' expression(&e2)
  38                                        {        e1=append(e1, e2);      }
  39                 ]*
  40                                        {        *e=e1;  }
  41               ;
  42 .ft
  43 .DE
  44 As LLgen generates a recursive-descent parser with no backtrack, it must at all
  45 times be able to determine what to do, based on the current input symbol.
  46 Unfortunately, this cannot be done for all grammars. Two kinds of conflicts
  47 are possible, viz. the \fBalternation\fP and \fBrepetition\fP conflict.
  48 An alternation confict arises if two sides of an alternation can start with the
  49 same symbol. E.g.
  50 .DS
  51 .ft CW
  52         plus:   '+' | '+' ;
  53 .ft
  54 .DE
  55 The parser doesn't know which `\f(CW+\fP' to choose (neither do we).
  56 Such a conflict can be resolved by putting an \fBif-condition\fP in front of
  57 the first conflicting production. It consists of a \fB``%if''\fP followed by a
  58 C-expression between parentheses.
  59 If a conflict occurs (and only if it does) the C-expression is evaluated and
  60 parsing continues along this path if non-zero. Example:
  61 .DS
  62 .ft CW
  63         plus:
  64                   %if (some_plusses_are_more_equal_than_others())
  65                   '+'
  66                 |
  67                   '+'
  68                 ;
  69 .ft
  70 .DE
  71 A repetition conflict arises when the parser cannot decide whether
  72 ``\f(CWproductionrule\fP'' in e.g. ``\f(CW[ productionrule ]*\fP'' must be chosen
  73 once more, or that it should continue.
  74 This kind of conflicts can be resolved by putting a \fBwhile-condition\fP right
  75 after the opening parentheses.  It consists of a \fB``%while''\fP
  76 followed by a C-expression between parentheses. As an example, we can look at
  77 the \fBcomma-expression\fP in C.  The comma may only be used for the
  78 comma-expression if the total expression is not part of another comma-separated
  79 list:
  80 .DS
  81 .nf
  82 .ft CW
  83         comma_expression:
  84                   sub_expression
  85                   [ %while (not_part_of_comma_separated_list())
  86                           ',' sub_expression
  87                   ]*
  88                 ;
  89 .ft
  90 .fi
  91 .DE
  92 Again, the \fB``%while''\fP is only used in case of a conflict.
  93 .LP
  94 Error recovery is done almost completely automatically. All the LLgen-user has to do
  95 is write a routine called \fILLmessage\fP to give the necessary error
  96 messages and supply information about terminals found missing.
  97 .NH 2
  98 Indentation
  99 .PP
 100 The way conflicts can be resolved are of great use to Occam. The use of
 101 indentation, to group statements, leads to many conflicts because the spaces
 102 used for indentation are just token separators to the lexical analyzer, i.e.
 103 ``white space''. The lexical analyzer can be instructed to generate `BEGIN' and
 104 `END' tokens at each indentation change, but that leads to great difficulties
 105 as expressions may occupy several lines, thus leading to indentation changes
 106 at the strangest moments. So we decided to resolve the conflicts by looking
 107 at the indentation ourselves. The lexical analyzer puts the current indentation
 108 level in the global variable \fIind\fP for use by the parser. The best example
 109 is the \fBSEQ\fP construct, which exists in two flavors, one with a replicator
 110 and one process:
 111 .DS
 112 .nf
 113 .ft CW
 114         seq i = [ 1 for str[byte 0] ]
 115                 out ! str[byte i]
 116 .ft
 117 .fi
 118 .DE
 119 and one without a replicator and several processes:
 120 .DS
 121 .nf
 122 .ft CW
 123         seq
 124                 in ? c
 125                 out ! c
 126 .ft
 127 .fi
 128 .DE
 129 The LLgen skeleton grammar to handle these two is:
 130 .DS
 131 .nf
 132 .ft CW
 133         SEQ                     {       line=yylineno; oind=ind; }
 134         [         %if (line==yylineno)
 135                   replicator
 136                   process
 137                 |
 138                   [ %while (ind>oind) process ]*
 139         ]
 140 .ft
 141 .fi
 142 .DE
 143 This shows clearly that, a replicator must be on the same line as the \fBSEQ\fP,
 144 and new processes are collected as long as the indentation level of each process
 145 is greater than the indentation level of \fBSEQ\fP (with appropriate checks on this
 146 identation).
 147 .PP
 148 Different indentation styles are accepted, as long as the same amount of spaces
 149 is used for each indentation shift. The ascii tab character sets the indentation
 150 level to an eight space boundary. The first indentation level found in a file
 151 is used to compare all other indentation levels to.