注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

bison基础  

2012-01-18 22:59:34|  分类: Bison基础 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、基础
前一篇文章看bash的源代码,里面有bash的语法文件parse.y,在这个文件中定义了bash的语法规则,事实上很多工程中的语法规则都叫这么名儿。计算机科班出身的人都知道这个是一个yacc(Yet Another Compiler Compiler Generator?)输入脚本,文件‘y’后缀就是YACC的首字母,该工具用来简化编译器的实现。当然bash不是一个编译器,而是一个解释器,但这不是重点,因为它也需要对语法/语义进行解析。其实很多脚本文件都会使用这个工具的,如果你说不知道,那可能是你木有注意。可以想起的有gnu ld使用的链接脚本、gcc早期的语法文件(好像4.1的就已经不使用语法文件,而是手动编写语法分析文件了,但是我猜测是在生成代码的基础上再手动调整,至少是受自动生成文件启发吧)、内核中KConfig脚本文件。好了,差不多就想到这么多了,另一个常用的脚本文件make--很遗憾--没有使用这种方法,而是自己硬来手动解析的。
yacc是unix传统的解析工具,也是语法规则定义语言的鼻祖。其实工具本身没有特殊意义,它的意义在于它体现的方法和思想,只要有了想法,实现起来都不是问题,虽然如果让我实现起来可能有问题。在GNU系统中,这个工具的实现工具叫做bison,应该是“野牛”的英文,和GNU表示“角马”一样,它也是一个蹄科哺乳动物。
有意思的是,在bison的实现中,它同样使用bison来定义语法文件,因为bison的输入也是一个脚本文件。这个说起来有些绕了,大致来说吧,就是gcc的源代码也是用C语言编译生成的。我这里只是想看看bison的源代码,看看一个bison的语法规则是怎样的,然后通过这个解析来分析一下bison的语法文件,再然后可以看看bash语法文件。
二、基础语法
1、%token
这个是最为基础的指示,但是这个指示看起来很晦涩呢,因为可以看到千奇百怪的花样,看一下bison自己的脚本解析文件有这样的形式
%token PERCENT_TOKEN       "%token"
在语法中还有这样的使用
| "%token" { current_class = token_sym; } symbol_defs.1
    {
      current_class = unknown_sym;
      current_type = NULL;
    }
而在bash的语法文件中,还有下面的内容
%token IF THEN ELSE ELIF FI CASE ESAC FOR SELECT WHILE UNTIL DO DONE FUNCTION COPROC
%token <number> NUMBER
其实还有其他的形式,符号之后跟数字的形式,这些由于没有找到实例,那就不显摆了。
看一下为什么需要这些token。token是事实上上下文无关语法中的一个符号,对于人类来说,它表示的就是一个符号。但是计算机只认识二进制数,所以这些token最终都要转换为数值。再具体的说,就是会转换为一个C语言中的
#define  WORD  number
    在上下文无关语法中,进行一个展望(lookahead)的单词就需要互相区分,区分其实也很简单,只要在自己确定的命名空间中能够互相区分就好了,语法分析器就需要为每个token分配一个编号。从更深层次的角度看,语法分析和词法分析是相互独立的,语法分析需要词法分析提供自己读入的到底是什么终结符。它的返回值需要和语法分析器中出现的单词的命名规则一致,或者说,它们要说相同的语言,至少yylex的返回值是如此,那么如何表示呢?看一下yylex的返回值就知道了,这个返回值就是这里的一个token,因为词法分析能够通过一个单词的书写方式就知道这是一个什么语法单位。例如,在C语言中 “Helloworld”是一个字符串;0XDEADBEFF是一个整数常量;而X0DEADBEEF就是一个标识符。
   那么语法分析器主要是干什么的呢?它的主要作用就是要根据给出的语法文件,生成一个优先确定状态机,这个状态机列出了所有的可能状态以及这些状态的转换。这些状态从哪里来呢?是根据书写规则形式化的、自动生成的,对语法分析器来说,它就是生成足够多的能够表现系统中所有可以相互区分的状态,并将这些状态节点使用带有语法单位的有向转换箭头连接起来,这之间要维护规约发生时需要执行的动作。这些东西我也没有理解深刻到能够用简单生动的语言表达出来的程度,很多东西也是想到哪里,说到哪里,所以如果说有人觉得不理解,那一定是我表述的问题。
在bison的语法文件parse-gram.y中定义了对于bison输入文件的%token的解析规则:
symbol_declaration:
……
| "%token" { current_class = token_sym; } symbol_defs.1
    {
      current_class = unknown_sym;
      current_type = NULL;
    }
/* One or more symbol definitions. */
symbol_defs.1:
  symbol_def
| symbol_defs.1 symbol_def
;
/* One token definition.  */
symbol_def:
  TYPE
     {
       current_type = $1;
       tag_seen = true;
     }
