Rust 实现一个表达式 Parser(6) 文法定义及其简单优化-六虎

至此咱们现已完成了 Lexer 的部分

接下来就能够进入到 Parser

可是在正式动手之前还需求先简略的界说一下文法

PS:

考虑到读者不一定接触过, 因此以下的内容

文法描绘言语均不是标准的 BNF 范式

文法的推导进程不一定标准

尽量削减理论概念的引进

直接左递归放到文末介绍

一切都是通俗易懂为优先

文法是什么

文法是完成一个编译东西必不可缺的部分, 设想咱们在解析的是天然言语

我不是程序员
他是教师
它是电脑

以上三句话都是完好的中文语句, 可是咱们能够发现, 通过组合不同的字词, 语句能够发生完全不同的意思, 但以上三句话都是在对某个事物下界说, 存在一定的共性

中文存在数不清的字词组合, 倘若咱们需求编写一个能够解析中文的编译前端, 在这儿能够穷举么?

穷举是不现实并且不聪明的, 以上语句能够被人们读懂的原因是因为它们都契合中文语法, 咱们将其简略拆解, 如下

我 不是 程序员
他 是  教师
它 是  电脑

如上便能够掏出咱们小学学习的语法常识, 分别是 主语, 谓语, 宾语, 而 主谓宾 也就构成了一个完好的简略语句

这儿咱们将 我, 不是, 是, 程序员 等字词视为 Token, 能够简略推导出下面的语法, 以下的管道符 | 是 或许 的意思

界说句 -> 主语 谓语 宾语
主语 -> 名词
谓语 -> 系动词
宾语 -> 名词
名词 -> "我" | "他" | "它" | "程序员" | "教师" | "电脑"
系动词 -> "是" | "不是"

如上简略的语法界说就能够代表简直一切的简略界说句, 咱们就算不拓展名词和系动词, 也能够重新组合出其他语句

他 不是 程序员
他 是   程序员
它 是   程序员
...

这便是文法, 简略下个界说, 文法是一种用来描绘合法语句的构成规矩的形式化言语

而文法中有两个简略的小概念, 简略区分一下

能打开或许能持续推导的, 则称为 非终止符, 如上例中的 主语, 名词 等
无法再进一步打开或许推导的, 则称为 终止符, 如上例中的 "我", "程序员" 等

文法作业方法

那么详细的, 文法该怎样对语句发生束缚效果呢

以上面的比如为例, 咱们会发现在前面咱们很天然的就将后面的 名词, 系动词 套入 主语, 谓语, 宾语, 再将他们套入前面的界说句, 终究得到咱们期望的语句

而在本专栏的系列文章中, 文法的作业方法是以上这个进程的逆进程

文法从起点开端, 不断的依照界说的规矩以及某种规矩进行推导打开, 终究若能够得到给定的语句, 则以为该语句合法, 不然不合法

举例如下

文法界说如下

界说句 -> 主语 谓语 宾语
主语 -> 名词
谓语 -> 系动词
宾语 -> 名词
名词 -> "我" | "他" | "它" | "程序员" | "教师" | "电脑"
系动词 -> "是" | "不是"

"它不是教师" 这个语句是合法的界说句么
界说句 => 主语 谓语 宾语
      => 名词 谓语 宾语
      => "它" 谓语 宾语
      => "它" 系动词 宾语
      => "它" "不是" 宾语
      => "它" "不是" 名词
      => "它" "不是" "教师"
能够从界说句推导出 "它不是教师" 这个语句, 是合法的

文法界说

上面简略介绍了文法的界说, 接下来咱们来推行到编程言语中, 先从 表达式 开端

咱们的表达式支撑四则运算, Token 类型现已提前界说好了, 那么很快速的就能够写出下列文法

Expr -> Add
      | Mul
      | Number
      | "(" Expr ")"
      ;
Add -> Expr ("+" | "-") Expr ;
Mul -> Expr ("*" | "/") Expr ;
Number -> NUM

