编译器学习之 (二) : 词法分析和语法分析

2017-09-26 本文已影响885人 sea_biscute

前言

前言:词法分析和语法分析部分的设计,和在实际编程过程中,编译期的语法检查和相关的错误提示是息息相关的
此篇可以看做是《自制编译器》的读书笔记,内部一些举例,例如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()
}

需要关注的细节有

前置运算符的规则
后置运算符的规则
字面量的规则

总结

总结:该篇较为细致(琐碎)的介绍了词法分析和语法分析的细节,对于终端符和非终端符的组合使用,以及在使用中容易遇到的错误进行了非常细致的举例说明,通过学习,需要掌握的有: 超前扫描的使用(很重要,是理解各种组合规则的基础), 各种运算法则(连接,选择,忽略,重复等).

编译器学习之 (二) : 词法分析和语法分析

前言

词法分析

基于EBNF的语法描述

语法的二义性和token的超前扫描

空悬else

选择冲突

token的超前扫描

可以省略的规则和冲突

重复和冲突

更灵活的超前扫描

超前扫描的相关注意事项

语法分析

语法单位

语句的分析

语句的语法

表达式的分析

表达式的整体结构

expr的规则

条件表达式

二元运算符

项的分析

项的规则

总结

猜你喜欢

热点阅读