Puitar's Blog
0%

Posted on Edited on In ,

自顶向下的分析

  • 从分析树的顶部（根节点）向底部（叶节点）方向构造分析树
  • 可以看成从文法开始符号S推导出词串w的过程

image-20220725082423234

  • 在每一步推导中，都需要做两个选择
    • 替换当前句型中哪一个非终结符
    • 用该非终结符的哪一个候选式进行替换

最左推导

在最左推导中，总是选择每个句型的最左非终结符进行替换

image-20220725082742910

最右归约过程是最左推导的逆过程。

最右推导

最右推导，总是选择每个句型的最右非终结符进行替换

image-20220725083615348

最左推导和最右推导的唯一性

在推导的过程中，可以选择不同的非终结符，因此推导不一定具备唯一性。

但是最左推导和最右推导总是选择最左或者最右的非终结符进行推导，因此最左推导和最右推导是唯一的。

由于分析器总是自左向右扫描字串，因此自顶向下的语法分析总是最左推导。

这个连接讲的非常清楚，可以直接看视频。

image-20220725084344378

自顶向下语法分析的通用形式

image-20220725084542735

预测分析

image-20220725084642107

文法转换

不是所有文法适合自定线下分析

问题1

image-20220725084803497

匹配abc的第一个a的时候，有两个可能的候选项。

问题2

image-20220725085030543

左递归文法会使得递归下降分析器陷入无限循环。因此需要消除左递归

消除直接左递归

image-20220725085616801

消除间接左递归

image-20220725085917479

把S的定义带入到下面的S中，转换成直接左递归的形式，再用直接左递归的消除方法来消除直接左递归。

提取左公因子

文法中的某个符号的多个候选式存在公共前缀的情况

image-20220725090839053

消除左递归和回溯的方法(※)

LL(1)文法

递归下降分析会遇到回溯，会影响效率，如果能预测每一步，就可以避免回溯。LL(1)文法可以使用预测分析技术。

S_文法

image-20220725222323392

image-20220725222535036

在上面的例子中，有两个输入字串，第一个使用空产生式没问题，第二个就有问题。但是不是所有都能使用。

image-20220725222705682

非终结符的后继符号集

image-20220725222900128

产生式的可选集

image-20220725224732986

串首终结符集

image-20220725224941060

写成=>*指可以通过n步推导出来，n可以为0

LL(1)文法

image-20220726104545972

由于LL(1)文法中同一非终结符的各个候选式的SELECT集互不相交，因此可以构造预测分析器

  • 第一个L表示的是从左向右扫描输入
  • 第二个L表示的是产生最左推导
  • “1”表示在每一步中只需要向前看一个输入符号来决定一个输入符号来决定语法分析动作

FIRST集和FOLLOW集的计算

计算（一个）符号X的FIRST(X)

FIRST(X)：可以从X推导出的所有串首终结符构成的集合

如果X=>*ε，那么ε∈FIRST(X)

先看一个例子，注意概念抽象，例子需要着重理解

image-20220726105546013

需要着重理解非终结符的FIRST集的含义。其实就是说这个非终结符能够推导出什么终结符，它们的集合就是FIRST集。如果推导出的是非终结符，那么就和推导出的第一个非终结符的FIRST集相同。

计算串的FIRST集

image-20220726110207539

就是加入最左的一个非终结符的FIRST集合，但是如果这个非终结符可以推导出ε的话，那么就考虑它右边的非终结符。

计算非终结符A的FOLLOW(A)

FOLLOW(A)：可能在耨个句型中紧跟在A后面的终结符的集合

如果A是某个句型的最右符号，那么将结束符“$”加入到FOLLOW(A)中

文法的开始符号本身就是一个句型，所以需要把$加入到开始符号的FOLLOW集中。同时终结符是不考虑空串ε的，所以第一个产生式的T后面跟了E‘，因此T的FOLLOW中应该有E’的FIRST集中的终结符（不包括ε）

这一讲比较难理解，建议看看视频理解

image-20220726113653932

算法如下

image-20220726113636491

这个算法最好在理解的基础上记忆，最好的办法就是能够做一个例题。

例：表达式文法各产生式的SELECT集

image-20220726143426088

第（2）个表达式和第（3）个表达式有相同的左部E‘，但是它们的SELECT集不相交，第（5）个表达式和第（6）个表达式也是如此。因此上面的文法是LL(1)文法。构造预测分析表如下

image-20220726143805504

