0%

类之间的运算

这里可以利用抽象代数的观点来看待这种处理,把运算扩充到任意的集合上,而不是只在数集上.运算可以对应于某个集合下元素之间的关系,可以在运算的世界中表达逻辑.在软件工程观点来看,让代码变得简洁

C++运算符重载:用同一个运算符完成不同的运算功能。

限制

基本原则

C++运算符重载的相关规定如下:
1.不能改变运算符的优先级。
2.不能改变运算符的结合性。
3.默认参数不能和重载的运算符一起使用,也就是说,在设计运算符重载成员函数时不能使用默认函数。
4.不能改变运算符的操作数的个数。
5.不能创建新的运算符,只有已有运算符可以被重载
6.运算符作用于C++内部提供的数据类型时,原来含义保持不变
7. 重载的运算符至少有一个操作数是自定义类型

C++中可被重载的运算符:

可被重载

不可被重载的运算符

  • sizeof
  • .: 成员运算符
  • .* 成员指针运算符
  • :: 作用域运算符
  • ?:: 条件运算符
  • typeid: 运行时信息运算符
  • const_cast/dynamic_cast/static_cast/reinterpret_cast 类型转换运算符
    上面这些并不是表达元素之间的运算关系,而是取成员和类型转换,这些由类的元数据决定,当一个类确定之后,这些的运算结果就应该是确定的

只可通过成员函数重载

  • = 赋值
  • () 函数调用
  • [] 下表
  • -> 通过指针访问类成员

格式

1
2
3
4
5
6
7
8
9
函数类型   	operator	重载运算符(形参表)
{
函数体;
}
//非成员函数
friend 函数类型 operator 重载运算符(形参表)
{
函数体;
}

原理

实际上都是编译器做了特定表达式/类型下运算符->函数的转换.最终都被编译器转换成函数

实例

重载自增自减运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
class MyClass2
{
int n;
public:
MyClass2(int i){ n = i; }
int operator ++(){ n++; return n; }
int operator ++(int){ n += 2; return n; }
void display()
{
cout << "n=" << n << endl;
}
};

int main()
{
MyClass2 A(5), B(5);
A++;
++B;
A.display();
B.display();
return 0;
}

重载双目运算符

成员函数

假设有一个类A,对于双目运算符op,如果重载运算符op使之能够实现表达式“obj1 op obj2”,其中obj1和obj2均为A类的对象。
若把op重载为A类的成员函数,该函数只有一个形参,形参的类型是obj2所属的类型。是把op前面的看成对象,op右边的看出函数参数

1
obj1.operator op(obj2)

友元函数

假设有一个类A,对于双目运算符op,如果重载运算符op使之能够实现表达式“obj1 op obj2”,其中obj1和obj2均为A类的对象。
若把op重载为A类的友元函数,该函数有两个形参,经过重载之后,表达式“obj1 op obj2”解释为:

1
obj1 op(obj1,obj2)

重载赋值运算符

哈哈,这里不就是我们熟悉的拷贝构造函数和赋值运算符.找到理论和实际的结合点了

重载下标运算符

下标运算符“[ ]”通常用于获取数组的某个元素,重载下标运算符可以实现数组下标的越界检测等。下标运算符重载只能作为类的成员函数,不能作为类的友元函数。

重载new delete换运算符

new和delete只能被重载为类的成员函数,不能重载为友元。而且,无论是否使用关键字static进行修饰,重载了的new和delete均为类的静态成员函数。
运算符new重载的一般格式如下:

1
2
3
4
5
void	*类名::operator	new(size_t,参数表);
void* operator new(size_t size,int x,int y,int z)
{……
}
void *类名“::operator delete(void*,参数表);

使用如下:

1
x*pX=new(1,2,3) X;

重载类型转换运算符

这个特性是和拷贝构造函数对应的,比如有一个类Stock可以根据传入的double来构造,

1
2
3
4
5
6
7
class Stock{
public:
Stock(double t){
value = t;
}
int value;
}

那么如果要将Stock转出double呢,就要用到下面的类型转换运算符.这两个函数是一一对应的
格式:

1
2
3
4
operator 类型名()
{
函数体;
}

重载函数调用运算符

函数调用运算符“()”只能说明成类的非静态成员函数,该函数具有以下的一般格式:

1
函数类型 类名::operator()(参数表)

重载移位运算符

按照输入流和输出流的概念,如果能有一种运算符可以让对象直接和输入流输出流交互,就不用再写printf(“%s”)这种冗余代码了,还要记类型的format.
于是我们想,把移位看出向输入流和输出流传递数据,正好有左移和右移.开口大的流向开口小的.于是会有下面的代码:

1
2
输出流 <<  obj
输入流 >> obj

