学习制作一门有趣的编程语言－0x03

分析一个C语言的Lex & Yacc 程序

博客地址： http://lfkdsk.github.io
代码地址： https://github.com/lfkdsk/CodeParse

本节我们来分析一个能匹配C语言的Lex & Yacc 程序

Lex文件:http://www.lysator.liu.se/c/ANSI-C-grammar-l.html

Yacc文件:http://www.lysator.liu.se/c/ANSI-C-grammar-y.html

也可以直接在我的github代码地址中进行下载。

先来分析Lex文件

D			[0-9]
L			[a-zA-Z_]
H			[a-fA-F0-9]
E			[Ee][+-]?{D}+
FS			(f|F|l|L)
IS			(u|U|l|L)*

首先定义了一些正则式，这些正则的功能都是一目了然的。他们都不是完整的功能性的定义，而是为了下文组装方便的。其中FS \ IS 的作用是在数字跟在后面的尾缀（浮点型、无符号、长整形之类的）。

"/*"			{ comment(); }

第16行匹配了C语言的注释开始，并且调用了comment()函数。

comment()
{
	char c, c1;

loop:
	while ((c = input()) != '*' && c != 0)
		putchar(c);

	if ((c1 = input()) != '/' && c != 0)
	{
		unput(c1);
		goto loop;
	}

	if (c != 0)
		putchar(c1);
}

comment()函数只做了一件事就是找到这个注释的结尾以判断这真的是一个注释，因为是注释，函数没有返回值，lex里面也没有对应的调用。

"auto"			{ count(); return(AUTO); }
"break"			{ count(); return(BREAK); }
"case"			{ count(); return(CASE); }
"char"			{ count(); return(CHAR); }
"const"			{ count(); return(CONST); }
...

18-49行定义了C语言的内置关键字他们都调用了一个count()返回了一个对应的Token。

int column = 0;

void count()
{
	int i;

	for (i = 0; yytext[i] != '\0'; i++)
		if (yytext[i] == '\n')
			column = 0;
		else if (yytext[i] == '\t')
			column += 8 - (column % 8);
		else
			column++;

	ECHO;
}

这段函数在每次匹配之后记录了当前行中的具体位置(每当\n时换行\t时计算位置)。

ECHO是一段宏：

/* Copy whatever the last rule matched to the standard output. */
#ifndef ECHO
/* This used to be an fputs(), but since the string might contain NUL's,
 * we now use fwrite().
 */
#define ECHO fwrite( yytext, yyleng, 1, yyout )
#endif

51-62一些类型匹配：

// 这是C中变量名的定义
{L}({L}|{D})*		{ count(); return(check_type()); }
// 16进制数
0[xX]{H}+{IS}?		{ count(); return(CONSTANT); }
// 各种数字
0{D}+{IS}?		{ count(); return(CONSTANT); }
{D}+{IS}?		{ count(); return(CONSTANT); }
// 字符
L?'(\\.|[^\\'])+'	{ count(); return(CONSTANT); }
// 科学计数法
{D}+{E}{FS}?		{ count(); return(CONSTANT); }
{D}*"."{D}+({E})?{FS}?	{ count(); return(CONSTANT); }
{D}+"."{D}*({E})?{FS}?	{ count(); return(CONSTANT); }
// 字符串
L?\"(\\.|[^\\"])*\"	{ count(); return(STRING_LITERAL); }

check_type()中对类型进行检查。

Lex就只有这么多了。

再来分析Yacc文件

%token IDENTIFIER CONSTANT STRING_LITERAL SIZEOF
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN TYPE_NAME

%token TYPEDEF EXTERN STATIC AUTO REGISTER
%token CHAR SHORT INT LONG SIGNED UNSIGNED FLOAT DOUBLE CONST VOLATILE VOID
%token STRUCT UNION ENUM ELLIPSIS

%token CASE DEFAULT IF ELSE LOWER_THAN_ELSE SWITCH WHILE DO FOR GOTO CONTINUE BREAK RETURN

%start translation_unit

%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE

这里我们定义了一些关键字的Token，重点看最后两行LOWER_THAN_ELSE 和ELSE分别代表了两种的ELSE的优先级，用于处理ELSE常见的悬空冲突问题。

