readme

从lex&yacc说到编译器

	     BTYACC -- backtracking yacc
	     ===========================

BTYACC was created by Chris Dodd using ideas from many
places and lots of code from the Berkeley Yacc
distribution, which is a public domain yacc clone put
together by the good folks at Berkeley.  This code is
distributed with NO WARRANTEE and is public domain. 
It is certain to contain bugs, which you should 
report to: [e-mail].

Vadim Maslov of Siber Systems <[e-mail]> 
considerably modified BTYACC to make it suitable 
for production environment.

Several people have suggested bug fixes that 
were incorporated into BtYacc.

See the README.BYACC files for more about 
Berkeley Yacc and other sources of info.

http://www.siber.com/btyacc/ is the current home of BtYacc.
It is provided courtesy of Siber Systems http://www.siber.com/.


		Version 3.0 changes
		-------------------
		  by Vadim Maslov

Changes mostly occurred in btyaccpa.ske file that 
contains the parsing shift/reduce/backtrack algorithm.

Version 3.0 innovations focus on:
- text position computation and propagation,
- industrial-strength error processing and recovery.


** Added mechanism for computing and propagating 
text position of tokens and non-terminals.

Compilers often need to build AST trees such that every node 
in a tree can relate to the parsed program source it came from.
The following applications are very likely to need this:
- debuggers that show actual source of the debugged program,
- source-to-source translators that want 
  unchanged parts of the tree to generate the unchanged code.

The new YYPOSN mechanism added in this version of BtYacc
helps you in automating the text position computation
and in assigning the computed text positions to the AST.
This mechanism is successfully used in commercial 
parsers and source-to-source translators.

In standard Yaccs every token and every non-terminal
has an YYSTYPE semantic value attached to it.
In this new version every token and every non-terminal
also has an YYPOSN text position attached to it.
YYPOSN is a user-defined type that can be anything and
that has a meaning of text position attached to
token or non-terminal.

In addition to semantic value stack BtYacc now maintains
text position stack. Behavior of the text position stack
is similar to the behavior of the semantic value stack.

If using text position mechanism, 
you need to define the following:

YYPOSN	Preprocessor variable that contains C/C++ type of 
	the text position attached to 
	every token and non-terminal.

yyposn  Global variable of type YYPOSN.
        The lexer must assign text position of 
	the returned token to yyposn, just like it assigns 
	semantic value of the returned token to yylval.

YYREDUCEPOSNFUNC
	Preprocessor variable that points to unction that 
	is called after the grammar rule reduction
	to reduce text positions located on the stack.
       
        This function is called by BtYacc to reduce text 
	positions. The function is called immediately after 
	the regular rule reduction occurs.
       
	The function has the following prototype:
	void ReducePosn(YYPOSN  &ret,
			YYPOSN  *terms, 
			YYSTYPE *term_vals,
			int      term_no, 
			int      stk_pos, 
			int      yychar,
			YYPOSN  &yyposn,
			UserType extra);

        The function arguments are:
        - ret         
	  Reference to the text position returned by 
          the rule. The function must write the computed 
          text position returned by the rule to ret.
          This is analogue of the $$ semantic value.

        - term_posns  
          Array of the right-hand side rule components 
	  YYPOSN text positions.  These are analogues of 
	  $1, $2, ..., $N in the text position world.

        - term_vals
	  Array of the right-hand side (RHS) rule components 
	  YYSTYPE values. These are the $1,...,$N themselves.

        - term_no
          Number of the components in RHS of the reduced rule.
          Equal to size of arrays term_posns and term_vals.
          Also equal to N in $1,...,$N in the reduced rule.

        - stk_pos 
          YYSTYPE/YYPOSN stack position before the reduction.

        - yychar
          Lookahead token that immediately follows 
 	  the reduced RHS components.

        - yyposn
          YYPOSN of the token that immediately follows 
	  the reduced RHS components.

        - extra
          User-defined extra argument passed to ReducePosn.
       
        Typically this function extracts text positions from 
	the right-hand side rule components and either 
	assigns them to the returned $$ structure/tree or
        if no $$ value is returned, puts them into 
	the ret text position from where
        it will be picked up by the later reduced rules.
       
YYREDUCEPOSNFUNCARG 
	Extra user-defined argument passed to 
	the ReducePosn function. This argument can use 
	any variables defined in btyaccpa.ske.


