2020-01-11

题解

34 分钟读完 (大约 5079 个字) 0次访问

LuoguP3695 - CYaRon!语

【LuoguP3695】 CYaRon!语
题目链接: https://www.luogu.com.cn/problem/P3695

前言

很早前就想写一个自己的语言，但教程一直看不懂，甚至无法写出一个代码优美、逻辑清晰的计算器。最近又有了这个念头，根据国外文献开始学习解释器。

写了一个简单的计算器之后发现效率有点低，甚至并不能很好地在此基础上扩展。然后就找了这道题开始根据文献yy。

给出解释器的相关内容，国外文献及国内翻译，文献所用语言是Python，并且国内只有计算器的部分（加减乘除，相反数）。

所以我写代码的时候更加注重工程风格，在保证无BUG前提下尽量严格，并且不依赖于其他库（STL）。

如果在代码中调用了我没有讲的函数，那么请看最后的完整代码，因为函数实在太多了。

类中必要的public函数基本都已省略

代码中...表示省略

解释器概述

建议先编写一个表达式求值，不过这道题需要处理的中缀表达式中只有加减运算，所以比较简单。

写一下的解释器通用的逻辑。

TOKEN

翻译为令牌、标记，我理解为单词，包括单关键字、变量名、符号等。

主要是将一段字符串转换为计算机可以理解的东西，通常是数字。每个TOKEN都有它自己的类型，并且存储原有的内容。TOKEN通常是解释器的最小单元。

具体实现可以用define、const、enum之一，我使用了enum。这些都是程序员自己定义的。例如此题（部分）：

enum TOKEN_TYPE {
	INTEGER = 1,    // 整形（数字）
	OPERATOR_PLUS,  // 操作符 '+'
	...,
	T_COLON,        // 符号 ':'
	T_COMMA         // 符号 ','
};
// TOKEN 类型

存储时即使用类或者结构体，代码（部分）：

class TOKEN {
	private:
	TOKEN_TYPE _typ;    // TOKEN类型
	const char *_val;   // 原有的值
	unsigned int _len;  // 值长度
    // 注：使用 const char* 是为了方便
    ...
};

LEXER

翻译为词法分析器。简单来说，输入一堆字符（本题是整个程序），经过LEXER的处理，输出一系列的TOKEN（按顺序）。

对于大部分OIER来说，都写过暴力模拟的表达式求值。两者想似，但是LEXER分析一段字符串后输出TOKEN并不直接让LEXER来处理。所以它还有个别名为scanner。

存储时依然是使用类或者结构体，代码（部分）：

class LEXER {
	private:
	const char *_text;  // 一堆字符（本题是整个程序）
	unsigned int _len;  // 字符长度
	unsigned int _pos;  // 处理到第_pos个字符（从 0 开始）
	char _ch;           // 当前字符为_ch
    ...
}

然后要在类中写几个函数，分别是扫描下一个字符、跳过间隔符、跳过数字等。扫描下一个字符时要判断是否已到字符串结尾，代码：

void nextChar() {
    this->_ch = (this->_pos >= this->_len ? 0 : this->_text[++this->_pos]);
    return;
}
unsigned int skipNumber() {
    unsigned int res = 0;
    while(this->_ch != 0 && isNumber(this->_ch)) ++res, nextChar();
    // isNumber(x) 表示 x 是否为数字
    return res;
}

LEXER最重要的作用还是获取TOKEN，对于本题的代码（部分）：

TOKEN getNextToken() {
    while(this->_ch != 0) {
        if(isSpacer(this->_ch)) {
        // isSpacer(x) 表示 x 是否为间隔符
            skipSpace();
        // skipSpace() 跳过间隔符
            continue;
        }
        if(isNumber(this->_ch)) {
        // isNumber(x) 表示 x 是否为数字
            const char *pos = getPosString();
            return TOKEN(INTEGER, pos, skipNumber());
        }
        if(this->_ch == '+') {
            nextChar();
            return TOKEN(OPERATOR_PLUS);
        }
        ...
        if(this->_ch == ',') {
            nextChar();
            return TOKEN(T_COMMA);
        }
        if(this->_ch == ':') {
            nextChar();
            return TOKEN(T_COLON);
        }
        return TOKEN(T_NULL);
        // 无法处理
    }
    return TOKEN(T_EOF);
    // 结尾
}

