preccx.1

編譯器的辭法分析器工具

The following macros can be set if required:
.IP
 # define READBUFFERSIZE length
.PP
(default 2048) This defines the lookahead token buffer length.  No more
than <length> tokens can appear between cut marks (`!')  in the script,
as without cut indicators, preccx cannot know if the parser might later
backtrack or not, and will not embed buffer reset instructions (in v2.41
and later versions, \fIpreccx\fP will attempt to increase the buffer in
READBUFFERSIZE increments when necessary, so it is not a hard limit).
.IP
 # define MAXPROGRAMSIZE length
.PP
(default 4096) This defines the maximum length of the internal program
built by parsers in order to execute attached actions.
.IP
 # define STACKSIZE length
.PP
(default 0) This defines the size of a runtime stack formerly used to
manipulate  attached attributes in versions prior to 2.41 and it is now
obsolete. The usage was approximately proportional  to  nesting  depth
in productions.   The stack can be re-enabled by setting the STACKSIZE
to some  positive amount. The V(n) macro can then be used to access it.
.PP
It can be safely left as 0 in code generated by preccx  2.41 and above.
.IP
 # define CONTEXTSTACKSIZE length
.PP
(default 1024) This defines the number of breakpoints that can be held
for backtracking.  Usage is proportional to the number of sequents in
productions between cuts.
.IP
# define C_STACKSIZE length
.PP
(default 0x7FFF or 32K) This is the C call stack.
.PP
Now for the horrors of synthetic attributes. To get a parser generated
by \fIpreccx\fP to do anything significant, you need either to get it to
synthesise a data structure, or get it to generate outputs.  Whichever,
you usually need to scatter \fIactions\fP and \fIattributes\fP through
the script.  There are two styles of script to get to know:
(a) old \fIyacc\fP(1)-style scripts, in which attributes are referred to by
number,  and (b) new style scripts,  in which synthesized 
attributes are referred to by name.
.PP
Actions are pieces of C code (terminated by a semi-colon) and placed
between a pair of bracket-colons (`{:\0...\0:}') in the grammar definition
script. For  example, this action uses old-style \fIyacc\fP(1) numerical
references  to  build a numerical value which it stashes in a C global
variable:
.IP
 @ addexpr = expr <'+'> expr {: total=$1+$3; :}
.PP
In the new style of named reference, this would be  rendered as follows:
.IP
 @ addexpr = expr\\x <'+'> expr\\y {: total=$x+$y; :}
.IP
If the computed value is to be attached as an  attribute for the parse,
this can be rendered as follows:
.IP
.@ addexpr = expr\\x <'+'> expr\\y {@ $x+$y @}
.PP
A newly attached attribute can then be used as an  inherited
parameter in the rest of the parse: 
.IP
 @ sum(subtotal) = addexpr\\x <'+'> sum(subtotal+$x)
 @ \0\0\0\0\0\0\0\0\0\0\0\0\0\0 | \0...
.PP
In contrast, the value of total generated in the action is not
available to the parse because actions execute later than the parse
time.  The value is available to later actions, however.  And it  is 
available  in  the parse once the next cut mark '!' in the script has
been passed. 
.PP
In the action, `$1' is the value attached to the leftmost term, and `$3'
is that attached to the rightmost term.  The `$1' may be replaced by the
explicit `*(VALUE*)p_1' within C macros (their contents are not directly
accessible to preccx and this is what `$1' expands to) in version 2.41
and above.  In earlier versions than 2.41, `V(1)' is the appropriate
replacement to use.
.PP
`Values' attached to each term of a \fIpreccx\fP expression are an appropriate
way to think of what is going on.  Note that the full \fIyacc\fP(1) style of
script,  with  attribute   assignments mixed into  the action code via
the `$$' pseudo-variable, is only supported until v2.40 and no later.
Moreover, the \fIyacc\fP-style numerical referencing via `$1',  `$2' and so
on,  from  v2.41 on requires the `-old' command line switch to 
preccx. In previous versions of \fIpreccx\fP, it was supported without
restriction.
.PP
Earlier versions of preccx than version 2.41 used a runtime interpreter
(like yacc(1)) and a dynamic stack to implement the synthesized
attributes.  Version 2.41 and above compiles the  attributes instead.
The  difference  makes  for some slight incompatibilities with yacc(1):
the $0 reference  now makes no sense, for example.  It used to refer to
the attribute attached to the term just seen  to  the  left  and was
available  below  on  the  dynamic stack.  But in a compiled model, it
is simply out of scope. 
.SH A BIT OF HISTORY
In version 1.5 to 2.40, \fIpreccx\fP generated code to  shift  the frame  of
reference  in a runtime attribute stack automatically.  This was set
by `call_mode=0' (the default)  in  the BEGIN  macro.   In earlier
versions, or if `call_mode=1' was set, frame shifts had to be coded
explicitly in the  script: this  would  be accomplished by including a
VV(n) call early in the action attached to each clause.  For example, a
three term  clause  would  need  a VV(3) call.  After the call (in
call_mode=1 mode) the $n values would be  correctly  aligned with the
grammar expressions, and without it, they would not be.  The value to be
associated with  the  whole  expression was  written  into  $1.  
Writing VV(3)=$2 was shorthand for VV(3);$1=$2.  After version 1.5 and
with `call_mode=0'  set, the  explicit VV(3) was not required and the
attribute build  could be coded as $1=$2 alone.  Or, for  compatability
with  \fIyacc\fP(1), as $$=$2.
.PP
This was all exactly equivalent to the treatment in the Unix \fIyacc\fP(1)
utility, and it allowed you to incorporate the same incomprehensible
tricks of pulling values off the stack when they were notionally
`further to the left' than the scope of the current expression, using $0
or even lower references.
.PP
To recap, in versions 1.50 to 2.40 the user had to choose a `call mode'
which controlled the way the stack of attributes is handled at run time.
Using the default call_mode=0  mode, stack  frame  shifts were automatic
and it was not necessary to set VV(n) (shift value stack by n) commands
in  actions. If call_mode=1, then stack shifts were left to the user,
and VV(n) instructions had to be added  explicitly  to  actions. From
version 2.41 up  `call mode' is  entirely  obsolete  so  you can forget
it!
.PP
In earlier versions  than  1.50,  the  only call mode was call_mode=1.
The call mode in later versions was set by: 
.IP
call_mode = 0 (automatic); or 1 (user-directed);
.PP
in the BEGIN macro,  to  be  #defined  before  the  #include <cc.h> or
<ccx.h>  in the script.  In version 2.41 none of this is necessary as
the attributes are  handled  in  the  C runtime call stack,  which is
looked  after by C.  You can #define  STACKSIZE  0 (to remove the stack
entirely, to save space), all this also before the  #include <cc.h> or
<ccx.h>  directive.
.PP
History off.
.SH ATTRIBUTES
In version 2.41 and above, the job of building synthetic attributes has
been hived off into the parser proper.  Synthetic attributes are any
non-side-effecting expression, possibly involving the dollar
variables which denote the values of attributes of other terms in a
clause. They are written within {@ ... @} symbols. The last attribute in a
clause becomes the attribute of a clause. For example:
.IP
@ tree = <'('> tree\\x <')'> tree\\y {@ mknode($x,$y) @}
.IP
@ \0\0\0\0 | ...
.PP
is sufficient to build a simple parse tree for bracketed input. Note
however that the attribute should be non-side-effecting. It may be
called several times in a parse. Since compound structures have to be
built via side-effects in C, each call to mknode will have to check its
arguments to see whether it has been called before, and to return the
previously built structure if it has. It will have to do its own
memoizing. On the other hand, rebuilding the structure several times
becomes an allowable strategy when garbage collection takes place often
enough to reclaim wasted structures. Either technique removes visible
side-effects. 
.SH ACTIONS
Real side-effects that the parse is intended to invoke are coded in all
versions of \fIpreccx\fP as actions between {:...:} pairs, analogously
to \fIyacc\fP(1). Side-effecting actions need a little explanation.
Because \fIpreccx\fP is an infinite look-ahead parser, it cannot
execute actions at the same time as it reads input. It might have to
later backtrack across its parse, and, whilst it might deconstruct data
structures built up in the parse, it is certainly impossible, for
example, to undo any writes to \fIstdout\fP which might have occurred.
.PP
So \fIpreccx\fP builds a program as it parses. When the parse finishes
correctly, the program is executed by an internal engine, but if the parse
is unsuccessful or has to be backtracked, the program is `unbuilt' before
its actions are executed. This program is a linear sequence of C code actions
which have been specified in the \fIpreccx\fP definition file. Thus the
specification:
.IP
 @abc=a\0b\0c\0{:printf("D");:}
.IP
 @a=<'a'>\0{:printf("A");:}
.IP
 @b=<'b'>\0{:printf("B");:}
.IP
 @c=<'c'>\0{:printf("C");:}
.PP
will, upon receiving input "abc", generate the program
.IP
 printf("A");printf("B");printf("C");printf("D");
.PP
to be executed later.
Thus actions attached to a sequence expression may be thought of as occurring
immediately after the actions attached to sub-expressions, and so on
down. That explanation should enable you to generate side-effects in
the correct sequence.
.PP
As remarked above, in version 1.50 to 2.40 of \fIpreccx\fP, attributes were
built in the side-effecting actions, in yacc(1) style. In version 2.41 and
above, attributes are attached using the new {@foo@} notation. This
is certainly mechanically more robust, and it ought to be conceptually
cleaner too. Attributes need  the {@ @} signs and should not have
side-effects.   Actions need {: :} signs and should contain only
side-effects, and cannot make attributes.
.PP
.SH USAGE
.I Preccx
grammar description files conventionally have the .\fIy\fP suffix, and
should follow the following format:
.IP
# define TOKEN ... (default = char)
.IP
# define VALUE ... (default = char*)
.IP
# define BEGIN ... (default nothing)
.IP
# define END\0\0 ... (default nothing)
.IP
# define ON_ERROR(x) ... (defaults to standard)
.IP
# include "cc.h"  (or ccx.h)
.IP
 @ first\0definition : attached action; :
.IP
 @ ...
.IP
 @ ...
.IP
MAIN(name of entry parser)
.PP
The cc.h header file may be used instead of ccx.h in scripts which
consist only of unparameterized definitions and terms.
.SH EXAMPLE
The following script defines a simple +/- calculator in the version
2.41 language, using parameters. For scripts that work with earlier
versions of the language, see earlier versions of the manual.  Some
notes on differences appear afterward.
.IP
# define TOKEN char
.IP
# define VALUE int
.IP
# define BEGIN printf("\\nready> ");
.IP
#\0include\0"ccx.h"
.IP
#\0include\0<ctype.h>
.IP
 @\0digit\0=\0(isdigit)\\x\0\0\0\0{@ $x-'0' @}
.IP
 @\0posint(t)=\0digit\\x\0posint(10*t+$x)
.IP
 @\0\0\0\0\0\0\0|\0digit\\x\0\0\0\0\0\0\0\0\0\0\0\0{@ 10*t+$x @}
.IP
 @\0posint0=\0posint(0)
.IP
 @\0anyint=\0<'-'>\0posint0\\x\0\0\0\0{@ -$x @}
.IP
 @\0\0\0\0\0\0\0|\0posint(0)
.IP
 @\0atom\0\0=\0<'('>\0expr\\x\0<')'>\0{@ $x @}
.IP
 @\0\0\0\0\0\0\0|\0int
.IP
 @\0expr\0\0=\0atom\\x\0sign_sum\\y\0\0{@ $x+$y @}
.IP
 @\0\0\0\0\0\0\0|\0atom
.IP
 @\0sign_sum=\0<'-'>\0atom\\x\0sign_sum\\y
.IP
 @\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0{@ -$x+$y @}
.IP
 @\0\0\0\0\0\0\0\0\0|\0<'-'>\0atom\\x\0\0\0\0\0{@ -$x @}
.IP
 @\0\0\0\0\0\0\0\0\0|\0<'+'>\0atom\\x\0sign_sum\\y
.IP
 @\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0{@ $x+$y @}
.IP
 @\0\0\0\0\0\0\0\0\0|\0<'+'>\0atom\\x\0\0\0\0\0{@ $x @}
.IP
 @\0top\0\0\0\0\0=\0expr\\x\0\0\0\0\0\0\0\0\0\0\0{: printf("=%d\\n",$x); :}
.IP
MAIN(expr)
.PP
This script must be passed through \fIpreccx\fP:
.IP
preccx\0<\0calculator.y\0>\0calculator.c
.PP
and then compiled, using the \fIpreccx\fP kernel library in libcc.a:
.IP
gcc\0\-Wall\0\-ansi\0\-o\0calculator\0calculator.c\0\-L\0...\0\-lcc
.PP
The three dots stand for the directory in which the preccx library file