编程语言 on lfkdsk's Blog

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

Sat, 25 Jun 2016 22:33:35 +0000

几种常用算法

我们日常会用正则表达式的时候，我们会发现正则表达式用了非常精简的语法就能概括多种输入串的特征，

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

Wed, 01 Jun 2016 22:28:06 +0000

分析一个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。

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

Wed, 01 Jun 2016 12:13:17 +0000

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

为计算器添加一些新功能

本节代码：CalcWithTable

上次我们使用Lex & Yacc制作了一个能够处理优先级的计算器，其中的优先级的设定是通过修改文法，将优先级提升，这次重写这个计算器并添加一些新的功能。

先看Lex文件


%{

#include "y.tab.h"
#include <math.h>
#include "link_list.h"

%}

%%
	/* 这段正则和之前都有所不同 明显的增加了对于科学技术法的支持 */
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
		 /* 转换为double类型 */
 yylval.dval = atof(yytext);
 /* 我把它打印出来 */
 printf("number : %s \n", yytext);
 return NUMBER;
 }

[ \t] ;

	/* 这里提供了对于字母和字母组合的识别 这是对于变量名的识别匹配 */
[A-Za-z][A-Za-z0-9]* {
		 /* addNode(char *)是link_list.c中的函数 将变量名和对应的参数存储在一个链表中 */
		 /* 返回值为对应的指针 */
 yylval.name = addNode(yytext);
 printLink();
 /* 返回的Token指变量名 */
 return NAME;
 }

"$" {
 return 0;
 }

\n |

. {
 return yytext[0];
 }

%%

这段代码和之前的区别不大，但是我们明显的为它增加了一个功能，就是识别变量名。

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

Fri, 27 May 2016 08:37:20 +0000

熟悉一下Lex 和 Yacc的用法

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

tips：阅读此篇需要一定的C语言基础和正则表达式的知识

首先上一篇提到了第一步的工作是要使用 Lex 和 Yacc 进行编写，所以说第一步首先简单的学习一下 Lex & Yacc 的用法，Lex & Yacc 是一套很古老的编译生成套件，大约在上个世纪80年代就有了。但是并不过时，我们今天生成编译程序仍然能够用得上。Lex & Yacc 如果简单的概括来说，Lex 负责词法分析，就是把输入串的纯字符转化为 词法记号流，而 Yacc 负责语法分析，将词法记号流处理成一种树形结构，叫做语法分析树的数据结构中。至此简单来讲的前端工作就基本完成了，代码就有机会被转换成一种三地址代码的形式，经过优化器的优化生成机器指令就可以运行在机器中了。

词法记号：一般被称作Token，是指对于输入串的内容进行词素分类，比如说数字、字符串、保留字（关键字）、保留字之间还有不同的 Token

三地址代码：一些语言转换机制的中间形式，每行代码只有三个对象（两个运算分量、一个操作符组成），转换这种形式能够便于机器指令的生成。

刚才说了这么多那Lex & Yacc帮我们做了什么呢？答案是在我们代码的辅助下几乎都做了，首先在前端方面，根据Lex & Yacc 进行了词法和语法分析，在后端代码被直接生成了C语言代码，借助C语言优秀的编译链可以轻松的生成的程序。

具体使用

上面我们介绍了Lex & Yacc的功能，毫无疑问Lex & Yacc是非常完美的编译生成程序，接下来我们来介绍一下Lex & Yacc的用法。

推荐书籍:O’Relly出版的 Lex & Yacc 是一本介绍 Lex 和 Yacc功能非常好的书，1994年出版，我在图书馆淘到了2002年的第二版。

Lex:

Lex的使用方法如图所示，分为三个区域：

定义部分：和普通的C语言程序区别不大，存放定义，和在接下来Lex生成的程序中使用的变量和方法的导入。
规则部分：规则部分起始于"%%“符号，终止于”%%“符号，通过书写正规式匹配文法符号，其中使用C程序处理匹配内容，接收到的符号保存在yytext[]中。
子程序部分：最后一个%%后面的内容是用户子程序部分，可以包含用C语言编写的子程序，而这些子程序可以用在前面的动作中，这样就可以达到简化编程的目的。这里需要注意的是，当编译时不带-ll选项时，是必须加入main函数和yywrap（见后文）。

只说概念不太直观，我们来写一段程序来试验一下，这个程序我们只用到了Lex。

1.首先是定义区：

#include <stdio.h>
unsigned charCount = 0, wordCount = 0, lineCount = 0;

%}

/* 这里是一个替换的规则 */
/* 不是 空格、制表符、换行符的非空内容 */
word [^ \t\n]+
eol \n

这部分很简单我们导入来C的基础输入输出库，定义了几个全局变量字符数，单词数、行数。定义了两个规则，第一个代表单词（所有空格、制表符、换行符取反的非空集），一个是输入结束匹配换行符。 2.规则区：