如上便是初步的文法界说, 咱们直接界说出三种语法, 分别是 Expr, Add, Mul

这儿的要点在于, Expr 能够发生 Add, Add 又能够发生 Expr, 这样的界说方法是递归的, 因此在进行文法打开的时分, 会出现下面的状况

"1 + 2 + 3" 是不是契合文法的表达式??
Expr => Add
     => Expr ("+" | "-") Expr
     => Expr "+" Expr
     => Add "+" Expr
     => Expr "+" Expr "+" Expr
     => Number "+" Expr "+" Expr
     => "1" "+" Expr "+" Expr
     => "1" "+" Number "+" Number
     => "1" "+" "2" "+" "3"
是契合文法的

处理算符优先级

为什么

以上界说出来的文法现在有一个很明显的问题, Add 和 Mul 是同一层级的, 这意味着 +, - 拥有和 *, / 相同的优先级, 咱们直接看看当时文法处理表达式 "1 + 2 * 3"

"1 + 2 * 3"
Expr => Add
     => Expr "+" Expr
     => Number "+" Mul
     => Number "+" Expr "*" Expr
     => Number "+" Number "*" Number
     => "1" "+" "2" "*" "3"

咱们将语法推导进程简略转化为树形结构, 如下

看似没有问题, 但还存在下面这种推导方法

"1 + 2 * 3"
Expr => Add
     => Expr "*" Expr
     => Add "*" Expr
     => Number "+" Expr "*" Expr
     => Number "+" Number "*" Number
     => "1" "+" "2" "*" "3"

其推导树如下

这下出现大问题了, 咱们都知道遍历 AST 会以 DFS 的方法, 这意味着若是遍历下面这棵树, 会发生过错的核算顺序

即, 1 + 2 * 3 算成 (1 + 2) * 3

怎样做

咱们现在的问题是文法的界说无法清晰核算顺序以及不同表达式的优先级问题, 在树形结构中就体现在咱们总是期望优先级高的表达式作为优先级低的表达式的子节点

那么咱们能够将优先级高的表达式作为优先级低的表达式的发生式, 文法修正如下

修正前

Expr -> Add
      | Mul
      | Number
      | "(" Expr ")"
      ;
Add -> Expr ("+" | "-") Expr ;
Mul -> Expr ("*" | "/") Expr ;
Number -> NUM

修正后

Expr   -> Add ;
Add    -> Add ("+" | "-") Mul
        | Mul
        ;
Mul    -> Mul ("*" | "/") Factor
        | Factor
        ;
Factor -> "(" Expr ")"
        | Number
        ;
Number -> NUM ;

这样修正之后, 加减法表达式总是优先打开, 这意味着加减法表达式总是作为父节点, 而乘除法表达式再次打开时就会作为加减法表达式的子节点, 也就达到了咱们的意图

修正后的文法推导刚才的表达式, 如下

"1 + 2 * 3"
Expr => Add
     => Add "+" Mul
     => Mul "+" Mul
     => Factor "+" Mul
     => Number "+" Mul
     => "1" "+" Mul
     => "1" "+" Mul "*" Factor
     => "1" "+" Number "*" Number
     => "1" "+" "2" "*" "3"

消除左递归

现在的文法还存在一个大大大问题

是什么

咱们抛开比如, 结合前文说到的 文法从起点开端, 不断的依照界说的规矩以及某种规矩进行推导打开, 终究若能够得到给定的语句, 则以为该语句合法, 不然不合法, 来调查一下现在的文法

Expr   -> Add ;
Add    -> Add ("+" | "-") Mul
        | Mul
        ;
Mul    -> Mul ("*" | "/") Factor
        | Factor
        ;
Factor -> "(" Expr ")"
        | Number
        ;
Number -> NUM ;

