-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
1988 lines (1485 loc) · 115 KB
/
index.html
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
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh">
<head><meta name="generator" content="Hexo 3.9.0">
<meta charset="utf-8">
<title>MechDancer - 机械舞者</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="keywords" content="MechDancer">
<meta property="og:type" content="website">
<meta property="og:title" content="MechDancer - 机械舞者">
<meta property="og:url" content="http://mechdancer.org/index.html">
<meta property="og:site_name" content="MechDancer - 机械舞者">
<meta property="og:locale" content="zh-CN">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="MechDancer - 机械舞者">
<link rel="icon" href="/css/images/favicon.png">
<link rel="stylesheet" href="/libs/font-awesome5/css/fontawesome.min.css">
<link rel="stylesheet" href="/libs/font-awesome5/css/fa-brands.min.css">
<link rel="stylesheet" href="/libs/font-awesome5/css/fa-solid.min.css">
<link rel="stylesheet" href="/libs/open-sans/styles.css">
<link rel="stylesheet" href="/libs/source-code-pro/styles.css">
<link rel="stylesheet" href="/css/style.css">
<script src="/libs/jquery/2.1.3/jquery.min.js"></script>
<link rel="stylesheet" href="/libs/lightgallery/css/lightgallery.min.css">
<link rel="stylesheet" href="/libs/justified-gallery/justifiedGallery.min.css">
</head>
</html>
<body>
<div id="container">
<header id="header">
<div id="header-main" class="header-inner">
<div class="outer">
<a href="/" id="logo">
<i class="logo"></i>
<span class="site-title">MechDancer - 机械舞者</span>
</a>
<nav id="main-nav">
<a class="main-nav-link" href="/.">主页</a>
<a class="main-nav-link" href="/archives">归档</a>
<a class="main-nav-link" href="/categories">分类</a>
<a class="main-nav-link" href="/tags">标签</a>
<a class="main-nav-link" href="/about">关于</a>
</nav>
<div id="search-form-wrap">
<form class="search-form">
<input type="text" class="ins-search-input search-form-input" placeholder="搜索" />
<button type="submit" class="search-form-submit"></button>
</form>
<div class="ins-search">
<div class="ins-search-mask"></div>
<div class="ins-search-container">
<div class="ins-input-wrapper">
<input type="text" class="ins-search-input" placeholder="想要查找什么..." />
<span class="ins-close ins-selectable"><i class="fas fa-times-circle"></i></span>
</div>
<div class="ins-section-wrapper">
<div class="ins-section-container"></div>
</div>
</div>
</div>
<script>
(function (window) {
var INSIGHT_CONFIG = {
TRANSLATION: {
POSTS: '文章',
PAGES: '页面',
CATEGORIES: '分类',
TAGS: '标签',
UNTITLED: '(未命名)',
},
ROOT_URL: '/',
CONTENT_URL: '/content.json',
};
window.INSIGHT_CONFIG = INSIGHT_CONFIG;
})(window);
</script>
<script src="/js/insight.js"></script>
</div>
</div>
</div>
<div id="main-nav-mobile" class="header-sub header-inner">
<table class="menu outer">
<tr>
<td><a class="main-nav-link" href="/.">主页</a></td>
<td><a class="main-nav-link" href="/archives">归档</a></td>
<td><a class="main-nav-link" href="/categories">分类</a></td>
<td><a class="main-nav-link" href="/tags">标签</a></td>
<td><a class="main-nav-link" href="/about">关于</a></td>
<td>
<div class="search-form">
<input type="text" class="ins-search-input search-form-input" placeholder="搜索" />
</div>
</td>
</tr>
</table>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-others/hello-world" class="article article-type-post" itemscope itemprop="blogPost">
<!-- <script>
function scalingBanner(obj){
var $this=obj
var imgWidth=$this.width();
var imgHeight=$this.height();
var result=scalingImage(imgWidth,imgHeight,300,300)
$this.attr('width',result.width)
$this.attr('height',result.height)
}
function scalingImage(imgWidth, imgHeight, containerWidth, containerHeight) {
var containerRatio = containerWidth / containerHeight;
var imgRatio = imgWidth / imgHeight;
if (imgRatio > containerRatio) {
imgWidth = containerWidth;
imgHeight = containerWidth / imgRatio;
} else if (imgRatio < containerRatio) {
imgHeight = containerHeight;
imgWidth = containerHeight * imgRatio;
} else {
imgWidth = containerWidth;
imgHeight = containerHeight;
}
return { width: imgWidth, height: imgHeight };
}
</script>
<div style="display:none">
<img src="" width="300" height="300">
<img src="" onload="scalingBanner(this)" width="" height="">
</div>
-->
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/9102/01/01/others/hello-world/">MechDancer Team 1329</a>
</h1>
<div class="article-meta">
<div class="article-date">
<i class="fas fa-calendar-alt"></i>
<a href="/9102/01/01/others/hello-world/">
<time datetime="9102-01-01T00:00:00.000Z" itemprop="datePublished">9102-01-01</time>
</a>
</div>
</div>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="欢迎访问-MechDancer-网站！"><a href="#欢迎访问-MechDancer-网站！" class="headerlink" title="欢迎访问 MechDancer 网站！"></a>欢迎访问 MechDancer 网站！</h2><p>这里会发布一些我们的技术及开发进程。</p>
<p>我们的软件文档位于：<a href="https://docs.mechdancer.org/" target="_blank" rel="noopener">https://docs.mechdancer.org/</a></p>
<p>同时，我们还在进行 VEX V5 PROS 文档的翻译：<a href="http://pros.mechdancer.org/" target="_blank" rel="noopener">http://pros.mechdancer.org/</a></p>
<p>扫描二维码，关注 <strong>交大附中智能社</strong>：</p>
<p><img src="/../images/qrcode.jpg" alt></p>
</div>
<footer class="article-footer">
<div class="share-container">
<div class="a2a_kit a2a_default_style">
<a class="a2a_dd" href="https://www.addtoany.com/share">Share</a>
<span class="a2a_divider"></span>
<!-- <a class="a2a_button_facebook"></a>
<a class="a2a_button_twitter"></a>
<a class="a2a_button_google_plus"></a>
<a class="a2a_button_pinterest"></a>
<a class="a2a_button_tumblr"></a> -->
<a class="a2a_button_wechat"></a>
<a class="a2a_button_sina_weibo"></a>
</div>
<script type="text/javascript" src="//static.addtoany.com/menu/page.js"></script>
<style>
.a2a_menu {
border-radius: 4px;
}
.a2a_menu a {
margin: 2px 0;
font-size: 14px;
line-height: 16px;
border-radius: 4px;
color: inherit !important;
font-family: 'Microsoft Yahei';
}
#a2apage_dropdown {
margin: 10px 0;
}
.a2a_mini_services {
padding: 10px;
}
a.a2a_i,
i.a2a_i {
width: 122px;
line-height: 16px;
}
a.a2a_i .a2a_svg,
a.a2a_more .a2a_svg {
width: 16px;
height: 16px;
line-height: 16px;
vertical-align: top;
background-size: 16px;
}
a.a2a_i {
border: none !important;
}
a.a2a_menu_show_more_less {
margin: 0;
padding: 10px 0;
line-height: 16px;
}
.a2a_mini_services:after{content:".";display:block;height:0;clear:both;visibility:hidden}
.a2a_mini_services{*+height:1%;}
</style>
</div>
</footer>
</div>
</article>
<article id="post-programming/pros-doc-contribution" class="article article-type-post" itemscope itemprop="blogPost">
<!-- <script>
function scalingBanner(obj){
var $this=obj
var imgWidth=$this.width();
var imgHeight=$this.height();
var result=scalingImage(imgWidth,imgHeight,300,300)
$this.attr('width',result.width)
$this.attr('height',result.height)
}
function scalingImage(imgWidth, imgHeight, containerWidth, containerHeight) {
var containerRatio = containerWidth / containerHeight;
var imgRatio = imgWidth / imgHeight;
if (imgRatio > containerRatio) {
imgWidth = containerWidth;
imgHeight = containerWidth / imgRatio;
} else if (imgRatio < containerRatio) {
imgHeight = containerHeight;
imgWidth = containerHeight * imgRatio;
} else {
imgWidth = containerWidth;
imgHeight = containerHeight;
}
return { width: imgWidth, height: imgHeight };
}
</script>
<div style="display:none">
<img src="/../images/pros-doc-contribution.svg" width="300" height="300">
<img src="/../images/pros-doc-contribution.svg" onload="scalingBanner(this)" width="" height="">
</div>
-->
<div class="article-inner">
<a href="/2019/08/03/programming/pros-doc-contribution/" itemprop="url">
<img src="/../images/pros-doc-contribution.svg" class="article-banner" />
</a>
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2019/08/03/programming/pros-doc-contribution/">PROS 文档翻译贡献指南</a>
</h1>
<div class="article-meta">
<div class="article-date">
<i class="fas fa-calendar-alt"></i>
<a href="/2019/08/03/programming/pros-doc-contribution/">
<time datetime="2019-08-03T20:47:00.000Z" itemprop="datePublished">2019-08-03</time>
</a>
</div>
<div class="article-category">
<i class="fas fa-folder"></i>
<a class="article-category-link" href="/categories/技术文档（软件）/">技术文档（软件）</a>
</div>
<div class="article-tag">
<i class="fas fa-tag"></i>
<a class="tag-link" href="/tags/翻译/">翻译</a>, <a class="tag-link" href="/tags/贡献指南/">贡献指南</a>
</div>
<div>
<i class="fas fa-pencil-alt"></i>
berberman
</div>
</div>
</header>
<div class="article-entry" itemprop="articleBody">
<p>随着 V5 的发布，Purdue ACM SIGBots 更新了对应的<a href="https://github.com/purduesigbots/pros-docs" target="_blank" rel="noopener">软件文档</a>。我们目前着手于 V5 文档的译制，<a href="https://github.com/MechDancer/pros-docs/tree/master/v5-chinese" target="_blank" rel="noopener">v5-chinese</a> 这个文件夹为 <a href="https://github.com/MechDancer/pros-docs/tree/master/v5" target="_blank" rel="noopener">v5</a> 的拷贝，所有中文翻译在此进行。</p>
<h2 id="搭建文档编译环境"><a href="#搭建文档编译环境" class="headerlink" title="搭建文档编译环境"></a>搭建文档编译环境</h2><p>为了良好的翻译体验及更高的翻译效率，在本地构建出文档工程并预览是很有必要的。下面几步介绍了如何搭建起该文档工程的编译环境。</p>
<h3 id="克隆工程"><a href="#克隆工程" class="headerlink" title="克隆工程"></a>克隆工程</h3><p>找一个地方，执行命令将仓库克隆到本地：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">> git <span class="built_in">clone</span> https://github.com/MechDancer/pros-docs</span><br></pre></td></tr></table></figure>
<h3 id="安装-PROS-CLI"><a href="#安装-PROS-CLI" class="headerlink" title="安装 PROS CLI"></a>安装 PROS CLI</h3><p>由于文档中使用 sphix-click 扩展将源码中的部分文档渲染进网页，因此需要先安装 PROS CLI。你可以在<a href="https://pros.mechdancer.org/getting-started/index.html" target="_blank" rel="noopener">这里</a>找到安装指南。</p>
<h3 id="初始化子模块"><a href="#初始化子模块" class="headerlink" title="初始化子模块"></a>初始化子模块</h3><p>在 <code>sphinx_rtd_theme</code> 和 <code>sphinx-tabs</code> 目录下运行：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">> git submodule init</span><br><span class="line">> git submodule update</span><br></pre></td></tr></table></figure>
<p>初始化两个依赖的源码仓库。之后分别安装这两个子模块中的依赖：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">> <span class="built_in">cd</span> sphinx_rtd_theme</span><br><span class="line">> pip install ./</span><br><span class="line"></span><br><span class="line">> <span class="built_in">cd</span> ../sphinx-tabs</span><br><span class="line">> pip install ./</span><br></pre></td></tr></table></figure>
<h3 id="安装依赖"><a href="#安装依赖" class="headerlink" title="安装依赖"></a>安装依赖</h3><p>进入工程文件夹，使用 <code>pip</code> 安装其他依赖：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">> <span class="built_in">cd</span> pros-docs</span><br><span class="line">> pip install -r requirements.txt</span><br></pre></td></tr></table></figure>
<h3 id="开始构建"><a href="#开始构建" class="headerlink" title="开始构建"></a>开始构建</h3><p>运行命令：</p>
<figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">> make chinese</span><br></pre></td></tr></table></figure>
<p>若构建成功便会在工程文件夹中得到 <code>./build/v5-chinese/html</code> 目录，其中包含网页文件。</p>
<blockquote>
<p>注意：Windows 系统中可能不存在 make 命令，即无法执行 Makefile，此时可替换为 <code>sphinx-build -M html v5-chinese/ build/v5-chinese/</code>。</p>
</blockquote>
<h2 id="进行预览"><a href="#进行预览" class="headerlink" title="进行预览"></a>进行预览</h2><p>我们推荐使用 <a href="https://code.visualstudio.com/" target="_blank" rel="noopener">Visual Studio Code</a> 作为文本编辑工具，它具有支持 <code>rst</code> 的插件，可以进行实时预览。</p>
<h3 id="安装扩展"><a href="#安装扩展" class="headerlink" title="安装扩展"></a>安装扩展</h3><p>在扩展商店中安装 <code>reStructuredText</code> 扩展。之后进行配置：</p>
<ul>
<li><code>Restructuredtext: Conf Path</code> 填写 <code>${workspaceFolder}/conf.py</code></li>
<li><code>Restructuredtext › Linter: Executable Path</code> 填写 <code>doc8</code> 安装位置</li>
<li><code>Restructuredtext: Sphinx Build Path</code> 填写 <code>sphinx-build</code> 安装位置</li>
</ul>
<h3 id="启用自动保存"><a href="#启用自动保存" class="headerlink" title="启用自动保存"></a>启用自动保存</h3><p>我们推荐打开 Visual Studio Code 的失焦点自动保存，这样可以点击右侧预览窗口随时得到最新渲染的网页。</p>
<h3 id="打开项目"><a href="#打开项目" class="headerlink" title="打开项目"></a>打开项目</h3><p>在顶部栏中点击 文件 > 打开文件夹，选择 <strong>v5-chinese</strong> 目录即可。享受翻译带来的快乐：)</p>
</div>
<footer class="article-footer">
<div class="share-container">
<div class="a2a_kit a2a_default_style">
<a class="a2a_dd" href="https://www.addtoany.com/share">Share</a>
<span class="a2a_divider"></span>
<!-- <a class="a2a_button_facebook"></a>
<a class="a2a_button_twitter"></a>
<a class="a2a_button_google_plus"></a>
<a class="a2a_button_pinterest"></a>
<a class="a2a_button_tumblr"></a> -->
<a class="a2a_button_wechat"></a>
<a class="a2a_button_sina_weibo"></a>
</div>
<script type="text/javascript" src="//static.addtoany.com/menu/page.js"></script>
<style>
.a2a_menu {
border-radius: 4px;
}
.a2a_menu a {
margin: 2px 0;
font-size: 14px;
line-height: 16px;
border-radius: 4px;
color: inherit !important;
font-family: 'Microsoft Yahei';
}
#a2apage_dropdown {
margin: 10px 0;
}
.a2a_mini_services {
padding: 10px;
}
a.a2a_i,
i.a2a_i {
width: 122px;
line-height: 16px;
}
a.a2a_i .a2a_svg,
a.a2a_more .a2a_svg {
width: 16px;
height: 16px;
line-height: 16px;
vertical-align: top;
background-size: 16px;
}
a.a2a_i {
border: none !important;
}
a.a2a_menu_show_more_less {
margin: 0;
padding: 10px 0;
line-height: 16px;
}
.a2a_mini_services:after{content:".";display:block;height:0;clear:both;visibility:hidden}
.a2a_mini_services{*+height:1%;}
</style>
</div>
</footer>
</div>
</article>
<article id="post-programming/scanning-digit-comment-DFA" class="article article-type-post" itemscope itemprop="blogPost">
<!-- <script>
function scalingBanner(obj){
var $this=obj
var imgWidth=$this.width();
var imgHeight=$this.height();
var result=scalingImage(imgWidth,imgHeight,300,300)
$this.attr('width',result.width)
$this.attr('height',result.height)
}
function scalingImage(imgWidth, imgHeight, containerWidth, containerHeight) {
var containerRatio = containerWidth / containerHeight;
var imgRatio = imgWidth / imgHeight;
if (imgRatio > containerRatio) {
imgWidth = containerWidth;
imgHeight = containerWidth / imgRatio;
} else if (imgRatio < containerRatio) {
imgHeight = containerHeight;
imgWidth = containerHeight * imgRatio;
} else {
imgWidth = containerWidth;
imgHeight = containerHeight;
}
return { width: imgWidth, height: imgHeight };
}
</script>
<div style="display:none">
<img src="/../images/scanning-digit-comment-DFA-DFA-digit.png" width="300" height="300">
<img src="/../images/scanning-digit-comment-DFA-DFA-digit.png" onload="scalingBanner(this)" width="" height="">
</div>
-->
<div class="article-inner">
<a href="/2018/11/12/programming/scanning-digit-comment-DFA/" itemprop="url">
<img src="/../images/scanning-digit-comment-DFA-DFA-digit.png" class="article-banner" />
</a>
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/11/12/programming/scanning-digit-comment-DFA/">确定性有穷自动机实现单词、数字和注释扫描</a>
</h1>
<div class="article-meta">
<div class="article-date">
<i class="fas fa-calendar-alt"></i>
<a href="/2018/11/12/programming/scanning-digit-comment-DFA/">
<time datetime="2018-11-12T00:00:00.000Z" itemprop="datePublished">2018-11-12</time>
</a>
</div>
<div class="article-category">
<i class="fas fa-folder"></i>
<a class="article-category-link" href="/categories/技术文档（软件）/">技术文档（软件）</a>
</div>
<div class="article-tag">
<i class="fas fa-tag"></i>
<a class="tag-link" href="/tags/算法/">算法</a>, <a class="tag-link" href="/tags/编译原理/">编译原理</a>, <a class="tag-link" href="/tags/造轮子/">造轮子</a>
</div>
<div>
<i class="fas fa-pencil-alt"></i>
Ydr
</div>
</div>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p>通过将整段的字符串结成单词，<strong>扫描器</strong> 可以显著简化语法分析的难度。而构造分词扫描器的通用方法就是使用 <strong>正则表达式</strong> 和 <strong>有穷自动机</strong>。有时设计一个新语言的第一步就是实现正则引擎，以便方便地测试词法分析，但是直接编码来产生自动机也是可行的，并且在词类较少时更方便调试和修改。</p>
<ul>
<li>下面我们所说的 <strong>单词（token）</strong> 指的是一类具有特殊含义的字符串，为了与通常的单词（word）区分开，这种 <strong>单词</strong> 都使用粗体。</li>
</ul>
<p>在代码中，扫描器是这样的东西：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">interface</span> <span class="title">Scanner</span><<span class="type">T</span>> </span>{ <span class="comment">// 输入单元类型为 T 的有状态的扫描器</span></span><br><span class="line"> <span class="keyword">val</span> length: <span class="built_in">Int</span> <span class="comment">// 匹配状态：当前匹配的长度</span></span><br><span class="line"> <span class="keyword">val</span> complete: <span class="built_in">Boolean</span> <span class="comment">// 匹配状态：是否在可接受的结束状态</span></span><br><span class="line"> <span class="keyword">operator</span> <span class="function"><span class="keyword">fun</span> <span class="title">invoke</span><span class="params">(char: <span class="type">T</span>)</span></span> <span class="comment">// 输入一个 T 类型的单元 char</span></span><br><span class="line"> <span class="function"><span class="keyword">fun</span> <span class="title">reset</span><span class="params">()</span></span> <span class="comment">// 重置内部状态</span></span><br><span class="line">} <span class="comment">//</span></span><br></pre></td></tr></table></figure>
<p>基于自动机的扫描器包含一系列 <strong>状态</strong>，其中有且仅有一个是起始状态，并有一部分状态是可接受的结束状态。每次扫描开始时，状态机从起始状态出发，对每一个输入单元发生一次状态转移，直到所有单元都输入到扫描器或扫描器因不合法的字符落入到不存在/错误的的状态中。</p>
<p>通过非常简单的代码就可以实现一个自动机引擎：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 确定性自动机扫描器</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> table 状态转移表（*行序号从 1 开始*，*0 表示错误状态*）</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> ending 合法结束状态</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> map 字符到转移表列序号的映射关系（*-1 表示无效字符*）</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">DFA</span><<span class="type">T</span>></span>(</span><br><span class="line"> <span class="keyword">private</span> <span class="keyword">val</span> table: List<List<<span class="built_in">Int</span>>>,</span><br><span class="line"> <span class="keyword">private</span> <span class="keyword">val</span> ending: Set<<span class="built_in">Int</span>>,</span><br><span class="line"> <span class="keyword">private</span> <span class="keyword">val</span> map: (T) -> <span class="built_in">Int</span></span><br><span class="line">) : Scanner<T> {</span><br><span class="line"> <span class="comment">// 当前状态（序号）</span></span><br><span class="line"> <span class="comment">// 正数表示正在匹配</span></span><br><span class="line"> <span class="comment">// 负数表示匹配失败前的最后状态，即能匹配的部分的结束状态</span></span><br><span class="line"> <span class="keyword">private</span> <span class="keyword">var</span> state = <span class="number">1</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">override</span> <span class="keyword">var</span> length: <span class="built_in">Int</span> = <span class="number">0</span>; <span class="keyword">private</span> <span class="keyword">set</span></span><br><span class="line"> <span class="keyword">override</span> <span class="keyword">val</span> complete <span class="keyword">get</span>() = abs(state) <span class="keyword">in</span> ending</span><br><span class="line"></span><br><span class="line"> <span class="keyword">override</span> <span class="keyword">operator</span> <span class="function"><span class="keyword">fun</span> <span class="title">invoke</span><span class="params">(char: <span class="type">T</span>)</span></span> {</span><br><span class="line"> <span class="keyword">if</span> (state > <span class="number">0</span>) {</span><br><span class="line"> state = map(char)</span><br><span class="line"> <span class="comment">// 是一个有意义的字符</span></span><br><span class="line"> .takeIf { it >= <span class="number">0</span> }</span><br><span class="line"> <span class="comment">// 查找转移表</span></span><br><span class="line"> ?.let { table[state - <span class="number">1</span>][it] }</span><br><span class="line"> <span class="comment">// 不导致错误状态</span></span><br><span class="line"> ?.takeIf { it != <span class="number">0</span> }</span><br><span class="line"> <span class="comment">// 匹配长度增加</span></span><br><span class="line"> ?.also { length }</span><br><span class="line"> <span class="comment">// 否则标记匹配结束</span></span><br><span class="line"> ?: -state</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">override</span> <span class="function"><span class="keyword">fun</span> <span class="title">reset</span><span class="params">()</span></span> {</span><br><span class="line"> state = <span class="number">1</span></span><br><span class="line"> length = <span class="number">0</span></span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>上面的代码展示了我实现的自动机引擎。其中类的构造参数描述了某一个状态机实例的结构。</p>
<ul>
<li><code>table</code> 是用数字表示的状态转移表，表的每一行表示一个状态，每一列表示在某状态下针对一类输入字符将转移到哪个状态；</li>
<li><code>ending</code> 是合法结束状态的集合，状态机根据当前状态是否集合中的元素判断匹配是否完成；</li>
<li><code>map</code> 是实际输入字符到状态转移表列的映射关系。用 -1 列表示转到错误状态；</li>
</ul>
<p>这是数字扫描器实际使用的状态机参数，后面会讲到如何决定这些参数：</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">table = <span class="comment">// 0 1 d b h x . //</span></span><br><span class="line">listOf(listOf( <span class="number">2</span>, <span class="number">11</span>, <span class="number">11</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">12</span>), <span class="comment">// 1 -> ε</span></span><br><span class="line"> listOf(<span class="number">11</span>, <span class="number">11</span>, <span class="number">11</span>, <span class="number">3</span>, <span class="number">0</span>, <span class="number">7</span>, <span class="number">12</span>), <span class="comment">// 2 -> 0</span></span><br><span class="line"> listOf( <span class="number">4</span>, <span class="number">4</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">5</span>), <span class="comment">// 3 -> 0b</span></span><br><span class="line"> listOf( <span class="number">4</span>, <span class="number">4</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">5</span>), <span class="comment">// 4 -> 0b...</span></span><br><span class="line"> listOf( <span class="number">6</span>, <span class="number">6</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>), <span class="comment">// 5 -> 0b... .</span></span><br><span class="line"> listOf( <span class="number">6</span>, <span class="number">6</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>), <span class="comment">// 6 -> 0b... . ...</span></span><br><span class="line"> listOf( <span class="number">8</span>, <span class="number">8</span>, <span class="number">8</span>, <span class="number">8</span>, <span class="number">8</span>, <span class="number">0</span>, <span class="number">9</span>), <span class="comment">// 7 -> 0x</span></span><br><span class="line"> listOf( <span class="number">8</span>, <span class="number">8</span>, <span class="number">8</span>, <span class="number">8</span>, <span class="number">8</span>, <span class="number">0</span>, <span class="number">9</span>), <span class="comment">// 8 -> 0x...</span></span><br><span class="line"> listOf(<span class="number">10</span>, <span class="number">10</span>, <span class="number">10</span>, <span class="number">10</span>, <span class="number">10</span>, <span class="number">0</span>, <span class="number">0</span>), <span class="comment">// 9 -> 0x... .</span></span><br><span class="line"> listOf(<span class="number">10</span>, <span class="number">10</span>, <span class="number">10</span>, <span class="number">10</span>, <span class="number">10</span>, <span class="number">0</span>, <span class="number">0</span>), <span class="comment">// 10 -> 0x... . ...</span></span><br><span class="line"> listOf(<span class="number">11</span>, <span class="number">11</span>, <span class="number">11</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">12</span>), <span class="comment">// 11 -> ...</span></span><br><span class="line"> listOf(<span class="number">13</span>, <span class="number">13</span>, <span class="number">13</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>), <span class="comment">// 12 -> ... .</span></span><br><span class="line"> listOf(<span class="number">13</span>, <span class="number">13</span>, <span class="number">13</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>)), <span class="comment">// 13 -> ... . ...</span></span><br><span class="line">ending = </span><br><span class="line">setOf(<span class="number">2</span>, <span class="number">4</span>, <span class="number">6</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">11</span>, <span class="number">13</span>),</span><br><span class="line">map = </span><br><span class="line">{ c: <span class="built_in">Char</span> -></span><br><span class="line"> <span class="keyword">when</span> (c.toLowerCase()) {</span><br><span class="line"> <span class="string">'0'</span> -> <span class="number">0</span> <span class="comment">// 0</span></span><br><span class="line"> <span class="string">'1'</span> -> <span class="number">1</span> <span class="comment">// 1</span></span><br><span class="line"> <span class="keyword">in</span> <span class="string">'0'</span>..<span class="string">'9'</span> -> <span class="number">2</span> <span class="comment">// d</span></span><br><span class="line"> <span class="string">'b'</span> -> <span class="number">3</span> <span class="comment">// b</span></span><br><span class="line"> <span class="keyword">in</span> <span class="string">'a'</span>..<span class="string">'f'</span> -> <span class="number">4</span> <span class="comment">// h</span></span><br><span class="line"> <span class="string">'x'</span> -> <span class="number">5</span> <span class="comment">// x</span></span><br><span class="line"> <span class="string">'.'</span> -> <span class="number">6</span> <span class="comment">// .</span></span><br><span class="line"> <span class="keyword">else</span> -> -<span class="number">1</span> <span class="comment">// e</span></span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>实现一个基于自动机的扫描器有三个步骤：</p>
<ol>
<li>根据要扫描的 <strong>单词</strong> 的特征设计识别 <strong>单词</strong> 的正则表达式；</li>
<li>直接将正则表达式（及其连接、选择和 Kleene 星号等元操作）转化为包含空转移的非确定性自动机 NFA；</li>
<li>对NFA进行约化和化简得到确定性有穷自动机 DFA；</li>
</ol>
<h2 id="示例"><a href="#示例" class="headerlink" title="示例"></a>示例</h2><p>虽然编译原理是每个计算机专业学生的必修课，但网上其实连能正确扫描 C 语言风格注释的 DFA 实现也很难找到。此处就以这个为例子介绍如何构造自动机扫描器。</p>
<ol>
<li><p>正则</p>
<p>C 语言风格的注释有两种形式：</p>
<ul>
<li>嵌入型 <code>/* … */</code></li>
<li>行尾型 <code>// …</code></li>
</ul>
<p>第一步先写出辨别这两种注释的正则表达式：</p>
<ul>
<li>嵌入型 <code>/*(?*)*/</code></li>
<li>行尾型 <code>//(?*)</code></li>
</ul>
<p>其中小括号内的 * 是 Kleene 星号，表示匹配任意字符任意次。</p>
</li>
<li><p>NFA</p>
<p>正则对应的 NFA 如图所示。现在先假设我们直接使用换行符分句，因此两种形式都不接受换行符，行尾型也不需要换行符来结束，因此可以直接简化到自环，不必再写出 Kleene 星号。</p>
<p><img src="/../images/scanning-digit-comment-DFA-NFA.png" alt="NFA"></p>
</li>
<li><p>DFA</p>
<p>由上图已经可以清晰地看到对于注释扫描来说，输入字符只有 3 类：</p>
<p>| 字符 | 代号 | 列号 |<br>| :–: | :–: | :–: |<br>| / | / | 0 |<br>| <em> | </em> | 1 |<br>| 其他 | e | 2 |</p>
<p>因此可以简化 DFA，主要操作就是：</p>
<ul>
<li>消除 ε 转换的歧义性；</li>
<li>消除相同符号的歧义性；</li>
</ul>
<p>转化后如图：</p>
<p><img src="/../images/scanning-digit-comment-DFA-DFA.png" alt="DFA"></p>
</li>
</ol>
<ol start="4">
<li><p>编写代码</p>
<figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ------ // / * e //</span></span><br><span class="line">listOf(listOf(<span class="number">2</span>, <span class="number">0</span>, <span class="number">0</span>), <span class="comment">// 1 -> ε</span></span><br><span class="line"> listOf(<span class="number">3</span>, <span class="number">4</span>, <span class="number">0</span>), <span class="comment">// 2 -> /</span></span><br><span class="line"> listOf(<span class="number">3</span>, <span class="number">3</span>, <span class="number">3</span>), <span class="comment">// 3 -> // ...</span></span><br><span class="line"> listOf(<span class="number">6</span>, <span class="number">5</span>, <span class="number">6</span>), <span class="comment">// 4 -> /*</span></span><br><span class="line"> listOf(<span class="number">7</span>, <span class="number">5</span>, <span class="number">6</span>), <span class="comment">// 5 -> /* ... *</span></span><br><span class="line"> listOf(<span class="number">6</span>, <span class="number">5</span>, <span class="number">6</span>), <span class="comment">// 6 -> /* ...</span></span><br><span class="line"> listOf(<span class="number">0</span>, <span class="number">0</span>, <span class="number">0</span>)), <span class="comment">// 7 -> /* ... */</span></span><br><span class="line">setOf(<span class="number">5</span>, <span class="number">7</span>),</span><br><span class="line">{ c: <span class="built_in">Char</span> -></span><br><span class="line"> <span class="keyword">when</span> (c) {</span><br><span class="line"> <span class="string">'/'</span> -> <span class="number">0</span></span><br><span class="line"> <span class="string">'*'</span> -> <span class="number">1</span></span><br><span class="line"> <span class="keyword">else</span> -> <span class="number">2</span></span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ol>
<h2 id="数字扫描器"><a href="#数字扫描器" class="headerlink" title="数字扫描器"></a>数字扫描器</h2><p>如图：</p>
<ul>
<li><p>NFA</p>
<p><img src="/../images/scanning-digit-comment-DFA-NFA-digit.png" alt="NFA digit"></p>
</li>
<li><p>DFA</p>
<p><img src="/../images/scanning-digit-comment-DFA-DFA-digit.png" alt="DFA digit"></p>
</li>
</ul>
</div>
<footer class="article-footer">
<div class="share-container">
<div class="a2a_kit a2a_default_style">
<a class="a2a_dd" href="https://www.addtoany.com/share">Share</a>
<span class="a2a_divider"></span>
<!-- <a class="a2a_button_facebook"></a>
<a class="a2a_button_twitter"></a>
<a class="a2a_button_google_plus"></a>
<a class="a2a_button_pinterest"></a>
<a class="a2a_button_tumblr"></a> -->
<a class="a2a_button_wechat"></a>
<a class="a2a_button_sina_weibo"></a>
</div>
<script type="text/javascript" src="//static.addtoany.com/menu/page.js"></script>
<style>
.a2a_menu {
border-radius: 4px;
}
.a2a_menu a {
margin: 2px 0;
font-size: 14px;
line-height: 16px;
border-radius: 4px;
color: inherit !important;
font-family: 'Microsoft Yahei';
}
#a2apage_dropdown {
margin: 10px 0;
}
.a2a_mini_services {
padding: 10px;
}
a.a2a_i,
i.a2a_i {
width: 122px;
line-height: 16px;
}
a.a2a_i .a2a_svg,
a.a2a_more .a2a_svg {
width: 16px;
height: 16px;
line-height: 16px;
vertical-align: top;
background-size: 16px;
}
a.a2a_i {
border: none !important;
}
a.a2a_menu_show_more_less {
margin: 0;
padding: 10px 0;
line-height: 16px;
}
.a2a_mini_services:after{content:".";display:block;height:0;clear:both;visibility:hidden}
.a2a_mini_services{*+height:1%;}
</style>
</div>
</footer>
</div>
</article>
<article id="post-briefing/communication-defy-2018.09.16" class="article article-type-post" itemscope itemprop="blogPost">
<!-- <script>
function scalingBanner(obj){
var $this=obj
var imgWidth=$this.width();
var imgHeight=$this.height();
var result=scalingImage(imgWidth,imgHeight,300,300)
$this.attr('width',result.width)
$this.attr('height',result.height)
}
function scalingImage(imgWidth, imgHeight, containerWidth, containerHeight) {
var containerRatio = containerWidth / containerHeight;
var imgRatio = imgWidth / imgHeight;
if (imgRatio > containerRatio) {
imgWidth = containerWidth;
imgHeight = containerWidth / imgRatio;
} else if (imgRatio < containerRatio) {
imgHeight = containerHeight;
imgWidth = containerHeight * imgRatio;
} else {
imgWidth = containerWidth;
imgHeight = containerHeight;
}
return { width: imgWidth, height: imgHeight };
}
</script>
<div style="display:none">
<img src="/../images/communication-defy-2018.09.16.jpg" width="300" height="300">
<img src="/../images/communication-defy-2018.09.16.jpg" onload="scalingBanner(this)" width="" height="">
</div>
-->
<div class="article-inner">
<a href="/2018/09/16/briefing/communication-defy-2018.09.16/" itemprop="url">
<img src="/../images/communication-defy-2018.09.16.jpg" class="article-banner" />
</a>
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/16/briefing/communication-defy-2018.09.16/">师大二附交流活动简报</a>
</h1>
<div class="article-meta">
<div class="article-date">
<i class="fas fa-calendar-alt"></i>
<a href="/2018/09/16/briefing/communication-defy-2018.09.16/">
<time datetime="2018-09-16T16:00:00.000Z" itemprop="datePublished">2018-09-16</time>
</a>
</div>
<div class="article-category">
<i class="fas fa-folder"></i>
<a class="article-category-link" href="/categories/简报-总结/">简报/总结</a>
</div>
<div class="article-tag">
<i class="fas fa-tag"></i>
<a class="tag-link" href="/tags/交流活动/">交流活动</a>, <a class="tag-link" href="/tags/任务分析/">任务分析</a>
</div>
<div>
<i class="fas fa-pencil-alt"></i>
杏鲍菇
</div>
</div>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>2018年9月16日，交大附中参加了在北师大二附中学术报告厅举行 2018-2019 赛季北京校际联盟第二次交流活动。本次活动参与的学校有：师大二附、交大附中、北京三帆中学、北京市广渠门中学、北京十一学校、北师大二附中（Horizons）、西城区科技馆、北京第四中学、师大附中和宣武科技馆。此此活动分为以下三个板块。</p>
<h2 id="规则解读"><a href="#规则解读" class="headerlink" title="规则解读"></a>规则解读</h2><p>本次活动个个学校表示了对 2018-2019 赛季规则的解读。具体分为任务难点的分析，误区的讲解，得分场地起落架的结构分析。此外众学校重新温故规则 part2 的部分，引起了大家的诸多思考。</p>
<h2 id="方案交流"><a href="#方案交流" class="headerlink" title="方案交流"></a>方案交流</h2><p>在这个部分里大家表达了在赛季初期对任务的理解，并相互交流了能想到的方案。同时列出了初期的方案侧重，例如主抓自动得分，高举的侧重。进入矿坑抓取得分物的结构。把得分物排除矿坑再得到得分物的方案。大家的思路百花齐放，并且都有对规则的侧重，利用，避让等。</p>
<h2 id="裁判视频见面会"><a href="#裁判视频见面会" class="headerlink" title="裁判视频见面会"></a>裁判视频见面会</h2><p>由于语言问题在赛季中有许多模糊不清的界定，所以大家与裁判长李博进行了在线见面讨论了一些关于规则的问题。例如 <em>in</em> 到底是得分物正投影在里面还是与地面接触。释放的定义是什么。大家相继提出来了很多问题。裁判长显然并不能依依解答，但他保证会在近期讲解答打包放在网上，供大家参考，尽情期待吧。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>这是这个赛季北京地区的第二次交流讨论会，规则下发后的第一次交流会。从交流频率来看，大家对交流的热情有了显著的提高。这是一个好兆头，希望各各学校都能在 2018-2019 赛季收获知识，当然能收获几个奖杯那是更好不过。</p>
</div>
<footer class="article-footer">
<div class="share-container">
<div class="a2a_kit a2a_default_style">
<a class="a2a_dd" href="https://www.addtoany.com/share">Share</a>
<span class="a2a_divider"></span>
<!-- <a class="a2a_button_facebook"></a>
<a class="a2a_button_twitter"></a>
<a class="a2a_button_google_plus"></a>
<a class="a2a_button_pinterest"></a>
<a class="a2a_button_tumblr"></a> -->
<a class="a2a_button_wechat"></a>
<a class="a2a_button_sina_weibo"></a>
</div>
<script type="text/javascript" src="//static.addtoany.com/menu/page.js"></script>
<style>
.a2a_menu {
border-radius: 4px;
}
.a2a_menu a {
margin: 2px 0;
font-size: 14px;
line-height: 16px;
border-radius: 4px;
color: inherit !important;
font-family: 'Microsoft Yahei';
}
#a2apage_dropdown {
margin: 10px 0;
}
.a2a_mini_services {
padding: 10px;
}
a.a2a_i,
i.a2a_i {
width: 122px;
line-height: 16px;
}
a.a2a_i .a2a_svg,
a.a2a_more .a2a_svg {
width: 16px;
height: 16px;
line-height: 16px;
vertical-align: top;
background-size: 16px;
}
a.a2a_i {
border: none !important;
}
a.a2a_menu_show_more_less {
margin: 0;
padding: 10px 0;
line-height: 16px;
}
.a2a_mini_services:after{content:".";display:block;height:0;clear:both;visibility:hidden}
.a2a_mini_services{*+height:1%;}
</style>
</div>
</footer>
</div>
</article>
<article id="post-programming/navigation-interface" class="article article-type-post" itemscope itemprop="blogPost">
<!-- <script>
function scalingBanner(obj){
var $this=obj
var imgWidth=$this.width();
var imgHeight=$this.height();
var result=scalingImage(imgWidth,imgHeight,300,300)
$this.attr('width',result.width)
$this.attr('height',result.height)
}
function scalingImage(imgWidth, imgHeight, containerWidth, containerHeight) {
var containerRatio = containerWidth / containerHeight;
var imgRatio = imgWidth / imgHeight;
if (imgRatio > containerRatio) {
imgWidth = containerWidth;
imgHeight = containerWidth / imgRatio;
} else if (imgRatio < containerRatio) {
imgHeight = containerHeight;
imgWidth = containerHeight * imgRatio;
} else {
imgWidth = containerWidth;
imgHeight = containerHeight;
}
return { width: imgWidth, height: imgHeight };
}
</script>
<div style="display:none">
<img src="" width="300" height="300">
<img src="" onload="scalingBanner(this)" width="" height="">
</div>
-->
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/14/programming/navigation-interface/">规范导航器接口</a>
</h1>
<div class="article-meta">
<div class="article-date">
<i class="fas fa-calendar-alt"></i>
<a href="/2018/09/14/programming/navigation-interface/">
<time datetime="2018-09-14T18:01:00.000Z" itemprop="datePublished">2018-09-14</time>
</a>
</div>
<div class="article-category">
<i class="fas fa-folder"></i>
<a class="article-category-link" href="/categories/技术文档（软件）/">技术文档（软件）</a>
</div>
<div class="article-tag">
<i class="fas fa-tag"></i>
<a class="tag-link" href="/tags/算法/">算法</a>, <a class="tag-link" href="/tags/路径规划/">路径规划</a>, <a class="tag-link" href="/tags/造轮子/">造轮子</a>
</div>
<div>
<i class="fas fa-pencil-alt"></i>
Ydr
</div>
</div>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>通过前一段时间实现的动态窗口法导航，我对导航模块也有了更深一层的认识。为了使软硬件异构的机器人都能使用导航模块，我抽象出了导航模块，以及可导航运动平台的共性，其实现即规范导航器接口。本文主要介绍导航器的模型和概念，并辅以少量演示代码。</p>
<p>下文中“导航”与“局部路径规划”是等价的，可互换。</p>
<h2 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h2><p>以动态窗口法和定时弹带法为代表的一系列导航算法具有相同的运行过程，即预测→优化→控制。其中预测过程确定有效控制量的范围，并根据控制量预测机器人可能轨迹；优化过程从所有可能轨迹里找到最优的一条；控制过程执行最优轨迹对应的控制量。</p>
<p>局部路径规划中有2个重要的概念。</p>