前言
前言:词法分析和语法分析部分的设计,和在实际编程过程中,编译期的语法检查和相关的错误提示是息息相关的
此篇可以看做是《自制编译器》的读书笔记,内部一些举例,例如stmts是在Cb语言内的描述,在C或者OC的编译器中名字未必一致,但是功能是相通的.
词法分析
基于EBNF的语法描述
以下这些是比较简单的逻辑概念,很容易理解
| 种类 | 举例 |
|---|---|
| 终端符 | <IDENTIFIER> 或 "," |
| 非终端符 | name() |
| 连接 | <UNSIGNED><LONG> |
| 重复 0 次或多次 | (","expr())* |
| 重复 1 次或多次 | (stmt())+ |
| 选择 | <CHAR> | <SHORT> | <INT> | <LONG> |
| 可以省略 | [<ELSE> stmt()] |
语法的二义性和token的超前扫描
空悬else
举个例子,如果规则设计为"if" "(" expr() ")" stmt() ["else" stmt()]
以下两种写法都符合以上规则:
写法1
if (cond1) {
if (cond2) {
f();
} else {
g();
} }
写法2
if (cond1) {
if (cond2) {
f();
}
} else {
g();
}
对应两种解释的语法树
if 语句的规则存在二义性的问题是比较有名的，俗称空悬 else(dangling else).
选择冲突
type(): {} {
<SIGNED> <CHAR>
| <SIGNED> <SHORT>
| <SIGNED> <INT>
| <SIGNED> <LONG>
......
事实上, 在遇到用“|”分隔的选项时，在仅读取了 1 个 token 的时刻就会对选项进 行判断，确切的动作如下所示。
- 读取1个
token - 按照书写顺序依次查找由上述
token开头的选项 - 找到的话就选用该选项
也就是说,根据上述规则, 在读取了 <SIGNED> token 时就已经选择了 <SIGNED> <CHAR>,因此即便写了选项 2 和选项 3，也是完全没有意义的。这个问题称选择冲突(choice conflict)
token的超前扫描
之前提到了在遇到选项时仅根据读取的 1 个 token 来判断选择哪个选项.事实上这只是因为仅根据读取的 1 个 token 进行判断.只要明确指定,可以在读取更多的 token 后再决定选择哪个选项。这个功能就称为 token 的超前扫描 (lookahead)
刚才列举的语法规则也能够用 token 的超前扫描进行分析
type(): {}
{
LOOKAHEAD(2) <SIGNED> <CHAR>
| LOOKAHEAD(2) <SIGNED> <SHORT>
| LOOKAHEAD(2) <SIGNED> <INT>
| <SIGNED> <LONG>
以下省略
添加的 LOOKAHEAD(2) 是关键.LOOKAHEAD(2) 表示的意思为“读取 2 个 token 后,如果读取的 token 和该选项相符合,则选择该选项”
也就是说,读取 2 个 token,如果它们是 <SIGNED> 和 <CHAR> 的话，就选用选项 1.同样,第 2 个选项的意思是读取 2 个 token,如果 它们是 <SIGNED> 和 <SHORT> 的话,就选用选项 2
需要超前扫描的 token 个数(上述例子中为 2)是通过“共通部分的 token 数 +1”这样的算式计算得到的
可以省略的规则和冲突
除“选择”以外，选择冲突在“可以省略”或“重复 0 次或多次”中也可能发生。
可以省略的规则中，会发生“是省略还是不省略”的冲突，而非“选择选项 1 还是选项 2”的冲突。之前提到的空悬 else 就是一个具体的例子
空悬 else 最直观的判断方法是“else 属于最内侧的 if”,因此试着使用 LOOKAHEAD 来进 行判断.首先,未使用 LOOKAHEAD 进行判断的规则描述如下所示
if_stmt(): {}
{
<IF> "(" expr() ")" stmt() [<ELSE> stmt()]
}
使用LOOKAHEAD来避免冲突发生的规则如下
if_stmt(): {}
{
<IF> "(" expr() ")" stmt() [LOOKAEHAD(1) <ELSE> stmt()]
}
如你所见,判断方法本身非常简单.通过添加 LOOKAHEAD(1),就可以指定“读取 1 个 token后,如果该token符合规则(即如果是<ELSE>)则不省略<ELSE> stmt()”.这样就能 明确 else 始终属于最内侧的 if 语句，空悬 else 的问题就可以解决了
重复和冲突
重复的情况下会发生“是作为重复的一部分读入还是跳出重复”这样的选择冲突。 来看一个具体的例子，如下所示为 C♭ 中表示函数形参的声明规则。
param_decls(): {}
{
type() ("," type())* ["," "..."]
}
这个规则中，表示可变长参数的"," "..."不会被解析
因为根据上述规则，在读取 type() 后又读到 "," 时，本来可能是 "," type() 也可能是 "..." 的,但默认向前只读取 1 个 token,因此在读到 "," 时就必须判断是继续 重复还是跳出重复。并且恰巧","和("," type())的开头一致，所以会一直判断为 重复 ("," type())*，而规则 "," "..." 则完全不会被用到。实际上如果程序中出现 ","
"..."，会因为不符合规则"," type()而判定为语法错误。 要解决上述问题，可以如下添加 LOOKAHEAD。
param_decls(): {}
{
type() (LOOKAHEAD(2) "," type())* ["," "..."]
}
这样在每次判断该重复时就会在读取 2 个 token 后再判断是否继续重复，因此在输 入了"," "..."后就会因为检测到和"," type()不匹配而跳出("," type())*的重复
更灵活的超前扫描
关于 token 的超前扫描,还有更为灵活的方法。之前提到的 LOOKAHEAD 可以指定“恰好读取了几个 token”，除此之外还可以指定“读取符合这个规则的所有 token”
举例
definition(): {}
{
storage() type() <IDENTIFIER> ";"
| storage() type() <IDENTIFIER> arg_decls() block() 以下省略
除了提取共通部分,还可以用超前扫描
用超前扫描来分析上述规则,读取“恰好 n 个”token 是行不通的.原因在于共通部分 storage() type() <IDENTIFIER>中存在非终端符号storage()和type().因为不知道 storage() 和 type() 实际对应几个 token，所以无法用读取“恰好 n 个”token 来处理
使用超前扫描的做法
definition(): {}
{
LOOKAHEAD(storage() type() <IDENTIFIER> ";")
storage() type() <IDENTIFIER> ";"
| storage() type() <IDENTIFIER> arg_decls() block() 以下省略
超前扫描的相关注意事项
即便写了 LOOKAHEAD 也并非一定能按照预期对程序进行分析。添加 LOOKAHEAD 后 Choice conflict 的警告消息的确消失了,不会对 LOOKAHEAD 描述的 内容进行任何检查.在发生选择冲突的地方加上 LOOKAHEAD 后不再显示警告,仅此而已. LOOKAHEAD 处理的描述是否正确,我们必须自己思考
语法分析
语法单位
一般编程语言的语法单位有下面这些
- 定义(definition)
- 声明(declaration)
- 语句(statement)
- 表达式(expression)
- 项(term)
对以下语法的声明进行了介绍,主要是通过正则表达的一些符号,终端符和非终端符的组合,使得对某些语法的定义符合实际使用的需求场景,并且避免在各种情况下出现的逻辑漏洞,较为细节
-
import声明的语法 - 各类定义的语法
- 变量定义的语法
- 函数定义的语法
- 结构体定义和联合体定义的语法
结构体 defstruct 的规则
defstruct(): {}
{
<STRUCT> name() member_list() ";"
}
联合体
defunion(): {}
{
<UNION> name() member_list() ";"
}
- 结构体成员和联合体成员的语法
- typedef语句的语法
- 类型的语法
type和typeref - 基本类型的语法
语句的分析
语句的语法
以stmts为例
stmts(): {} {
(stmt())*
}
stmt(): {} {
( ";"
| LOOKAHEAD(2) labeled_stmt() | expr() ";"
| block()
| if_stmt()
| while_stmt()
| dowhile_stmt()
| for_stmt()
| switch_stmt()
| break_stmt()
| continue_stmt()
| goto_stmt()
| return_stmt()
)
}
-
if语句的语法 - 省略
if语句和大括号 -
while语句的语法 -
for语句的语法 - 各类跳转语句的语法
表示 break 语句的 break_stmt() 和表示
return 语句的 return_stmt()
表达式的分析
表达式的整体结构
一般来说，越是离语法树的根节点近的符号，其解析规则越是先出 现。这里的“先”是指，从 compilation_unit() 跟踪调查规则时， 会较早地出现在跟踪到的规则中。
表达式的语法树
换言之，就是可以从优先级低的运算符的规则开始，按照自上而下的顺序来描述表达式的 规则。
expr的规则
expr(): {} {
LOOKAHEAD(term() "=")
term() "=" expr()
| LOOKAHEAD(term() opassign_op())
term() opassign_op() expr()
| expr10()
}
这个规则比较难以理解，我们姑且如下所示把 LOOKAHEAD 去掉。
term() "=" rhs_expr() // 选项1
| term() opassign_op() expr() // 选项2
| expr10() // 选项3
此时，选项 1 是 通的赋值表达式，选项 2 表示的是自我赋值的表达式，选项 3 的 expr10() 是比赋值表达式优先级更高的表达式。像这样在 expr 后添加数字的符号有 expr1() 到 expr10()。数字越小，所对应的表达式的优先级越高
二元运算符
opassign_op(): {}
{
( "+="
| "-="
| "*="
| "/="
| "%="
| "&="
| "|="
| "^="
| "<<="
| ">>="
)
}
条件表达式
接着来看一下 expr10() 的规则。这是条件运算符(三元运算符)的规则
expr10(): {}
{
expr9() ["?" expr() ":" expr10()]
}
非终端符号 exprN 中的“N”部分是与优先级对应的，数值越小优先级越高。上述规则的 优先级为 10，所以属于较低的优先级。
条件表达式中有 3 个表达式，各个表达式分别用哪个 expr 是这里的难点。原则上来说 “只要是该处允许的语法所对应的符号就可以”，但至少对于最左侧的 expr 有着特别的限制，
那就是“不允许 expr10 自身或开头和 expr10 相匹配的符号”。
JavaCC 会将 1 个规则转化为 1 个方法，即如果像上面这样定义了符号 expr10 的规则，就
会生成 expr10 方法，并且会根据规则生成方法的处理内容。如果在规则中写有非终端符号， 就会直接调用符号所对应的方法。也就是说，像上面这样写有 expr9() 的话，就会在该处调 用 expr9 方法。如果写的是终端符号，则直接转化为 token。
那么如果在 expr10 的定义中又出现了 expr10 的话会怎么样呢?这样就相当于在方法 expr10 中又调用了 expr10 自身，会陷入无限的递归之中。所以在 expr10 规则的左侧不能 出现 expr10 自身或者以 expr10 开头的符号。
二元运算符
二元运算符的优先级
项的分析
项的规则
term(): {} {
LOOKAHEAD("(" type()) "(" type() ")" term()
| unary()
}
需要关注的细节有
- 前置运算符的规则
- 后置运算符的规则
- 字面量的规则
总结
总结:该篇较为细致(琐碎)的介绍了词法分析和语法分析的细节,对于
终端符和非终端符的组合使用,以及在使用中容易遇到的错误进行了非常细致的举例说明,通过学习,需要掌握的有: 超前扫描的使用(很重要,是理解各种组合规则的基础), 各种运算法则(连接,选择,忽略,重复等).
网友评论