五. 基于Bison设计实现C子集的语法分析器

[基本完成，有个小bug，估计没人发现hh...]
[只实现了一部分的语法分析...实在是太多了]

目前能识别的C语法：

char c;
void add(int a);
int sum(int a,int b)
{
    return a+b;
}
//This is comment.
int main(){
    int a = (1+1)/1.23-1;
    a = add(a);
    a = sum(a,1);
    double nums[10];
    nums[0] = 1;
    if ( a > 1 ) {
        a+=2;
    } else {
        a-=2;
    }
    for (int i=1;i++;i<10)
    {}
    
    while (1)
    {}
    return 0;
}
int add(int a)
{
    a++;
    return a;
}

实现代码

执行脚本：

#!/bin/bash

if (( $# != 1 ));then 
        echo "输入参数不正确"
        exit 1
fi
flex -o C-lexical-analyzer.yy.c C-lexical-analyzer.l 
echo "flex编译完成"
bison -o C-Parser.tab.h C-Parser.y
echo "bison编译完成"
gcc -o C-Parser -w C-Parser.tab.* C-lexical-analyzer.yy.c -lfl
echo "gcc编译完成"
rm C-Parser.tab.* C-lexical-analyzer.yy.c
echo "正在运行:(没有错误便说明通过)"
./C-Parser < $1
echo "运行结束"
rm C-Parser

bison：

/*
 *file: C-Parser.y
 *auther: jin1ming
 *system: manjaro
 */
%{
#include<stdio.h>
#include<stdlib.h>
#define YYSTYPE char*
%}

%token identifier AUTO BREAK CASE CHAR 
%token CONST CONTINUE DEFAULT DO DOUBLE 
%token ELSE ENUM EXTERN FLOAT FOR GOTO 
%token IF INT LONG REGISTER RETURN AND_NOT
%token SHORT SIGNED SIZEOF STATIC STRUCT 
%token SWITCH TYPEDEF UNSIGNED UNION 
%token DEC INC LPAREN NOT RPAREN SEMICOLON
%token VOID VOLATILE WHILE number array
%token LBRACE RBRACE RBRACK LBRACK
%token COMMA AND_NOT_ASSIGN PERIOD 
%token RBRAEN COLON POT DQUA SQUA
%left ASSIGN    ADD_ASSIGN  SUB_ASSIGN  MUL_ASSIGN  QUO_ASSIGN REM_ASSIGN  AND_ASSIGN  OR_ASSIGN  XOR_ASSIGN  SHL_ASSIGN  SHR_ASSIGN AND_NOASSIGN
/*条件运算符?:还未实现*/

/*以下操作符有优先级，顺序不可改变*/
%left LOR
%left LAND
%left OR
%left XOR
%left AND
%left NEQ EQL
%left LSS GTR LEQ GEQ
%left SHR SHL
%left ADD SUB
%left MUL QUO REM
/*单目运算符未声明*/
%start translation_unit
%%
/*C代码入口*/
translation_unit: 
    external_declaration
    | translation_unit external_declaration
    ;
/* 
 *代码块
 *分为函数块、变量块
 */
external_declaration
    : function_definition
    | declaration
    ;
/*
 *函数块
 *分为4种情况：
 * 1. int print(int a, int b){int a = 0;}
 * 2. int print();
 * 3. int print(){int a = 0;}
 * 4. int print(int a, int b);
 */
function_definition
    : type_specifier identifier LPAREN parameter_list RPAREN compound_statement
    | type_specifier identifier LPAREN RPAREN compound_statement
    | type_specifier identifier LPAREN parameter_list RPAREN SEMICOLON
    |   type_specifier identifier LPAREN RPAREN SEMICOLON
    ;
/*变量块*/
declaration
    : type_specifier declarator SEMICOLON
    | type_specifier assignmenexpression SEMICOLON
    ;
/*参数列表*/
parameter_list
    : parameter_declaration
    | parameter_list COMMA parameter_declaration
    ;
/*参数声明*/
parameter_declaration
    : type_specifier declarator
    ;
/*变量*/
declarator
    : identifier
    | array
    ;
/*函数实现块*/
compound_statement
    : LBRACE RBRACE
    | LBRACE block_item_list RBRACE
    ;
/*C语句块列表*/
block_item_list
    : block_item
    | block_item_list block_item
    ;
/*C语句块
 *分为声明语句和操作语句
 */
block_item
    : declaration
    | statement
    | RETURN arithmetic_expression_list SEMICOLON
    | RETURN conditional_expression_list SEMICOLON
    ;
/*操作语句*/
statement
    : compound_statement
    | expression_statement
    | selection_statement
    | iteration_statement
    ;
/*操作语句：多条语句*/
expression_statement
    : SEMICOLON
    | expression SEMICOLON
    ;
/*
 *操作语句：选择
 *分成两个，以消除偏移/规约冲突
 */
selection_statement
    : IF LPAREN expression RPAREN statement statement
    |   IF LPAREN expression RPAREN statement ELSE statement
    | SWITCH LPAREN expression RPAREN statement
    ;
/*操作语句：迭代循环*/
iteration_statement
    : WHILE LPAREN expression RPAREN statement
    | DO statement WHILE LPAREN expression RPAREN SEMICOLON
    | FOR LPAREN expression_statement expression_statement RPAREN statement
    | FOR LPAREN expression_statement expression_statement expression RPAREN statement
    | FOR LPAREN declaration expression_statement RPAREN statement
    | FOR LPAREN declaration expression_statement expression RPAREN statement
    ;
/*
 *表达式
 *分为条件表达式、赋值表达式、算数表达式
 */
expression
    : conditional_expression_list
    | assignmenexpression
    |   arithmetic_expression_list
    ;
/*赋值表达式*/
assignmenexpression
    :   declarator assignmenoperator expression
    ;
/*
 *算数表达式
 *  拆分成两个，以消除偏移/规约冲突
 */
arithmetic_expression_list
    :   arithmetic_expression_list arithmetic_operator arithmetic_expression
    |   arithmetic_expression_list arithmetic_operator LPAREN arithmetic_expression_list RPAREN 
    |   arithmetic_expression
    |   LPAREN arithmetic_expression_list RPAREN 
    ;
arithmetic_expression
    : value
    | identifier    INC
    | identifier    DEC
    |   ADD identifier
    |   SUB identifier
 /*
  *函数调用
  *特性与算数表达式比较类似
  */
    |   identifier LPAREN RPAREN 
    |   identifier LPAREN value_list RPAREN
    ;
/*传参*/
value_list
    :   value
    | value COMMA value
/*
 *值
 *分为标识符和数字(这里变量只实现数字)
 */
value   
    :   number
    | declarator
    ;
/*
 *条件表达式
 *拆分成两个，以消除偏移/规约冲突
 */
conditional_expression_list
    :   conditional_expression
    |   conditional_expression logical_operator conditional_expression
conditional_expression
    ;
conditional_expression
    :   arithmetic_expression relational_operator arithmetic_expression 
    |   NOT conditional_expression
    ;
/*算数/位运算符*/
arithmetic_operator
    :   ADD
    |   SUB
    |   MUL
    |   QUO
    |   REM
    |   AND
    |   OR
    |   XOR
    |   SHL
    |   SHR
    |   AND_NOT
    ;
/*逻辑运算符*/
logical_operator
    :   LAND
    |   LOR
    ; 
//NOT是单目运算符比较特殊
/*关系运算符*/
relational_operator
    :   EQL
    |   LSS
    |   GTR
    |   NEQ
    |   LEQ
    |   GEQ
    ;
/*赋值符号*/    
assignmenoperator
    : ASSIGN
    |   ADD_ASSIGN
    |   SUB_ASSIGN
    |   MUL_ASSIGN
    |   QUO_ASSIGN
    |   REM_ASSIGN
    |   AND_ASSIGN
    |   OR_ASSIGN
    |   XOR_ASSIGN
    |   SHL_ASSIGN
    |   SHR_ASSIGN
    |   AND_NOASSIGN
    ;
/*类型*/
type_specifier
    : VOID
    | CHAR
    | SHORT
    | INT
    | LONG
    | FLOAT
    | DOUBLE
    | SIGNED
    | UNSIGNED
    ;
%%
main(int argc,char **argv){
        yyparse();
}
yyerror(char *s)
{
    fprintf(stderr,"error: %s\n",s);
}

flex:

/*
 *file: C-lexical-analyzer.l
 *auther: jin1ming
 *system: manjaro
 */
%option yylineno
%{
#include<stdio.h>
#include<stdlib.h>
#include"C-Parser.tab.h"
extern int yylineno;
%}
/*数字定义*/
/*科学计数表示*/
science {decimal}(\.[0-9]+)?([Ee][-+]?[0-9]+)?
/*十进制*/
decimal 0|[1-9][0-9]*
/*十六进制*/
hexadecimal 0[xX][a-fA-F0-9]+
/*二进制*/
binary 0[bB][01]+
/*八进制*/
octal 0[0-7]+
/*总表示*/
number ({hexadecimal}|{binary}|{science}|{octal})(([uU]?[Ll]?)|([Ll]?[Uu]?)|([fF]?))
/*注意浮点数总是有符号，不需要Uu后缀，所以在接下来单做一个浮点数异常处理*/
/*数字异常处理*/
floatexcption {decimal}\.[0-9]+([Ee]?[-+]?[0-9]+)?[Uu]
excption [0-9][0-9a-zA-Z\.]+

/*关键字*/
AUTO auto 
BREAK break
CASE case
CHAR char
CONST const
CONTINUE continue
DEFAULT default
DO do
DOUBLE double
ELSE else
ENUM enum
EXTERN extern
FLOAT float
FOR for
GOTO goto
IF if
INT int
LONG long 
REGISTER register
RETURN return
SHORT short
SIGNED signed
SIZEOF sizeof
STATIC static
STRUCT struct
SWITCH switch
TYPEDEF typedef
UNSIGNED unsigned
UNION union
VOID void 
VOLATILE volatile
WHILE while

/*注释*/
COMMENT (\/\/.*)|(\/\*(.|\n)*\/)

/*数组*/
array {identifier}\[(0|([1-9][0-9]*))\]

/*标识符定义*/
identifier [a-z_A-Z][a-z_A-Z0-9]*

/*其它字符*/
whitespace [ \t\n\r\f\v]+
errno .
 
 /*运算符*/
 /*算术运算符*/
ADD  \+
SUB  \-
MUL  \*
QUO  \/
REM  %
INC    \+\+
DEC    \-\-
 /*赋值运算符*/
ASSIGN  =
ADD_ASSIGN  \+=
SUB_ASSIGN  \-=
MUL_ASSIGN  \*=
QUO_ASSIGN  \/=
REM_ASSIGN  %=
AND_ASSIGN  \&=
OR_ASSIGN  \|=
XOR_ASSIGN  \^=
SHL_ASSIGN  <<=
SHR_ASSIGN  >>=
AND_NOT_ASSIGN  ~=
 /*位运算符*/
AND      &
OR       \|
XOR      \^
SHL      <<
SHR      >>
AND_NOT  ~
 /*逻辑运算符*/
LAND   &&
LOR    \|\|
NOT    \!
 /*关系运算符*/
EQL     ==
LSS     <
GTR     >
NEQ       !=
LEQ       <=
GEQ       >=
 /*标点符号*/
LPAREN  \(
LBRACK  \[
LBRACE  \{
COMMA   ,
PERIOD  \.
RPAREN     \)
RBRACK     \]
RBRACE     \}
SEMICOLON  ;
COLON      :
POT         \->
DQUA       \"
SQUA       \'
%%
 
 /*关键字*/
{AUTO} {return AUTO;}
{BREAK} {return BREAK;}
{CASE} {return CASE;}
{CHAR} {return CHAR;}
{CONST} {return CONST;}
{CONTINUE} {return CONTINUE;}
{DEFAULT} {return DEFAULT;}
{DO} {return DO;}
{DOUBLE} {return DOUBLE;}
{ELSE} {return ELSE;}
{ENUM} {return ENUM;}
{EXTERN} {return EXTERN;}
{FLOAT} {return FLOAT;}
{FOR} {return FOR;}
{GOTO} {return GOTO;}
{IF} {return IF;}
{INT} {return INT;}
{LONG} {return LONG;}
{REGISTER} {return REGISTER;}
{RETURN} {return RETURN;}
{SHORT} {return SHORT;}
{SIGNED} {return SIGNED;}
{SIZEOF} {return SIZEOF;}
{STATIC} {return STATIC;}
{STRUCT} {return STRUCT;}
{SWITCH} {return SWITCH;}
{TYPEDEF} {return TYPEDEF;}
{UNSIGNED} {return UNSIGNED;}
{UNION} {return UNION;}
{VOID} {return VOID;}
{VOLATILE} {return VOLATILE;}
{WHILE} {return WHILE;}

 /*提前处理浮点数+uU的异常*/
{floatexcption} {printf("Float Execption: %s\n",yytext);} 
 /*数字表示*/
{number} {return number;}
 /*数组*/
{array} {return array;}
 /*异常数字处理*/
{excption} {printf("Number Execption:  %s\n",yytext);}

 /*跳过空白和注释*/
{whitespace} {}
{COMMENT} {}

 /*运算符*/
 /*算术运算符*/
{ADD} {return ADD;}
{SUB} {return SUB;}
{MUL} {return MUL;}
{QUO} {return QUO;}
{REM} {return REM;}
{INC} {return INC;}
{DEC} {return DEC;}
 /*逻辑运算符*/
{LAND} {return LAND;}
{LOR} {return LOR;}
{NOT} {return NOT;}
 /*赋值运算符*/
{ASSIGN} {return ASSIGN;}
{ADD_ASSIGN} {return ADD_ASSIGN;}
{SUB_ASSIGN} {return SUB_ASSIGN;}
{MUL_ASSIGN} {return MUL_ASSIGN;}
{QUO_ASSIGN} {return QUO_ASSIGN;}
{REM_ASSIGN} {return REM_ASSIGN;}
{AND_ASSIGN} {return AND_ASSIGN;}
{OR_ASSIGN} {return OR_ASSIGN;}
{XOR_ASSIGN} {return XOR_ASSIGN;}
{SHL_ASSIGN} {return SHL_ASSIGN;}
{SHR_ASSIGN} {return SHR_ASSIGN;}
{AND_NOT_ASSIGN} {return AND_NOT_ASSIGN;}
 /*位运算符*/
{AND} {return AND;}
{OR} {return OR;}
{XOR} {return XOR;}
{SHL} {return SHL;}
{SHR} {return SHR;}
{AND_NOT} {return AND_NOT;}
 /*关系运算符*/
{EQL} {return EQL;}
{LSS} {return LSS;}
{GTR} {return GTR;}
{NEQ} {return NEQ;}
{LEQ} {return LEQ;}
{GEQ} {return GEQ;}
 /*标点符号*/
{LPAREN} {return LPAREN;}
{LBRACK} {return LBRACK;}
{LBRACE} {return LBRACE;}
{COMMA} {return COMMA;}
{PERIOD} {return PERIOD;}
{RPAREN} {return RPAREN;}
{RBRACK} {return RBRAEN;}
{RBRACE} {return RBRACE;}
{SEMICOLON} {return SEMICOLON;}
{COLON} {return COLON;}
{POT} {return POT;}
{DQUA} {return DQUA;}
{SQUA} {return SQUA;}


{identifier} {return identifier;}

{errno} {fprintf(stderr,"Mystery character:  %s\n",yytext);}
%%
%%

一个真正的语法分析器离不开符号表，如果有时间我将加入符号表到语法分析器中，符号表设计思路：
符号表应该包括：变量符号表、函数符号表、数组符号表、结构体符号表
(1) 变量符号表应该包括：类型、变量名、作用域、指针
(之前我觉得应该使用union保存值，现在认为并不需要保存)
(2) 函数符号表应该包括：函数名、函数类型、返回值类型、形参个数、指针(考虑函数指针)
(3) 数组符号表应该包括：数组名、数组类型、指针
(4) 结构体符号表应该包括：结构体名、指针，以及用一个变量符号表链表来保存结构体成员变量。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 219,366评论 6赞 508
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,521评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 165,689评论 0赞 356
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,925评论 1赞 295
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,942评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,727评论 1赞 305
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,447评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,349评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,820评论 1赞 317
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,990评论 3赞 337
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,127评论 1赞 351
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,812评论 5赞 346
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,471评论 3赞 331
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,017评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,142评论 1赞 272
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,388评论 3赞 373
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,066评论 2赞 355