用户
搜索

该用户从未签到

i春秋作家

Rank: 7Rank: 7Rank: 7

18

主题

48

帖子

3801

魔法币
收听
0
粉丝
97
注册时间
2016-12-7

i春秋签约作者春秋文阁

发表于 2018-4-17 16:11:55 22227
什么是词法分析
   先来说说什么是词法,比如下面这个句子
一个 傻_逼。
  初中的语文老师估计就会给你科学的分析这句话的意义了,首先是分主谓宾定状补,这句话要先确定一个主体,最直接的是谁是一个大傻_逼,主语很重要,他直接指出了那个傻_逼到底是谁,在上面的句子中,“我”这个字就作为了主语,笔者小心翼翼地决定这个主语(要是换成你估计你就不看了),最终决定还是自己来背这个锅。

  谓语就是句子中的“是”字,主要作用估计是用来表达那种强烈的情感,表示“我”怎么样,当然,去掉在中文中没有什么问题,比如
我,一个 傻_逼
  然后就是“一个”这个表示数量的词了,当然显然的,在这里仍然是更多的情感修饰因为我是大**这样也没什么问题,不过你要是换成两个这句话就有点问题了,比如“我是两个大傻_逼”,当你说出这句话时恐怕你真是个傻_逼了。
  下面就很重要了,比如那个**是个定语,这句话的目的就是确定我是傻_逼这个事实,如果没有定语,或者定语从傻_逼换成天才,那么意义就完全不一样了是不是,至于这句话的补语简直起了画龙点睛之妙,首先是一个大,而不是小,如果说“我是一个小傻_逼”这效果就差的有点多了。
   语法分析就说到这里,笔者就不继续深究说出这句话作者内心活动到底有什么不为人知的故事了,上完了语文课,其实笔者想要说的无非是一个语句可以分成多种的成分,词法分析很多的时候就是为接下来的语法分析做准备工作的,主要的作用就是将一个表达式分成多种不同的成分。


词法分析做什么
比如上面这句话,笔者在写的时候刻意将不同的词性成分用空格分开来了,实际上如果是英文的话词法分析会简单的多,例如:
I am a big idiot
那么除去词性分析,只需要依据空格来区分各个词了。当然,我们现在所说的词法分析并不是用于分析莎士比亚的诗写的有多屌的,我们的词法分析也没有主谓宾定状补,先来看下面的C语言代码:
[C] 纯文本查看 复制代码
#include "stdio.h"
int main()
{
   int a,b;
   a=1,b=2;
   printf("a+b=%d",a+b);
}
我们以该代码的第一行为例,如果按照之前所述的词法分析办法,那么第一行应该被分解为以下词的组合
  • 符号#
  • 词include
  • 空格符
  • 符号“
  • stdio
  • .
  • h
  • 符号“
  • 回车


可以看到,我们不仅使用空格来区分单词,同时需要注意那些标点符号包括回车换行等特殊字符,他们也是将词分开的成分。


词法分析的成分
           如果按照上一章节的区分在编程语言角度来说没有任何问题,但是词法分析最终是为了语法分析进行服务的,实际上上一章节的分词手段并不高明,我们在上一章节仅仅是区分了分隔符(Delimiter)与词(lexeme),例如在上一章节中,空格,回车,符号,符号.都作为了分隔符,这无疑给语法分析加重了负担,为此我们需要重新调整思路,为词法分析做更进一步的细分与优化,例如在上一章节中,我们完全可以按下面的方式进行区分
  • 符号#
  • 词Include
  • 空格
  • “stdio.h”


其中,”stdio.h”被包括在了一起作为一个特殊的lexeme出现,在词法分析中,我们把它称为container
   笔者通过自身编写词法分析机的经验将词法分析需要区分的元素主要分为以下几种大类。
  • 常规分隔符(Delimiter)
  • 常规词(Token)
  • 空格(Spacer)
  • 换行(Newline)
  • 容器词(container)


常规分隔符
      常规分隔符主要是类似于逗号冒号分号括号诸如此类的语法组成例如表达式1+2*3,当中的+*都是分隔符。


常规词
      简单来说就是被其它符号分开的词就是常规词,例如表达式
int a,b;中的int a b这都是常规的词,常规词当然在很多的时候可以被进一步细分,比如
   int a=123
当中的int a 123都是词,但123作为纯数字的表达可以作为数字词被特殊处理。

空格符
   就如同表述的那样,空格符最多用的就是空格,当然,别忘了很多时候我们将对齐缩进符号也作为空格符。

换行
   我们常常将回车换行(看好了,是回车符和换行符)统称为换行符

