【Suatin】不学编译原理就制作语言6——语法树引入逻辑运算和关键字方法-白红宇

【Suatin】不学编译原理就制作语言6——语法树引入逻辑运算和关键字方法

阅读量：722 次

发布时间：2019-03-21

本文共 7623 字，大约阅读时间需要 25 分钟。

前言

三千行代码，写了个寂寞。

做了这么几个项目，一直都在操作语法树，我也不知道怎样才写的好，之前的任务都完成了是因为复杂的我都跳过了（汗）多亏了VS的调试很强大，懂得使用SHIFT+F9的才能熟练掌握C++内存管理（误）。

之前的判断运算我取了巧，让判断式只能有一个判断符，一般是没问题的，但是引入逻辑运算就有问题了！一个表达式（无赋值）可以出现多个判断符、多个逻辑符、五则运算、字符串、判断符和逻辑符混在一起这些情况都要考虑清楚——现在还没到要转方向的时候，一点点摸索着！！！

改进字符串拼接

之前都字符串拼接模式，是在completedName_flag为真，即定义了变量之后，碰见的第一个Token是Str时设置的。并且字符串拼接模式下，不能除了加号和字符串本身，不能有其他符号在字符串拼接的表达式中！

改进之后，1.允许定义变量后的第一个Token是Id，当此Id是字符串类型时，设置表达式为字符串拼接模式。

2.字符串拼接模式下的表达式可以有类型为字符串的Id存在！

void Parser::DealToken_Id(int& _t) {
   		if (exprType == ExprType_StringConnect) {
   			/*即出现了这种情况："xxx"+a				其中a是字符串类型				       +           ->             +				    /    \                      /   \		    	"xxx"      None             "xxx"    a			*/			if (expTmp == NULL) {
    //不存在待处理的节点				ThrowException
   
    ("[Id] string connect expression wrong");				return;			}            //字符串拼接模式，不处理非Str类型的id			if (SuatinEnv[global_infix[_t]->name]->type != SuatinIDType_string) {
   				return;			}			SymbolExpr* node_tmp = dynamic_cast
    
     (expTmp);			node_tmp->SetRight(new IDExpr(global_infix[_t]->name));			expTmp = NULL;			return;		}		//处理关键字		if (global_infix[_t]->k_type != SuatinKeyWordType_NOT_KEYWORD) {
   			(this->*k_funcMap[global_infix[_t]->k_type])(_t);			return;		}		//存在待处理的节点		if (expTmp) {
   			if (typeid(*(expTmp->GetClassType())) == typeid(LLeftExpr)) {
   //待处理节点是左括号节点				LLeftExpr* node_tmp = dynamic_cast
     
      (expTmp);				node_tmp->SetContent(new IDExpr(global_infix[_t]->name));			}			else {
   				SymbolExpr* node_tmp = dynamic_cast
      
       (expTmp);				node_tmp->SetRight(new IDExpr(global_infix[_t]->name));				expTmp = expTmpLeft;//上移待处理节点的指针			}			return;		}				//不存在待处理的节点		exprRoot = new IDExpr(global_infix[_t]->name);				//检查一下，表达式的开头第一个id的类型，如果是字符串类型就转变表达式类型为字符串拼接模式		if (firstId_is_string_flag) {
   			if (SuatinEnv[global_infix[_t]->name]->type == SuatinIDType_string) {
   				exprType = ExprType_StringConnect;				firstId_is_string_flag = false;			}		}	}

解释器的类

目前24个类，类多不多到是无所谓，只是代码是真的乱！！！

Parser类

这次多加了二十多个函数，用来处理关键字！在进行词法分析的时候，关键字和变量我都当成是标识符，在遍历中缀表达式时，遇到Id会进入DealToken_Id函数，在其中判断是否是关键字并进入对应函数！

