123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151 |
- .NH
- The Compiler
- .PP
- The compiler is written in \fBC\fP using LLgen and Lex and compiles
- Occam programs to EM code, using the procedural interface as defined for EM.
- In the following sub-sections we describe the LLgen parser generator and
- the aspect of indentation.
- .NH 2
- The LLgen Parser Generator
- .PP
- LLgen accepts a Context Free syntax extended with the operators `\f(CW*\fP', `\f(CW?\fP' and `\f(CW+\fP'
- that have effects similar to those in regular expressions.
- The `\f(CW*\fP' is the closure set operator without an upperbound; `\f(CW+\fP' is the positive
- closure operator without an upperbound; `\f(CW?\fP' is the optional operator;
- `\f(CW[\fP' and `\f(CW]\fP' can be used for grouping.
- For example, a comma-separated list of expressions can be described as:
- .DS
- .ft CW
- expression_list:
- expression [ ',' expression ]*
- ;
- .ft
- .DE
- .LP
- Alternatives must be separated by `\f(CW|\fP'.
- C code (``actions'') can be inserted at all points between the colon and the
- semicolon.
- Variables global to the complete rule can be declared just in front of the
- colon enclosed in the brackets `\f(CW{\fP' and `\f(CW}\fP'. All other declarations are local to
- their actions.
- Nonterminals can have parameters to pass information.
- A more mature version of the above example would be:
- .DS
- .ft CW
- expression_list(expr *e;) { expr e1, e2; } :
- expression(&e1)
- [ ',' expression(&e2)
- { e1=append(e1, e2); }
- ]*
- { *e=e1; }
- ;
- .ft
- .DE
- As LLgen generates a recursive-descent parser with no backtrack, it must at all
- times be able to determine what to do, based on the current input symbol.
- Unfortunately, this cannot be done for all grammars. Two kinds of conflicts
- are possible, viz. the \fBalternation\fP and \fBrepetition\fP conflict.
- An alternation confict arises if two sides of an alternation can start with the
- same symbol. E.g.
- .DS
- .ft CW
- plus: '+' | '+' ;
- .ft
- .DE
- The parser doesn't know which `\f(CW+\fP' to choose (neither do we).
- Such a conflict can be resolved by putting an \fBif-condition\fP in front of
- the first conflicting production. It consists of a \fB``%if''\fP followed by a
- C-expression between parentheses.
- If a conflict occurs (and only if it does) the C-expression is evaluated and
- parsing continues along this path if non-zero. Example:
- .DS
- .ft CW
- plus:
- %if (some_plusses_are_more_equal_than_others())
- '+'
- |
- '+'
- ;
- .ft
- .DE
- A repetition conflict arises when the parser cannot decide whether
- ``\f(CWproductionrule\fP'' in e.g. ``\f(CW[ productionrule ]*\fP'' must be chosen
- once more, or that it should continue.
- This kind of conflicts can be resolved by putting a \fBwhile-condition\fP right
- after the opening parentheses. It consists of a \fB``%while''\fP
- followed by a C-expression between parentheses. As an example, we can look at
- the \fBcomma-expression\fP in C. The comma may only be used for the
- comma-expression if the total expression is not part of another comma-separated
- list:
- .DS
- .nf
- .ft CW
- comma_expression:
- sub_expression
- [ %while (not_part_of_comma_separated_list())
- ',' sub_expression
- ]*
- ;
- .ft
- .fi
- .DE
- Again, the \fB``%while''\fP is only used in case of a conflict.
- .LP
- Error recovery is done almost completely automatically. All the LLgen-user has to do
- is write a routine called \fILLmessage\fP to give the necessary error
- messages and supply information about terminals found missing.
- .NH 2
- Indentation
- .PP
- The way conflicts can be resolved are of great use to Occam. The use of
- indentation, to group statements, leads to many conflicts because the spaces
- used for indentation are just token separators to the lexical analyzer, i.e.
- ``white space''. The lexical analyzer can be instructed to generate `BEGIN' and
- `END' tokens at each indentation change, but that leads to great difficulties
- as expressions may occupy several lines, thus leading to indentation changes
- at the strangest moments. So we decided to resolve the conflicts by looking
- at the indentation ourselves. The lexical analyzer puts the current indentation
- level in the global variable \fIind\fP for use by the parser. The best example
- is the \fBSEQ\fP construct, which exists in two flavors, one with a replicator
- and one process:
- .DS
- .nf
- .ft CW
- seq i = [ 1 for str[byte 0] ]
- out ! str[byte i]
- .ft
- .fi
- .DE
- and one without a replicator and several processes:
- .DS
- .nf
- .ft CW
- seq
- in ? c
- out ! c
- .ft
- .fi
- .DE
- The LLgen skeleton grammar to handle these two is:
- .DS
- .nf
- .ft CW
- SEQ { line=yylineno; oind=ind; }
- [ %if (line==yylineno)
- replicator
- process
- |
- [ %while (ind>oind) process ]*
- ]
- .ft
- .fi
- .DE
- This shows clearly that, a replicator must be on the same line as the \fBSEQ\fP,
- and new processes are collected as long as the indentation level of each process
- is greater than the indentation level of \fBSEQ\fP (with appropriate checks on this
- identation).
- .PP
- Different indentation styles are accepted, as long as the same amount of spaces
- is used for each indentation shift. The ascii tab character sets the indentation
- level to an eight space boundary. The first indentation level found in a file
- is used to compare all other indentation levels to.
|