咱们对以上文法的进行部分抽离, 独自来看愈加清晰, 此处为了进一步简化, 将 Mul 替换为 Number, 且 ("+" | "-") 简化为 "+"

Add -> Add "+" Number ;

咱们依照之前的流程, 对该文法界说进行推导打开, 如下

Add => Add "+" Number
    => Add "+" Number "+" Number
    => Add "+" Number "+" Number "+" Number
    => Add "+" Number "+" Number "+" Number "+" Number
    => ...

能够发现, Add 能够无止境的打开自己, 终究陷入一个死循环, 这个问题会导致 Parser 解析进程爆栈, 这便是著名的 左递归(Left Recursion)问题

为什么

再次调查这个出现左递归问题的文法

Add -> Add "+" Number ;

咱们发现, 箭头左边的非终结符和右边的第一项如出一辙, 并且在推导进程中, 也总是由箭头右边的非终止符 Add 打开, 发生一个 Add 再发生一个 "+" Number, 而推导前后只会增加 "+" Number, 不会导致任何符号的削减, 这意味着, 这是一匹不需求吃草就能跑的马

怎样做

现已得知问题出现在箭头右边的第一项 Add, 那么咱们想办法将其替换掉或许移动到别的地方就能够了, 可是要怎样确保不改变原有语义呢

直接上公式, 这个公式简直能够解决一切的左递归问题

$\alpha | \beta$

改写为

$\beta A’$

$\alpha A’ | \epsilon$

对公式进行简略的解释

