p2 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151
  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.