NODE

NODE是我起的名字，因为它代表语法树的一个节点。获得程序根节点的返回值意味着运行整个程序。

每个NODE存储一个TOKEN，TOKEN的类型表示NODE的任务类型，TOKEN的值表示NODE可用的参数。NODE还有它的子节点，每个NODE运作时都会用指定方式使它的子节点运作。

它的类在此题如下：

class NODE {
	private:
	TOKEN _token;               // 必需的
	NODE **_list;               // 子节点指针数组
	bool _multi;
	unsigned int _siz, _msiz;
	bool _flag;
}

_multi、_msiz、_flag是我的实现，可能有更好的方法。至于它们的作用会在下面再讲。

NODE的两个核心方法为getValue和setValue，但对于本题来说，前置更复杂一些。

PARSER

翻译为语法分析器。输入TOKEN，生成语法树，输出根节点。因为此题不涉及运算符先后顺序，所以只需实现判断。循环等语法即可。

PARSER类的代码（部分）：

class PARSER {
	private:
	LEXER _lexer;   // 绑定的LEXER
	TOKEN _tok;     // 当前处理的TOKEN
    ...
};

同样在类中有获得下一个TOKEN的函数，代码：

void nextToken(TOKEN_TYPE typ) {
    if(this->_tok.getType() == typ) this->_tok = this->_lexer.getNextToken();
    return;
}

有方法parser用来生成语法树，内部由多个函数递归实现，因语言而异。

CALCULATOR

推荐先写一个加减乘除相反数的计算器来练手，此处为我的代码。

本题分析

计算器和本题差别还是很大的，对比发现，本题多了变量、判断、循环、数组、输出、比较，少了乘除。再进一步发现，少了运算优先级的问题。

TOKEN

我定义本题有30个TOKEN，可以说是非常多了，所以请对照完整代码。然后只讲一些本题的核心语法和逻辑。

如果不知道某个TOKEN_TYPE的含义，那么请看在代码里的LEXER中TOKEN是如何产生的。

VARIABLE

至于为什么先讲这个，因为程序一上来就要定义变量。我是针对本题只有int来解决的，解释器文献的这部分在C++中出入较大。

本着不用STL的原则，因此无法使用map。我并不想也不会写红黑树，而本题只有10个变量，所以就链表查询变量了。代码（部分）：

class VAR {
	private:
	const char *_name;  // 变量名
	unsigned int _len;  // 变量名长度
	VAR *_nxt;          // 链表下一个
	int *_mem;          // 内存
	int _s, _t;         // 数组下标起始和终止，非数组中分别为0、1
    ...
};

然后定义一个链表首节点var_first，写两个函数分别为getVar、setVar，前置是根据名称获得VAR指针，后者实际上是注册一个VAR。

BLOCK

BLOCK是一个TOKEN类型，目的表示代码块。一个{}所包含的内容即是一个代码块，特别的，整个程序也是一个代码块。

根据语言的特性，代码块的第一行通常为控制语句，比如判断、循环、vars等。如果没有控制语句，设置BLOCK为默认控制语句，代表只运行一次，vars也是如此。

我们将根据第0个子节点的返回值是否为true循环运行BLOCK中的内容。

NODE

所以问题又来了，如何存储子节点列表。我们并不想使用vector，只好自己实现。

根据vector的思想，只需要在列表已满时将空间扩大一倍（变为两倍），效率比较高。

为了方便使用，特化出自运算、一元运算和二元运算，以~~提高代码复杂度~~便于编写。

按照规则，BLOCK表示代码块时是多元运算。如果BLOCK表示控制语句时是自运算。

因此在代码中用_multi表示是否为多元运算，_siz记录子节点数，_msiz记录分配内存大小。

VARIABLE_DEFINE