幸运的是,C++大佬们设计出了这样的特性. 根据友元函数运算符重载的特点,对于双目操作符是将 obj1 op opj2转换成 op(obj1,obj2);
并且这样还可以支持任意一种自定义类型却不用修改std库中输入流和输出流的代码.这实际上也是友元函数重载解决的问题

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
#include<iostream>
using namespace std;
class Person {
friend ostream& operator<<(ostream& out, Person& p);

public:

Person(int a, int b)
{
this->m_A = a;
this->m_B = b;
}

//成员函数 实现不了 p << cout 不是我们想要的效果
//void operator<<(Person& p){
//}

private:
int m_A;
int m_B;
};

//全局函数实现左移重载
//ostream对象只能有一个
ostream& operator<<(ostream& out, Person& p) {
//ostream是标准的输出流,全局只能有一个,所以用引用引用的方式
out << "a:" << p.m_A << " b:" << p.m_B;
return out;
}

void test() {

Person p1(10, 20);

cout << p1 << "hello world" << endl; //链式编程
}

int main() {

test();

return 0;
}


运算符重载的坑

意外的类型转换

在编程实践中,对于类型转换和拷贝构造函数有可能发生了意外的隐式转换,导致bug,所以最好是加上explict关键字,告诉编译器不要做隐式转换

重载双目运算符不满足交换律

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
#include<iostream>
using namespace std;
class MyClass2
{
int n;
public:
MyClass2(int i){ n = i; }
MyClass2 operator +(int a){ n+=a; return n; }
void display()
{
cout << "n=" << n << endl;
}
friend MyClass2 operator +(MyClass2 a, int b){
a.n += b;
return a;
}
};

int main()
{
MyClass2 A(5), B(5);
A = 5 + A;// 会报错
A.display();
B.display();
return 0;
}

例子中会无法通过编译,因为双目运算符成员函数左边必须是对象,友元重载必须参数类型要匹配(按照前面双目运算符的等价函数调用来理解)。这就导致的加法不满足交换律.

过多的转换函数导致的二义性

假定Stock有形参为double的拷贝构造函数,并且重载了Stock类之间的加法

1
2
3
4
Stock a(1.0);
double b = 2.0;
Stock total;
total = a + b;// 将b转成Stock,再相加

如果此时还又定义了Stock到double的转换函数,那么最后一行将不知道是将a转成double还是将b转成Stock,导致歧义

测试代码见

我的github

引用

  1. C++ Prime Plus
  2. C++重载运算符实例

简单介绍下编译原理

词法分析->语法分析->生成中间代码->机器无关的优化->生成汇编(机器相关的优化)->交给汇编器生成机器码
编译原理我当时看完了龙书+斯坦福的编译器公开课之后,对其中细节还是一知半解,当时就暂时先放下了.最开始的递归下降,nfa,dfa直接给我劝退了。
AST啥的也理解不透彻.

词法分析

token

解析字符串流,确定一个个的token,比如在c语言中,确定是if,while这些关键字还是变量名,运算符等.最终会生成符号表。
语言中关键字:这些关键字会被保存在一种表中,在解析字符流的时候,如果碰到关键字则直接保留。

词法框架

根据正则表达式来定义某种特定token的规则,在解析字符串流的时候,根据正则来判断属于哪种token

常见的词法框架/工具

lex/flex,是通过正则表达式和自定义解析字符串综合工作的

语法分析

主要在于如何表达语法规则和检验语法规则.

语法规则

编译器大佬提出了一种文法,只关注字符串的变换.并定义终结符号和非终结符号的概念.非终结符号则可以继续产生新符号,从而用字符串实体表达出了语言的语法规则.非终结符号到另外一个符号串叫做产生式.

产生式

比如程序一开始会有一个非终结符号S,对于C语言这个语法来说,会有下面的产生式.下面给出部分产生式做说明

1
2
3
4
5
6
7
S -> void main(){B}
B -> Y;
Y -> Y;STATEMENT | e
STATEMENT -> D | A | BLOCK
D -> TYPE id | TYPE* id
BLOCK -> IF(C){B} ELSE{B} | while(C){B}
A -> id + id | id -id | id * id | id /id

解释一下上面的产生式,id和e,type这些是终结符.
第1行: S是非终结符号,可以变成main函数,里面是函数体
第2行: 表示函数体可以是分号组成的各种语句
第3行: 表示语句之间是可以不断拼接的,从而理论上可写出无限长度的程序
第4行:表示语句可以有声明语句,算术运算和语句块
第5行: 表示声明语句只能是类型名空格+标志符组成
第6行: 表示语句块可以有条件块和循环块
第7行: 表示算数运算可以有加减乘除

语法分析的实现

给定一组字符串可以是递归去判断,看最终会不会达到终结符,然后比对终结符是否和字符串中的相同.但在实际中采用的是更有效率的DFA表格,预先对产生式处理,然后可以对扫一遍字符串就可以判定是否合法,并构建出语法树

语法树

TODO,这块我目前还没搞懂

语法分析框架

好在大佬们已经写出来好的工具来给咱们使用了.yacc是语法分析的一种实现,根据用户定义的语法规则,做对应的动作.所有的查询引擎都有这个模块,比如mysql,prometheus.根据不同语言的yacc(c语言),javacc还有goyacc

goyacc做一个简单的计算器

我们来2步走,主要是这2个方法