| id
     {
       symbol_class_set ($1, current_class, @1, true);
       symbol_type_set ($1, current_type, @1);
     }
| id INT
    {
      symbol_class_set ($1, current_class, @1, true);
      symbol_type_set ($1, current_type, @1);
      symbol_user_token_number_set ($1, $2, @2);
    }
| id string_as_id
    {
      symbol_class_set ($1, current_class, @1, true);
      symbol_type_set ($1, current_type, @1);
      symbol_make_alias ($1, $2, @$);
    }
| id INT string_as_id
    {
      symbol_class_set ($1, current_class, @1, true);
      symbol_type_set ($1, current_type, @1);
      symbol_user_token_number_set ($1, $2, @2);
      symbol_make_alias ($1, $3, @$);
    }
;
这里的语法解析出来之后它对应的C语言代码应该相对就比较熟悉了,因为毕竟这些都是大家的老熟人了。这里的symbol_def的定义中表示了%token之后可以跟很多东西,而不仅仅是一些token。具体可以跟什么呢?看一下这个语法文件,一个定义可以跟 类型 、名称、数值、字符串这些属性。例如
%token  <keyword> FOR 300 "for" <keyword> WHILE 301 "while"
解析上面的一个语法,其中的<keyword>对应symbol_def中的TYPE、FOR对应id,300对应INT,“for”对应string_as_id,这些都是解释性说明,那么语法解析器是如何区分这些概念的呢?答案就是通过这些token的书写方式,我们看看他们的书写方式,一个TYPE的书写形式为<{tag}>形式,也就是是在一对尖括号中定义一个类型,而id是一个赤裸裸的标识符,INT是一个以数字开始并且全部以数字组成的单词,最后的string则是一对双引号引导的内容,所以它们具有不同的词法形式,进而成为不同的语法单位。

再看一下这个TYPE是从哪里来的,这个实在词法分析器中定义,在scan-gram.l文件中:
tag     [^\0\n>]+
 /* A type. */
  "<"{tag}">" {也就是一对尖括号,中间有一个或多个非零、非换行字符组成的单词,它就是一个TYPE
    obstack_grow (&obstack_for_string, yytext + 1, yyleng - 2);
    STRING_FINISH;
    val->uniqstr = uniqstr_new (last_string);
    STRING_FREE;
    return TYPE;
  }
2、%union
这个结构是必须的,随便找一个bison中的语法文件
symbol_declaration:
……
| "%type" TYPE symbols.1
    {
      symbol_list *list;
      tag_seen = true;
      for (list = $3; list; list = list->next)
    symbol_type_set (list->content.sym, $2, @2);
      symbol_list_free ($3);
    }
这里可以看到对语法中第二个单词的引用,并且是是用在了一个函数中。明显地,这个函数并不吃这一套,你给人间一个美元,算是怎么回事,根本不是C语言嘛。所以这里就要确定出来这个$2到底是什么,并且用C语言表达出来,但是明显地,这里只说了是$2,并没有说这个是什么类型,从任何一个语法文件中看,可以看到文件中有茫茫多的这种引用,而且大家都这么赤裸裸的用,此时如何转换呢?再进一步,对于字符串,“Hello World”这个在C语言是个字符串,而0xDEADBEEF则是一个数值,它们肯定要使用不同的结构来表示,不能一概而论。
此时就需要使用union,这是一个大而全的概念,就是说,这个结构中可能是union中的任意一种类型,例如bison中的定义就是
%union
{
  symbol *symbol;
  symbol_list *list;
  int integer;
  char const *chars;
  char *code;
  assoc assoc;
  uniqstr uniqstr;
  unsigned char character;
  named_ref *named_ref;
};
也就是整个语法中的语法单位可能有上面所有的形式中的任意一种,但是具体是哪一种,需要用户说明。但是这里至少给出了一个形式化的统一界面,就是所有的语法单位都可以通过这个类型表示出来,这是一个形式化的统一,也是计算机解决问题的一种方法。那么我们刨根问底的问:到底是咋确定的嘛?
这就需要用户通过
%type
指示指明,其它的方法也有,例如在前一节中说明的通过%token中的<type>指明。看一下bison中的指示

%type <character> CHAR
%type <chars> STRING "%{...%}" EPILOGUE braceless content.opt
%type <integer> INT
%type <list>  symbols.1 symbols.prec generic_symlist generic_symlist_item
%type <uniqstr> BRACKETED_ID ID ID_COLON TYPE variable

可以看到,这里用户声明了CHAR STRING INT这些我们最为常见的token使用的union中的成员域(不是类型),这样,在这些token被引用到的时候,bison就知道如何替换其中的$NUM,也就是知道了使用联合中的哪一个域。看一个代码
还是以
symbol_declaration:
| "%type" TYPE symbols.1
    {
      symbol_list *list;
      tag_seen = true;
      for (list = $3; list; list = list->next)
    symbol_type_set (list->content.sym, $2, @2);
      symbol_list_free ($3);
    }