首先知道格式为name:type/array[type, s..t]，即名称:类型/数组[类型, 起始下标..终止下标]。

那么组成它的TOKEN包括VARIABLE_NAME、VARIABLE_TYPE、BRACKET_LEFT、BRACKET_RIGHT、INTEGER、T_DOT。

语法树构建时，我把T_COLON设为多元运算符，VARIABLE_NAME设为第0子节点，省去了VARIABLE_TYPE，如果为数组再新建两个INTEGER节点当做T_COLON的子节点。

此为parserVar函数。

运作时判断子节点数，VAR中的_s为第1个子节点的值，_t为第2个子节点的值，无子节点视为0、1。

EXPRESSION

表达式已经是老生常谈的问题了，所以不再细说。

遇到表达式调用parserSecond，内部调用parserThird，分析出常量、变量、加减运算符，遇到括号（然而此题没有，才发现）就递归调用parserSecond。

VARIABLE

读取变量的值时先读入VARIABLE_NAME，再判断是否有BRACKET_LEFT（左中括号），之后再调用parserSecond读取内部表达式，再读入BRACKET_RIGHT，然而本题内部表达式并不会很复杂。

所以此处我把VARIABLE_NAME设为一元运算符，仅有的一个子节点为下标（不是数组则为0）。

YOSORO | ASSIGN(SET)

先分析输出和赋值语句，因为它们逻辑最简单且作用相反（似乎并不相反）。

当PARSER遇到类型为T_COLON的TOKEN时，那么就视为要执行函数了，进入parserCall函数。

YOSORO为一元运算符，仅有一个子节点为表达式。ASSIGN为二元运算符，左儿子为变量名，右儿子为表达式。

IF(IHU) | WHILE

之所以它们放在一块，是因为语法相同。当遇到对应的TOKEN时，依次读取比较操作符、逗号、表达式、逗号、表达式，函数为parserIhu和parserWhile。

IF和WHILE为一元运算符，仅有一个子节点为比较操作符的返回值。众所周知比较操作符是二元运算符，这个非常简单。

为了判断一个节点是否第一次运作，所以在NODE中加入了变量_flag。

IF和WHILE的差别在于IF后需要将_flag设为true。

BLOCK ADDITION 1

在BLOCK运作结束后还需要重置子节点的状态信息（如_flag），以让下次进入BLOCK节点时所有的子节点是新的。

FOR(HOR)

FOR应该是比较麻烦的一个，我将它设为多元运算符。

函数为parserHor，依次读取表达式、逗号、表达式、逗号、表达式。三个表达式依次为它的三个子节点。

运作时先判断_flag，第一次需要给第0个子节点赋值为第1个子节点的值。然后再通过判断第0个子节点是否小于等于第2个子节点。

还需要让FOR节点也要有一个赋值的方法，为了在循环结束时给第0个子节点加1。

BLOCK ADDITION 2

所以BLOCK结束时还要调用控制语句（第0个子节点）的赋值操作，当然值就不必设置了。

GLOBAL FUNCTION

运行程序使用calc，参数为整个程序和字符串长度。

int calc(const char *exp, unsigned int len) {
	char *_exp = new char[len]();
	for(unsigned int i = 0; i < len; i++) _exp[i] = exp[i];
    // 改为用户不可变内存，安全起见
	int res = PARSER(LEXER(_exp, len)).parser()->getValue();
	delete[] _exp;
	return res;
}

并未使用strcmp，手写了equalString用来判断字符串是否相等。

剩下的方法都比较简单，自行理解即可。

图例

如果还不懂可以看图例，纯手工良心制作。

P3695

代码

无O2用时37ms内存820KB