容器词
         举个例子,在c语言中,我们最常见的的容器词应该就是字符串了,字符串以一个引号开始一个引号结束,当然除了字符串,字母也属于一个容器词,那种以某种字符作为开始某些字符作为结束的作为容器词。

词法分析优化
如果只是简简单单依靠分隔符来分分词而没有优化,那这个词法分析机基本也就属于废品了,不管怎么样,词法分析的最终目的是服务语法分析机的,下面举一些关于词法分析的例子。

换行符和空白符优化
      这是最直接也是最简单的一种优化,当连续出现多个换行符时,将会被解析为一个换行符。例如之前说的C语言代码,你在#include “stdio.h”下多敲几个回车,其结果也和只有一个回车等价,同样空白符优化如下表达式
     #include        “stdio.h”
也应该等价于
#include “stdio.h”
多个连续出现的换行符及空白符都会被优化为1

空白符优化
空白符除了连续出现会被优化外,在特殊的情况下会被直接忽略,查看下面的C语言表达式
inta= b  + c;
可以看到,空白符在+号前后都有出现,这个时候,空白符应该被直接忽略,因为上面的表达式等价于
int a=b+c;
除此之外,首行缩进部分的空白符也应该被忽略,其并不影响语法分析的结果反而会加重语法分析的负担。


歧义container带来的歧义
歧义说白点就是可以这样理解也可以那样理解的句子,但不确定究竟在表达哪种意思。上面的的表达式解析办法也存在不少的歧义
在这里主要列举几种常见的歧义,例如下面的表达式
int a=1 + 2
string a=“1 + 2”;
上述表达式的第一句的+号被解释为分隔符没有任何的问题,但是在第二个表达式中就会出问题了,问题就出在这个+号出现在一个container当中,那么,他就应该是container的一部分而不该被解析为分隔符,同时我们可以看到,在词法分析优化的过程中,第一个表达式+号左右两边的空格被顺利优化掉了,但是表达式2中空白符作为container的一部分,不应该被优化。
可能你会说,这好办啊,在container开始符号到结束符号所有的字符都作为container的一部分,那么我们来看下面的情况
string a=“hello
world”
   在这种特殊情况中,换行符作为container里的一部分,那么,它应该被包含么,如果在c语言中,这可能会直接报错,因为词法分析机无法确认这是否是一个container,而在其他语言中,里面的换行符可能被直接忽略。同样的还可能碰到如下的情况
   string a=“hello world
是的,这个container不完整,那么它就不能被归类为任何一种词格式,这个时候,词法分析机会报错,可见,词法分析也不是任何时候都完美无缺的。


符号冲突带来的歧义
  查看下面的代码
  
[AppleScript] 纯文本查看 复制代码
#include <stdio.h>
  int main()
{
int a=a<2,b=1>2;
}
当然C语言的编译器已经非常成熟了上面的情况不会出任何问题,但是我们的问题来了,首先我们将<>作为container的开始结束,那么<stdio.h>显然是一个正确的container,问题是main函数里的表达式<2,b=1>这是一个container类型么,显然不是,这已经跨了两个子表达式了,如果继续使用上章节我们想当然的container解析手段,这显然要吃个大亏。当然在笔者开发编译器方面语法设计方面,笔者都会尽量避免出现符号冲突


数字带来的歧义
观察下面的代码
[AppleScript] 纯文本查看 复制代码
typedef struct 
{float a;}foo;
int main()
{
 foo myst;
 myst.a=3.14159265;
}
问题来了符号.是该作为分隔符还是浮点数的一部分,这个坑是数字的表达方式带来的,如果没有好好处理,那可就要栽跟头了,上面的表达式正确应该处理为
  • myst
  • 符号.
  • 符号=
  • 3.14159265


当然关于歧义这点还有很多没有写,有兴趣的读者可以自行探索。但是对一个语言的设计对歧义的分析始终是一个不可避免的问题,因此我们能做的就是慎之又慎的去处理这些问题。


如何打造词法分析机
当然,一个优秀的词法分析机,不仅要根据语言语法做好优化,更总要的是需要避免很多的歧义问题,很多时候词法分析机需要特殊问题特殊处理,不过这回笔者也小气一回并不打算将自己的词法分析机进行开源不过谈谈词法分析机如何设计。
  • 如果需要制作一个通用的词法分析机可以编写一系列的注册函数将不同类别的词性分隔符分别注册。
  • 首先分隔符和空格符可以用一个数组进行存储,例如我们需要将逗号标记为分隔符只需要将调用注册函数注册一下就行。
  • 注意各种歧义问题,除了container带来的歧义(个人感觉最多)其它就是各种数字表达方式带来的歧义了。
  • 编译原理救不了你如果你对词法分析只停留在理论而不去动手自己写写,我只能说你活在梦里,很多坑书上根本没提。
  • 少YY多动手