#pragma once#ifndef _PARSER_H_#define _PARSER_H_#include"Expr.h"namespace sua {
   	//成员函数指针，如果不加上Parser::修饰，就只能把对应的成员函数都改成静态的！！！	class Parser;	typedef void(Parser::*DealFuncPtr)(int&);	//语法解析器	class Parser {
   	private:		//处理Token的函数		void DealToken_Num(int& _t);		void DealToken_Id(int& _t);		void DealToken_Str(int& _t);		void DealToken_Pow(int& _t);		void DealToken_Mul(int& _t);		void DealToken_Div(int& _t);		void DealToken_Add(int& _t);		void DealToken_Sub(int& _t);		void DealToken_Gre(int& _t);		void DealToken_GreEq(int& _t);		void DealToken_Les(int& _t);		void DealToken_LesEq(int& _t);		void DealToken_Neq(int& _t);		void DealToken_EqEq(int& _t);		void DealToken_Eq(int& _t);		void DealToken_Com(int& _t);		void DealToken_ML(int& _t);		void DealToken_MR(int& _t);		void DealToken_LL(int& _t);		void DealToken_LR(int& _t);		void DealToken_BL(int& _t);		void DealToken_BR(int& _t);		void DealToken_Dot(int& _t);		void DealToken_Sem(int& _t);		//void DealToken_Eol(int& _t);				//处理关键字的函数		void Deal_k_if(int& _t);		void Deal_k_elif(int& _t);		void Deal_k_else(int& _t);		void Deal_k_for(int& _t);		void Deal_k_break(int& _t);		void Deal_k_continue(int& _t);		void Deal_k_do(int& _t);		void Deal_k_until(int& _t);		void Deal_k_while(int& _t);		void Deal_k_local(int& _t);		void Deal_k_const(int& _t);		void Deal_k_and(int& _t);		void Deal_k_or(int& _t);		void Deal_k_not(int& _t);		void Deal_k_function(int& _t);		void Deal_k_end(int& _t);		void Deal_k_return(int& _t);									//创建语法树		void SetupASTree(int start, int end);//实际的创建函数		//打印漂亮的二叉树		void DisplayASTree(Expr* _node, int _num = 0);//实际打印的函数		//删除二叉树		void DelTree(Expr* _expr);			public:		Parser();		~Parser();		//创建语法树		void CreateASTree();//留给外面的接口		//打印漂亮的语法树		void ShowASTree();//留给外面的接口		//解释语法树		void interpret();		//是否已经构造完成		bool GetCompletedASTreeFlag()const;	private:		bool   completedASTree_flag = false;//是否已经完成语法树的构造		int  v_forDisplayASTree[100] = {
    0 };//打印语法树要用的工具		bool firstEq_flag = true;//是否第一次遇到等于号		bool firstId_is_string_flag = true;	//表达式的第一个Id是否是flag		std::map
   
     funcMap;//为了减少if-else的个数，使用查表的方法，根据不同的枚举来调用不同的函数		std::map
    
      k_funcMap;//处理keyword的函数表		ExprType exprType = ExprType_NumberCalculate;//表达式类型,默认是数字运算模式，只有第一个Token是字符串时会变为字符串拼接模式						bool   completedName_flag = false;//是否完成左边的变量的声明													 				/*root不为空时语句是赋值语句,exprRoot不为空时是表达式，root和exprRoot在构造完语法树后不能同时为空也不能同时不为空*/		//与exprRoot进行交互		Expr* root = NULL;											//语法树根节点				/*logicRoot不为空时语句和exprRoot不为空时一样，都是表达式！！！*/		//与judgeRoot进行交互，最后用exprRoot去替换掉logicRoot		Expr*  logicRoot = NULL;								//逻辑式语法树根节点		/*judgeRoot不为空时语句和exprRoot不为空时语句一样，都是表达式！！！	*/		//judgeRoot与exprRoot进行交互，最后用exprRoot去替换掉judgeRoot		Expr* judgeRoot = NULL;								//判断式语法树根节点													//普通表达式要构造语法树用得到的指针		Expr* exprRoot = NULL;													//表达式语法树根节点		Expr* expTmp = NULL;													//待处理的节点（为空）的父节点		Expr* expTmpLeft = NULL;												//最下层的没匹配到右括号的左括号节点		std::stack
     
        v_NoMatchedLLeft;							//保存所有的未匹配到右括号的左括号节点						};};#endif