#include <stdio.h>
namespace CALCULATOR {
enum TOKEN_TYPE {
	INTEGER = 1,
	OPERATOR_PLUS,
	OPERATOR_MINUS,
	OPERATOR_LT,
	OPERATOR_GT,
	OPERATOR_LE,
	OPERATOR_GE,
	OPERATOR_EQ,
	OPERATOR_NEQ,
	PAR_LEFT,
	PAR_RIGHT,
	BRACKET_LEFT,
	BRACKET_RIGHT,
	BLOCK_LEFT,
	BLOCK_RIGHT,
	PROGRAM,
	BLOCK,
	VARIABLE_NAME,
	VARIABLE_TYPE,
	VARS,
	YOSORO,
	OPERATOR_ASSIGN,
	IHU,
	HOR,
	WHILE,
	T_DOT,
	T_EOF,
	T_NULL,
	T_COLON,
	T_COMMA
};

bool equalString(const char *a, const char *b, unsigned int len) {
	for(unsigned int i = 0; i < len; i++)
		if(a[i] != b[i]) return 0;
	return 1;
}
class VAR {
	private:
	const char *_name;
	unsigned int _len;
	VAR *_nxt;
	int *_mem;
	int _s, _t;

	public:
	VAR() : _name(), _len(), _nxt(), _mem(), _t(), _s() {}
	VAR(const char *name, unsigned int len) : _name(name), _len(len), _nxt(), _mem(), _t(), _s() {}
	VAR(const char *name, unsigned int len, int s, int t) : _name(name), _len(len), _nxt(), _mem(), _t(t), _s(s) {
		this->_mem = new int[this->_t - this->_s]();
	}
	unsigned int getLen() const {
		return this->_len;
	}
	void setValue(int x, int v) {
		this->_mem[x - this->_s] = v;
		return;
	}
	const char *getName() const {
		return this->_name;
	}
	VAR *getNext() const {
		return this->_nxt;
	}
	void setNext(VAR *v) {
		this->_nxt = v;
	}
	int getValue(int x) {
		return this->_mem[x - this->_s];
	}
} var_first;
VAR *getVar(const char *name, unsigned int len) {
	VAR *p = &var_first;
	while(p) {
		if(p->getLen() == len && equalString(p->getName(), name, len)) return p;
		p = p->getNext();
	}
	return 0;
}
void setVar(VAR *nxt) {
	VAR *p = &var_first;
	while(p->getNext()) p = p->getNext();
	p->setNext(nxt);
	return;
}
class TOKEN {
	private:
	TOKEN_TYPE _typ;
	const char *_val;
	unsigned int _len;

	public:
	TOKEN(TOKEN_TYPE typ = T_NULL) : _typ(typ), _val(), _len() {}
	TOKEN(TOKEN_TYPE type, const char *val, unsigned int len) : _val(val), _typ(type), _len(len) {}
	TOKEN_TYPE getType() const {
		return this->_typ;
	}
	const char *getValue() const {
		return this->_val;
	}
	unsigned int getLength() const {
		return this->_len;
	}
	~TOKEN() {}
};
int toInteger(const char *val, unsigned int len) {
	int res = 0;
	for(unsigned int i = 0; i < len; i++) res = res * 10 + val[i] - '0';
	return res;
}

unsigned int toString(int val, char *res) {
	unsigned int len = 0;
	int val2 = val;
	while(val2) ++len, val2 /= 10;
	unsigned int len2 = len;
	while(val) res[--len2] = '0' + val % 10, val /= 10;
	if(len == 0) res[len = 1] = '0';
	return len;
}

bool isNumber(char ch) {
	return ch >= '0' && ch <= '9';
}

bool isLetter(char ch) {
	return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}

bool isSpacer(char ch) {
	return ch == ' ' || ch == '\n' || ch == '\t';
}

class LEXER {
	private:
	const char *_text;
	unsigned int _len;
	unsigned int _pos;
	char _ch;
	void nextChar() {
		this->_ch = (this->_pos >= this->_len ? 0 : this->_text[++this->_pos]);
		return;
	}
	void skipSpace() {
		while(this->_ch != 0 && isSpacer(this->_ch)) nextChar();
		return;
	}
	unsigned int skipNumber() {
		unsigned int res = 0;
		while(this->_ch != 0 && isNumber(this->_ch)) ++res, nextChar();
		return res;
	}
	unsigned int skipWord() {
		unsigned int res = 0;
		while(this->_ch != 0 && isLetter(this->_ch)) ++res, nextChar();
		return res;
	}
	const char *getPosString() const {
		return _text + _pos;
	}

