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

编程语言

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

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

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

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

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

为了定义我们的编程语言（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函数，他会将字符串转换为符号（语句）

写成代码就是下面的样子

// 建立名词解析器
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指定各个语句的组织和删除方式，暂时先忽略他们

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

定义句子

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

mpc_parser_t* Sentence = mpc_many(mpcf_strfold, Phrase);

简化模拟过程

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

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描述上面的语法规则，这里我直接加上了其他的操作符，包含了浮点数

// 创建解析器
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

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

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

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

例如

MyLisp Version 0.0.2
By jasmine-leaf
Press Ctrl+c to ExitMyLisp> + 1 1
>regexoperator|char:1:1 '+'expr|number|regex:1:3 '1'expr|number|regex:1:5 '1'regex
MyLisp> * 1 ( % 2 2 )
>regexoperator|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
>regexoperator|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)
>regexoperator|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

#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)){// 成功打印ASTmpc_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;
}