接下来我们看看yacc文件中的BNF式都是怎么写的。

primary_expression
	: IDENTIFIER
	| CONSTANT
	| STRING_LITERAL
	| '(' expression ')'
	;

最小的子集由ID，常量，字符串，还有括号覆盖的表达式构成。

postfix_expression
	: primary_expression
	| postfix_expression '[' expression ']'
	| postfix_expression '(' ')'
	| postfix_expression '(' argument_expression_list ')'
	| postfix_expression '.' IDENTIFIER
	| postfix_expression PTR_OP IDENTIFIER
	| postfix_expression INC_OP
	| postfix_expression DEC_OP
	;

这个指出了postfix_expression可以代表数组，函数调用，带参数的函数调用，.表达式，->指针，++,–。

argument_expression_list
	: assignment_expression
	| argument_expression_list ',' assignment_expression
	;

unary_expression
	: postfix_expression
	| INC_OP unary_expression
	| DEC_OP unary_expression
	| unary_operator cast_expression
	| SIZEOF unary_expression
	| SIZEOF '(' type_name ')'
	;

参数表达式列表由多个’,‘和assignment_expression组成，其实就是函数的多个传参。

一元表达式包含之前的postfix还有前置的++, –。还有就是对一个东西求sizeof也是。

unary_operator
	: '&'
	| '*'
	| '+'
	| '-'
	| '~'
	| '!'
	;

一元运算符。

cast_expression
	: unary_expression
	| '(' type_name ')' cast_expression
	;

multiplicative_expression
	: cast_expression
	| multiplicative_expression '*' cast_expression
	| multiplicative_expression '/' cast_expression
	| multiplicative_expression '%' cast_expression
	;

additive_expression
	: multiplicative_expression
	| additive_expression '+' multiplicative_expression
	| additive_expression '-' multiplicative_expression
	;

cast_expression:强制类型转换

multiplicative_expression/additive_expression:区分这五种运算的优先级。

shift_expression
	: additive_expression
	| shift_expression LEFT_OP additive_expression
	| shift_expression RIGHT_OP additive_expression
	;

relational_expression
	: shift_expression
	| relational_expression '<' shift_expression
	| relational_expression '>' shift_expression
	| relational_expression LE_OP shift_expression
	| relational_expression GE_OP shift_expression
	;

equality_expression
	: relational_expression
	| equality_expression EQ_OP relational_expression
	| equality_expression NE_OP relational_expression
	;

shift->位运算 ；relational_expression 处理比较；equality_expression 处理相等关系。

and_expression
	: equality_expression
	| and_expression '&' equality_expression
	;

exclusive_or_expression
	: and_expression
	| exclusive_or_expression '^' and_expression
	;

inclusive_or_expression
	: exclusive_or_expression
	| inclusive_or_expression '|' exclusive_or_expression
	;

logical_and_expression
	: inclusive_or_expression
	| logical_and_expression AND_OP inclusive_or_expression
	;

logical_or_expression
	: logical_and_expression
	| logical_or_expression OR_OP logical_and_expression
	;

conditional_expression
	: logical_or_expression
	| logical_or_expression '?' expression ':' conditional_expression
	;

下面是几种逻辑运算符的匹配关系，还有三目运算符。

assignment_expression
	: conditional_expression
	| unary_expression assignment_operator assignment_expression
	;

assignment_operator
	: '='
	| MUL_ASSIGN
	| DIV_ASSIGN
	| MOD_ASSIGN
	| ADD_ASSIGN
	| SUB_ASSIGN
	| LEFT_ASSIGN
	| RIGHT_ASSIGN
	| AND_ASSIGN
	| XOR_ASSIGN
	| OR_ASSIGN
	;

expression
	: assignment_expression
	| expression ',' assignment_expression
	;

constant_expression
	: conditional_expression
	;

declaration
	: declaration_specifiers ';'
	| declaration_specifiers init_declarator_list ';'
	;

declaration_specifiers
	: storage_class_specifier
	| storage_class_specifier declaration_specifiers
	| type_specifier
	| type_specifier declaration_specifiers
	| type_qualifier
	| type_qualifier declaration_specifiers
	;