为例,看一下它对应的代码,它生成的对应的C语言代码为
/* Line 1806 of yacc.c  */
#line 419 "parse-gram.y"
    {
      symbol_list *list;
      tag_seen = true;
      for (list = (yyvsp[(3) - (3)].list); list; list = list->next)
    symbol_type_set (list->content.sym, (yyvsp[(2) - (3)].uniqstr), (yylsp[(2) - (3)]));可以看到,这里使用的list和uniqstr是和上面的声明对应的
      symbol_list_free ((yyvsp[(3) - (3)].list));
    }
    break;
3、%union及内嵌代码解析
可以看到%union中是C语言可识别的类型声明,这一点对于语法中穿插的语法动作代码(例如上面的引用$3的C语言语句)同样适用。这项工作也是语法分析其需要完成的一个重要功能部分,所以这里也大致的了解一下。
看一下union的声明
grammar_declaration:
  "%union" union_name braceless
    {
      union_seen = true;
      muscle_code_grow ("stype", $3, @3);
      code_scanner_last_string_free ();
    }
;
%token BRACED_CODE     "{...}"
braceless:
  "{...}"我觉得这个东西还是很神秘的,它字面内容不一致,这里的"…"代表了任意多的C语言代码,此时%union已经被匹配,剩余{}
    {
      code_props plain_code;
      $1[strlen ($1) - 1] = '\n';
      code_props_plain_init (&plain_code, $1+1, @1);
      code_props_translate_code (&plain_code);
      gram_scanner_last_string_free ();
      $$ = plain_code.code;
    }