	public:
	LEXER(const char *text, unsigned int len) : _text(text), _len(len), _pos() {
		this->_ch = (this->_pos >= this->_len ? 0 : this->_text[this->_pos]);
	}
	~LEXER() {}
	TOKEN getNextToken() {
		while(this->_ch != 0) {
			if(isSpacer(this->_ch)) {
				skipSpace();
				continue;
			}
			if(isNumber(this->_ch)) {
				const char *pos = getPosString();
				return TOKEN(INTEGER, pos, skipNumber());
			}
			if(isLetter(this->_ch)) {
				const char *pos = getPosString();
				unsigned int len = skipWord();
				if(len == 2 && equalString("lt", pos, len)) return TOKEN(OPERATOR_LT);
				if(len == 2 && equalString("gt", pos, len)) return TOKEN(OPERATOR_GT);
				if(len == 2 && equalString("le", pos, len)) return TOKEN(OPERATOR_LE);
				if(len == 2 && equalString("ge", pos, len)) return TOKEN(OPERATOR_GE);
				if(len == 2 && equalString("eq", pos, len)) return TOKEN(OPERATOR_EQ);
				if(len == 3 && equalString("neq", pos, len)) return TOKEN(OPERATOR_NEQ);
				if(len == 3 && equalString("set", pos, len)) return TOKEN(OPERATOR_ASSIGN);
				if(len == 3 && equalString("ihu", pos, len)) return TOKEN(IHU);
				if(len == 3 && equalString("hor", pos, len)) return TOKEN(HOR);
				if(len == 3 && equalString("int", pos, len)) return TOKEN(VARIABLE_TYPE, pos, len);
				if(len == 4 && equalString("vars", pos, len)) return TOKEN(VARS);
				if(len == 5 && equalString("while", pos, len)) return TOKEN(WHILE);
				if(len == 5 && equalString("array", pos, len)) return TOKEN(VARIABLE_TYPE, pos, len);
				if(len == 6 && equalString("yosoro", pos, len)) return TOKEN(YOSORO);
				return TOKEN(VARIABLE_NAME, pos, len);
			}
			if(this->_ch == '+') {
				nextChar();
				return TOKEN(OPERATOR_PLUS);
			}
			if(this->_ch == '-') {
				nextChar();
				return TOKEN(OPERATOR_MINUS);
			}
			if(this->_ch == '(') {
				nextChar();
				return TOKEN(PAR_LEFT);
			}
			if(this->_ch == ')') {
				nextChar();
				return TOKEN(PAR_RIGHT);
			}
			if(this->_ch == '.') {
				nextChar();
				nextChar();
				return TOKEN(T_DOT);
			}
			if(this->_ch == ',') {
				nextChar();
				return TOKEN(T_COMMA);
			}
			if(this->_ch == ':') {
				nextChar();
				return TOKEN(T_COLON);
			}
			if(this->_ch == '[') {
				nextChar();
				return TOKEN(BRACKET_LEFT);
			}
			if(this->_ch == ']') {
				nextChar();
				return TOKEN(BRACKET_RIGHT);
			}
			if(this->_ch == '{') {
				nextChar();
				return TOKEN(BLOCK_LEFT);
			}
			if(this->_ch == '}') {
				nextChar();
				return TOKEN(BLOCK_RIGHT);
			}
			return TOKEN(T_NULL);
		}
		return TOKEN(T_EOF);
	}
};

class NODE {
	private:
	TOKEN _token;
	NODE **_list;
	bool _multi;
	unsigned int _siz, _msiz;
	bool _flag;
	int getConstantValue() {
		if(this->_token.getType() == INTEGER) return toInteger(this->_token.getValue(), this->_token.getLength());
		if(this->_token.getType() == VARS && this->_flag == 0) return this->_flag = 1;
		if(this->_token.getType() == BLOCK && this->_flag == 0) return this->_flag = 1;
		return 0;
	}
	int getUnaryValue() {
		if(this->_token.getType() == OPERATOR_PLUS) return +this->_list[0]->getValue();
		if(this->_token.getType() == OPERATOR_MINUS) return -this->_list[0]->getValue();
		if(this->_token.getType() == YOSORO) return printf("%d ", this->_list[0]->getValue()), 0;
		if(this->_token.getType() == VARIABLE_NAME) return getVar(this->_token.getValue(), this->_token.getLength())->getValue(this->_list[0]->getValue());
		if(this->_token.getType() == IHU && this->_flag == 0) return this->_flag = 1, this->_list[0]->getValue();
		if(this->_token.getType() == WHILE) return this->_list[0]->getValue();
		return 0;
	}
	int getBinValue() {
		if(this->_token.getType() == OPERATOR_PLUS) return this->_list[0]->getValue() + this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_MINUS) return this->_list[0]->getValue() - this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_LT) return this->_list[0]->getValue() < this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_GT) return this->_list[0]->getValue() > this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_LE) return this->_list[0]->getValue() <= this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_GE) return this->_list[0]->getValue() >= this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_EQ) return this->_list[0]->getValue() == this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_NEQ) return this->_list[0]->getValue() != this->_list[1]->getValue();
		if(this->_token.getType() == OPERATOR_ASSIGN) return this->_list[0]->setValue(this->_list[1]->getValue());
		return 0;
	}
	int getMultiValue() {
		if(this->_token.getType() == T_COLON) {
			if(this->_siz == 1) {
				this->_list[0]->registerVar(0, 1);
			}
			else {
				this->_list[0]->registerVar(this->_list[1]->getValue(), this->_list[2]->getValue());
			}
			return 0;
		}
		if(this->_token.getType() == BLOCK) {
			while(this->_list[0]->getValue()) {
				for(unsigned int i = 1; i < this->_siz; i++) {
					this->_list[i]->getValue();
				}
				this->_list[0]->setValue(0);
			}
			this->clearST();
		}
		if(this->_token.getType() == HOR) {
			if(this->_flag == 0) {
				this->_list[0]->setValue(this->_list[1]->getValue());
				this->_flag = 1;
			}
			return this->_list[0]->getValue() <= this->_list[2]->getValue();
		}
		return 0;
	}
	int registerVar(int s, int t) {
		VAR *p = new VAR(this->_token.getValue(), this->_token.getLength(), s, t);
		setVar(p);
		return 0;
	}
	int setValue(int v) {
		if(this->_token.getType() == VARIABLE_NAME) {
			VAR *p = getVar(this->_token.getValue(), this->_token.getLength());
			p->setValue(this->_list[0]->getValue(), v);
		}
		if(this->_token.getType() == HOR) {
			this->_list[0]->setValue(this->_list[0]->getValue() + 1);
		}
		return 0;
	}
	void clearST() {
		if(this->_siz == -1) return;
		for(unsigned int i = 0; i < this->_siz; i++) this->_list[i]->_flag = 0, this->_list[i]->clearST();
	}

	public:
	NODE(bool multi = 0) : _token(T_NULL), _list(), _siz(-1), _multi(multi), _msiz(), _flag() {
		if(this->_multi) this->_siz = 0;
	}
	NODE(TOKEN token) : _token(token), _list(), _siz(), _multi(), _msiz(), _flag() {}
	NODE(TOKEN token, NODE *expr0) : _token(token), _siz(1), _multi(), _msiz(1), _flag() {
		this->_list = new NODE *[this->_siz]();
		this->_list[0] = expr0;
	}
	NODE(TOKEN token, NODE *expr0, NODE *expr1) : _token(token), _siz(2), _multi(), _msiz(2), _flag() {
		this->_list = new NODE *[this->_siz]();
		this->_list[0] = expr0;
		this->_list[1] = expr1;
	}
	~NODE() {
		if(this->_list)
			for(unsigned int i = 0; i < this->_siz; i++) delete this->_list[i];
	}
	int getValue() {
		if(this->_multi) return getMultiValue();
		switch(_siz) {
			case 0: return getConstantValue();
			case 1: return getUnaryValue();
			case 2: return getBinValue();
			default: break;
		}
		return 0;
	}
	void setToken(const TOKEN &token) {
		this->_token = token;
		return;
	}
	void push(NODE *expr0) {
		if(this->_siz >= this->_msiz) {
			unsigned int lmsiz = this->_msiz;
			this->_msiz = (this->_siz + 1) * 2;
			NODE **list = new NODE *[this->_msiz]();
			for(unsigned int i = 0; i < this->_siz; i++) list[i] = this->_list[i];
			if(this->_list) {
				delete[] this->_list;
			}
			this->_list = list;
		}
		this->_list[this->_siz++] = expr0;
		return;
	}
	int getSize() const {
		return this->_siz;
	}
};
class PARSER {
	private:
	LEXER _lexer;
	TOKEN _tok;
	void nextToken(TOKEN_TYPE typ) {
		if(this->_tok.getType() == typ) this->_tok = this->_lexer.getNextToken();
		return;
	}
	NODE *parserThird() {
		TOKEN token = this->_tok;
		if(token.getType() == INTEGER) {
			nextToken(INTEGER);
			return new NODE(token);
		}
		if(token.getType() == PAR_LEFT) {
			nextToken(PAR_LEFT);
			NODE *res = parserSecond();
			nextToken(PAR_RIGHT);
			return res;
		}
		if(token.getType() == VARIABLE_NAME) {
			nextToken(VARIABLE_NAME);
			NODE *res;
			if(this->_tok.getType() == BRACKET_LEFT) {
				nextToken(BRACKET_LEFT);
				res = parserSecond();
				nextToken(BRACKET_RIGHT);
			}
			else {
				res = new NODE();
			}
			return new NODE(token, res);
		}
		if(token.getType() == OPERATOR_PLUS || token.getType() == OPERATOR_MINUS) {
			nextToken(token.getType());
			return new NODE(token, parserThird());
		}

		return new NODE();
	}
	NODE *parserSecond() {
		NODE *res = parserThird();
		while(this->_tok.getType() != T_EOF) {
			TOKEN token = this->_tok;
			if(token.getType() == OPERATOR_PLUS || token.getType() == OPERATOR_MINUS) {
				nextToken(token.getType());
				res = new NODE(token, res, parserThird());
			}
			else {
				break;
			}
		}
		return res;
	}
	NODE *parserCall() {
		TOKEN token = this->_tok;
		if(token.getType() == YOSORO) {
			nextToken(YOSORO);
			return new NODE(token, parserSecond());
		}
		if(token.getType() == OPERATOR_ASSIGN) {
			nextToken(OPERATOR_ASSIGN);
			NODE *res = parserThird();
			nextToken(T_COMMA);
			return new NODE(token, res, parserSecond());
		}
		return new NODE();
	}
	NODE *parserVar() {
		NODE *res = new NODE(1);
		res->push(new NODE(this->_tok));
		nextToken(VARIABLE_NAME);
		res->setToken(this->_tok);
		nextToken(T_COLON);
		if(this->_tok.getLength() == 5) {
			nextToken(VARIABLE_TYPE);
			nextToken(BRACKET_LEFT);
			nextToken(VARIABLE_TYPE);
			nextToken(T_COMMA);
			res->push(new NODE(this->_tok));
			nextToken(INTEGER);
			nextToken(T_DOT);
			nextToken(T_DOT);
			res->push(new NODE(this->_tok));
			nextToken(INTEGER);
			nextToken(BRACKET_RIGHT);
		}
		else {
			nextToken(VARIABLE_TYPE);
		}
		return res;
	}
	NODE *parserIhu() {
		NODE *res;
		nextToken(IHU);
		TOKEN token = this->_tok;
		if(token.getType() == OPERATOR_LT || token.getType() == OPERATOR_GT || token.getType() == OPERATOR_LE || this->_tok.getType() == OPERATOR_GE || this->_tok.getType() == OPERATOR_EQ || token.getType() == OPERATOR_NEQ) {
			nextToken(token.getType());
			nextToken(T_COMMA);
			NODE *res1 = parserSecond();
			nextToken(T_COMMA);
			NODE *res2 = parserSecond();
			res = new NODE(token, res1, res2);
		}
		else {
			res = new NODE();
		}
		return new NODE(TOKEN(IHU), res);
	}
	NODE *parserHor() {
		NODE *res = new NODE(1);
		res->setToken(this->_tok);
		nextToken(HOR);
		res->push(parserSecond());
		nextToken(T_COMMA);
		res->push(parserSecond());
		nextToken(T_COMMA);
		res->push(parserSecond());
		return res;
	}
	NODE *parserWhile() {
		NODE *res;
		nextToken(WHILE);
		TOKEN token = this->_tok;
		if(token.getType() == OPERATOR_LT || token.getType() == OPERATOR_GT || token.getType() == OPERATOR_LE || this->_tok.getType() == OPERATOR_GE || this->_tok.getType() == OPERATOR_EQ || token.getType() == OPERATOR_NEQ) {
			nextToken(token.getType());
			nextToken(T_COMMA);
			NODE *res1 = parserSecond();
			nextToken(T_COMMA);
			NODE *res2 = parserSecond();
			res = new NODE(token, res1, res2);
		}
		else {
			res = new NODE();
		}
		return new NODE(TOKEN(WHILE), res);
	}
	NODE *parserFirst() {
		NODE *res = new NODE(1);
		res->setToken(TOKEN(BLOCK));
		while(this->_tok.getType() != T_EOF) {
			TOKEN token = this->_tok;
			if(token.getType() == VARS) {
				nextToken(VARS);
				res->push(new NODE(TOKEN(VARS)));
			}
			else if(token.getType() == IHU) {
				res->push(parserIhu());
			}
			else if(token.getType() == HOR) {
				res->push(parserHor());
			}
			else if(token.getType() == WHILE) {
				res->push(parserWhile());
			}
			else if(token.getType() == VARIABLE_NAME) {
				if(res->getSize() == 0) res->push(new NODE(TOKEN(BLOCK)));
				res->push(parserVar());
			}
			else if(token.getType() == T_COLON) {
				if(res->getSize() == 0) res->push(new NODE(TOKEN(BLOCK)));
				nextToken(T_COLON);
				res->push(parserCall());
			}
			else if(token.getType() == BLOCK_LEFT) {
				if(res->getSize() == 0) res->push(new NODE(TOKEN(BLOCK)));
				nextToken(BLOCK_LEFT);
				res->push(parserFirst());
				nextToken(BLOCK_RIGHT);
			}
			else {
				break;
			}
		}
		return res;
	}