$\alpha$ 和 $\beta$ 表明恣意终结符
$A$ 和 $A^{'}$ 表明恣意非终结符
$\epsilon$ , 表明空匹配, 简略视为空即可

做一下

上面引出了最重要的解决左递归的公式, 下面直接实践, 现有文法

Add    -> Add ("+" | "-") Mul
        | Mul
        ;
Mul    -> Mul ("*" | "/") Factor
        | Factor
        ;
Factor -> "(" Expr ")"
        | Number
        ;
Number -> NUM ;

咱们仔细调查会发现, Add 和 Mul 的语法界说存在左递归的问题

此处直接将 Mul 视为终结符
Add -> Add ("+" | "-") Mul | Mul ;
       --- ---------------   ---
        |         |           |
        A         a           b

带入公式得到

Add  -> Mul Add' ;
Add' -> ("+" | "-") Mul Add'
      | <empty>
      ;

对 Mul 进行相似的处理, 得到如下文法

Mul  -> Factor Mul' ;
Mul' -> ("*" | "/") Factor Mul'
      | <empty>
      ;

终究文法如下

Expr   -> Add ;
Add    -> Mul Add' ;
Add'   -> ("+" | "-") Mul Add'
        | <empty>
        ;
Mul    -> Factor Mul' ;
Mul'   -> ("*" | "/") Factor Mul'
        | <empty>
        ;
Factor -> "(" Expr ")"
        | Number
        ;
Number -> NUM ;

化简文法

现在的文法现已能够正常作业了, 可是还存在优化的空间, 如下

咱们调查一下这两个文法界说

Add  -> Mul Add' ;
Add' -> ("+" | "-") Mul Add'
      | <empty>
      ;

若是将 Add' 打开, 咱们会发现它会长成这样

Add' => ("+" | "-") Mul Add'
     => ("+" | "-") Mul ("+" | "-") Mul Add'
     => ("+" | "-") Mul ("+" | "-") Mul ("+" | "-") Mul Add'
     => ...

上面这个式子会一直循环, 直到打开时挑选了一个 $\epsilon$ , 也便是空匹配 <empty>, 或许从一开端就直接匹配 $\epsilon$ , 咱们用正则表达式来描绘这种情景, 便是下面这样

Add' -> (("+" | "-") Mul )* ;

正则表达式中, * 通常表明匹配 0 次或许更屡次, 刚好对应了这个场景, 咱们再把这条文法合并到 Add 的文法中, 如下

Add -> Mul (("+" | "-") Mul)* ;

将 Mul 的文法也进行相似的处理, 咱们就得到了终究化简过后的文法

Expr   -> Add ;
Add    -> Mul (("+" | "-") Mul)* ;
Mul    -> Factor (("*" | "/") Factor)* ;
Factor -> "(" Expr ")"
        | Number
        ;
Number -> NUM ;

直接左递归 & 直接左递归

直接比照一下, 仍是很好了解的, 实际上原本并不打算介绍直接左递归的解决方法, 可是想起自己写代码格式化东西项意图时分, 碰到的左递归问题基本上都是直接左递归问题, 因此仍是在这儿提一嘴

直接左递归
A -> Aa | b ;
直接左递归
A -> B | b;
B -> Aa ;

直接左递归的消除其实大体上来说仍是正文说到的公式

$\alpha | \beta$

改写为

$\beta A’$

$\alpha A’ | \epsilon$

可是直接左递归需求简略的将中心项消去, 以上面那个比如来说

A -> B | b ;
B -> Aa ;
改写为
A -> Aa | b ;
消除左递归
A  -> b A' ;
A' -> aA' | <empty> ;

在这儿罗列另一种经常碰到的状况, 没有很好的比如, 就顺手写了

如

A -> Bb | Cc | a ;
B -> C  | a ;
C -> Aa ;

能够发现这儿存在一个直接左递归, A -> B -> C -> A, 解决方案如下

A -> Bb | Cc | a ;
B -> C  | a ;
C -> Aa ;
B 带入 A 得到
A -> Cb | ab | Cc | a ;
C -> Aa ;
C 带入 A 得到
A -> Aab | Aac | ab | a ;

发现这儿存在两个直接左递归, 直接上公式

A -> Aab | Aac | ab | a ;
      --    --   --   -
      |     |    |    |
      a     a    b    b
消除左递归后如下
A -> abA' | aA' ;
A' -> abA' | acA' | <empty> ;

总而言之, 解决直接左递归的方法便是转化为直接左递归

总结

本文完成了基础的文法界说及其相关的处理和简略的化简作业, 可是实际上这儿面有很多很复杂的操作, 也存在很多很不流畅的理论, 为了下降阅读门槛, 在正文的描绘中会存在一些不严谨不标准的地方

不过从实践角度来考虑的话, 好歹是正确完成了, 便是说最少能跑

Q&A

Q: 怎样讲的这么难明?

A: 这部分真的很费事, 本文现已极力防止引进过多的理论, 尽量从实操出发了, 可是不可防止的需求用到一些公式和形式化描绘之类的东西, 这些真实无法防止

Q: 怎样觉得你写的像是在读 PPT 似的?

A: 你别说, 这部分真的就大部分都是机械性的作业, 我乃至觉得我列个提纲然后把要害公式和模板之类的给出来会更好, 文中说到的优先级的处理方法和左递归的处理方法基本都是固定的, 完全能够把现在这个处理流程作为一个模板, 是的没错, 我写其他编程言语的文法的时分, 用的也是这三板斧

Rust 实现一个表达式 Parser(6) 文法定义及其简单优化

文法是什么

文法作业方法

文法界说

处理算符优先级

为什么

怎样做

消除左递归

是什么

为什么

怎样做

做一下

化简文法

直接左递归 & 直接左递归

总结

Q&A

作者信息

推广

Rust 实现一个表达式 Parser(6) 文法定义及其简单优化

文法是什么

文法作业方法

文法界说

处理算符优先级

为什么

怎样做

消除左递归

是什么

为什么

怎样做

做一下

化简文法

直接左递归 & 直接左递归

总结

Q&A

相关文章

研发过程中的文档管理与工具

一文弄懂 Diffusion Model

火山引擎 DataLeap 下 Notebook 系列文章一：技术选型之路

视野修炼-技术周刊第78期 | Node.js纪录片

作者信息

推广