1
2
3
4
5
6
7
8
9
type exprLexer interface {
Lex(lval *exprSymType) int
Error(s string)
}

type exprParser interface {
Parse(exprLexer) int
Lookahead() int
}

expr函数前缀,goyacc中可以自定义. 在自己的app中可以直接调用Parser来分析。但要提供lex的实现.下面实例中就可以看到

分析词法

细心的同学就会发现,这里实际上实现了上面lexer的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
func (x *exprLex) Lex(yylval *exprSymType) int {
for {
c, _, err := x.input.ReadRune()
if err != nil {
return eof
}
switch c {
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
return x.num(c, yylval)
case '+', '-', '*', '/', '(', ')':
return int(c)
case '×':
return '*'
case '÷':
return '/'

case ' ', '\t', '\n', '\r':
default:
log.Printf("unrecognized character %q", c)
}
}
}

// Lex a number.
func (x *exprLex) num(c rune, yylval *exprSymType) int {
var b bytes.Buffer
b.WriteRune(c)
L:
for {
c, _, err := x.input.ReadRune()
if err != nil {
return eof
}
switch c {
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.', 'e', 'E':
b.WriteRune(c)
default:
_ = x.input.UnreadRune()
break L
}
}
yylval.num = &big.Float{}
_, ok := yylval.num.SetString(b.String())
if !ok {
log.Printf("bad number %q", b.String())
return eof
}
return NUM
}

func (x *exprLex) Error(s string) {
log.Println("parse error: ", s)
}

分析语法

产生式

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
%{

package main
import (
"fmt"
"math/big"
)

%}

%union {
num *big.Float
}

%type <num> expr expr1 expr2 expr3 // 定义在后面的符号比定义在前面的符号具有更好的优先级

%token '+' '-' '*' '/' '(' ')'

%token <num> NUM

%%

top:
expr
{
if $1.IsInt() {
fmt.Println($1.String())
} else {
fmt.Println($1.String())
}
}

expr:
expr1
{}
|
'+' expr
{
$$ = $2
}
|
'-' expr
{
$$ = $2.Neg($2)
}
;

expr1:
expr2
{}
|
expr1 '+' expr2
{
$$ = $1.Add($1, $3)
}
|
expr1 '-' expr2
{
$$ = $1.Sub($1, $3)
}
;

expr2:
expr3
{}
|
expr2 '*' expr3
{
$$ = $1.Mul($1, $3)
}
|
expr2 '/' expr3
{
$$ = $1.Quo($1, $3)
}
;

expr3:
NUM
|
'(' expr ')'
{
$$ = $2
}

%%

应用中如何调用分析器

读取命令行的输入,并调用分析器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func main() {
in := bufio.NewReader(os.Stdin)
a := big.Float{}
a.String()
for {
if _, err := os.Stdout.WriteString("> "); err != nil {
log.Println("WriteString: ", err)
}
line, err := in.ReadBytes('\n')
if err == io.EOF {
return
}
if err != nil {
log.Fatalf("ReadBytes: %s", err)
}
//调用分析器
exprParse(newExprLex(line))
}
}

运行

安装

go install golang.org/x/tools/cmd/goyacc@latest

goyacc使用

Usage of goyacc:
-l disable line directives
-o string
parser output (default “y.go”)
-p string
name prefix to use in generated code (default “yy”)
-v string
create parsing tables (default “y.output”)
会根据你的语法规则(.y后缀的)生成.go文件. -o指定文件的名称 -p 指定生成parse函数前缀,默认是叫yyParse,以供外部调用
goyacc -o expr.go -p expr expr.y

构建

go build expr.go lexer.go main.go

执行

运行结果

goyacc 做json parser

最主要是整理出json的产生式,然后理解下yacc框架下的整体工作流程,就可以搞出来

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
%{
package jsonparser

type pair struct {
key string
val interface{}
}

func setResult(l yyLexer, v map[string]interface{}) {
l.(*lex).result = v
}
%}

%union{
obj map[string]interface{}
list []interface{}
pair pair
val interface{}
}

%token LexError
%token <val> String Number Literal

%type <obj> object members
%type <pair> pair
%type <val> array
%type <list> elements
%type <val> value


%start object

%%

object:
'{' members '}'
{
$$=$2
setResult(yylex, $$)
}

members:
{
$$ = map[string]interface{}{}
}
| pair
{
$$ = map[string]interface{}{$1.key: $1.val}
}
| members ',' pair
{
$1[$3.key] = $3.val
$$ = $1
}

pair:
String ':' value
{
$$ = pair{key: $1.(string), val: $3}
}

array: '[' elements ']'
{
$$ = $2
}


elements:
{
$$=[]interface{}{}
}
| value
{
$$=[]interface{}{$1}
}
|
elements ',' value
{
$$=append($1, $3)
}

value:
String
| Number
| Literal
| object
{
$$ = $1
}
| array

测试代码见

https://github.com/dingweiqings/study/tree/master/goyacc-study

引用

  1. 龙书 编译原理
  2. yacc使用