MyLisp项目日志：解析用户输入与波兰表达式

项目
2.5k words

编程语言

编程语言是类似于自然语言的，虽然我们是自然而然就学会了自己的母语，但实际上自然语言是建立在递归和重复的子结构之上的

在语文的学习过程中我们会学到一些语法，例如名词、动词、谓语、连词

他的结构体现在，例如谓语可以是形容词，是动词，是副词加动词

他的递归体现在，主语可以是名词，可以是形容词加名词，甚至是一个句子，再由这个主语去构成另一个句子

这些说白了是一种有限的规则，而由这些优先的规则延申出来的就是无限的句子

为了定义我们的编程语言（MyLisp），我们首先需要正确解析用户按照语法规则写的代码，因此我们就需要编写一个语法解析器，用于判断用户的输入是否合法，并且产生解析后的内部表示

但是这一步十分繁琐且枯燥，我们使用mpc库来帮助我们完成这个工作，这个库是一个解析器组合子库，可以为任何语言编写语法解析器，他极大的简化了原本枯燥无聊的工作，仅仅编写高层的抽象语法规则即可

mpc库的项目地址，非常感谢Daniel Holden大佬！！

模拟自然语言

下面我们将使用mpc的一些函数，尝试描述英语的部分语法，熟悉mpc的使用步骤，更多的函数请移步项目主页

我们只采用最基础的语法，以后如果想完善的话只需要添加规则即可

大致规则框架是这样的

  • 句子（Sentence）包括一系列短语（Phrase）
  • 短语（Phrase）由形容词（Adjective）和名词（Noun）构成
  • 名词（Noun）包括以下几个符号：lisp，language，c，book，build
  • 形容词（Adjective）包括以下几个符号：many，so，much

那我们就需要讲上述描述使用mpc库中的函数写出来，这样就能构建出一个解析系统了，只要满足上面的语法规则，我们就可以进行解析

定义名词和形容词

我们需要创建两个解析器，类型是mpc_parser_t*，分别命名为Noun和Adjective，作为两个变量

再使用mpc_or函数表示创建一个解析器，返回值是解析器，参数是解析的符号（单词），而这些单词之间是或的关系，只要出现一个即可，使用mpc_sym函数，他会将字符串转换为符号（语句）

写成代码就是下面的样子

1
2
3
4
5
6
7
8
9
// 建立名词解析器
mpc_parser_t* Noun = mpc_or(4,
    mpc_sym("lisp"), mpc_sym("language"),
    mpc_sym("c"), mpc_sym("book"),
	mpc_sym("build"));

// 建立形容词解析器
mpc_parser_t* Adjective = mpc_or(3,
	mpc_sym("many"), mpc_sym("so"), mpc_sym("much"));

定义短语

接下来我们就要使用名词解析器和形容词解析器来构造短语解析器

同理我们直接使用mpc_and函数即可，然后我们再用mpcf_strfold和free指定各个语句的组织和删除方式，暂时先忽略他们

1
mpc_parser_t* Phrase = mpc_and(2, mpcf_strfold, Adjective, Noun, free);

定义句子

句子是由多个短语构成的，我们使用mpc_many函数即可

1
mpc_parser_t* Sentence = mpc_many(mpcf_strfold, Phrase);

简化模拟过程

mpc有一个mpca_lang函数可以简化这个编写的过程，不用再重复的写许多mpc_sym函数，而是允许我们直接用字符串来表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
mpc_parser_t* Adjective = mpc_new("adjective");
mpc_parser_t* Noun = mpc_new("noun");
mpc_parser_t* Phrase = mpc_new("phrase");
mpc_parser_t* Sentence = mpc_new("sentence");

mpca_lang(MPCA_LANG_DEFAULT,
  "                                           \
    adjective : \"such\" | \"many\"           \
              |  \"so\";                      \
    noun      : \"lisp\" | \"language\"       \
              | \"book\" | \"build\" | \"c\"; \
    phrase    : <adjective> <noun>;           \
    sentence      : <phrase>*;                \
  ",
  Adjective, Noun, Phrase, Sentence);

mpc_cleanup(4, Adjective, Noun, Phrase, Sentence);

那整个定义解析的过程就可以分成三步

  1. mpc_new定义语法规则的名字
  2. mpca_lang定义具体的连接规则
  3. mpc_cleanup清理

