readme.txt

编译原理中的First集与 Follow集生成程序

Create First & Follow Set(CFF).
( First 与 Follow 集生成程序 )

作者:吕进华 (lvjinhua)
版本:V1.5
mail:[e-mail]
修改日期:2005年3月27日

    这是我的一个防 Bison 1.24 扫描器自动生成器中的一部分,将它提取出来,以
方便大家在需要的时候使用。
    本程序可以从输入文件中读取类似于 Bison1.24 中定义的上下文无关文法并对其
进行处理,输出其终结符集、非终结符集、产生式（文法）集、First与Follow集。


++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    [Copyright]你可以任意的使用、传播或修改本程序而无需特别的知会我，但我不会
对你使用本程序所造成的后果负任何责任。

    [简介]本程序是一个用于生成上下文无关文法FIRST集与FOLLOW集的工具,可从文件中
读取文法并对文法进行处理,输出其终结符、非终结符、产生式（文法）、First与Follow集。

    [用法]输入 “CFF 文件名” 即可将打开“文件名”,并可处理里边的文法文件内容.处理后
的内容将输出到“文件”.out.txt 中。如输入 “CFF a.txt” （注意，没有双引号）即开始处
理 a.txt 中的文法内容并输出结果存入到当前文件夹下的“a.txt.out.txt” 文件中。还可以
直接双击可执行文件，然后根据提示输入待处理的源文件文件名。

    [环境]本程序所附的源代码在使用Windows XP系统下使用VC7.1编译通过，在VC6.0不能
正确的产生可执行代码，在GCC3.2下也编译通过。由于条件有限，其它编译器没有进行测试。

    [反馈]如果你在使用本程序的过程中遇到了任何的BUG或有什么不明白的地方，欢迎与
我取得联系，谢谢您的支持。

    [最后修改日期]2005年4月2日。


+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 *  CFF1.5 改动: executable code

 *  1) 可以对文法进行化简。
 *  2) 增加 '.' 作为标识符的一部分,其作用相当于下划线('_'),即现在
 *     a.ff 也可以是一个合法的标识符名称。
 *  3) 支持绝大部分的 Bison1.24 语法规则,如 %token,%left,%right,%prec...,
 *     注释,文法动作,嵌入式文法动作等。
 *  4) 程序结果输出到独立的文件中。
 *  5) 取消命令行参数。
 *  6) 为原始文法添加 “@start->开始符号” 的新产生式。
 *  7) 修改了一些小错误。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 文法文件语法简单说明：

    《注释》：本分析程序可以识别类似C++语言中  /* */ 及  // 风格的注释。
    其中  /* */ 代表从第一个 /* 到与其配对的下一个  */ 之间的内容均为注释，注释不
支持嵌套。
    其中  //  代表从  // 开始到本行结束为注释内容。


    本程序能够识别的文法文件的格式与 Bison 1.24 兼容（因此强烈建议有趣的朋友找一些
Bison 的相关文档看看），共分三大部分，每部分使用“%%”
进行分隔，分别为：

      预定义
      %%
      规则说明
      %%
      其它

    《其它》部分为可以包含任何内容，它不作为CFF语法的一部分，一般情况下可忽略，Bison 
中这部分用于定义一些C语言函数。


    《预定义》部分为记号声明部分，声明的记号用于代替一个终结符或非终结符，其书写规则
为：第一个字符必须为字母或下划线，后边可跟字母、数字或下划线，长度限制在56个字符以内，
各个记号之间使用空白进行分隔。
     1）“%token”关键字进行终结符的声明即可，而非终结符不需要进行声明。
     格式如下：
      %token 标识符1  标识符2  ... 标识符N
     或
      %token 标识符1 , 标识符2 , ... , 标识符N
  
     声明了标识符后在“规则说明”部分即可以使用这些标识符所代表的终结符。

      2） “%start” 关键字用于声明开始符号。
      %start 标识符用于声明开始符号，如果没有使用此关键字，则默认使用第一个产生式的左
部作为方法开始符号。

      3）  其它关键字
      其它关键字如  “%left ,%right,%nonassoc,%type,%union”的使用同 Bison 相同，但在
本程序中它们均失去了本来的功能，比如 %left ,%right,%nonassoc 可以被 %token 代替，%type
定义可有可无。
      除了关键字，程序还支持  “%{ ... %}”的C语言语句声明格式。

      4）  建议
      由于本程序是主要是用于计算first集与follow集，因此Bison中那些复杂的规则也用处不大，