目前构造语法树的逻辑

一条语句，可以不是赋值语句，即root为空

赋值语句后面可以跟着赋值语句，最后面的语句是表达式

一条语句以分号结尾

表达式有4种模式，分别是五则运算、字符串拼接、判断运算、逻辑运算

几乎每一个Token都要区分一下几种表达式模式

表达式模式除了有特定的标志外，与exprRoot、judgeRoot、logicRoot是否为空有关

每次遇到一个等于号，都要把这个等于号挂载在root的语法树中。赋值语法树除了第一个赋值是左结合的外，后面跟着的其他赋值都是右结合的，即每假如一个赋值就要查找root语法树最右的赋值节点，并把新树挂在它右孩子上。

赋值节点的左边一定是变量节点

赋值节点最后一个孩子，在出现分号后，将exprRoot(简单表达式)挂在root语法树中

没有逻辑运算的式子里只能有一个判断节点，6种判断节点优先级一样

当出现判断节点后，将exprRoot挂在判断节点左孩子上，当出现逻辑节点或分号时，才把新的exprRoot挂在此判断节点的有孩子上

判断模式的句子遇到分号后，会先装载好judeRoot语法树，然后用exprRoot替换掉judgeRoot，这样的话判断模式就不会和赋值语句有直接交互！！！

当出现逻辑节点后，将exprRoot挂在逻辑节点左孩子上，当出现逻辑节点或分号时，先执行第11条，才把新的exprRoot挂在此逻辑节点的有孩子上

逻辑模式的句子遇到分号后，先执行第12条，再装载好logicRoot语法树，然后用exprRoot替换掉logicRoot，这样的话逻辑模式就不会和赋值语句有直接交互！！！

无论是判断模式还是逻辑模式，除了表达式可以有括号外，其他位置不能有括号！

逻辑模式中，not只能有一个，必须是表达式开头第一个

逻辑模式下，or优先级比and低

//下面的语句都是合法的1 + 2 * (3 / 4) ^5 - 100;a = TEST_C + "AAAAA" +"SSSSS";//TEST_C是预定义变量，用了测试的，前一篇有提到   //返回author@DemllieAAAAASSSSSa = b = c = 2;a = b = 3 + 1 > 5 * 8 ;//返回falsea = 1 >2 and 2 ~= 3 or 4<5 and 5 ==6;//返回falsea = not 1 > 3;//返回truenot 1~=2 and 3~= 4;//返回false

项目演示

文件中内容： a = not 1 < 2 + 1 and 4 == 5 or 2~=1;

词法分析 time consumed 211 ms初始化语言环境 time consumed 1 ms语法分析·构造语法树 time consumed 1 ms------------------------------------------------------------=├── a└── not    └── or        ├── and        │   ├── <        │   │   ├── 1        │   │   └── +        │   │       ├── 2        │   │       └── 1        │   └── ==        │       ├── 4        │       └── 5        └── ~=            ├── 2            └── 1------------------------------------------------------------语法分析·显示语法树 time consumed 39 msresult = false语法分析·解释语法树 time consumed 1 ms语言环境>                name   isconst    type      funcPtr     flag             num   str                 NIL    true       nil     00000000    false               0              TEST_C    true       int     00000000     true               7               FALSE    true      bool     00000000    false               0              TEST_D    true      bool     00000000    false               0                TRUE    true      bool     00000000     true               0                   a   false      bool     00000000    false               0              TEST_B    true    number     00000000     true     1.22323e+06              TEST_A    true    string     00000000     true               0   author@Demllie显示环境信息 time consumed 650 ms

项目代码地址CSDN

http://download.csdn.net/download/weixin_41374099/12203591

项目代码地址BDWP

链接：https://pan.baidu.com/s/1S4e1KvZ5uv8XBAkwUvklEA

提取码：i72f

转载地址：http://qtngz.baihongyu.com/

你可能感兴趣的文章