微信网站域名备案成功后怎么做站长工具网
文章目录
- 编程语言
- 模拟自然语言
- 定义名词和形容词
- 定义短语
- 定义句子
- 简化模拟过程
- 正则表达式
- 波兰表达式及其解析
- 波兰表达式
- 语法描述
- 波兰表达式语法解析
- 解析用户输入
- v0.0.2
编程语言
编程语言是类似于自然语言的，虽然我们是自然而然就学会了自己的母语，但实际上自然语言是建立在递归和重复的子结构之上的
在语文的学习过程中我们会学到一些语法，例如名词、动词、谓语、连词
他的结构体现在，例如谓语可以是形容词，是动词，是副词加动词
他的递归体现在，主语可以是名词，可以是形容词加名词，甚至是一个句子，再由这个主语去构成另一个句子
这些说白了是一种有限的规则，而由这些优先的规则延申出来的就是无限的句子
为了定义我们的编程语言（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);
那整个定义解析的过程就可以分成三步
- mpc_new定义语法规则的名字
- mpca_lang定义具体的连接规则
- 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) |
语法描述
我们可以直观的从表格中提取一些信息，一共有三类符号，操作符，数字，括号
我们可以细看括号内的部分，其实也就是表达式，而这一个整体也可以看作一个表达式
因此我们可以递归下去，得出以下规则
- 一个程序（波兰表达式）由一个操作符加上一个或多个表达式构成
- 一个表达式又由操作符加上数字或者表达式构成
具体下来就是这样的
| 名称 | 定义 |
|---|---|
程序(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;
}