字符串中有一些要求，一个字符串可以有很多语法规则，每一个语法规则分为左右两部分，左边是名称，右边是具体的内容，两项之间用竖划线分割开，使用分号作为标记结尾，需要注意的是，在这里我们只想使用字符串含义的双引号，因此要使用转义字符

正则表达式

我们当然可以使用字符串来表示语法，但是这样的输入始终是有限的，还有一些我们无法表达的开始输入，结束输入，可选字符，可选范围

这时候就需要我们使用正则表达式（Regular Expression）来定义，他是一直小型的语法规则，可以用于表达整数，浮点数等一些简单的规则

他的具体规则如下

语法表示 作用
. 要求任意字符
a 要求字符 a
[abcdef] 要求 abcdef 中的任意一个
[a-f] 要求按照字母顺序，a 到 f 中的任意一个
a? 要求 a 字符或什么都没有，即 a 为可选的
a* 要求有 0 个或多个字符 a
a+ 要求有 1 个或多个字符 a
^ 开始输入
$ 结束输入

上面是一些我们会用到的规则，具体的完整教程仍需要额外学习

在这里，我们需要将正则表达式放在一对/中

例如，整数的表达/-?[0-9]+/

波兰表达式及其解析

这里我们将会使用上面学习的内容和mpc库实现一个简单的波兰表达式的解析器

波兰表达式

波兰表达式也称之为前缀表达式，是一种数学标记语言，简单说就是他的运算符在操作数的前面

例如

普通表达式 波兰表达式
1 + 2 + 6 + 1 2 6
6 + (2 * 9) + 6 (* 2 9)
(10 * 2) / (4 + 2) / (* 10 2) (+ 4 2)

语法描述

我们可以直观的从表格中提取一些信息，一共有三类符号，操作符，数字，括号

我们可以细看括号内的部分，其实也就是表达式，而这一个整体也可以看作一个表达式

因此我们可以递归下去，得出以下规则

  1. 一个程序（波兰表达式）由一个操作符加上一个或多个表达式构成
  2. 一个表达式又由操作符加上数字或者表达式构成

具体下来就是这样的

名称 定义
程序(Program) 开始输入 –> 操作符 –> 一个或多个表达式(Expression) –> 结束输入
表达式(Expression) 数字、左括号 (、操作符 –> 一个或多个表达式 –> 右括号 )
操作符(Operator) '+'、'-'、'*' 、 '/'
数字(Number) 可选的负号 - –> 一个或多个 0 到 9 之间的字符

当然我们可以将这个操作符和数字做扩展，例如支持取模操作，最大最小值操作，数字加上浮点数，都是可以的

波兰表达式语法解析

接下来我们将使用mpc描述上面的语法规则，这里我直接加上了其他的操作符，包含了浮点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 创建解析器
mpc_parser_t* Number = mpc_new("number");
mpc_parser_t* Operator = mpc_new("operator");
mpc_parser_t* Expr = mpc_new("expr");
mpc_parser_t* MyLisp = mpc_new("mylisp");

// 定义
	mpca_lang(MPCA_LANG_DEFAULT,
		"                                                              \
		 number   : /-?[0-9]+(\\.[0-9]*)?/ ;                           \
		 operator : '+' | '-' | '*' | '/' | '%' | /add|sub|mul|div/ ;  \
		 expr     : <number> | '(' <operator> <expr>+ ')' ;            \
		 lispy    : /^/ <operator> <expr>+ /$/ ;                       \
		",
		Number, Operator, Expr, MyLisp);

mpc_cleanup(4, Number, Operator, Expr, MyLisp);

解析用户输入

这里我们先只进行语法解析，下一篇会进行表达式的计算

我们调用mpc_parse函数，将MyLisp解析器和用户输入input作为参数，将他的解析结果保存到ret中，如果解析成功，返回值为1，失败为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 尝试分析用户输入
mpc_result_t r;
if (mpc_parse("<stdin>", input, MyLisp, &r))
{
	// 成功打印AST
	mpc_ast_print(r.output);
	mpc_ast_delete(r.output);
}
else
{
	// 其他打印失败的情况
	mpc_err_print(r.error);
	mpc_err_delete(r.error);
}

当解析成功，则会打印出AST（抽象语法树），这个东西不好解释，但是我们可以通过输出大致看出来语法之间的关系

当解析失败就会输出报错的信息