assignment_operator 指定了一类缩略形式，诸如：/= *= += -=之类的。

declaration 添加了‘;’

declaration_specifiers定义了类型的声明。

init_declarator_list
	: init_declarator
	| init_declarator_list ',' init_declarator
	;

init_declarator
	: declarator
	| declarator '=' initializer
	;

storage_class_specifier
	: TYPEDEF
	| EXTERN
	| STATIC
	| AUTO
	| REGISTER
	;

storage_class_specifier 定义了几种类型。init_declarator完成了初始化。

init_declarator_list ‘,’ init_declarator 是在对于多个同类型的参数的初始化。

type_specifier
	: VOID
	| CHAR
	| SHORT
	| INT
	| LONG
	| FLOAT
	| DOUBLE
	| SIGNED
	| UNSIGNED
	| struct_or_union_specifier
	| enum_specifier
	| TYPE_NAME
	;

struct_or_union_specifier
	: struct_or_union IDENTIFIER '{' struct_declaration_list '}'
	| struct_or_union '{' struct_declaration_list '}'
	| struct_or_union IDENTIFIER
	;

struct_or_union
	: STRUCT
	| UNION
	;

type_specifier 中定义了很多的数据类型。struct_or_union是结构体和联合的定义。

struct_or_union_specifier 给出了对结构体的定义。

struct_declaration_list
	: struct_declaration
	| struct_declaration_list struct_declaration
	;

struct_declaration
	: specifier_qualifier_list struct_declarator_list ';'
	;

specifier_qualifier_list
	: type_specifier specifier_qualifier_list
	| type_specifier
	| type_qualifier specifier_qualifier_list
	| type_qualifier
	;

继续给出了一些结构体的申请。

struct_declarator_list
	: struct_declarator
	| struct_declarator_list ',' struct_declarator
	;

struct_declarator
	: declarator
	| ':' constant_expression
	| declarator ':' constant_expression
	;

enum_specifier
	: ENUM '{' enumerator_list '}'
	| ENUM IDENTIFIER '{' enumerator_list '}'
	| ENUM IDENTIFIER
	;

enumerator_list
	: enumerator
	| enumerator_list ',' enumerator
	;

enumerator
	: IDENTIFIER
	| IDENTIFIER '=' constant_expression
	;

struct_declarator_list 是多个结构体的申请过程。

struct_declarator 结构体的声明符。

constant_expression 指向了一些逻辑表达式。

enum_specifier 定义了联合的声明，同样list就是多个同类型的声明，emumerator是对结构体的初始化。

type_qualifier
	: CONST
	| VOLATILE
	;

declarator
	: pointer direct_declarator
	| direct_declarator
	;

direct_declarator
	: IDENTIFIER
	| '(' declarator ')'
	| direct_declarator '[' constant_expression ']'
	| direct_declarator '[' ']'
	| direct_declarator '(' parameter_type_list ')'
	| direct_declarator '(' identifier_list ')'
	| direct_declarator '(' ')'
	;

type_qualifier 定义了const 和 volatile 关键字。

declarator 声明符指向了指针类型和基础类型。

direct_declarator 直接声明符，包含了数组、带参数的函数返回值，等等等。

pointer 指针类型。

pointer
	: '*'
	| '*' type_qualifier_list
	| '*' pointer
	| '*' type_qualifier_list pointer
	;

type_qualifier_list
	: type_qualifier
	| type_qualifier_list type_qualifier
	;


parameter_type_list
	: parameter_list
	| parameter_list ',' ELLIPSIS
	;

pointer 指明了几种指针的书写方式。

parameter_type_list 代表参数列表。

		/* 这里的无else的优先级是低于由else 的 */
selection_statement
	: IF '(' expression ')' statement %prec LOWER_THAN_ELSE
	| IF '(' expression ')' statement ELSE statement
	| SWITCH '(' expression ')' statement
	;

其余的只有这里值得注意一下，这里出现了著名的ELSE悬空的移进规约bug，所以使用了一个优先级低于ELSE的LOWER_THAN_ELSE来指定优先级。