yacc语法分析器_gcc的语法分析器是通过yacc生成的吗 - CSDN
精华内容
参与话题
  • Yacc实现语法分析器 一、实验目的 掌握语法分析器的构造原理,掌握Yacc的编程方法。 二、实验内容 用Yacc编写一个语法分析程序,使之与词法分析器结合,能够根据语言的上下文无关文法,识别输入的单词序列...

     Yacc实现语法分析器

     

    一、实验目的

    掌握语法分析器的构造原理,掌握Yacc的编程方法。

     

    二、实验内容

    Yacc编写一个语法分析程序,使之与词法分析器结合,能够根据语言的上下文无关文法,识别输入的单词序列是否文法的句子。

    program      → block

    block     →   { stmts }

    stmts     → stmt stmts | e

           stmt       →   id= expr ;

                            |      if ( bool ) stmt

                                |      if ( bool) stmt else stmt

    |      while (bool) stmt

    |      do stmt while (bool ) ;

    |      break ;

    |      block

    bool      expr < expr

    |     expr <= expr

    |     expr > expr

    |     expr >= expr

    |     expr

    expr      → expr + term

    |     expr - term

    |     term

    term      → term * factor

     |   term / factor

    |     factor

    factor     → ( expr ) | id| num 

     

     

    三、实验步骤及结果

    实验环境:unix

    实验结果:按归约的先后顺序显示每次归约时所使用的产生式。

    部分代码:

    用于产生flex输入的代码

    View Code
    Test.l:[a-zA-Z_][a-zA-Z_0-9]* {return ID;}
    
    [0-9]+\.[0-9]+ {return REAL;}
    
    [0-9]+ {return NUM;}
    
    "||" {return OR;}
    
    "&&" {return AND;}
    
    "|" {return '|';}
    
    "&" {return '&';}
    
    "<=" {return LE;}
    
    "<" { return '<';}
    
    ">=" {return GE;}
    
    ">" {return '>';}
    
    "!=" {return NE;}
    
    "=" { return '=';}
    
    "==" {return EQ;}
    
    "\+"  {return '+';}
    
    "\-" {return '-';}
    
    "\*" {return '*';}
    
    "\/" {return '/';}
    
    "(" {return '(';}
    
    ")" {return ')';}
    
    ";" {return ';';}
    
    "{" {return '{';}
    
    "}" {return '}';}
    
    "[" {return '['; }
    
    "]" {return ']';}
    
    Test.y:rel : expr '<' expr { printf("rel-->expr<expr\n"); }
    
        | expr LE expr { printf("rel-->expr<=expr\n"); }
    
           | expr GE expr { printf("rel-->expr>=expr\n"); }
    
           | expr '>' expr { printf("rel-->expr>expr\n"); }
    
           | expr { printf("rel-->expr\n"); }
    
           ;
    
    expr : expr '+' term { printf("expr-->expr+term\n"); }
    
         | expr '-' term { printf("expr-->expr-term\n"); } 
    
            | term { printf("expr-->term\n"); }
    
            ;
    
    term : term '*' unary { printf("term-->term*unary\n"); }
    
         | term '/' unary { printf("term-->term/unary\n"); }
    
            | unary { printf("term-->unary\n"); }
    
            ;
    
    unary : '!' unary { printf("unary-->!unary\n"); }
    
          | '-' unary %prec UMINUS{ printf("unary-->-unary\n"); }
    
             | factor { printf("unary-->factor\n"); }
    
             ;
    
    factor : '(' bool ')' { printf("factor-->(bool)\n"); }
    
           | loc { printf("factor-->loc\n"); }
    
              | NUM { printf("factor-->num\n"); }
    
              | REAL { printf("factor-->real\n"); }
    
              | TRUE { printf("factor-->true\n"); }
    
              | FALSE { printf("factor-->false\n"); }

    Flex生成代码:

    View Code
    Test.l:[a-zA-Z_][a-zA-Z_0-9]* {return ID;}
    
    [0-9]+\.[0-9]+ {return REAL;}
    
    [0-9]+ {return NUM;}
    
    "||" {return OR;}
    
    "&&" {return AND;}
    
    "|" {return '|';}
    
    "&" {return '&';}
    
    "<=" {return LE;}
    
    "<" { return '<';}
    
    ">=" {return GE;}
    
    ">" {return '>';}
    
    "!=" {return NE;}
    
    "=" { return '=';}
    
    "==" {return EQ;}
    
    "\+"  {return '+';}
    
    "\-" {return '-';}
    
    "\*" {return '*';}
    
    "\/" {return '/';}
    
    "(" {return '(';}
    
    ")" {return ')';}
    
    ";" {return ';';}
    
    "{" {return '{';}
    
    "}" {return '}';}
    
    "[" {return '['; }
    
    "]" {return ']';}
    
    Test.y:rel : expr '<' expr { printf("rel-->expr<expr\n"); }
    
        | expr LE expr { printf("rel-->expr<=expr\n"); }
    
           | expr GE expr { printf("rel-->expr>=expr\n"); }
    
           | expr '>' expr { printf("rel-->expr>expr\n"); }
    
           | expr { printf("rel-->expr\n"); }
    
           ;
    
    expr : expr '+' term { printf("expr-->expr+term\n"); }
    
         | expr '-' term { printf("expr-->expr-term\n"); } 
    
            | term { printf("expr-->term\n"); }
    
            ;
    
    term : term '*' unary { printf("term-->term*unary\n"); }
    
         | term '/' unary { printf("term-->term/unary\n"); }
    
            | unary { printf("term-->unary\n"); }
    
            ;
    
    unary : '!' unary { printf("unary-->!unary\n"); }
    
          | '-' unary %prec UMINUS{ printf("unary-->-unary\n"); }
    
             | factor { printf("unary-->factor\n"); }
    
             ;
    
    factor : '(' bool ')' { printf("factor-->(bool)\n"); }
    
           | loc { printf("factor-->loc\n"); }
    
              | NUM { printf("factor-->num\n"); }
    
              | REAL { printf("factor-->real\n"); }
    
              | TRUE { printf("factor-->true\n"); }
    
              | FALSE { printf("factor-->false\n"); }

    Yacc生成部分代码:

    View Code
    #line 1334 "y.tab.c"
    
      yyvsp -= yylen;
    
      yyssp -= yylen;
    
      YY_STACK_PRINT (yyss, yyssp);
    
      *++yyvsp = yyval;
    
      /* Now `shift' the result of the reduction.  Determine what state
    
         that goes to, based on the state we popped back to and the rule
    
         number reduced by.  */
    
     
    
      yyn = yyr1[yyn];
    
     
    
      yystate = yypgoto[yyn - YYNTOKENS] + *yyssp;
    
      if (0 <= yystate && yystate <= YYLAST && yycheck[yystate] == *yyssp)
    
        yystate = yytable[yystate];
    
      else
    
        yystate = yydefgoto[yyn - YYNTOKENS];
    
     
    
      goto yynewstate;
    
     
    
     
    
    /*------------------------------------.
    
    | yyerrlab -- here on detecting error |
    
    `------------------------------------*/
    
    yyerrlab:
    
      /* If not already recovering from an error, report this error.  */
    
      if (!yyerrstatus)
    
        {
    
          ++yynerrs;
    
    #if YYERROR_VERBOSE
    
          yyn = yypact[yystate];
    
     
    
          if (YYPACT_NINF < yyn && yyn < YYLAST)
    
           {
    
             YYSIZE_T yysize = 0;
    
             int yytype = YYTRANSLATE (yychar);
    
             const char* yyprefix;
    
             char *yymsg;
    
             int yyx;
    
     
    
             /* Start YYX at -YYN if negative to avoid negative indexes in
    
                YYCHECK.  */
    
             int yyxbegin = yyn < 0 ? -yyn : 0;
    
     
    
             /* Stay within bounds of both yycheck and yytname.  */
    
             int yychecklim = YYLAST - yyn;
    
             int yyxend = yychecklim < YYNTOKENS ? yychecklim : YYNTOKENS;
    
             int yycount = 0;
    
     
    
             yyprefix = ", expecting ";
    
             for (yyx = yyxbegin; yyx < yyxend; ++yyx)
    
               if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR)
    
                 {
    
                  yysize += yystrlen (yyprefix) + yystrlen (yytname [yyx]);
    
                  yycount += 1;
    
                  if (yycount == 5)
    
                    {
    
                      yysize = 0;
    
                      break;
    
                    }
    
                 }
    
             yysize += (sizeof ("syntax error, unexpected ")
    
                       + yystrlen (yytname[yytype]));
    
             yymsg = (char *) YYSTACK_ALLOC (yysize);
    
             if (yymsg != 0)
    
               {
    
                 char *yyp = yystpcpy (yymsg, "syntax error, unexpected ");
    
                 yyp = yystpcpy (yyp, yytname[yytype]);
    
     
    
                 if (yycount < 5)
    
                  {
    
                    yyprefix = ", expecting ";
    
                    for (yyx = yyxbegin; yyx < yyxend; ++yyx)
    
                      if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR)
    
                        {
    
                         yyp = yystpcpy (yyp, yyprefix);
    
                         yyp = yystpcpy (yyp, yytname[yyx]);
    
                         yyprefix = " or ";
    
                        }
    
                  }
    
                 yyerror (yymsg);
    
                 YYSTACK_FREE (yymsg);
    
               }
    
             else
    
               yyerror ("syntax error; also virtual memory exhausted");
    
           }
    
          else

    例如,程序片断

    {

           i = 2;

           while (i <=100)

           {

                  sum = sum + i;

                  i = i + 2;

           }

    }

     (注:原本是在windwos环境下编程,最后到unix环境下,发现速度快了,灵活性高了,同时方便了很多。(flex,bison))

    test.l

    View Code
    %option noyywrap
    %{
    #include<stdlib.h>
    #include<ctype.h>
    #include<stdio.h>
    %}
    %%
    "if" {return IF;} 
    "while" {return WHILE;} 
    "do" {return DO;} 
    "break" {return BREAK;}
    "int"|"float"|"bool"|"char" {return BASIC;}
    "true" {return TRUE;}
    "false" {return FALSE;}
    "else"  {return ELSE;}
    [a-zA-Z_][a-zA-Z_0-9]* {return ID;}
    [0-9]+\.[0-9]+ {return REAL;}
    [0-9]+ {return NUM;}
    "||" {return OR;}
    "&&" {return AND;}
    "|" {return '|';}
    "&" {return '&';}
    "<=" {return LE;}
    "<" { return '<';}
    ">=" {return GE;}
    ">" {return '>';}
    "!=" {return NE;}
    "=" { return '=';}
    "==" {return EQ;}
    "\+"  {return '+';}
    "\-" {return '-';}
    "\*" {return '*';}
    "\/" {return '/';}
    "(" {return '(';}
    ")" {return ')';}
    ";" {return ';';}
    "{" {return '{';}
    "}" {return '}';}
    "[" {return '['; }
    "]" {return ']';}
    "//".*  {}
    [ \n\t] {}
    %%

    test.y

    View Code
    %{
    #include<ctype.h>
    #include<stdio.h>
    %}
    %left '+' '-'
    %left '*' '/'
    %nonassoc UMINUS
    %token NUM AND BASIC BREAK DO ELSE EQ FALSE GE
    %token ID IF INDEX LE MINUS NE OR REAL TRUE WHILE
    KET
     %token  RIGHT_BRA
    %%
    program : block { printf("program-->block\n"); }
            ;
    block : '{' decls stmts '}' { printf("block-->{decls stmts}\n"); }
          ;
    decls : decls decl { printf("decls-->decls decl\n"); }
          | /*empty*/
          ;
    decl : type ID ';' { printf("decl-->type id;\n"); }
         ;
    type : type '[' NUM ']' { printf("type-->type[num]\n"); }
         | BASIC { printf("type-->basic\n"); }
         ;
    stmts : stmts stmt { printf("stmts-->stmts stmt\n"); }
         | /*empty*/
         ;
    stmt : DO stmt WHILE '(' bool ')' ';' { printf("stmt-->do stmt while(bool);\n"); }
         | IF '(' bool ')' stmt { printf("stmt--if(bool)stmt\n"); }
         | IF '(' bool ')' stmt ELSE stmt { printf("stmt-->if(bool)stmt else stmt\n"); }
         | WHILE '(' bool ')' stmt { printf("stmt-->while(bool)stmt\n"); }
         | BREAK ';' { printf("stmt-->break;\n"); }
         | block { printf("stmt-->block\n"); }
         | loc '=' bool ';' { printf("stmt-->loc=bool;\n"); }
         ;
    loc : loc '[' bool ']' { printf("loc-->loc[bool]\n"); }
        | ID { printf("loc-->id\n"); }
        ;
    bool : bool OR join { printf("bool-->bool||join\n"); }
         | join { printf("bool-->join\n"); }
         ;
    join : join AND equality { printf("join-->join&&equality\n"); }
         | equality { printf("join-->equality\n"); }
         ;
    equality : equality EQ rel { printf("equality-->equality==rel\n"); }
             | equality NE rel { printf("equality-->equality!=rel\n"); }
             | rel { printf("equality-->rel\n"); }
             ;
    rel : expr '<' expr { printf("rel-->expr<expr\n"); }
        | expr LE expr { printf("rel-->expr<=expr\n"); } 
        | expr GE expr { printf("rel-->expr>=expr\n"); }
        | expr '>' expr { printf("rel-->expr>expr\n"); }
        | expr { printf("rel-->expr\n"); }
        ;
    expr : expr '+' term { printf("expr-->expr+term\n"); }
         | expr '-' term { printf("expr-->expr-term\n"); }  
         | term { printf("expr-->term\n"); }
         ;
    term : term '*' unary { printf("term-->term*unary\n"); }
         | term '/' unary { printf("term-->term/unary\n"); }
         | unary { printf("term-->unary\n"); }
         ;
    unary : '!' unary { printf("unary-->!unary\n"); }
          | '-' unary %prec UMINUS{ printf("unary-->-unary\n"); }
          | factor { printf("unary-->factor\n"); }
          ;
    factor : '(' bool ')' { printf("factor-->(bool)\n"); }
           | loc { printf("factor-->loc\n"); }
           | NUM { printf("factor-->num\n"); }
           | REAL { printf("factor-->real\n"); }
           | TRUE { printf("factor-->true\n"); }
           | FALSE { printf("factor-->false\n"); }
           ;
           
    %%
    #include "lex.yy.c"
    int  main()
    {
     extern FILE *yyin;
     yyin=fopen("b.txt","r");
     yyparse();
     return 0;
    }
    yyerror(char *s)
    {
        printf("%s error!\n",s);
    }

    b.txt

    View Code
    {
        i = 2;
        while (i <=100)
        {
            sum = sum + i;
            i = i + 2;
        }
    }

    在unix可以生成a.out就能直接用。

    《Lex与Yacc》中文第二版(带源码)_yacc_flex_两份文档:http://pan.baidu.com/share/link?shareid=167248&uk=1678594189

    实验4 secomd time 晋级版():http://pan.baidu.com/share/link?shareid=167252&uk=1678594189

    转载于:https://www.cnblogs.com/xjx-user/archive/2012/12/16/2820676.html

    展开全文
  • 【编译原理】用Yacc语法分析

    万次阅读 多人点赞 2014-01-09 12:53:40
    08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业... 语法分析 Yacc 全称 Yet Another Compiler Compiler Yacc是一个用来生成编译器的编译器(编译器代码生成)。yacc生成的

    08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://blog.csdn.net/xiaowei_cqu/article/details/7747205


    语法分析

    Yacc 全称 Yet Another Compiler Compiler
    Yacc是一个用来生成编译器的编译器(编译器代码生成器)。yacc生成的编译器主要是用C语言写成的语法解析器(Parser),需要与词法解析器Lex一起使用,再把两部份产生出来的C程序一并编译。
    作为 Yacc 对说明文件中的 %token NUMBER 声明的对应。Yacc 坚持定义所有的符号记号本身,而不是从别的地方引入一个定义。但是却有可能通过在记号声明中的记号名之后书写一个值来指定将赋给记号的数字值。
    Yacc的输入是巴科斯范式(BNF)表达的语法规则以及语法规约的处理代码,Yacc输出的是基于表驱动的编译器,包含输入的语法规约的处理代码部分。
    Yacc是开发编译器的一个有用的工具,采用LALR(1)语法分析方法。

    【实验内容】

    1、实验环境配置
    安装Parser Generator,并编译lex和yacc函数库

    2、编写Lex程序
    (1)练习9.4.1:编写一个Yacc程序。该程序以布尔表达式作为输入(如习题4.2.2所示)并输入次布尔表达式的值。
    编写Yacc程序如下:


    编写Lex程序如下:


    布尔表达式对应的文法如下:
    • bexpr→bexpr or bterm | bterm
    • bterm→bterm and bfactor | bfactor
    • bfactor→not bfactor |(bexpr) | true |false
    所以程序中通过相应的语法定义规则:
    line : bexpr '\n'   {if($1==1){printf("true");}else{printf("false");}}
         | '\n'         {printf("\n");}
         ;
    bexpr : bexpr '&' bterm   { if(($1==1)&&($3==1)){$$=1;}else{$$=0;} }
          | bterm
          ;
    bterm : bterm '|' bfactor   {if(($1==0)&&($3==0)){$$=0;}else{$$=1;}}
          | bfactor           
          ;
    bfactor :'~' bfactor     {if($2==1){$$=0;}else{$$=1;}}
            | '('bexpr')'   {$$=$2;}
            |  TRUE         
            |  FALSE
    
    在读到1或0(通过Lex定义的语法返回的响应值)以及‘|’或‘&’‘~’布尔运算符号时,进行布尔预算,并返回值
    根据布尔运算的结果打印“true”或“false”的消息
    程序运行结果:


    (2)练习9.4.2:编写一个yacc程序,把字符串(按4.2.2(5)语法定义,但使得可以输出任何一个字符元素,而不是仅仅字符a)作为输出,并输出相同顺序的字符串
    4.2.2定义的规则(5)为:S→(L)|a    L→L,S|S
    在Yacc中只需定义相应的语法规则
    line:  L '\n'		 	 
        | '\n' 
    	;
    L   : S					
        | L ',' S				
    	    ;
    S   :'(' L ')'	{$$=$2;}
        |  LETTER	{printf("%c",$1);}
    
    并在遇到字符时,打印字符即可得到效果

    编写Lex程序如下:

    程序运行结果:

    (3)练习9.4.3:编写一个Yacc程序。判断输入的字符串是否是回文(正读或逆读的结果相同)。


    编写Lex程序如下:


    程序通过Lex识别连续的字符串
    之后通过C语言判断是否是回文:将第i个字符与第len-i-1个字符比较,如果有不相同的,则将标记tag标记为0(否则为1)
    程序最后(读入换行符‘\n’时)通过tag标记输出是否为回文。
    程序运行结果:


    【结果分析】

    1. 通过实验熟悉了Yacc做语法分析。尝试了Yacc程序两种编写方式,只有Yacc以及与Lex结合。感觉还是与Lex结合更灵活一些,因为Lex定义正则表达式作词法分析。比如字符串true。Lex只需写true{yylval=1;return TRUE;}而在Yacc中尝试判断写出来的语句为char c=getchar();int i=0;while(c=getchar()){if(c=='t')i=1;else if(c=='r'&&i==1)i=2;else if(c=='u'&&i==2)i=3;else if(c=='e'&&i==3)yylval=1;i=0;return TRUE;}(当然也可能是自己的思路复杂了些。。。)
    2. 实验中几个题目并不复杂,前两个更侧重语法判断,但第三个回文测试时,感觉并没用到太多Yacc的语法分析。而是通过Lex识别字符串,之后用C的思想判断是为回文。虽然也达到了效果,但不知是否还有其他的方法? 
    3. 实验程序的容错能力都比较差,输入一些没有定义的字符程序就会弹出终止,调了很久也没有解决。感觉自己语法分析还是掌握的不够扎实。

    转载请注明出处:http://blog.csdn.net/xiaowei_cqu/article/details/7764913




    展开全文
  • Redy语法分析--语法分析工具yacc

    千次阅读 2012-03-01 13:10:19
    返回文档首页 在文章中有关yacc的内容摘自:编译原理(第三版).蒋立源,康慕宁主编.... ...(1)yacc简介 ...YACC的全名为Yet Another Compiler-Compiler ,是LALR(1)分析器的自动生成工具,它...使用YACC构造语法分析程序

    返回文档首页


    在文章中有关yacc的内容摘自:编译原理(第三版).蒋立源,康慕宁主编. 西北工业大学出版社.


    (1)yacc简介

    YACC的全名为Yet Another Compiler-Compiler ,是LALR(1)分析器的自动生成工具,它的第一版于20世纪70年代初发表,是美国贝尔实验实的产品,作者为S.C.Johnson

    使用YACC构造语法分析程序非常方便,它要求用户按一定的规则编写出“文法处理说明文件”,简称YSP(Yacc Specification)文件,文件的扩展名为".y",当输入YSP文件时,YACC会自动构造出相应的C语言形式的语法分析器。该分析器主要包括由YACC提供的标准总控制程序和一个LALR(1)分析表。

    (2)YSP文件结构

    一个完整的YSP文件由说明,规则,程序三个部分组成各部分之间由双百分号隔开:

    [说明部分]
    %%
    规则部分
    [%%
    程序部分
    ]

    其中用方括号括起来的说明部分和程序部分可以空缺,但是规则部份是必须的。因此YSP文件最简章的形式是

    %%
    规则部分


    (3)YSP说明部分的组成

    YSP文件的说明部分用于定义规则部分所使用的变量及语法符号,它可以包含以下几类信息:

    1. 变量定义

    变量的定义需要用一对持殊括号 "%{"和 "%}括起来,其内容包括规则部份中语义动作及程序部分所需使用的有关文件(如C语言的有关头文件)的引用及说明、数据结构的定义,全局和外部变量的定义以及函数原型的定义等等,这部分内部,应该遵守C语言的规定

    2. 开始符号定义

    文法的开始符号由说明符号%start 指明(Yacc中所有的说明符号均由"%"引出),例如:

    %start  StartSymbol

    指明的StartSymbol为文法的开始符号,若未给出开始符号的定义,则系统将自动以第一个语法规则的左部符号作为开始符号

    3. 词汇表定义

    在这部分,用户可以给出终结符号表,联合(uniion)和类型(type)说明,YACC要求所用到的所有终结符号都应明确的加以说明;对于未说明者,则均按非终结符号处理,终结符号说明由说明符号%token 或%term 引出,其书写格式有两种,第一种书写格式为

    %token Tname [Tname2 ...]

    各个终结符号之间用空格分隔。在一行写不下时,可以%token 别起一行继续定义。第二种书写格式允许用户自行定义终结符号的内部编码值,其格式为

    %token Tname <integer>

    其中,<integer>应为大于256的整数,当用户未给定终结符号的内部编码时,系统将按终结符号的出现顺序,从257开始,依次为其定义内部码值:257,257,...。YACC内部约定,当词法分析程序从输入字符串中识别出一个终结符号时,将返回该终节符号的内部编码值。还需指出,除文主字型的终结符号外,对于程序设计语言中的单字符运算符、分隔符等终结符号,可在文法中用单引号括起来直接使用,不必使用%token定义,其内部码值就是它的ASCII码(其值不将不会大于256,这也是用户自定义的终结符号内部码之值不能小于257的原困

    在词汇表定义中,还可以通过使用联合(%union)和类型说明(%type),对每个文法符号定义其语义属性应具有的数据类型。例如,假定非终结符号A具有属性Attr_a,其值为整型;非终结符号B具有两个属性b1各b2,其中b1为整数,b2为浮点数;则可以通过联合说明告诉Yacc,文法符号具有两种类型:

    %union
    {
        int attr_a;
        struct 
        {
            int b1;
            float b2;
       }attr_b;
    }


    然后再用%type说明非终结节符号A和B所具有的类型:

    %type <attr_a> A
    %type <attr_b> B


    其中尖括号<>中的名字是联合定义中的成员,一般来说若使用了联合定义,则须使用类型说明(%type)对每个文法符号的数据类型进行定义(每个文法符号有且仅有一个符号类型),否则YACC将会报错。使用上述方式,允许在一行中定义多个文法符号,只需用空格将其隔开即可,若在一行写不下时,则需别起一行后重新用%type命定继续定义。若在说明部分未用联合进行说明,则YACC自动使用缺省类型,Yacc约定,每一个文法符号的缺省类型为整型。




    (4)YSP文件程序部分的组成

    YSP文件的和序部分是可选的,它由例行C语言程序(函数)组成,主要包括主程序main(),词法分析程序yylex(),出错处理子程序yyerror(),语法规则部份语义动作中所调用的用户自定义函数以及其它辅助函数等等。下面对它们的格式,功能和用法作用概括地说明。

    (1)YACC在处理YSP文件之后,将输入一个名为y.tab.c的C程序文件,此文件含有名为yyparser()的语法分析程序。主程序main()的主要作用,在于调用函数yyparser()对源程序进行语法分析。当语法分析成功结束时,yyparser()返回值为0,而在发现源程序有语法错语的,除返加值为1外,它还调用yyerror()函数输出出错信息。函数main()和yerror()可由yacc库提供(只需在编译命令中加入选择项-ly即可)。如果用户认为上述函数的功能不满足要求,例如还需要在主程序中做其它的辅助处理,或需要yyerror输出更详细的出错信息,也可以自行编写这个函数。

    (2)YACC系统规定,在语法分析程序yyparser()运行时,需要一个名为yylex()的词法分析程序对其支持,每当yyparse()调用yylex()时,yylex()就从输入字符流中识别出一个单词,并将该单词的内部码及其语义值(若有的话)分别通过return语句及全局变量yylval回送给yyparser(),可见yyparser()的输入来源于yylex()的返回信息。



    (5)YACC的安装

    在linux平台,yacc的GUN版本为bison

    ubuntu用户可以用下面命令来安装:

    sudo apt-get install bison



    返回文档首页










    展开全文
  • 学习如何使用Yacc设计一个语法分析器,并与用lex写的词法分析器链接起来。 实验内容: 使用yacc为实验2所给的语言写一个语法分析器(你可以重新设计该语言的文法,但不能改变语言)。其中,词法分析使用实验3中已...

    所有实验的源代码:点此下载

    实验目的:

    学习如何使用Yacc设计一个语法分析器,并与用lex写的词法分析器链接起来。

    实验内容:

    使用yacc为实验2所给的语言写一个语法分析器(你可以重新设计该语言的文法,但不能改变语言)。其中,词法分析使用实验3中已完成的词法分析器(即,你需要将本实验的语法分析器和实验3的词法分析器链接起来)。

    实验要求:

    输入为实验2所给语言写的源程序文件;输出为屏幕显示语法分析是否成功。
    在语法分析中不能出现任何的冲突(移进-归约或归约-归约冲突),或者虽然有冲突,但是你能够说清楚冲突是如何解决的。
    在cygwin下用flex,bison和gcc工具将实验调试通过,并且你写的语法分析器至少应该能通过例子parser0中testcases目录下的test0.p和test1.p两个测试例的测试。

    重要算法或文法正规式:

    在实验二中,已经为给定的语言写了词法分析器,也就是说已经分析出了该语言的所有终结符,那么在这个实验中,只要按照给定的文法,写出产生式即可。产生式的书写并不困难,此处就不再单独放上写出的产生式了,因为在后面给出的源代码中也可以看出产生式是如何书写的。在写产生式时,有一个地方需要注意,如果完全按照实验手册中给定的文法写产生式,最后写出的产生式会发生冲突。下面给出会发生冲突的地方:

    <变量说明> --> VAR <变量说明表>;
    <变量说明表>–> <变量表>: <类型> | <变量表>: <类型>; <变量说明表>

    按照上面的文法,分析如下句子的移进规约过程。
    VAR i, j : integer; f0 : real ;
    当遇到VAR时,这是一个关键字,应该移进,遇到i,逗号,j时应该先移进再规约成<变量表>,遇到冒号移进,遇到关键字integer移进再规约成<类型>,此时栈中的内容为:VAR <变量表> : <类型>,输入指针指向的下一个记号是分号,此时可以将这个分号看成第一条产生式的最右符号,那么现在应该按照第二条产生式规约,也可以将这个分号看成第三条产生式里面的分号,那么现在应该将分号移进,由于面对同一个记号,分析器动作不唯一,因此上面的产生式会有移进-规约冲突。解决方法是将产生式修改如下:
    <变量说明> --> VAR <变量说明表>
    <变量说明表> --> <变量表>: <类型> ;| <变量表>: <类型>; <变量说明表>
    修改之后的产生式,当分析器遇到分号时,一定是移进,根据下一个记号是否为BEGIN来判断是规约还是继续移进。
    修改实验二写的词法分析器,将对记号名的所有宏定义删除,因为记号名是在语法分析器中定义的,词法分析器只需要包含相应的头文件就可以使用这些记号名了,在写语法分析器时需要注意,对于同一记号的记号名要与词法分析器保持一致,否则词法分析器和语法分析器链接不起来。删除词法分析器中的主函数和输出函数,将主函数写到语法分析器,因为语法分析器是主导,它需要的时候去调用词法分析器。
    语法分析器的源代码文件名为exp5.y,那么在词法分析器中应该包含exp5.tab.h头文件,这个头文件的内容主要是记号名和yylval的定义,在用bison编译exp5.y时,首先输入命令bison exp5.y -d以生成exp5.tab.h,当然也可以把编译命令都写在makefile文件中,通过一条make命令就能将词法分析器和语法分析器链接起来。

    词法分析器代码:

    /* 把讨厌的注释去掉 */
    
    %{
    
    #include <stdio.h> 
    #include "exp5.tab.h"
    
    %}
    
    delim		[ \t \n]
    ws			{delim}+
    letter		[A-Za-z]
    digit		[0-9]
    int			{digit}+
    float		\.{int}|{int}\.{int}
    id			{letter}({letter}|{digit})*
    
    /* 状态(或条件)定义可以定义在这里 
     * INITIAL是一个默认的状态,不需要定义
     */
    %s COMMENT
    %s LINECOMMENT
    
    %%
    
    <INITIAL>"(*"						{ BEGIN COMMENT;}
    <COMMENT>"*)"						{ BEGIN INITIAL;}
    <COMMENT>.|\n						{ ;}
    
    <INITIAL>"IF"				{return (IF);}
    <INITIAL>"THEN"				{return (THEN);}
    <INITIAL>"ELSE"				{return (ELSE);}
    <INITIAL>"WHILE"			{return (WHILE);}
    <INITIAL>"DO"				{return (DO);}
    <INITIAL>"PROGRAM"			{return (PROGRAM);}
    <INITIAL>"BEGIN"			{return (BEGIN0);}
    <INITIAL>"END"				{return (END);}
    <INITIAL>"VAR"				{return (VAR);}
    <INITIAL>"INTEGER"			{return (INTEGER);}
    <INITIAL>"REAL"				{return (REAL);}
    <INITIAL>"<"				{return (LT);}
    <INITIAL>"<="				{return (LE);}
    <INITIAL>">"				{return (GT);}
    <INITIAL>">="				{return (GE);}
    <INITIAL>"="				{return (EQ);}
    <INITIAL>"<>"				{return (NE);}
    <INITIAL>"+"				{return (PLUS);}
    <INITIAL>"-"				{return (MINUS);}
    <INITIAL>"*"				{return (TIMES);}
    <INITIAL>"/"				{return (DIVIDE);}
    <INITIAL>":="				{return (ASSIGNMENT);}
    <INITIAL>";"				{return (SEMI);}
    <INITIAL>":"				{return (COLON);}
    <INITIAL>","				{return (COMMA);}
    <INITIAL>"."				{return (DOT);}
    <INITIAL>{id}				{return (ID);}
    <INITIAL>{int}				{return (INT);}
    <INITIAL>{float}			{return (FLOAT);}
    
    <INITIAL>{ws}				{;}
    
    %%
    
    int yywrap (){
      return 1;
    }
    

    语法分析器代码:

    %{
    	#include <ctype.h>
    	#include <stdio.h>
    	int yylex();
    	int yyerror(char* s);  
    	#define YYDEBUG 1      
    %}
    
    %union {
    	int i;
    	float f;
    	char* id;
    }
    
    %token LT LE GT GE EQ NE WHILE DO  PROGRAM BEGIN0 END VAR INTEGER REAL ASSIGNMENT IF THEN ELSE PLUS MINUS TIMES DIVIDE SEMI COLON COMMA DOT LPAREN RPAREN
    %token <id> ID
    %token <i> INT
    %token <f> FLOAT
    %%
    
    
    prog : PROGRAM ID SEMI subprog	{printf("语法分析成功!\n");}
    	;
    subprog : varExplain BEGIN0 stateTab END DOT
    	;
    varExplain : VAR varExpTab
    	;
    varExpTab : varTab COLON type SEMI
    	| varTab COLON type SEMI varExpTab
    	;
    type : INTEGER
    	| REAL
    	;
    varTab : ID
    	| ID COMMA varTab
    	;
    stateTab : statement
    	| statement SEMI stateTab
    	;
    statement : assignState
    	| condiState
    	| whileState
    	| complexState
    	;
    assignState : ID ASSIGNMENT algoriExpe
    	;
    condiState : IF realExpe THEN statement ELSE statement
    	;
    whileState : WHILE realExpe DO statement
    	;
    complexState : BEGIN0 stateTab END
    	;
    algoriExpe : item
    	| algoriExpe PLUS item
    	| algoriExpe MINUS item
    	;
    item : factor
    	| item TIMES factor
    	| item DIVIDE factor
    	;
    factor : ID
    	| constNum
    	| LPAREN algoriExpe RPAREN
    	;
    realExpe : algoriExpe realOp algoriExpe
    	;
    constNum : INT 
    	| FLOAT
    	;
    realOp : LT
    	| LE
    	| EQ
    	| GT
    	| GE
    	| NE
    	;
    
    %%
    
    int main(int argc, char ** argv){
    	//yydebug = 1;
    	extern FILE* yyin;
    	if (argc == 2){
    	  if ((yyin = fopen(argv[1], "r")) == NULL){
    	    printf("Can't open file %s\n", argv[1]);
    	    return 1;
    	  }
    	}
    	
    	yyparse();
    
    	if(argc == 2){
    	  fclose(yyin);
    	}
    
    	return 0;
    }
    

    实验结果:

    在这里插入图片描述

    遇到的问题、实验难点、解决方法:

    和理论课上接触的语言相比,这个实验的语言显然要复杂很多,虽然实验要求中对给定语言的描述已经很清楚了,但是在写产生式时,还是感觉手忙脚乱,只能是根据语言的描述,将语言给拆解开,实际上这个语言的程序可以分为三部分:程序名、变量声明、语句,这样拆解之后,书写产生式会变的相对容易一些。
    直接按照实验给的文法写出的产生式会发生移进规约冲突,因此需要对产生式做一些修改,以避免冲突的发生。
    最初因为词法分析器和语法分析器的记号名不同,导致链接不起来,后来重新检查了一遍记号名,修改之后就能成功链接了。

    展开全文
  • Yacc语法分析

    千次阅读 2013-06-18 10:54:16
    Yacc语法分析 YACC简介 Yacc 全称 Yet Another Compiler Compiler Yacc是一个用来生成编译器的编译器(编译器代码生成)。yacc生成的编译器主要是用C语言写成的语法解析(Parser),需要与词法解析...
  • Yacc 与 Lex 快速入门(词法分析和语法分析

    万次阅读 热门讨论 2016-10-17 10:41:23
    原文 :Yacc 与Lex 快速入门 Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another Compiler Compiler。 让我们从 Lex 开始吧。 Lex Lex 是一种生成扫描的工具。扫描是一种识别文本中的词汇模式的程序。 ...
  • YACC(Yet Another Compiler-Compiler)是一个LALR(1)分析器自动生成器,是贝尔实验室在UNIX上首次实现,与LEX有直接的接口。此外GNU(GNU is not UNIX)的Bison是对YACC的兼容性扩充。YACC自动构造分析器的模式及...
  • yacc

    千次阅读 2012-08-21 16:54:46
    根据BNF自动生成语法分析器代码的程序,最后输出一颗语法树出来。 全称  yacc(Yet Another Compiler Compiler) 编辑本段简介  是Unix/Linux上一个用来生成编译器的编译器(编译器代码生成器)。yacc...
  • SQL 语句的处理过程: ...与之对比的Sqlite3数据库,SQLite的词法分析器是手工写的,语法分析器由Lemon生成。 要学习Mysql的分析器,则需要具备lex和yacc的相关知识。 (一)词法分析 在sql/
  • Yacc yacc(Yet Another ...yacc生成的编译器主要是用C语言写成的语法解析(Parser),需要与词法解析Lex一起使用,再把两部份产生出来的C程序一并编译。yacc本来只在Unix系统上才有,但现时已普遍移植往Windows
  • YACC构造简单语法分析器

    千次阅读 2015-12-02 21:23:04
    通过YACC构造能够识别台式计算器表达式的文法的语法分析程序 文法: E–>E+T|E-T|T T–>T*F|F F–>(E)|DIGIT 分析 YACC的工作流程是: 1.L语言的YACC源程序trans.y 通过YACC编译器生成trans_tab.c 2....
  • Yacc介绍与使用

    万次阅读 2011-12-28 13:21:11
    yacc(Yet Another Compiler Compiler),是Unix/Linux上一个用来生成编译器的编译器(编译器代码生成). 使用巴克斯范式(BNF)定义语法,能处理上下文无关文法(context-free)。出现在每个产生式左边(left-hand ...
  • LEX与YACC 词汇表

    千次阅读 2007-07-04 08:45:00
    LEX与YACC 词汇表 Action(动作)与LEX模式和YACC规则有关的C代码。当模式或规则与输入序列匹配时,执行动作代码。 Alphabet(字母表)不同符号的...在YACC语法中,字母表是语法中使用的标记和非终结符的集合。Ambig
  • 注:工作环境
  • 语法分析程序生成器可以被用于开发许多语言的语法分析器,由简单的桌面计算器到复杂的程序语言.Yacc是一个由给定的上下文无关文法构造,可以根据语法规则分析输入的C语言程序的程序.Yacc由S.C.Johnson和其他一些贝尔...
  • Lex与Yacc学习(十)之Yacc

    千次阅读 2015-01-22 15:31:26
    Yacc库 每个实现都需要有用的例程库,在UNIX系统中,可以通过cc命令行尾端给出-ly标志(或通过其他系统下的等价物)来包含库。 库的内容在不同的实现之间是不同的,但总是包括main()和yyerror() main() yacc的...
  • LALR语法分析器

    千次阅读 2016-01-27 15:31:10
    LALR分析器是一种规范LR分析方法的... LALR分析器可以根据一种程序设计语言的正式语法的产生式而对一段文本程序输入进行语法分析,从而在语法层面上判断输入程序是否合法。 实际应用中的LALR分析器并不是由人手工
  • boa的make错误解析

    千次阅读 2014-05-13 23:35:26
    yacc是一个文法分析器的生成器,bison即是yacc的GNU版本.Lex和YACC是用于构造词法分析机和语法解释器的工具,利用Lex和YACC你可以轻松的构造一个语法解释器。 一开始make 错误1: debian:/home/a/boa-0.94.13/src#...
  • 什么是yacc

    千次阅读 2011-12-15 16:57:11
    yacc生成的编译器主要是用C语言写成的语法解析(Parser),需要与词法解析Lex一起使用,再把两部份产生出来的C程序一并编译。yacc本来只在Unix系统上才有,但现时已普遍移植往Windows及其他平台。 yacc的输入是...
  • lex和yacc

    千次阅读 2010-06-13 23:25:00
    lex负责词法解析,而yacc负责语法解析,其实说白了就是lex负责根据指定的正则表达式,将输入的字符串匹配成一个一个的token,同时允许用户将当前匹配到的字符串进行处理,并且允许返回一个标识当前token的标识...
1 2 3 4 5 ... 20
收藏数 6,319
精华内容 2,527
关键字:

yacc语法分析器