** Added code to btyaccpa.ske that automatically cleans up
semantic semantic values and text positions of tokens 
and non-terminals that are discarded and deleted as 
a result of error processing.

In the previous versions the discarded token and non-terminal
semantic values were not cleaned that caused quite severe
leaks.  The only way to fix it was to add garbage collection
to YYSTYPE class.

Now BtYacc skeleton calls delete functions for semantic
values and positions of the discarded tokens and
non-terminals.

You need to define the following functions that BtYacc 
calls when it needs to delete semantic value or text position.

YYDELETEVAL
	User-defined function that is called by BtYacc
	to delete semantic value of the token or non-terminal.
	
	The user-defined function must have the prototype:
	void DeleteYYval(YYSTYPE v, int type);
	v    is semantic value to delete,
	type is one of the following:
	0 	discarding token
	1       discarding state
	2       cleaning up stack when aborting

YYDELETEPOSN 
	User-defined function that is called by BtYacc
	to delete text position of the token or non-terminal.

	The user-defined function must have the prototype:
	void DeleteYYposn(YYPOSN p, int type);
	v    is semantic value to delete,
	type is one of the following:
	0 	discarding token
	1       discarding state
	2       cleaning up stack when aborting


** User can define "detailed" syntax error processing
function that reports an *exact* position of 
the token that caused the error.

If you define preprocessor variable YYERROR_DETAILED in 
your grammar then you need define the following 
error processing function:

void yyerror_detailed(char    *text, 
		      int      errt, 
		      YYSTYPE &errt_value,
		      YYPOSN  &errt_posn);

It receives the following arguments:
text		Error message.
errt		Code of the token that caused the error.
errt_value	Value of the token that caused the error.
errt_posn	Text position of token that caused error.


** Dropped compatibility with C.

Compatibility with C became increasingly difficult 
to maintain as new features were added to btyaccpa.ske.
So we dropped it. If anybody wants to make the new version
compatible with C, we would gladly accept the changes.

Meanwhile we expect that you use C++ to write grammar 
actions and everything else in grammar files.
Since C is (in a sense) subset of C++, your C-based 
grammar may work if you use C++ compiler to compile it.

		Version 3.0 bugs fixed
		----------------------

Matthias Meixner <[e-mail]> fixed a bug:
BtYacc does not correctly handle typenames, if one typename 
is a prefix of another one and if this type is used after 
the longer one. In this case BTYacc produces invalid code.


		Version 2.1 changes
		-------------------
		  by Vadim Maslov

** Added preprocessor statements to BtYacc that are similar 
in function and behavior to C/C++ preprocessor statements.

These statements are used to:

- Introduce modularity into a grammar by breaking it
  into several *.y files and assembling different
  grammars from the *.y modules using %include and %ifdef.

- Have several versions of the same grammar
  by using %ifdef and $endif.

- To include automatically generated grammar fragment.
  For instance, we use %include to include
  automatically generated list of tokens.

Preprocessor statements are:

%define <var-name> 
	Define preprocessor variable named <var-name>.

%ifdef <var-name>
	If preprocessor variable named <var-name> 
	is defined by %define, then process the text from
	this %ifdef to the closing %endif.

%endif
	Closing bracket for %ifdef preprocessor statement.
	Only one nesting level of %ifdef-%endif is allowed.

%include <file-name>
	Process contents of the file named <file-name>.
	If <file-name> is a relative name, it is looked up
        in a directory in which btyacc was started.
	Only one nesting level of %include is allowed.


		Version 2.0 changes
		-------------------
		  by Vadim Maslov


** Changed 16-bit short numbers to 32-bit int numbers in
grammar tables, so that huge grammar tables (tables that
are larger than 32768 elements) resulting from huge
grammars (Cobol grammar, for instance) can work correctly.
You need to have 32-bit integer to index table bigger than
32768 elements, 16-bit integer is not enough.

The original BtYacc just generated non-working tables
larger than 32768 elements without even notifying about
the table overflow.


** Make error recovery work correctly when error happens
while processing nested conflicts. Original BtYacc could
infinitely cycle in certain situations that involved error
recovery while in nested conflict.

More detailed explanation: when we have nested conflicts
(conflict that happens while trial-processing another
conflict), it leads btyacc into NP-complete searching of
conflict tree. The ultimate goal is YYVALID operator that
selects a particular branch of that tree as a valid one.

If no YYVALID is found on the tree, then error recovery