因此在预定义部分使用“%token”关键字即可满足要求，具体可以查看附带的示例“C99.txt”。


    《规则说明》部分对文法的产生式进行说明。可采用简单的写法，如：  expr:expr '+' term ;
即一次书写一个文法，文法左部与右部使用一个冒号(:)进行分隔，文法的结尾须加分号(;)，如果文
法中使用了单个符号的终结符，可以使用单引号将其直接使用到产生式中。如果是多个符号的终结符必
须在“预定义”部分将其声明为一个标识符。
    文法也可以采用复合的写法，如：
    expr:
         expr '+' term
       | expr '-' term
       | term
       |
       ;
    上边的文法代表三个产生式，每个产生式的左部均为expr，右部使用“|”进行分隔，最后也需
使用分号标明文法结束。在这三个产生式中有一个为空产生式，即在“|”后直接跟分号，等价的格
式如下：
    expr:expr '+' term;
    expr:expr '-' term;
    expr:term;
    expr: ;
   
    也可以在“规则说明”的文法中插入“语义动作”，但它们对于计算first集与follow集没有实
际意义，因此在些不加以说明，有兴趣可以查看Bison的相关使用说明。



    程序输出结果的First集中的 $Null 代表空标记，Follow集中的 $Sharp 代表输入结束标记(即
有些编译原理书中的“#”或“$”号)。


    本程序所附带的测试文件 C99.txt 是一个标准C语言文法,gcc2.9.txt 是 Djgpp 编译器源程序中
自带的一个C++语言完整 Bison 语法描述文件，它综合展示了 Bison 中绝大部分功能的使用方法 , 
test.txt即附录1中的计算器文法文件。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
附录1 ： 一个简单的计算器文法


%token ID NUM
%%
line:
    expr ';' line
   |
  ;
expr:
    expr '+' term
  | expr '-' term
  | term
  |
  ;
term:
    term '*' factor
  | term '/' factor
  | factor
  ;
factor:
    ID
  | NUM
  | '(' expr ')'
  ;



附录2：CFF 文法扫描程序文法（这个文法描述不是很精确，但源程序中就是使用这个文法
       实现的递归下降分析程序）

%token ID NUM ASC MARK PREC
  /* 关键字  */
%token START TOKEN UNION LCURL RCURL LEFT RIGHT NONASSOC TYPE

%%
spec  : defines MARK rules tail
   ;
  
tail  : MARK eat_up_rest
    | // empty 
;

defines: // empty
    |   START    ID                 defines
    |   UNION    eat_up_union       defines
    |   LCURL    eat_up_defs RCURL  defines
    |   TOKEN    symtype            nlist
    |   LEFT     symtype            nlist
    |   RIGHT    symtype            nlist
    |   NONASSOC symtype            nlist
    |   TYPE     symtype            nlist2
;

eat_up_defs:
      /* Call the function eat_up_def() to copy
         the C declare to output file.*/
    ;

eat_up_union:
      /* Call the function eat_up_union()to copy
         the union declear to output file.*/
    ;

eat_up_symtype:
      /* Call the function eat_up_symtype() to
         copy between '<' to '>' into symbol's
         symtype field.*/
    ;

eat_up_rest:
      /* Call function eat_up_rest() to copy the
         rest of the Grammar file into output file.
       */
    ;
     
symtype:  /* empty */
    |   '<' eat_up_symtype '>'
    ;

nlist : factor
    |   factor nlist
    |   factor ',' nlist
    ;
    
factor: ID
    |   ID NUM
    |   ASC
    |   ASC NUM
    ;

nlist2 : factor2
    |    factor2 nlist2
    |    factor2 ',' nlist2
    ;
factor2: ID
    |    ASC
    ;

rules : ID ':' rbodys ';' rules
    | /* empty */
    ;

rbodys: '|' rbody prec rbodys
    |   ID  rbody prec rbodys
    |   ASC rbody prec rbodys
    |   '{' rbody prec rbodys
    |   PREC      prec rbodys /* 处理由 %prec 指定优先级的空产生式.*/
    |   ';'                   /* 处理分号前边可能产生的空产生式*/
    ;

rbody : /* empty */
    |   ID  rbody
    |   ASC rbody
    |   '{' eat_act '}'           /* common action*/
    |   '{' eat_act '}' ID  rbody /* panel action */
    |   '{' eat_act '}' ASC rbody /* panel action */
    |   '{' eat_act '}' '{' rbody /* panel action */
    ;

prec  : /* empty */
    |   PREC ID
    |   PREC ID '{' eat_act '}'
    ;

eat_act: 
    // empty
    ;