	public:
	PARSER(LEXER lexer) : _lexer(lexer) {
		this->_tok = this->_lexer.getNextToken();
	}
	NODE *parser() {
		return parserFirst();
	}

	~PARSER() {}
};

int calc(const char *exp, unsigned int len) {
	char *_exp = new char[len]();
	for(unsigned int i = 0; i < len; i++) _exp[i] = exp[i];
	int res = PARSER(LEXER(_exp, len)).parser()->getValue();
	delete[] _exp;
	return res;
}

}  // namespace CALCULATOR

#include <stdio.h>
#include <iostream>
using namespace std;
string str, str2;

int main() {
	while(getline(cin, str2)) {
		str += str2;
	}
	CALCULATOR::calc(str.c_str(), str.size());
	return 0;
}

后记

题解写了半个下午，继续学习变量类型去了。

# Cpp, 模拟, 解释器, 题解

LuoguP3695 - CYaRon!语

前言

解释器概述

TOKEN

LEXER

NODE

PARSER

CALCULATOR

本题分析

TOKEN

VARIABLE

BLOCK

NODE

VARIABLE_DEFINE

EXPRESSION

VARIABLE

YOSORO | ASSIGN(SET)

IF(IHU) | WHILE

BLOCK ADDITION 1

FOR(HOR)

BLOCK ADDITION 2

GLOBAL FUNCTION

图例

代码

后记

评论

目录

链接

分类

标签云

最新文章

归档

标签

最新文章

归档

标签

Your browser is out-of-date!