基于词法分析机的斯坦福兔子模型解析格式一览


斯坦福兔子讲白点就是斯坦福大学里几个大佬在早期制作的一个模型文件,因为当时的模型实在太少了,所以这只兔子可以说是天下闻名,笔者手中的这个文件是以.obj格式进行存储的,当然,OBJ模型很多是以文本格式描述的,因此首先要做的是如何使用我们的词法分析思路去解析这只兔子,打开文件先来看看这个是什么样子:
首先笔者手中obj文件主要分两个部分,第一部分用于描述顶点坐标,包括一个坐标一个法线信息,第二部分用于描述顶点索引
第一部分类似这个样子
[AppleScript] 纯文本查看 复制代码
g group0
v -0.42187118417501057 -0.22432552280819007 0.036021387899898456
vt 1.0616153811436097e+292 1.0616130146821015e+292
vn -0.81664695887937799 -0.54215649761442541 -0.19787389076763764
v -0.42332360766571125 -0.18158828292695459 -0.013206771121193818
vt 8.4900776652466857e-314 1.5931989486733829e-304
vn -0.82843019548361763 -0.31065771214419546 -0.46604205507261864
v -0.39457719052454332 -0.22780876852482612 -0.026677034999550136
其中vvn分别由三个数组成,分别表示一个三维坐标系中的一个坐标和该坐标的归一化法线向量 第二部分是顶点索引,类似这个样子
[AppleScript] 纯文本查看 复制代码
f 2/2/2 3/3/3 1/1/1
f 5/5/5 6/6/6 4/4/4
f 8/8/8 9/9/9 7/7/7
f 11/11/11 12/12/12 10/10/10
f 14/14/14 15/15/15 13/13/13
f 17/17/17 18/18/18 16/16/16
f 20/20/20 21/21/21 19/19/19
f 23/23/23 24/24/24 22/22/22
f 29/29/29 30/30/30 28/28/28
f 32/32/32 33/33/33 31/31/31
f 35/35/35 36/36/36 34/34/34
f 38/38/38 39/39/39 37/37/37
f 41/41/41 42/42/42 40/40/40
f 44/44/44 45/45/45 43/43/43
f 47/47/47 14/14/14 46/46/46
f 49/49/49 50/50/50 48/48/48
这里描述的是顶点位置索引f表示face的意思,就是面,每个面三个顶点,其中比如14/14/14表示索引为14的顶点及索引为14uv坐标和索引为14的法线。


词法解析
可以看到obj文件的词法简单没有太多的内容,在文件中存在的常规分隔符仅有一个/,另外就是空格符和换行符了,因为符号点不作为分隔符因此不存在数字歧义这一点,另外还有一个符号#QUAN,这个表示该点是一个无效的数字,把它注册为container并认为其是一个注释就行了,之后将这三个符号注册进词法分析机配合语法分析机就能够对该文件进行解析了。笔者代码如下:
         m_Lexer.RegisterSpacer('');
         m_Lexer.RegisterSpacer('\t');
         m_Lexer.RegisterComment('#','\n');
         m_Lexer.RegisterDelimiter('/');
当然最终的解析方式笔者在本篇文章中并不打算进一步叙述,本文只是讨论词法分析机的,最后贴上这个斯坦福兔子的解析图助助兴吧。
bunny.gif
后记
词法分析作为编译器的一部分,看似简单,做起来却有非常多的问题需要处理,其中的大多数是歧义导致的问题,当然大多数书上绝对不会告诉你,实际上很多项目都是这样,笔者看过一群自我感觉良好的理论大佬能搬出一套理论各种高大上,等真要动真格的时候随便一个问题就能让他懵逼,所以别说东西多简单,简不简单等做出来了再说也不迟。毕竟扯淡吹牛逼又解决不了实际问题。


表示居然还能这么玩
使用道具 举报 回复
发表于 2018-4-21 16:06:56
编译原理说白了就是把人看的翻译成机器看得代码,这个学期学了前三章,理论感觉还可以接受。如果自己想写一款编程语言,先自己设计下,在看编译原理感觉会有很多共同点
python部署的在线渗透平台http://systeminfo.applinzi.com/
使用道具 举报 回复
发新帖
您需要登录后才可以回帖 登录 | 立即注册