parser 词法分析含义
将源代码中人类可读但计算机不可读的字符对它做一些基本的分析
告诉计算机这些字符是什么
需要识别的内容
关键字
首先识别跟语言相关的关键字
比如 if、else、while
每个语言都有每个语言的特色
包括语言的类型系统 会识别类型关键字
int、char、char*(char封装的指针)
还比如goto关键字
定义的变量、函数
比如 int a变量，int add(int a,int b)函数
字面量
比如 a=3 a如果是整数 那么3就是一个int的字面量或叫number字面量
比如字符串字面量 printf("hello world")
操作符
+-*/(=>{[
停用词
没有意义 实际不需要解析 直接跳过的
比如注释符号、空格、换行
那编译器如何识别上述内容呢？
词法解析里面唯一的方法 tokenize
这个方法会去读源码的字符
这个方法做分词
分词完了之后 输出它是什么类别、在类别中具体的内容
它的返回值叫token和token value
这个方法的返回值类型是void
通过全局变量来定义token和token value
通过修改全局变量来告诉parser的其他部分
读到的源码字符串是什么类别、具体内容是什么
parser接下来就可以做词法分析 比如生成相应的vm指令
如果解析出来的变量或字符 发现是个函数的时候
这个变量或函数 会有一个声明或定义的地方
也会有一个使用的地方
需要保证声明和定义需要在使用之前
在声明和定义的地方就已经可以对这个变量和函数做出很充分的解析
知道它是什么类别 也知道它各种的属性
解析完之后 需要把这些内容存放在一个地方即某个table中
在使用的时候 比如使用add函数 就需要去table中找到这个函数
读出相应的属性 对它做语法的分析和代码的生成
都需要定义过程中解析出来的各种属性
存中间变量的地方是symbol table
使用场景中再遇到这个符号的时候 能读到在声明定义的过程中已经解析好的属性值
symbol table（符号表不属于词法分析而属于语法分析）有哪些内容
token
只有在变量和函数的时候才需要使用symbol table
其他情况不需要symbol table 比如乘号*
关键字也需要特殊处理下 因为关键字也可能是很长的字符串
在关键字keyword之外就是变量和函数
所以token分为2类 一类是keyword 一类是id
keyword的token值就是keyword具体的值
如果是程序员自己定义的变量或字符串
把它的token统一定义成id（identitier）
hash
name字符串压缩成的数字
只是为了后续加速查找的过程
直接比较hash值，hash值相同的情况下取name
这是一个优化的实现
如果是用户定义的变量或函数的话
比如add是一个函数function还是变量（局部变量还是全局变量）
如果是关键字的话 也有一种特殊情况 比如是printf（属于system call）
还有可能是number 比如用了枚举 enum {A,B,C} ABC看起来是符号
但实际上它表示的是A是0，B是1，C是2
如果是number或变量的话 value值可能是具体的数值 比如0，1
如果不是number类型或char类型 它可能是指针类型比如430430地址
假设函数中的全局变量装的是字面量 比如hello world
字面量是装在data区的
那么value里面装的就是data区的地址比如230258
如果是一个函数的话 可能是一个函数地址
pc最终会跳转到这个函数地址 比如是code区的地址123123
所以value是什么 取决于class是什么 也取决于type是什么
还有3个属性 Gclass、Gtype、GValue
这就涉及到c语言的feature 局部变量的遮蔽
比如有一个全部变量 char* a
又有一个函数 里面有一个局部变量 int a
那么在解析这段函数的时候 需要知道函数中的a是局部变量a
而不是全局变量 a
char * a //行1 function(){ int a //行2 }
在执行函数之前 已经解析过行1了
a已经有了属性对应的class、type、value了
token、hash、name可能是一样的
但class、type、value属性是不一样的
在解析函数的时候 需要把之前全局解析出来的属性
暂存到G开头的这3个属性中 Gclass、Gtype、Gvalue
在解析局部变量a这个属性值赋值到class、type、vlaue中
等函数全部解析完了，退出这个函数的时候 需要把这个全局遮蔽的全局属性
又得写回至目前它的属性里
函数之外的a还是原来全局的那个a
通过暂存全局属性的方式来实现局部遮蔽的featrue
依照符号表来看下tokenize的代码实现（词法分析最核心的逻辑）
首先从源码中把字符取出来
然后字符指针往后移
src++
如果发现是一个换行符
会把全局变量line++
这个是为了debug用的 没什么实际的含义
就是当debug报错信息的时候 源代码多少行有什么样的语法错误
只要遇到宏就完全忽略
然后就是处理符号identifier
c语言里面是有规定的
由大写字母小写字母下划线和数字组成
以这种字符开头的就知道它是一个符号
处理符号的过程 就会计算它的hash值
因为它已经是个符号了 那么token一定是id
所以先用token来暂存下它的hash值
然后通过while循环读取它的hash值和name
然后就知道了这么一个identifier
然后去symbol table中暂存的所有的identifier
对比看下 是否是以前已经解析过的
一个个的找 先比较hash再比较名字
如果hash不同就直接跳过了
如果找到了就把找到后的结果直接返回就行了
在真正对代码做parser之前 会把所有的keyword
全部调用一遍tokenize
也就是说在调用parser方法 已经把所有的keyword解析完了
存进了symbol table里面了
所以这个时候遇到了keyword一定能够在symbol table中找到
找到了就直接返回了
如果是一个没有遇到过的用户写的变量或方法
就新增一个符号 这个符号的名字就是它的字符串
它的hash就是刚刚算出来的hash
它的token就是这个id
这个时候为什么不解析它的class、type、value呢
因为这个时候还不知道
比如看到了一个int a
刚读完a
后面无论遇到一个分号还是括号 这个时候已经停下来了
但不知道它到底是个什么
如果是括号 它可能是个函数
如果是个分号的话 那有可能是个变量
这个时候仅仅知道它是a
那a具体是什么呢 这是在语法解析的时候需要关心的
解析完了identifier之后 需要解析num
如果它是0-9开头的
那就是一个num
这个num有可能是十进制、十六进制、八进制的
num的值可以直接算出来即token_val
如果是双引号开头或是单引号开头
那它就是一个字符串或字符
如果是字符串的话 就把字符串全部读取出来
存到data区 ，data区开头的地址就是token value
如果是一个字符呢比如A 它的token value就是它本身即A这个字符的ascii码
然后还剩下operator
先处理下特殊符号/除号，如果2个除号一起//就是注释符
如果是注释符就把内容忽略掉
再比如++
如果一个+它就是add
如果是连续的两个加
那它就是自增
以上就是词法分析中最核心的逻辑
先从identifier开头
再解析字面量里的数字、string和char
最后解析运算符
举一个简单的例子 来讲解整个词法分析的过程
首先会提前把关键字处理掉 存到symbol table中去
比如这里是char(枚举的变量)、int、return
对应的name就是 "char" "int" "return"
由于这3个关键字不是系统函数
所以这些属性class、type、value是不关心的
然后是真正解析它的内容
首先遇到一个*号
后面在文法分析的时候会发现它是一个指针类型
但在目前的词法分析的时候 直接返回token就是一个*号
然后是空格是忽略的
然后发现一个identifier 小写字母a
后面发现是一个分号 那么这个identifier长度是1
在后面的文法分析的时候 会发现它的class是一个全局变量
它的类型是一个char型的指针
value值还不知道 还没有用到 还未给它赋值
然后再解析int 发现它是一个关键字
然后空格跳过
然后是add 一个新的id
长度是3位 一直到括号才能终结查询的过程
并且add在字符表中没有 所以加入进去
它的class类型是一个函数
返回值是一个int
在边解析的过程中会生成vm指令
所以在解析到add的时候
该生成的code指令都已经在逐步生成过程中了
所以pc就已经移动到了add代码的位置了
后续就是add代码的具体内容了
所以add的函数地址就是生成code的过程中pc的地址
然后解析 又发现一个a
在语法分析里面 可以在符号表中找到一个a了
需要对符号表中的a做个遮蔽
也就是把符号表中的a的class、type、value全部存在Gclass、Gtype、Gvalue中
然后会把目前分析出来的值放入class、type、vlaue中
首先class是一个局部变量
type是int
vlaue还不知道
当解析完这个函数的时候 会把Gclass、Gtype、Gvalue还原回去
然后会找到一个b 它也是identifier
对应的name是 "b"
它也是一个局部变量class
类型也是int
值也是不知道的
ret也是一样的
符号也会正常解析比如;、()但不会进入符号表
在语法分析解析完之后 会得到一个符号表
文法分析与递归下降
概念
- • 语法 ： 单词怎么组合成一个句子
语法最小单元是单词
每个单词会有不同的形态
比如run ran running
其实它们的词素lexcme是一样的
在分析一门语言的时候
首先要定位到这个语言的词素是什么
然后看这些词素之间是怎么组成一个句子的
一个组织的规则就是语法syntax
有些分词器比如lexer会把词素提取出来
一个句子里面有哪些词素 比如 I am ok
词素有I,am,ok
token和lexcme(词素)区别
int a;
int b;
a和b是两个不同的词素
是同一类别的词素 这一类的词素就叫token
a和int是不同类的词素
这种由程序员自定义的变量名和方法名 叫identifier 简称id
它其实就是一个token 代表好多不同的词素
在syntax词的层面 它们的作用是相同的
所以把它们理解为相同的token
token本身的含义就是代号的意思
在做语法分析的时候真正关心的是token 而不是词素
i++;
这个完全符合语法
意思是让i这个值 自增加1
这个里面有多少种token呢？
i是id,2个加号也是一个token，分号也是一个token
由三种token组成的句子 符合语法
- • 语义
语法背后实际的含义
int i; i=0; i++;
这个代码语法没有问题，语义也没有问题，什么情况下语义有问题呢？
float i; i=2.15; i++;
这个时候i++就有问题了 不能对浮点数做自增计算
i++只能对int/char/char*(指针)做计算
浮点数指针也是可以的float*
相当于指针地址往后移一位
所以在语义层面i++是错误的
哪怕在语法层面符合规范
- • 文法 program
文法是语法的合集 比如
s=as | bs' s'=a | 空符
|表示或的意思
S表示开始符
这个代码的整体就是S
要解析这段代码就从S开始
后面的每一行叫过程
a和b这些小写字母叫终结符
是不可再生的
可以简单理解为是一个token或词素
解析到它这就停了
文法把语言中所有的语法规则表示清楚了
根据文法表达式可以生成这个语言所有的可能的文本
即这个语言所有的可能的文本都可以通过这个文法解析
C4（c语言的子集）文法
enum {A,B,C}; char * a; int add(int a,int b){ int ret; ret=a+b; return ret; } int main(){ int tmp; tmp=add(3,4); return 0; }
在语义层面必须要有main方法 但语法层面是无所谓的
根据这段代码来推导下它的文法是怎样的
program= {var decl} | {func decl}
全局变量的声明或函数的声明 也可能是多个
用{}表示一个或多个
这2个是没有带终结符的
如果直接通过这种方式调用的话 会有一些问题
需要用带终结符的定义替换掉 不带终结符的定义
让每一个规则都以终结符开头
这样每一层解析都至少会解析掉一部分的token
剩下的代码会越来越少 这样的话 递归会有一个尽头
上面代码中变量有2种情况 一个是枚举一个是普通的变量的声明
上面代码中没有结构体 没有数组 都是通过指针的方式去实现
var_decl = enum decl|type Id;
这个类型type不管是普通类型还是指针类型
这个是变量所有的可能性
func_decl= type Id(param){ statement }
param=...; statement=...;
所有函数都有返回类型、函数名、参数..
enum decl=enum[Id]{ Id[,Id] }
可能有Id即enum可能有个名字 {}里面可能有一个Id或多个Id
使用递归下降 根据文法解析代码
parse_S(token){ if token == 'a' { parse_S(token++); }else if token == 'b' { parse_S'(token++); }else{ print(sytax_error); } } parse_S'(token){ if token == 'a' { succ; }else if token == 'end of file' { succ; }else{ print(sytax_error); } }
在词法分析的基础上把文法分析出来了
拿到了token 看是否符合S的解析规则
如果符合的话 就逐步解析剩下的部分
剩下的部分也可能是一个S 那就递归的调用这个S的解析方法
去解析剩下的部分
由于每一层解析都至少调了一个终结符
每次都会处理调一个token
那么剩下的token会越来越少
即它的解析是有终点的
如果通过递归下降的方法 去解析一个代码
需要把文法里的每一个规则 都要写一个对应的parse_xx
的函数 把代码逐行解析每一个token 直到EOF
递归下降的文法
program = {global_decl}
program是一个开始符 它的定义是很多个全局定义
global_decl=var_decl | func_decl
全局定义有可能是变量的定义也可能是函数的定义
var_decl = type[* ] Id [','[*] Id]';'|enum
变量的定义可能包含这些;
func_func = type[* ] Id (param_decl) '{' { statement} '}'
param_decl = type[* ] Id [',' type ['*'] Id]
statement = if_stmt | while_stmt | return_stmt | empty_stmt | normal_stmt
normal_stmt = experssion ';'
type = char | Int
Id = ...
experssions = ...
最外层的parse须直接解析到enum或tpye开头的
然后再逐层解析
如果是var_decl就解析变量相关的
如果是func_decl就解析函数相关的
解析func_decl的过程中也需要解析param和statement
statement又需要解析到表达式expressions
递归下降的终点就是解析到表达式
但实际上没有使用递归下降来解析的 因为它的文法比较复杂
所以使用了C4的一个方法 叫优先级爬山
为了在递归下降的过程中解析到表达式停止
需要有一个方法叫 parse_express(){}
当递归下降发现后面是一个表达式的时候
调用parse_express去解析这个表达式
这个函数怎么实现的 递归下降不需要关心的
相当于把表达式当成了终结符
对于递归下降来讲 它遇到终结符就停止了
也相当于遇到表达式就停止了
表达式通过parse_express这个函数单独实现
这个函数使用了优先级爬上的算法