;
braceless的扫描在另一个词法扫描文件scan-gram.l中,其中对于这个的扫描为
<SC_BRACED_CODE>
{
  "{"|"<"{splice}"%"  STRING_GROW; braces_level++;这里为什么需要记录层次呢?因为两个符号也是C语言的保留字,作为句子分割符
  "%"{splice}">"      STRING_GROW; braces_level--;
  "}" {
    obstack_1grow (&obstack_for_string, '}');

    --braces_level;
    if (braces_level < 0)只有当嵌套次数归位为零的时候才返回找到一个BRACED_CODE语法单位
      {
    STRING_FINISH;
    loc->start = code_start;
    val->code = last_string;
    BEGIN INITIAL;
    return BRACED_CODE;
      }
  }
这里实体的内容和规约动作的内容相同,都是%type <code> "{...}",而union中的code域的定义为 char *code;,简简单单一个字符串。
4、更加鸟瞰的语法文件布局图
input:
  prologue_declarations "%%" grammar epilogue.opt
;
从这里看,一个“%%”将整个语法文件一分为二,但事实上可能有三份,因为epilogue.opt也可以有一个自己的“%%”,从而再将文件切出一个epilogue,当然这个是可选的,如果有的话,它(epilogue.opt )的语法为| "%%" EPILOGUE

%token PROLOGUE        "%{...%}"

    /*------------------------------------.
    | Declarations: before the first %%.  |
    `------------------------------------*/

prologue_declarations:
  /* Nothing */
| prologue_declarations prologue_declaration 这里可以看到一点,可以在正文开始之前(第一个%%之前)使用任意多对%{%},因为这里的
                                                                          prologue_declarations是可以递归的
;

prologue_declaration:
  grammar_declaration
| "%{...%}"

对于prologue的解析,同样在词法文件scan-gram.l中
  /* Prologue. */
  "%{"        code_start = loc->start; BEGIN SC_PROLOGUE;
<SC_PROLOGUE>
{
  "%}" {
    STRING_FINISH;
    loc->start = code_start;
    val->chars = last_string;
    BEGIN INITIAL;
    return PROLOGUE;
  }
5、语法规则中出现的字符及字符串
在bison的语法规则定义中出现了比较多的字符串,例如
grammar_declaration:
  precedence_declaration
| symbol_declaration
| "%start" symbol
    {
      grammar_start_symbol_set ($2, @2);
    }
| "%destructor" "{...}" generic_symlist
    {
      symbol_list *list;
      for (list = $3; list; list = list->next)
    symbol_list_destructor_set (list, $2, @2);
      symbol_list_free ($3);
    }
在bash的语法文件中有一些字符形式的token,例如
redirection:    '>' WORD
            {
              source.dest = 1;
              redir.filename = $2;
              $$ = make_redirection (source, r_output_direction, redir, 0);
            }
字符是可穷举的,一个char最多使用256个值,所以可以将字符的token编号直接映射到它的ASCII内码。对于字符串来说,明显地,它们不是一个真正的token,因为token是需要ID,然后转换为一个语法分析可以识别的整数,所以字符串要做特殊处理。如何处理呢?还是使用我们%token中说明的方法,通过
%token  ID “string”
这里要求为“string”分配一个ID,这个ID是bison和lex约定的共识ID,当词法分析的时候,它可以返回这个ID值(注意,这同样是bison处理完语法文件之后会给ID分配一个唯一的数值),而对于bison的语法文件,则依然使用这个字符串。为什么这么做呢?输出来不怕你笑,是为了便于维护。以前可能只知道写程序,事实上写程序在整个软件开发中的比例大概有10%吧,可能更少,我们就不少构思代码的时间了,代码写出来之后调试的时间会很多,更多的则是维护成本。这种方法,通过bison源代码中的一些变量/函数命名可以知道,这是一种别名(alias)机制。
看一下parse-gram.c生成的定义
enum yytokentype {
     GRAM_EOF = 0,
     STRING = 258,这里从258开始,所以1--255保留给了字面字符串。至于256和257用来干什么了,只找到#define YYERRCODE    256,257下落不明。
     INT = 259,
6、语法动作中'$'的解析处理
这个主要是通过handle_action_dollar函数处理,它首先调用parse_ref来解析出'$'后面的数值,然后返回到handle_action_dollar函数中,
   case LHS_REF:这个是 “$$”符号的处理
      if (!type_name)
    type_name = symbol_list_n_type_name_get (rule, dollar_loc, 0);
……
  default:
      if (max_left_semantic_context < 1 - n)
    max_left_semantic_context = 1 - n;
      if (!type_name && 0 < n)
    type_name =
      symbol_list_n_type_name_get (effective_rule, dollar_loc, n);这里是从符号列表中取到第n个符号,然后获得这个符号的类型。例如$2,则获得语法规则第二个符号的名称,然后再符号中提取出该token的类型,这个类型就是通过%type声明的类型
      if (!type_name)
    {
    ……
    }

      obstack_fgrow3 (&obstack_for_string,
              "]b4_rhs_value(%d, %d, [%s])[",
              effective_rule_length, n, type_name);
 ……
      break;
7、C代码如何生成
例如,这里定义的union将会生成一个YYSSTATE类型,这个是C语言代码,而bison的工作也就是根据一个语法文件生成一个C语言代码,这个代码是在何时生成的呢?现在可以知道的是,它是定义了一些宏,然后使用M4宏处理工具进行处理,然后生成文件。例如在上面的
obstack_fgrow3 (&obstack_for_string,
              "]b4_rhs_value(%d, %d, [%s])[",
              effective_rule_length, n, type_name);
这里的字符串应该就是一个M4语句,但是具体是怎么实现的,我现在也没有看。这里M4的接口有一个
muscle_code_grow ("stype", $3, @3);
这里的stype将会和之后的一些预处理结合生成一些M4宏,具体来说感觉还是很繁琐的。

在bison-2.5\data\bison.m4中有一些相关的宏,大家有兴趣的话可以研究一下
# ----------------------
# Macros that issue user code, ending with synclines.
b4_define_user_code([actions])
b4_define_user_code([initial_action])
b4_define_user_code([post_prologue])
b4_define_user_code([pre_prologue])
b4_define_user_code([stype])
8、和词法分析的接口
现在觉得比较重要的有两个,一个是yylex,返回解析的词法属性,例如是字符串,整数,字符等。但是这里还有一个问题,这里只是返回了一个类型,但是没有返回具体值。例如 “Hello” 和 “World”都是字符串,但是打印的时候还是需要知道具体值的,更直观的说,规约命令中的$1之类的引用如何交代。此时就还有一个变量,就是yylval,这个变量中的l是lookahead的缩写,表示当前展望符号的内容。毫无疑问,它是一个union类型,这个union如果在语法文件中不命名,那就叫做YYSSTATE(YY Symbol State),这个需要在yylex中对这个全局变量赋值。例如,在bash的词法分析函数read_token_word 中,其中的赋值为
  if (command_token_position (last_read_token))
    {
      struct builtin *b;
      b = builtin_address_internal (token, 0);
      if (b && (b->flags & ASSIGNMENT_BUILTIN))
    parser_state |= PST_ASSIGNOK;
      else if (STREQ (token, "eval") || STREQ (token, "let"))
    parser_state |= PST_ASSIGNOK;
    }

  yylval.word = the_word;

  if (token[0] == '{' && token[token_index-1] == '}' &&
      (character == '<' || character == '>'))
    {
      /* can use token; already copied to the_word */
      token[token_index-1] = '\0';
      if (legal_identifier (token+1))
    {
      strcpy (the_word->word, token+1);
/*itrace("read_token_word: returning REDIR_WORD for %s", the_word->word);*/
      return (REDIR_WORD);
    }
    }
  评论这张
 
阅读(1745)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017