LL(1）文法的分析方法

  • 递归的预测分析法
  • 非递归的预测分析法

递归的预测分析法

递归的预测分析法是指：在递归下降分析中，编写每一个非终结符对应的过程的时候，根据预测分析表进行产生式的选择

image-20220726144719741

Posted on Edited on In

黑标签统计

实验安排（更新）

基于内存版本

基于内存版本的黑标签统计，在这里不做过多介绍。项目地址

[基于内存黑标签统计]: https://github.com/PUITAR/BlackLabelCount

1
git clone git@github.com:PUITAR/BlackLabelCount.git

基于磁盘版本

由于后续实验需要一个基准baseline，因此这里使用RocksDB作为基准工作的基础。

1_0版本概述

版本设计思路分为两个模块：

  • 小世界模型图生成
  • 小世界模型图的读取和计算

小世界网络生成

[matlab生成小世界网络思路]: https://ww2.mathworks.cn/help/matlab/math/build-watts-strogatz-small-world-graph-model.html

生成的算法如附录B，实验先用已有数据集。

和前面内存版本一样，只是获取一阶好友的方式由从内存取到从磁盘取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @description: 通过点的id从数据库获取一阶好友
 * @param <str_t> k 传入点id作为键
 * @param <DB*> db 传入数据库指针
 * @return <*> 返回一阶好友的数组
 */
vec_t GetFriends1Vec(str_t k, DB* db) {
    str_t v;
    vec_t vec;
    db->Get(ReadOptions(), k, &v);
    stringstream ss(v);
    while (ss >> v)
        vec.push_back(v);
    return vec;
}

由于在数据库中以字节流的形式（字符串）存储，所以需要用stringstream读出每一个一阶好友。

2_0统计结果

该版本是多线程版本，工程文件树和代码放在附录A中，其中计算时间和IO时间单位都是时钟周期数

wiki-topcats

下图是wiki数据集在黑点比例为0.005的情况下，计算总时间和IO所用的时间，其中纵轴单位是时钟周期

[可视化链接]: https://puitar.github.io/echarts/wiki_chart1

下图是wiki数据集在黑点比例为0.005的情况下，IO所用时间占总体计算时间的占比的折线图，纵轴单位是“1”

[可视化链接]: https://puitar.github.io/echarts/wiki_chart2

就wiki的数据集来看，当线程数量较大的时候的计算时间很长，而且IO占总时间的比例很大（大于30%）。但是，随着现成的数量减少，计算时间和IO占比都下降。可以推测，限制计算的瓶颈是磁盘的IO，而磁盘的IO瓶颈在图计算的随机读过程中充分体现，这种现象会随着线程数目的增加而加剧。

twitter-2010

[计算时间和IO时间柱状图]: https://puitar.github.io/echarts/twitter_chart1

[IO时间/计算时间 占比折线图]: https://puitar.github.io/echarts/twitter_chart2

arabic-2005

[计算时间和IO时间柱状图]: https://puitar.github.io/echarts/arabic_chart1

[IO时间/计算时间 占比折线图]: https://puitar.github.io/echarts/arabic_chart2

enwiki-2021

[计算时间和IO时间柱状图]: https://puitar.github.io/echarts/enwiki_chart1

[IO时间/计算时间 占比折线图]: https://puitar.github.io/echarts/enwiki_chart2

论文阅读

HyperANF

文献名称：HyperANF_ Approximating the Neighbourhood Function of Very Large Graphs on a Budget

HyperLogLog（HLL）

参考：HyperLogLog · 语雀 (yuque.com)

Triangle Enumeration

Improving I/O Complexity of Triangle Enumeration

ICDE2023-VEND-524(RevisionOf-37)-C

先看这篇文章Introduction部分Algorithm 2 Trigon的原理，有助于理解

优化版本

伪代码

  • 需要两种边集文件

    • Partition文件：对边以目的点进行排序（分interval）
    • Edges：对边以源点进行排序（不分interval）

  • 对于边集E的某个子集Esub的两种操作：

    • Esub.first：表示边集的源点集合
    • Esub.second：表示边集的目的点集合

  • 一个映射函数：

    FindTwoHopRange(S[i], P[i])：找到P[i]中起点在S[i]中的边的中点集合

  • 函数Union(1, p, R)的含义是

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 求点v的二阶范围内所有点，带去重效果 */
function FindTwoHopNeighbors(v) {
	Nv ← Edges[v].second;						// 从Edges文件种读取以v为源点的边集的目的点集合
    for each partition P[i] in PartitionFile {
        S[i] = Nv ∩ P[i].first;					// 找到2阶在400-500范围内的一阶好友
        R[i] = FindTwoHopRange(S[i], P[i]); 	// R[i]是v的在400-500范围内的二阶好友
    }
    Fv = {v} ∪ Nv ∪ Union(1, p, R) 		   	   // 二阶范围所有点为v、一阶好友、二阶好友
    return Fv;
}

/* 统计二阶标签过程 */
compute(v, Fv, lables);

由于上一阶段的统计发现IO占时间为70%到80%，因此FindTwoHopNeighbors可能对IO存在优化，使得整体有优化效果。

附录

附录A

附录A是黑标签统计基于磁盘版本的代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
/*
 * @author: puitar
 * @Description: 版本2.0
 * @Date: 2022-07-30 15:15:11
 * @LastEditTime: 2022-07-30 23:48:14
 * @FilePath: /rocksdb/bkc/2_0.cc
 */

#include <iostream>
#include <assert.h>
#include <fstream>
#include <unordered_map>
#include <string>
#include <vector>
#include <sstream>
#include <thread>
#include <stdlib.h>
#include <time.h>

#include "rocksdb/db.h"
#include "rocksdb/slice.h"
#include "rocksdb/options.h"
#define MAX_MUT_NUM 80


using namespace std;
using ROCKSDB_NAMESPACE::DB;
using ROCKSDB_NAMESPACE::Options;
using ROCKSDB_NAMESPACE::ReadOptions;
using ROCKSDB_NAMESPACE::Status;
using ROCKSDB_NAMESPACE::WriteBatch;
using ROCKSDB_NAMESPACE::WriteOptions;

typedef int ReturnType;
typedef string str_t;
typedef vector<str_t> vec_str_t;
typedef vector<int> vec_int_t;

const char kDBPath[] = "db/data2/";
str_t gTxtPath = "2.txt";

enum ReturValue {
    SUCCESS,
    FAILED,
};

/* 计算全局变量 */
DB* db = nullptr;
vec_int_t result;
vec_str_t visited;
mutex mutexs[MAX_MUT_NUM];
vec_str_t blacks;
int threads = 0;
int bkn = 0;
double io_time = 0;


/**
 * @description: 从txt中读取将图以键值对形式存入数据库，其中键是点id，值是邻接表
 * @param <str_t> gTxtPath txt路径
 * @param <DB*> db 数据库指针
 * @return <*> 若成功返回SUCCESS, 否则返回FAILED
 */
ReturnType Generation(str_t gTxtPath)
{
    Status s;
    ReturnType r = FAILED;
    ifstream fin(gTxtPath);
    str_t k, v;
    unordered_map<str_t, str_t> g;
    while (fin >> k >> v) {
        g[k] += v + " ";
        g[v] += k + " ";
    }
    int n = g.size();
    for (int u = 0; u < n; u++) {
        str_t v = to_string(u);
        s = db->Put(WriteOptions(), v, g[v]);
        if (!s.ok()) return r;
    }
    r = SUCCESS;
    return r;
}


/**
 * @description: Get函数的封装，可以对IO时间进行累加
 * @param <str_t> k 键
 * @param <str_t> &v 值
 * @param <DB*> db 传入数据库指针
 * @return <*>
 */
void MyGet(str_t k, str_t &v) {
    clock_t start_time = clock();
    db->Get(ReadOptions(), k, &v);
    io_time += (double)(clock()-start_time);
}

/**
 * @description: 通过点的id从数据库获取一阶好友
 * @param <str_t> k 传入点id作为键
 * @param <DB*> db 传入数据库指针
 * @return <*> 返回一节好友的数组
 */
vec_str_t GetFriends1Vec(str_t k)
{
    str_t v;
    vec_str_t vec;
    MyGet(k, v);
    stringstream ss(v);
    while (ss >> v)
        vec.push_back(v);
    return vec;
}


/**
 * @description: 线程计算函数
 * @param <int> start 线程的初始黑点
 * @return <*>
 */
void Computation(int start)
{
    for (int u = start; u < bkn; u += threads)
    {
        str_t v = blacks[u];
        vec_str_t friends1 = GetFriends1Vec(v);
        for (auto f1: friends1) {
            int f1_;
            stringstream ss1(f1);
            ss1 >> f1_;
            mutexs[f1_%MAX_MUT_NUM].lock();
            if (visited[f1_] != v) {
                result[f1_]++;
                visited[f1_] = v;
            }
            mutexs[f1_%MAX_MUT_NUM].unlock();
            vec_str_t friends2 = GetFriends1Vec(f1);
            for (auto f2: friends2) {
                int f2_;
                stringstream ss2(f2);
                ss2 >> f2_;
                mutexs[f2_%MAX_MUT_NUM].lock();
                if (visited[f2_] != v) {
                    result[f2_]++;
                    visited[f2_] = v;
                }
                mutexs[f2_%MAX_MUT_NUM].unlock();
            }
        }
    }
}



int main(int argc, char* argv[])
{
    /* 一些必要的声明 */
    Options options;
    Status s;
    options.IncreaseParallelism();
    options.OptimizeLevelStyleCompaction();
    options.create_if_missing = true;
    int rm = 0;   

    // 参数列表有参数则生成图，否则直接计算
    assert(argc == 2);
    gTxtPath = argv[1];   

    assert(DB::Open(options, kDBPath, &db).ok());

/* 产生图 */
generation: 
    cout << "generation start!" << endl;
    assert(Generation(gTxtPath) == SUCCESS);
    cout << "generation finish!" << endl;


/* 计算黑标签过程 */
computation: 
    /* 获取数据库中键值对的数量 */
    uint64_t n;
    db->GetIntProperty("rocksdb.estimate-num-keys", &n);
    cout << "vertex numbers: " << n << endl;
    
    /* 黑标签生成 */
    float p = 0;
    while (p<=0 || p>=1) {
        cout << "black ratio: "; 
        cin >> p;
        cout << p << endl;
    }
    bkn = n*p;
    for (int i = 0; i < bkn; i++) {
        blacks.push_back(to_string(rand()%n));
    }  
    // cout << "blacks:\n";
    // for (auto b: blacks)
    //     cout << b << endl;
    bkn = blacks.size();
    cout << "black numbers: " << bkn << endl;
    
    /* 开始计算 */
    result.resize(n);
    visited.resize(n);

    while (threads <= 0 || threads > MAX_MUT_NUM) {
        cout << "threads: ";
        cin >> threads;
        cout << threads << endl;
    }

    thread pool[threads];
    double total_time;

    clock_t start_time = clock();
    for (int start = 0; start < threads; start++)
    {
        pool[start] = thread(Computation, start);
    }
    for (int start = 0; start < threads; start++)
    {
        pool[start].join();
    }
    total_time = (double)(clock()-start_time);

    /* 输出结果 */
    // cout << "result:" << endl;
    // for (int v = 0; v < n; v++) {
    //     cout << v << ": " << result[v] << endl; 
    // }

    printf("Coputation Time: %.0f CLKs\n", total_time);
    printf("I/O Time: %.0f CLKs\n", io_time);
    rm = system("make rm2");
    cout << "Work Finished!\n\n\n\n" << endl;

    delete db;
    return 0;
}

工程文件树

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
bash-4.2$ tree
.
├── 1_0
├── 1_0.cc
├── 2_0
├── 2_0.cc
├── data		# 用于导入图的txt文件
│   ├── arabic-2005.txt
│   ├── comfriends.txt
│   ├── twitter-2010.txt
│   └── wiki-topcats.txt
├── db			# 数据库，包含不同版本存储图的数据
│   ├── data1
│   └── data2
├── input 		# 输入文件输入各种配置，设置黑标签占比以及运行线程数
│   ├── input_0.00001_1
│   ├── input_0.00001_10
│   ├── input_0.00001_20
│   ├── input_0.00001_40
│   ├── input_0.005_1
│   ├── input_0.005_10
│   ├── input_0.005_20
│   └── input_0.005_40
└── Makefile	# makefile

5 directories, 17 files

附录B

如果需要自己生成小世界网络，则使用该伪代码的算法生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* `Watts-Strogatz`小世界网络生成算法伪码 */
Function SmallWorldNetwork(n, k, p)
Output: 小世界网络图
Require: k是偶数且p∈[0, 1]
begin
	procedure 参数初始化
    	n: 网络节点总数;
        k: 每个节点的边连接数;
        p: 每条边发生重连的概率;
	end
    procedure 初始边连接
    	for 网络中的每一个结点v do
    		将其与所有距离小于等于k/2的其他结点相连; // 要求k为偶数
    	end
    end
    procedure 已有边重连
    	for 网络中的每一条边e do
    		以概率p重连此边; // 要求不能有自环或者重复边
    	end
    end
end

Posted on Edited on In ,

正则表达式

正则表达式（Regular Expression，RE）是一种用来描述正则语言的更紧凑的表示方法

例如：r = a(a|b)*(ε|(.|_)(a|b)(a|b)*)

正则表达式可以由较小的正则表达式按照特定规则递归构造。每个正则表达式r定义（表示）一个语言，记为L(r)。这个语言也根据r的子表达式所表示的语言递归定义。

例子：

  • digit → 0|1|..|9
  • digits → digit digit*
  • 可选小数部分：optionalFraction → .digits|ε
  • 可选指数指数部分：optionalExponent → (E(+|-|ε)digits)|ε
  • number → digits optionalFraction optionalExponent
1
2
# 例子
2	2.15	2.15E+3		2.15E-3		2.15E3		2E-3

有穷自动机

有穷自动机的定义

是对一类处理系统建立的数学模型。这一类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：对过去输入信息处理的状态）。参考有限状态机。

FA的典型例子：电梯控制装置

  • 输入：顾客乘电梯的需求（要达到的楼层号）
  • 状态：电梯所处的层数和运动方向
  • 电梯控制装置不需要记住先前全部的服务要求，只要记住电梯当前所处的状态以及还没满足的所有服务请求。

image-20220724153635370

FA定义（接收）的语言

image-20220724153914512

L(M) = 所有以abb结尾的字母表{a，b}上的串的集合

最长子串匹配原则

image-20220724154114487

所以上面的例子中，输入串中匹配的应该是“<=”和“++”，而不是“<”和“=”或者两个“+”

有穷自动机的分类

确定的有穷自动机(DFA)

image-20220724160205619

image-20220724160540181

转换图和转换表是等价的，所以可以不用转换表来表示状态转移。

非确定的有穷状态机(NFA)

image-20220724160802826

不确定的FA就是，一个状态，沿着标记为a的边出发，不止到达一个状态。例如上面的状态0，沿着a的标记边出发，可以到达状态0和状态1。如果某个状态从一个标记的边出发不能到达任何状态，就把空集放到表项中，例如上面的状态1通过a边，就不能到任何状态。

DFA和NFA的等价性

  • 对于任意的NFA N，存在识别同一语言的DFA D
  • 对于任意的DFA D，存在识别同一语言的NFA N

image-20220724164312824

NFA看起来分析起来要更加直观简单，但是计算机实现DFA要更容易一点

带有“ε-边”的NFA

image-20220724164550054

r = 0*1*2*

image-20220724164719463

DFA的算法实现

前面说到DFA在计算机实现上要比NFA更加容易，下面是它的算法实现

image-20220724164844160

s表示当前状态，如果最后s在接收状态集F中，则表示成功接收。否则到不确定状态了，就回答no。

从正则表达式到有穷自动机

前面说到DFA在计算机上要更容易实现，但是NFA要更加容易分析，所以我们通常先得到NFA，再得到DFA

根据RE(正则表达式)构造NFA

image-20220724165517326

image-20220724165601319

image-20220724165711728

从NFA到DFA的转换方法

image-20220724170114615

方法就是从初始状态开始，到第一个状态A，然后看所有的边，只有a可以进入非空下一状态，所以A通过a进入状态{A,B}，也就是DFA中的A,B状态；然后看状态A和状态B的所有边，首先是a，可以进入{A,B}和∅，它们的并集就是{A,B}，所以状态A,B可以通过a边进入自身，同理通过b可以进入{B,C}和∅的并集，所以状态A,B通过b边进入状态B,C；然后看状态B,C，方法和前面一样，最后得到通过b进入自身，通过c进入状态C,D；状态C,D是终止状态，只能通过c进入自身。

最多只能进入到自身的状态就是终止状态太。不能进入到自身的状态同时不需要任何条件进入下一状态的一般是起始状态，这列的start就是自动进入状态A的

如果类似于C,D状态这种状态，它包含在NFA中的终止状态D，那么在DFA中C,D状态就是终止状态

在看一个例子

image-20220724171239688

注意到，这里有三个终止状态，也就说DFA可以不止一个终止状态。只要包含NFA中的终止状态的状态就是DFA中的终止状态。

子集构造法

由于从NFA构造的DFA中的每一个状态都是NFA中状态集合的一个子集，因此NFA转换成DFA的算法又称作子集构造法

这里伪代码就不写了，感兴趣可以搜索一下，原理上面都讲过了。

识别单词的DFA

image-20220724172022748

image-20220724172239405

通过上面NFA转DFA的方法，可以画出DFA

image-20220724173247829

识别各进制无符号整数的DFA

image-20220724173527397

识别注释的DFA

image-20220724173810908

识别Token的DFA

image-20220724173906227

把上面讲的各类识别的DFA合到一个DFA下，就可以构造一个识别Token的DFA，可以识别不同类型单词的DFA，就达到了我们这一节的识别单词的DFA的目的

这里没有提到关键字，但是可以用上图标志符（IDN）的识别方法。如果识别出来一个标识符它是在关键字表里面的就把他识别成一个关键字，否则就照常识别成一个标识符。

词法分析阶段的错误处理

image-20220724174231290

image-20220724174318518

最简单的错误恢复策略是“恐慌模式（panic mode）”恢复：

从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符位置

Posted on Edited on In ,

词法语法分析基本概念

字母表

字母表（Alphabet）：字母表∑是一个有穷符号集合

  • 符号：字母、数字、标点符号、…

例如：

  • 二进制字母表：{0，1}
  • ASCII字符集
  • Unicode字符集

字母表的运算

  • 字母表$∑_1$和$∑_2$的乘积

    image-20220706001340805

  • 字母表的n次幂

image-20220706001746142

  • 字母表的正闭包运算

image-20220706001834961

  • 字母表的克林闭包

image-20220706001936935

串

设∑是一个字母表，任意x∈∑*（克林闭包），x称为是∑上的一个串

由此可见，串是字母中符号的一个又穷序列

串s的长度，通常记为|s|，是指s中符号的个数

  • 例如|aab| = 3

空串是长度为0的串，用ε（epsilon）表示

  • |ε| = 0

串上的运算——连接

x和y是两个串，x和y的连接时把y附加到x的后面形成的串，记为xy

  • 例如x = dog且y = house，则xy = doghouse

空串时连接运算的单位元，即，对于任何串s有，εs = sε = s

image-20220706002929267

串上的运算——幂运算

image-20220706003037100

文法的定义

文法概述

image-20220706093506887

image-20220706093617730

image-20220706093821496

PS：E表示的是表达式

产生式的简写

image-20220706094045868

符号约定

image-20220706094125505

image-20220706094210869

image-20220706094418507

类型 示例 补充说明 示例
终结符 a,b,c 终结符号串 u,v,…,z
非终结符 A,B,C
文法符号 X,Y,Z 文法符号串 α,β,γ

语言的定义

推导和归约

image-20220707070400509

image-20220707070547641

推导和规约的例子

例句：little boy eats apple.

image-20220707070757275

句型和句子

image-20220707070943358

image-20220707071112194

可以产生无穷个句子，也就是说，文法解决了“无穷语言的有穷表达形式”。

文法定义标识符的例子

image-20220707071406429

课上提出的问题：请写出无符号整数和浮点数的文法定义

1
2
3
4
/* 无符号整数的文法定义 */
S->0|D(D∪0)*
D->1|2|3|...|9
PS: 无符号整数实际上就是0和非零数构成的，所以S由0和(D∪0)*[非零数]构成
1
2
3
4
5
6
7
/* 浮点数的文法定义 */
S->MFNE
N->.|ε	// 整数还是小数
M->+|-	// 符号
E->ED|ε // 任意长度的数字串或空串
F->FD|D // 非零长度数字串(浮点数非空)
D->0|1|...|9

文法的运算

image-20220707074537980

文法的分类

0型文法

image-20220707074702293

1型文法（上下文有关文法）

image-20220707074803369

2型文法（上下文无关文法）

image-20220707074916160

3型文法（正规文法）

image-20220707075219571

四种文法的关系

image-20220707075342222

判断文法类型
有文法G为：A->ε|aB，B->Ab|a，请判断文法G属于哪一类文法？
解题思路: 第一步：判断是否是0型文法，推导式左边是否至少包含一个非终结符，如果满足，则符合0型文法，；第二步：判断是否是1型文法：推导式右边的长度是否大于等于推导式左边的长度，如果满足，则符合1型文法；第三部：判断是否是2型文法，推导式左边是否是非终结符，如果满足，则符合2型文法；第四步：判断是左线性还是右线性，同时满足则不符合，只能是左线性和或者右线性中一个。
答案：2型文法

CFG的分析树

正则文法可以满足程序设计语言中的几乎所有单词构造，但是生成能力有限，不能满足句子构造。所以退而求其次，我们研究上下文无关文法的分析树。

分析树

image-20220707075704552

分析树是推导的图形化表示！

image-20220707075918441

（句型的）短语

image-20220707080434612

  • 直接短语一定是某一个产生式的右部
    • 例如下面的“提高|人民|生活|水平”都是直接短语，都是④或者⑤的右部
  • 产生式的右部不一定是给定句型的直接短语
    • 例如“高人|民生|活水”，虽然是右部但是不是直接短语

image-20220707080733037

这是由于，句型只是这个文法的一个特例模板，不一定式所有的右部的定义都用的上的。

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的

让我们直接看一个例子，给定下面的文法和一个给定的句型，可以构造这个句型的两个分析树。

image-20220707081301716

image-20220707081322485

由于这个文法可以为这个句型，构造两个分析树，所以称为二义性文法。大多数编译器都希望不要有二义性文法。因此要对文法进行改造，但是要付出代价，下面看看如何改造。

上面产生歧义的源头是：有两个if但是只有一个else！这使得else可以和两个if中的任意一个匹配。

大多数程序设计语言中都有这样的消歧规则：每一个else和最近的尚未匹配的if匹配。

因此引入这条规则上面两棵分析树只能保留左边的分析树。

image-20220707082156672

Posted on Edited on In ,

什么是编译

计算机程序设计语言以及编译

  • 机器语言
    • 可以被计算机直接理解
    • 二进制和十六进制
    • 编写阅读困难
  • 汇编语言
    • 引入注记符
    • 依赖于特定机器
    • 书写效率低
  • 高级语言
    • 类似数学定义和自然语言
    • 更接近人类习惯
    • 不依赖特定机器
    • 简洁

将高级语言翻译成汇编语言或者直接翻译成机器语言的过程称为编译。

将汇编语言翻译成机器语言的称为汇编。

编译的定义：将高级语言（源语言）翻译成汇编语言或机器语言（目标语言）的过程。

编译器在语言处理系统的位置

image-20220630224930676

  • 预处理器把存在不同文件中的源程序聚合在一块，把称为宏的编写语句转换为原始语句

  • 加载器修改可重定位地址：将修改后的指令和数据放到内存中适当的位置

  • 链接器将多个可重定位的机器代码文件（包括库文件）链接在一块，解决外部内存地址（引用其他文件对象或过程）问题

  • 可重定位：在内存中存放的起始位置L不是固定的

编译系统的结构

高级语言程序 =》编译器 =》机器语言

下面是编译的流程图，编译过程，编译器主要进行如下步骤

image-20220704135027449

词法分析

原理概述

词法分析是编译器的第一个阶段。

词法分析的主要任务：从左向右进行扫描源程序的字符，识别出各个单词，确定单词类型。将识别出的单词转换成统一的机内表示——词法单元（token）形式

token：<种别码，属性值>

  • 种别码是单词的种类（词性词类）
  • 属性值是区分同一种别的标识，具体来说就是存储字面值

image-20220704135633686

词法分析例子

image-20220704140102740

  • while是一个关键字，一词一码，种别码就可以唯一确定这个单词，所以属性值空。同样的道理，左括号、不等号、右括号、左花括号、++、封号、右花括号 他们都是一词一码，所以属性值空。
  • value和num是两个标识符，还有100是常量，仅仅凭借种别码不能唯一确定，所以在属性值中放入他们的字面值，来唯一确定他们。

语法分析

语法分析是编译的第二个阶段。

语法分析的主要任务：语法分析器(parser)从词法分析输出的token序列中识别出各类短语，并构造语法分析树(parse tree)

语法分析树描述了程序语句的语法结构

例1：赋值语句的语法分析树

1
position = initial + rate * 60;

经过词法分析我们可以得到对应的token序列

1
2
  position    =   initial    +   rate    *   60;
<id,position><=><id,initial><+><id,rate><*><num,60>

我们可以的到语法分析树：

image-20220704141928523

  • 一个标识符和一个常数，它们本身可以构成表达式。一个表达书通过运算符，例如“+、*”又可以构成另外一个表达式。
  • 标识符连接上一个赋值符号再连接上一个表达式最后连接一个封号可以构成赋值语句。

例2：变量声明语句的分析树

  • 文法，文法是一系列规则构成的：

    • 这里的D表示declaration，表示声明语句
    • T是type，表示类型
    • IDS是identifier sequence，表示标识符序列
    1
    2
    3
    4
    5
    6
    <D>-><T><IDS>;
    一个声明语句是由一个类型连接上一个标识符序列和一个封号构成
    <T>->int|real|char|bool
    类型可以是int，real，char，bool中的一个
    <IDS>->id|<IDS>,id
    一个标识符id本身可以构成一个标识符序列；一个标识符序列和一个id通过","连接起来，可以构成一个更大的标识符序列

  • 根据上面的文法，我们输入：

    1
    int a,b,c;

    可以得到它的分析树

    image-20220704143428661

语义分析

语义分析是编译的第三个阶段

语义分析的主要任务：

  • 收集标识符的属性信息
  • 语义检查

收集标识符属性信息

标识符的属性

标识符都有哪些属性呢？

  • 种属（Kind）

    • 简单变量、复合变量（数组、记录、…）、过程、…

  • 类型（Type）

    • 整型、实型、字符型、布尔型、指针型、…

  • 存储位置、长度

    image-20220704144057609

  • 值

  • 过程的作用域
  • 参数和返回值信息
    • 参数个数、参数类型、参数传递方式、返回值类型、…

符号表

image-20220704144846519

语义分析的到的标识符的信息都会存放在符号表中。

上面的表中，每一行，称为符号表的一条记录。每一个标识符都会对应一条记录。每一个字段就对应了标识符的一个属性，比如类型type、种属kind等。

符号表通常带有一个字符串表，存放程序中用到的标识符和常字符串。

NAME分成两部分，一部分存放标志符在字符串表中的起始位置，另一部分用来存放标识符的长度。

语义检查

语义分析主要包括如下工作

  • 变量或过程未经声明就使用
  • 变量或过程名重复声明
  • 运算分量类型不匹配（可能进行强制类型转换）
  • 操作符和操作数的类型不匹配
    • 数组下标不是整数
    • 对非数组变量使用数组访问操作符
    • 对非过程名使用调用操作符
    • 过程调用的参数类型或数目不匹配
    • 函数返回类型有错误

中间代码生成和编译器后端

中间代码生成

常用的中间表示形式

  • 三地址码（Three-address Code）

    • 三地址码由类似于汇编的指令序列组成，每个指令最多有三个操作数（operand）

    • 常用的三地址指令

      image-20220704150228720

      • 地址可以具有如下形式之一
        • 源程序中的名字（NAME）
        • 常量（constant）
        • 编译器生成的临时变量

    • 三地址指令表示

      • 四元式（Quadruples）

        • （op，y，z，x）

        image-20220704151132100

        从上面的示例，我们可以看出：三地址指令序列唯一确定了一个运算完整的顺序

      • 三元式（Triples）

      • 间接三元式（Indirect triples）

  • 语法结构树/语法树（Syntax Trees）

    • 请注意这里的的语法结构树和起那面的语法分析树不是一回事

中间代码生成的例子

image-20220704151743975

右边的式中间代码，左边的式语法结构树。

其中左边的树中：S是中间代码集合，B是判断语句，E是表达式

目标代码生成

image-20220704153054925

  • 目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言
  • 目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器

代码优化

为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些、或者两者兼顾

包括例如：自动识别代码中得重复运算

Posted on In ,

红外协议

image-20220701164207348

由于目前能够使用的STC单片机库的红外传输一次只能传输10 bits，因此一种比较合理的并且安全稳定的设计方法是按位进行编码。编码设计如上

各个位功能说明

  • 选择位
    • 选择位可以进行类别的选择选择某一类指令或者是一个数据
      • 选择位最高位是0，标识为数据，此时使用偶校验
      • 选择位最高位是1，标识为指令，此时使用奇校验
  • 指令位
    • 指令位共有6位，可以进行自主设计
    • 如果选择位最高位是0，标识是数据，则选择位的低两位作为数据为和指令位6位连接成一个字节
    • 如果最高位是1，则是指令，在这个基础上选择位还有四位所以一共可以分成四大类的指令，如果还要细分，可以在指令位中进行进一步划分
  • 奇偶校验位
    • 奇偶校验位是根据选择位的最高位来决定的
    • 同时奇偶校验位对自己以外的前9位进行计算
    • 因此选择位最高位会对奇偶校验位的方式进行选择，奇偶校验位又会对包括选择位最高位在内的所有位进行校验，这种方式能够稳定传输

具体位功能设计这里不强制说明，由使用者编写。

Posted on In ,

可变调蜂鸣器工程

这一次出现蜂鸣器的使用如果是C语言版本要如何使用，如果是BSP版本，参考上一篇博文。

这里涉及到了定时器，定时器实际上是对单片机的机器周期进行计数，就是一个计数器，定时器设置一个初值，然后在初值上累加，直到溢出，一但溢出就产生中断。这里通过调整初值，改变时钟周期的长短。每一个时钟周期会产生蜂鸣器翻转，反转时间长短变化音调变化。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**********************
myBeep2 可变调蜂的鸣器
型号:STC15F2K60S2 主频:11.0592MHz
************************/
#include <STC15F2K60S2.H>
#define uint  unsigned int
#define uchar unsigned char

/*---------引脚别名定义---------*/
sbit sbtBeep = P3 ^ 4;                  //蜂鸣器引脚
sbit sbtKey1 = P3 ^ 2;                  //按键1引脚
sbit sbtKey2 = P3 ^ 3;                  //按键2引脚
sbit sbtSel0 = P2 ^ 0;                  //位选信号位
sbit sbtSel1 = P2 ^ 1;                  //位选信号位
sbit sbtSel2 = P2 ^ 2;                  //位选信号位
sbit sbtSel3 = P2 ^ 3;                  //LED与数码管显示的控制位

/*---------变量定义---------*/
uint sbtKey1_state = 0;         //0：Key1未按下         1：Key1已按下
uint sbtKey2_state = 0;         //0：Key2未按下         1：Key1已按下
bit  btBeepFlag;                //控制蜂鸣器开关的标志位
uint uiToneNum = 0;             //音调
uchar arrSegSelect[] = {
    0x3f, 0x06, 0x5b, 0x4f, 0x66, 0x6d, 0x7d, 0x07,
    0x7f, 0x6f, 0x77, 0x7c, 0x39, 0x5e, 0x79, 0x71
}; //段选0-f

/*---------初始化函数--------*/
void Init()
{
    P0M0 = 0xff;
    P0M1 = 0x00;
    P2M0 = 0x08;
    P2M1 = 0x00;
    //设置P3^4为推挽模式
    P3M1 = 0x00;
    P3M0 = 0x10;						//P3第四位设置为推挽输出模式

    AUXR |= 0x80;                       //定时器时钟1T模式
    TMOD &= 0xF0;                       //设置定时器模式为16位自动重装
    TL0 = 0xCD;                         //设置定时初值
    TH0 = 0xF4;                         //设置定时初值
    TF0 = 0;                            //清除TF0标志
    TR0 = 1;                            //定时器0开始计时

    btBeepFlag = 0;
    P0 = 0x00;                          //数码管和LED显示清零

    sbtSel0 = 1;                        //位选设置为第七位
    sbtSel1 = 1;
    sbtSel2 = 1;

    sbtBeep = 0;                        //蜂鸣器引脚置0，以保护蜂鸣器
    ET0 = 1;
    EA = 1;
}

/*---------延时子函数--------*/
void DelayMs( uint xms )
{
    uchar i;
    for( ; xms > 0; xms-- )
        for( i = 114; i > 0; i-- )
        {
            ;
        }
}

/*---------显示子函数--------*/
void DisplaySeg7Led()
{
    P0 = 0;
    sbtSel3 = 0;
    P0 = arrSegSelect[uiToneNum];
    DelayMs( 1 );

    P0 = 0;
    sbtSel3 = 1;
    P0 = 0x08;
    DelayMs( 1 );
}

/*---------主函数--------*/
void main()
{
    Init();
    while( 1 )
    {
        if( sbtKey1 == 0 )
        {
            if( sbtKey1_state == 0 )        //判断按键1是否按下
            {
                DelayMs( 10 );              //延时消除抖动
                if( sbtKey1 == 0 )
                {
                    uiToneNum++;            //声调改变
                    if( uiToneNum == 10 )
                        uiToneNum = 0;
                    TH0 = 0xF4 - uiToneNum; //减小重装值，从而减小
                    						//定时器中断（蜂鸣器振动）频率
                    sbtKey1_state = 1;      //设置按键1为已按下
                }
            }
        }
        else
            sbtKey1_state = 0;

        if( sbtKey2 == 0 )
        {
            if( sbtKey2_state == 0 )          //判断按键2是否按下 
            {
                DelayMs( 10 );                //延时消除抖动
                if( sbtKey2 == 0 )
                {
                    btBeepFlag = !btBeepFlag; //蜂鸣器开关切换
                    sbtKey2_state = 1;        //设置按键1为已按下
                }
            }
        }
        else
            sbtKey2_state = 0;

        DisplaySeg7Led();
    }
}

/*---------T0定时器中断服务处理函数--------*/
void T0_Process() interrupt 1
{
    if( btBeepFlag )
    {
        sbtBeep = ~sbtBeep;            //产生方波使得蜂鸣器发声
    }
    else
        sbtBeep = 0;                  //如果开关关闭,则蜂鸣器断电以保护蜂鸣器
}

Posted on In ,

三按键测试

文件结构说明

image-20220630084706907

在前几个实验的基础上，增加了key.h和beep.h

KEY.H头文件

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
/**********************************key V2.0 说明 ************************************************************************
Key模块用于获取“STC-B学习板”上三个按键的状态。提供按键模块加载和一个应用函数,一个“按键事件：enumEventKey：
  (1) KeyInit()：按键模块加载函数；
  (2) char GetKeyAct(char Key)：获取按键状态。
        函数参数：Key，指定要获取状态的按键。Key取值：
						enumKey1
						enumKey2
						enumKey3    
    			（当参数取值超出有效范围，函数将返回fail）
        函数返回值：
						enumKeyNull（无按键动作）
						enumKeyPress（按下）
						enumKeyRelease（抬起）
						enumKeyFail（失败） 
	  	返回值是经过多次检测按键实时状态和统计检测结果后（软件消抖）的有效事件。
    	每个按键查询一次后,事件值变成enumKeyNull。事件值仅查询一次有效。
  (3) 按键事件：enumEventKey
      当三个按键（enumKey1,enumKey2,enumKey3）中任意一个按键有”按下“或”抬起“动作时，将产生一个”按键事件“，
      响应按键事件的用户处理函数由用户编写,并有sys中提供的SetEventCallBack函数设置.	 
      补充说明：如果启用了ADC模块，按键3（Key3）任何操作在本模块不可检测到和有任何信息反应，
      这时按键3（Key3）任何操作将在  ADC模块中检测和反应。使用方法相同，具体见ADC模块说明。	
*/

#ifndef _key_H_
#define _key_H_

extern void KeyInit();
extern unsigned char GetKeyAct(char Key) ; //获取按键enumKey1,enumKey2,enumKey3事件
//返回值：enumKeyNull——无，enumKeyPress——下降沿，enumKeyRelease——上升沿，enumKeyFail——错误
enum KeyName     {enumKey1,enumKey2,enumKey3};                          //按键名
enum KeyActName  {enumKeyNull,enumKeyPress,enumKeyRelease,enumKeyFail}; //按键动作名

#endif

BEEP.H

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
/**
Beep V2.0 说明 
Beep用于控制“STC-B学习板”上无源蜂鸣器的发声。Beep模块共提供1个驱动函数、2个应用函数：
  (1)  BeepInit(): 蜂鸣器模块驱动函数
  (2)  Set_Beep(unsigned int Beep_freq, unsigned char Beep_time): 控制蜂鸣器发声，非阻塞型
	   函数参数：
       Beep_freq：指定发声频率，单位Hz。小于10将无输出  
	   Beep_time：指定发声时长。发声时长＝10*Beep_time(mS)，最长 655350mS
	   函数返回值：enumSetBeepOK：调用成功，enumSetBeepFail：调用失败（或因蜂鸣器正在发音）	 
  (3)  GetBeepStatus(void): 获取Beep当前状态,enmuBeepFree:空闲, enumBeepBusy ,正在发音
  (4)  Beep模块使用了STC内部CCP模块1通道
*/

#ifndef _beep_H_			
#define _beep_H_		

extern void BeepInit();	// 蜂鸣器初始化

extern char SetBeep(unsigned int Beep_freq, unsigned int Beep_time);   
// 发指定频率声音， 发声时长＝10×Beep_time	  (mS)  ，最长 655350mS
// Beep_freq < 10 Hz, 不发音
// 函数返回 enumSetBeepOK：调用成功，   enumSetBeepFail：调用失败（调用时正在发音）

extern unsigned char GetBeepStatus(void); // 获取状态,enumBeepFree:自由, enumBeepBusy,正在发声

enum BeepActName {enumBeepFree=0,enumBeepBusy,enumSetBeepOK,enumSetBeepFail}; 

#endif

BSP版本主函数逻辑

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
#include "STC15F2K60S2.H"        //必须。
#include "sys.H"                 //必须。
#include "displayer.H" 
#include "key.H" 
#include "beep.H" 

code unsigned long SysClock=11059200; //必须。定义系统工作时钟频率(Hz)，用户必须修改成与实际工作频率（下载时选择的）一致
#ifdef _displayer_H_                  //显示模块选用时必须。（数码管显示译码表，用戶可修改、增加等） 
code char decode_table[]={
    0x3f,
    0x06,
    0x5b,
    0x4f,
    0x66,
    0x6d,
    0x7d,
    0x07,
    0x7f,
    0x6f,
    0x00,
    0x08,
    0x40,
    0x01, 
    0x41, 
    0x48, 
    0x3f|0x80,
    0x06|0x80,
    0x5b|0x80,
    0x4f|0x80,
    0x66|0x80,
    0x6d|0x80,
    0x7d|0x80,
    0x07|0x80,
    0x7f|0x80,
    0x6f|0x80 
};  
#endif

char a;

void myKey_callback()
{ 
    char k;
    SetBeep(1000,10); // BEEPing
    
    /* 根据按键设置LED */
    k=GetKeyAct(enumKey1);
    if( k == enumKeyPress ) a |=0x01;
    else if( k == enumKeyRelease ) a &=~0x01;
    k=GetKeyAct(enumKey2);
    if( k == enumKeyPress ) a |=0x02;
    else if( k == enumKeyRelease ) a &=~0x02;
    k=GetKeyAct(enumKey3);
    if( k == enumKeyPress ) a |=0x04;
    else if( k == enumKeyRelease ) a &=~0x04;
}

void my10mS_callback()
{ 
    LedPrint(a);
}

void main() 
{ 
    DisplayerInit();  
    KeyInit();
    BeepInit();
    SetDisplayerArea(0,7);	
    Seg7Print(1,2,3,4,5,6,7,8);	
    SetEventCallBack(enumEventSys10mS, my10mS_callback);
    SetEventCallBack(enumEventKey, myKey_callback);
    // 循环等待事件
    MySTC_Init();
    while(1)             	
    { 
        MySTC_OS();    
    }	             
}

C版本

没有蜂鸣器。没有数码管。过于简单，按下按键，对应的LED亮起。

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
/**********************
        三按键测试
型号:STC15F2K60S2 主频:11.0592MHz
************************/
#include <STC15F2K60S2.H>

/*---------引脚别名定义---------*/
sbit sbtKey1 = P3 ^ 2;
sbit sbtKey2 = P3 ^ 3;
sbit sbtKey3 = P1 ^ 7;
sbit sbtLedSel = P2 ^ 3;

/*---------初始化函数---------*/
void Init()
{
    //推挽输出
    P0M0 = 0XFF;
    P0M1 = 0X00;
    P2M0 = 0X08;
    P2M1 = 0X00;
    sbtLedSel = 1;          //选择让LED灯发光,可以不设置，默认为1
    P0 = 0;                 //初始化P0，让LED灯全部熄灭
}

/*---------主函数---------*/
void main()
{
    Init();
    while( 1 )
    {
        if( sbtKey1 == 0 )  //检测按键1是否被按下
            P0 |= 0x01;     //按下则L0发光
        else
            P0 &= ~0x01;    //否则L0熄灭

        if( sbtKey2 == 0 )  //检测按键2是否被按下
            P0 |= 0x02;     //按下则L1发光
        else
            P0 &= ~0x02;    //否则L1熄灭

        if( sbtKey3 == 0 )  //检测按键3是否被按下
            P0 |= 0x04;     //按下则L2发光
        else
            P0 &= ~0x04;    //否则L2熄灭
    }
}

Posted on In ,

八位数码管滚动显示

如果又看明白的请会看之前的博文。

BSP库版本

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
#include "STC15F2K60S2.H"       
#include "sys.H"                 
#include "displayer.H" 

code unsigned long SysClock=11059200;         
#ifdef _displayer_H_                         
code char decode_table[]={
    0x3f,
    0x06,
    0x5b,
    0x4f,
    0x66,
    0x6d,
    0x7d,
    0x07,
    0x7f,
    0x6f,
    0x00,
    0x08,
    0x40,
    0x01, 
    0x41, 
    0x48,                			
    0x3f|0x80,
    0x06|0x80,
    0x5b|0x80,
    0x4f|0x80,
    0x66|0x80,
    0x6d|0x80,
    0x7d|0x80,
    0x07|0x80,
    0x7f|0x80,
    0x6f|0x80 
}; 
#endif
/* 上面的和之前的完全一致 */

/** 
 * 回调函数 
 * 滚动显示0123456789，八位数码管显示如下:
 * i = 0: 0 1 2 3 4 5 6 7 
 * i = 1: 1 2 3 4 5 6 7 8
 * i = 2: 2 3 4 5 6 7 8 9
 * ...
 */
void my1S_callback()
{ 
    static unsigned char i=0;
    code char a[10]={0,1,2,3,4,5,6,7,8,9};
    Seg7Print(           	
        a[i%10],
        a[(i+1)%10],
        a[(i+2)%10],
        a[(i+3)%10],
        a[(i+4)%10],
        a[(i+5)%10],
        a[(i+6)%10],
        a[(i+7)%10]
    );	
    i++;
}

void main() 
{ 
    DisplayerInit(); // 初始化显示设备
    SetDisplayerArea(0,7); // 设置显示数码管是0-7
    LedPrint(0); // LED灯不显示
    SetEventCallBack(enumEventSys1S, my1S_callback); // 没一秒钟回调一次函数，让数码管从右向左滚动
    /* 初始化系统，并循环捕捉事件 */
    MySTC_Init();	    
    while(1)             	
    { 
        MySTC_OS();    
    }	             
}

C语言版本

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
/**********************
mySeg7Shift 八位数码管滚动显示
型号:STC15F2K60S2 主频:11.0592MHz
************************/
#include "STC15F2K60S2.H"
#define uint unsigned int
#define uchar unsigned char

/*---------引脚别名定义---------*/
//位选的三个引脚控制位
//起始就是位选信息，用来选择显示哪一个数码管显示
sbit sbtSel0 = P2 ^ 0; 
sbit sbtSel1 = P2 ^ 1; 
sbit sbtSel2 = P2 ^ 2; 

/*---------变量定义---------*/
//show_wi(i=1,2,3,4,……,8)分别是对应左到右的各个数码管上的显示的数字
uchar ucDig1Tmp;
uchar ucDig2Tmp;
uchar ucDig3Tmp;
uchar ucDig4Tmp;
uchar ucDig5Tmp;
uchar ucDig6Tmp;
uchar ucDig7Tmp;
uchar ucDig8Tmp;
uchar ucSeg7State;
uchar ucCount;

//段选，显示0-f
uchar arrSegSelect[] = {
    0x3f, 
    0x06, 
    0x5b, 
    0x4f, 
    0x66, 
    0x6d, 
    0x7d, 
    0x07, 
    0x7f, 
    0x6f, 
    0x77, 
    0x7c, 
    0x39, 
    0x5e, 
    0x79, 
    0x71, 
    0x40, 
    0x00
}; 

//位选,选择是0-7中的一个数码管
uchar arrDigSelect[] = {
    0x00, 
    0x01, 
    0x02, 
    0x03, 
    0x04, 
    0x05, 
    0x06, 
    0x07
}; 

/*---------初始化函数---------*/
void Init()
{
    //P0，P2都设置为推挽输出
    P2M0 = 0xff;
    P2M1 = 0x00;
    P0M0 = 0xff;
    P0M1 = 0x00; 

    ucSeg7State = 0;
    ucCount = 0;

    //最开始数码管从左到右显示0-7
    ucDig1Tmp = 0; 
    ucDig2Tmp = 1;
    ucDig3Tmp = 2;
    ucDig4Tmp = 3;
    ucDig5Tmp = 4;
    ucDig6Tmp = 5;
    ucDig7Tmp = 6;
    ucDig8Tmp = 7;

    // 这一部分是相应的设置，在BSP版本中，放在了MySTC_Init()中
    TMOD = 0x01;             		//定时器0，方式1
    ET0 = 1;                  		//开启定时器中断
    TH0 = ( 65535 - 1000 ) / 256; 	//定时器0的高八位设置
    TL0 = ( 65535 - 1000 ) % 256; 	//定时器0的低八位设置，这里总体就是设置定时器0的初始值是1ms
    TR0 = 1;                 		//启动定时器
    EA = 1;                  		//打开总的中断
}

/*---------定时器T0中断服务函数---------*/
void T0_Process() interrupt 1     	//把数码管的显示提到中断里面来了，所以每次中断就运行这个函数
{
    TH0 = ( 65535 - 1000 ) / 256; 	//重新装载定时器0的初始值，为了下一次定时器溢出准备
    TL0 = ( 65535 - 1000 ) % 256;
    ucSeg7State++;         			//这变量两个作用：具有下面分频作用，和扫描过程中显示第ucSeg7State个数码管的作用
    if( ucSeg7State == 8 )    		//进行分频，每中断八次才让ucCount的值加一次
    {
        ucSeg7State = 0;
        ucCount++;
    }
    if( ucCount == 100 )     //考虑到扫描频率很高这里再次分频，ucCount加到100才执行
    {
        //让从左到右各个数码管上的数字都加一
        ucCount = 0;
        ucDig1Tmp++;     
        ucDig2Tmp++;
        ucDig3Tmp++;
        ucDig4Tmp++;
        ucDig5Tmp++;
        ucDig6Tmp++;
        ucDig7Tmp++;
        ucDig8Tmp++;
    }
    P0 = 0;                       		//让数码管显示更加好，不受上一次P0赋的值的影响
    P2 = arrDigSelect[ucSeg7State];   	//位选，选第ucSeg7State个数码管
    switch( ucSeg7State )           	//每次中断显示一个数码管来显示
    {
        case 0:
            P0 = arrSegSelect[ucDig1Tmp % 10];
            break;//从左到右，第一个数码管显示
        case 1:
            P0 = arrSegSelect[ucDig2Tmp % 10];
            break;//从左到右，第二个数码管显示
        case 2:
            P0 = arrSegSelect[ucDig3Tmp % 10];
            break;//从左到右，第三个数码管显示
        case 3:
            P0 = arrSegSelect[ucDig4Tmp % 10];
            break;//从左到右，第四个数码管显示
        case 4:
            P0 = arrSegSelect[ucDig5Tmp % 10];
            break;//从左到右，第五个数码管显示
        case 5:
            P0 = arrSegSelect[ucDig6Tmp % 10];
            break;//从左到右，第六个数码管显示
        case 6:
            P0 = arrSegSelect[ucDig7Tmp % 10];
            break;//从左到右，第七个数码管显示
        default:
            P0 = arrSegSelect[ucDig8Tmp % 10];
            break;//从左到右，第八个数码管显示
    }
}

/*---------主函数---------*/
void main()
{
    Init(); //初始化
    // 死循环，防止程序运行完，单片机挂掉
    while( 1 )
    {
    }
}