例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
MyLisp Version 0.0.2
By jasmine-leaf
Press Ctrl+c to Exit

MyLisp> + 1 1
>
  regex
  operator|char:1:1 '+'
  expr|number|regex:1:3 '1'
  expr|number|regex:1:5 '1'
  regex
MyLisp> * 1 ( % 2 2 )
>
  regex
  operator|char:1:1 '*'
  expr|number|regex:1:3 '1'
  expr|>
    char:1:5 '('
    operator|char:1:7 '%'
    expr|number|regex:1:9 '2'
    expr|number|regex:1:11 '2'
    char:1:13 ')'
  regex
MyLisp> / 1.1 5
>
  regex
  operator|char:1:1 '/'
  expr|number|regex:1:3 '1.1'
  expr|number|regex:1:7 '5'
  regex
MyLisp> hello
<stdin>:1:1: error: expected '+', '-', '*', '/', '%', 'a', 's', 'm' or 'd' at 'h'
MyLisp> 1jas
<stdin>:1:1: error: expected '+', '-', '*', '/', '%', 'a', 's', 'm' or 'd' at '1'
MyLisp> add 2 ( mul 2 2)
>
  regex
  operator|regex:1:1 'add'
  expr|number|regex:1:5 '2'
  expr|>
    char:1:7 '('
    operator|regex:1:9 'mul'
    expr|number|regex:1:13 '2'
    expr|number|regex:1:15 '2'
    char:1:16 ')'
  regex
MyLisp>

v0.0.2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h> 
#include<stdlib.h>
#include"mpc.h"
void PrintPrompt()
{
	// printf("MyLisp Version 0.0.1\n");
	printf("MyLisp Version 0.0.2\n");
	printf("By jasmine-leaf\n");
	printf("Press Ctrl+c to Exit\n\n\n");
}
// v0.0.1
// 实现了用户输入和读取功能
// v0.0.2
// 增加了波兰表达式的解析功能

#ifdef _WIN32 

// 为实现跨平台功能
// 在windows平台下定义实现editline和history的同名函数

#define INPUT_MAX 2048 // 缓冲区最大值

#include<string.h>
static char Buffer[INPUT_MAX]; // Buffer输入缓冲区


char* readline(char* prompt) // 模拟实现readline
{
	fputs(prompt, stdout);
	fgets(Buffer, INPUT_MAX, stdin);


	char* tmp = malloc(strlen(Buffer) + 1);
	if (tmp != NULL)
	{
		strcpy(tmp, Buffer);
		tmp[strlen(tmp) - 1] = '\0';
	}
	return tmp;
}

void add_history(char* unused)
{}

#else
#ifdef __linux__ // 在linux平台下
#include<editline/readline.h>
#include<editline.history.h>
#endif

#ifdef __MACH__ // 在mac平台下
#include<editline/readline.h>
#endif
#endif 

void Lisp()
{
	// 创建解析器
	mpc_parser_t* Number = mpc_new("number");
	mpc_parser_t* Operator = mpc_new("operator");
	mpc_parser_t* Expr = mpc_new("expr");
	mpc_parser_t* MyLisp = mpc_new("mylisp");

	// 定义
	mpca_lang(MPCA_LANG_DEFAULT,
		"                                                              \
		 number   : /-?[0-9]+(\\.[0-9]*)?/ ;                           \
		 operator : '+' | '-' | '*' | '/' | '%' | /add|sub|mul|div/ ;  \
		 expr     : <number> | '(' <operator> <expr>+ ')' ;            \
		 lispy    : /^/ <operator> <expr>+ /$/ ;                       \
		",
		Number, Operator, Expr, MyLisp);

	while (1)
	{
		char* input = readline("MyLisp> ");
		add_history(input);

		// 尝试分析用户输入
		mpc_result_t r;
		if (mpc_parse("<stdin>", input, MyLisp, &r))
		{
			// 成功打印AST
			mpc_ast_print(r.output);
			mpc_ast_delete(r.output);
		}
		else
		{
			// 其他打印失败的情况
			mpc_err_print(r.error);
			mpc_err_delete(r.error);
		}

		free(input); // 释放在readline中malloc的空间
	}

	mpc_cleanup(4, Number, Operator, Expr, MyLisp);
}

int main()
{
	PrintPrompt();
	Lisp();
	return 0;
}
Comments