乐趣区

关于golang:Go编译原理系列2词法分析语法分析基础

jiezi

前言

关注公众号：IT 猿圈，后盾回复：Go 编译原理系列 1，可取得 pdf 版

在 前一篇 编译原理的文章中，并没有介绍词法剖析是如何将源文件中的字符转换成一个个的词法单元，两头用到了哪些技术或工具。也没有具体的介绍语法分析阶段中的一些常见的文法及语法分析形式。所以，本文你能够理解到：

  • 词法分析器是如何将咱们的源文件中的字符翻译成词法单元的（不确定有穷状态机 & 确定有穷状态机）
  • 有哪些常见的词法分析器？他们是如何工作的？
  • 上下文无关文法
  • Go 语言中的一些文法的规定
  • 形象语法树的生成
  • 语法分析的一些办法（自顶向下、自底向上）

💡 Tips：下边的内容可能会比拟形象，特地是语法分析根底局部波及到的文法以及解决文法的两种办法。然而我都会通过表格或者图的形式，将每一步都形容分明，置信您保持看完，肯定会有所播种

词法剖析根底

Token

在 前一篇 编译原理的文章中能够晓得，词法剖析的工作是从左往右逐字符扫描源程序内容，辨认出各个单词，确定单词的类型 。将辨认出的单词转换成对立的机内示意——— 词法单元 (token) 模式

比方辨认出这些单词是关键字、标识符、常量、界线符、还是运算符等。因为在任何一门编程语言中，这些类型是能够枚举的，所以个别会给定义好，比方 Go 语言中用 _Name 来示意标识符，用 _Operator 来示意操作符

像 _Name、_Operator 就是咱们常说的 Token，最终被编译的源文件中的内容，都会被词法分析器解析成这样的 Token 模式

那词法解析器是如何辨认出源文件中各个单词，并判断单词是关键字？还是运算符？还是界线符的？这就用到了 确定有穷自动机

不确定有穷自动机 & 确定有穷自动机

这里不具体介绍有穷自动机里边的字母表、句子、符号等形象的概念，次要弄明确它是怎么工作的即可，它的实现不是本文的重点，对有穷自动机感兴趣的能够看《编译原理》的第三章

有穷自动机分为两类，即 不确定的有穷自动机 （NFA）和 确定的有穷自动机（DFA）。下边顺次介绍这两个有穷自动机是如何工作的

不确定有穷自动机（NFA）

其实咱们用一门编程语言编写的代码，能够看做是一个长字符串，词法剖析过程要做的就是辨认出这个长字符串中，哪些是关键字、哪些是运算符、哪些是标识符等

如果让咱们来做这样一件事件，最容易想到的就是用 正则表达式。其实词法分析器进行解析的过程，也是利用正则，通过正则将长字符串进行宰割，宰割进去的字符串（可能是标识符、可能是运算符等）去匹配到相应的 token

假如说有一个正则表达式(a|b)*abb，而后给你一个字符串，判断这个字符串是否满足这个正则表达式？

如果你对回溯算法比拟相熟的话，咱们晓得它能够通过简略的回溯算法来实现。然而这里用到另一种办法来实现，就是 不确定有穷自动机（NFA）

依据前边给的正则表达式，能够画出如下的有穷自动机：

红色圆中的数字示意的是 状态

  • 当在 0 这个状态的时候遇到字符 a 或者 b，则状态迁徙到自身
  • 0 这个状态遇到 a 也能够迁徙到状态 1
  • 1 这个状态遇到 b，则迁徙到状态 2
  • 2 这个状态遇到 b，则迁徙到状态 3（3 是最终状态）

该状态机一共有四个状态，其中 0、1、2 这三个状态是一个单层的圆示意的，3 这个状态是用两层的圆示意的。单层的圆示意的是状态机的 中间状态 ，双层的圆示意的是状态机的 最终状态。箭头和其上方的字符，示意的是每个状态遇到不同的输出，迁徙到另一个状态

你能够把以下几个字符串作为上边这个状态机的输出，看是否可能走到最终状态，如果能走到，阐明能够匹配，如果不能走到，阐明不能匹配

能够匹配：abb、aabb、babb、aababb
不可匹配：a、ab、bb、acabb

从上边能够看进去，NFA 可能解决匹配源文件中字符串目标，这样看如同咱们只有针对标识符、关键字、常量等写出相应的正则表达式，而后通过自动机就能宰割出源文件中各个字符串，而后匹配相应的 token

然而它有一个缺点，比方拿 abb 去上边的状态机去匹配，0 状态遇到 a 可能还是 0 这个状态，0 状态再遇到 0，还是 0 这个状态，再遇到 b 还是 0 这个状态，这样它又不能匹配了，实际上 abb 是能满足(a|b)*abb 这个正则表达式的。起因就是在 0 状态的时候遇到 a，它转移的状态是不确定的，所以它叫不确定有穷自动机

为了解决上边的问题，就呈现了确定有穷自动机

确定有穷自动机（DFA）

还是上边那个正则表达式：(a|b)*abb，画出它的有穷自动机就是下边这样

  • 0 这个状态遇到 a，则迁徙到状态 1
  • 0 这个状态遇到 b，则还是迁徙到自身状态 0
  • 1 这个状态遇到 a，则还是迁徙到自身状态 1
  • 1 这个状态遇到 b，则迁徙到状态 2
  • 2 这个状态遇到 a，则迁徙到状态 1
  • 2 这个状态遇到 b，则迁徙到状态 3（3 是最终状态）
  • 3 这个状态遇到 a，则迁徙到 1 状态
  • 3 这个状态遇到 b，则迁徙到 0 状态

0、1、2 是中间状态，3 是最终状态。与不确定有穷自动机的区别就是，它的每一个状态遇到的输出，都会有一个确定的状态迁徙。你能够用前边给的字符串来验证一下这个有穷自动机

这样通过 DFA 就能够解决咱们的问题。然而，如果这样的话，要对一个源文件进行词法剖析，咱们就须要写很多的正则表达式，并且须要手动的为每一个正则表达式写有穷状态机的实现

为了解决这个问题，就呈现了很多的词法解析器的工具，能让咱们防止手动的去实现一个有穷自动机，下边就简略介绍两个常见的词法解析器的工具

词法分词器

re2c

咱们能够编写合乎 re2c 规定的文件，而后通过 re2c 生成.c 的文件，再去编译执行这个.c 文件

如果你没有装置 re2c，须要先装置一下（点击下载）。下载实现之后，装置过程

1. 解压：tar -zxvf re2c-1.1.1.tar.gz
2. 进入解压进去的目录：cd re2c-1.1.1
3. ./configure
4. make && make install

下边就是编写一个 re2c 的源文件。假如我要辨认一个数字是二进制的还是八进制的还是十六进制的，看一下用 re2c 是如何编写的（re2c 的源文件是.l 的文件）

#include <stdio.h> // 头文件，后边用到的标注输入输出就用到了这个头文件里的办法
enum num_t {ERR, BIN, OCT, DEC, HEX}; // 定义了 5 个枚举值
static num_t lex(const char *YYCURSOR) // 返回值类型是 num_t。下边函数看着只有一行代码，还有一堆正文，其实这一堆正文就是 re2c 的外围代码，!re2c 是它的结尾
{
    const char *YYMARKER;
    /*!re2c
        re2c:define:YYCTYPE = char;
        re2c:yyfill:enable = 0;
        end = "\x00";
        bin = '0b'[01]+; // 这些都是正则表达式
        oct = "0"[0-7]*;
        dec = [1-9][0-9]*;
        hex = '0x'[0-9a-fA-F]+;
        *       {return ERR;}
        bin end {return BIN;} // 如归以匹配的二进制模式结尾，并且以匹配的 end 模式结尾，就返回二进制的枚举值，其余同理
        oct end {return OCT;}
        dec end {return DEC;}
        hex end {return HEX;}
    */
}
int main(int argc, char **argv) // 获取参数并遍历，调用 lex 函数，依据它的返回值来进行 switch，看它属于那种类型的数字
{for (int i = 1; i < argc; ++i) {switch(lex(argv[i])) {case ERR: printf("error\n");break;
            case BIN: printf("binary\n");break;
            case OCT: printf("octal\n");break;
            case DEC: printf("decimal\n");break;
            case HEX: printf("hexadecimal\n");break;
        }
    }
    return 0;
}

阐明：如果你将代码粘过来不能失常应用，尝试把我写的正文去掉

而后去解决这个.l 文件

# re2c integer.l -o integer.c
# g++ integer.c -o integer
# ./integer 0b10（此时应该输入 binary）

你也能够试一下其它的进制数，都能够失常失去它是哪种进制的数

当初你能够关上方才咱们生产的 integer.c 文件，它的内容如下：

/* Generated by re2c 1.1.1 on Thu Dec  9 23:09:54 2021 */
#line 1 "integer.l"
#include <stdio.h>
enum num_t {ERR, BIN, OCT, DEC, HEX};
static num_t lex(const char *YYCURSOR)
{
    const char *YYMARKER;
    
#line 10 "integer.c"
{
    char yych;
    yych = *YYCURSOR;
    switch (yych) {
    case '0':    goto yy4;
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':    goto yy5;
    default:    goto yy2;
    }
yy2:
    ++YYCURSOR;
yy3:
#line 14 "integer.l"
    {return ERR;}
#line 32 "integer.c"
yy4:
    yych = *(YYMARKER = ++YYCURSOR);
    switch (yych) {
    case 0x00:    goto yy6;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':    goto yy8;
    case 'B':
    case 'b':    goto yy11;
    case 'X':
    case 'x':    goto yy12;
    default:    goto yy3;
    }
yy5:
    yych = *(YYMARKER = ++YYCURSOR);
    switch (yych) {
    case 0x00:    goto yy13;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':    goto yy15;
    default:    goto yy3;
    }
yy6:
    ++YYCURSOR;
#line 16 "integer.l"
    {return OCT;}
#line 71 "integer.c"
yy8:
    yych = *++YYCURSOR;
    switch (yych) {
    case 0x00:    goto yy6;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':    goto yy8;
    default:    goto yy10;
    }
yy10:
    YYCURSOR = YYMARKER;
    goto yy3;
yy11:
    yych = *++YYCURSOR;
    if (yych <= 0x00) goto yy10;
    goto yy18;
yy12:
    yych = *++YYCURSOR;
    if (yych <= 0x00) goto yy10;
    goto yy20;
yy13:
    ++YYCURSOR;
#line 17 "integer.l"
    {return DEC;}
#line 101 "integer.c"
yy15:
    yych = *++YYCURSOR;
    switch (yych) {
    case 0x00:    goto yy13;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':    goto yy15;
    default:    goto yy10;
    }
yy17:
    yych = *++YYCURSOR;
yy18:
    switch (yych) {
    case 0x00:    goto yy21;
    case '0':
    case '1':    goto yy17;
    default:    goto yy10;
    }
yy19:
    yych = *++YYCURSOR;
yy20:
    switch (yych) {
    case 0x00:    goto yy23;
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
    case 'A':
    case 'B':
    case 'C':
    case 'D':
    case 'E':
    case 'F':
    case 'a':
    case 'b':
    case 'c':
    case 'd':
    case 'e':
    case 'f':    goto yy19;
    default:    goto yy10;
    }
yy21:
    ++YYCURSOR;
#line 15 "integer.l"
    {return BIN;}
#line 160 "integer.c"
yy23:
    ++YYCURSOR;
#line 18 "integer.l"
    {return HEX;}
#line 165 "integer.c"
}
#line 19 "integer.l"

}
int main(int argc, char **argv)
{for (int i = 1; i < argc; ++i) {switch(lex(argv[i])) {case ERR: printf("error\n");break;
            case BIN: printf("binary\n");break;
            case OCT: printf("octal\n");break;
            case DEC: printf("decimal\n");break;
            case HEX: printf("hexadecimal\n");break;
        }
    }
    return 0;
}

这段代码其实就是实现了上边说的确定有穷自动机。代码很简略，你能够拿示例中的 0b10 作为这段代码的输出，看一下通过这个是否能失去它是 binary

所以，咱们其实只需提供一些正则表达式，re2c 就能够帮咱们实现一个确定有穷自动机（DFA）。这样就能够轻松的做一些词法解析的事件，咱们就提供正则表达式即可

lex

lex 这个词法分析器生成工具在《编译原理》这本书的第三章有介绍，我这里仅简略的介绍一下，更具体的内容能够去对应章节看

lex 跟 re2c 原理其实是一样的，依照 lex 的规定编写它的源代码（也是以.l 结尾的），而后将其生成.c 文件，生成的.c 文件其实就是将.l 文件中编写的正则匹配转换成有穷状态机的 C 语言实现

我这里参考王晶大佬的《面向信奉编程》中编译原理相干博客中的一段 lex 代码，它通过这段代码能够对简略的 go 源文件进行词法解析

%{
#include <stdio.h>
%}

%%
package      printf("PACKAGE");
import       printf("IMPORT");
\.           printf("DOT");
\{printf("LBRACE");
\}           printf("RBRACE");
\(printf("LPAREN");
\)           printf("RPAREN");
\"printf("QUOTE ");
\n           printf("\n");
[0-9]+       printf("NUMBER");
[a-zA-Z_]+   printf("IDENT");
%%

这里边其实就是定义了一些关键字的正则，去匹配 go 源文件中的关键字、数字、标识符等。同样通过 lex 命令将上边这个.l 文件编译成.c 文件，.c 文件其实就是实现了一个有穷的状态机（依据.l 文件中提供的正则），可能匹配.l 中定义的一些符号

假如有这么一段 go 的代码

package main

import ("fmt")

func main() {fmt.Println("Learn Compile")
}

通过词法分析器解决当前就会变成这个样子

PACKAGE  IDENT

IMPORT  LPAREN
    QUOTE IDENT QUOTE
RPAREN

IDENT  IDENT LPAREN RPAREN  LBRACE
    IDENT DOT IDENT LPAREN QUOTE IDENT IDENT QUOTE RPAREN
RBRACE

有了以上这些根底的货色，后边看 Go 的词法剖析源码的时候就轻松许多。因为 Go 语言的词法剖析和语法分析其实是连在一起的，所以这里顺便也整顿一下语法分析，须要理解哪些根底的货色是否帮忙咱们去看 Go 的语法分析局部的源码

语法分析根底

文法

在设计语言时，每种程序设计语言都有一组准确的规定来形容程序的语法结构。比方在 C 语言中，一个程序由多个函数组成，一个函数由申明和语句生成，一个语句由表达式组成等等。程序设计语言结构的语法能够应用 上下文无关文法 或BNF（巴科斯范式）表示法来描

  1. 文法给出了一个程序设计语言的准确易懂的语法规约
  2. 对于某些类型的文法，咱们能够主动地结构出高效的语法分析器，它可能确定一个源程序的语法结构
    3. 一个正确设计的文法给出了一个语言的构造。该构造有助于把源程序翻译为正确的指标代，也有助于检测谬误

这里简略的再形容一下语法分析器在编译过程中表演的角色和作用（在 上一篇 文章中有详细描述），不便后边的了解

语法分析器从词法分析器取得一个由词法单元组成的串，并验证这个串能够由源语言的文法生成。对于良构的程序，语法分析器结构出一棵语法分析树，并把它传递给编译器的其余局部进一步解决。实际上，并不需要显式地结构岀一棵语法分析树，因为，对源程序的检查和翻译动作能够和语法分析过程交替实现。因而语法分析器和前端的其余局部能够用一个模块来实现

解决文法的语法分析器大体上能够分为三种类型：通用的 、 自顶向下的 和自底向上的。像 Cocke-Younger-Kasami 算法和 Earley 算法这样的通用语法分析办法能够对任意文法进行语法分析。然而些通用办法效率很低，不能用于编译器产品

下边具体的介绍一下上下文无关文法以及两种解决文法的类型

上下文无关的文法

下边的形容可能很形象，没关系，看下边的示例就明确了（咱们要了解，越通用的货色往往就越形象）

一个上下文无关文法 (简称文法) 由终结符号 、 非终结符号 、一个 开始符号 和一组产生式 组成

  1. 终结符号 是组成串的根本符号。通常咱们所说的词法单元，你就能够把它了解成是终结符号，比方 if、for、)、(等，都是终结符号
  2. 非终结符号 是示意串的汇合的语法变量。非终结号示意的串汇合用于定义由文法生成的语言。非终结符号给出了语言的层次结构，而这种层次结构是语法分析和翻译的要害
  3. 在一个文法中，某个非终结符号被指定为开始符号。这个个符号示意的串汇合就是这个文法生成的语言。依照常规，先列出开始符号的产生式
  4. 一个文法的 产生式 形容了 将终结符号和非终结符号组合成串的办法 。每个产生式由下列元素组成：
    a. 一个被称为 产生式头 或左部的 非终结符号 。这个产生式定义了这个头所代表的串汇合的一部分
    b. 方向向右的箭头
    c. 一个 由零个或多个终结符号与非终结符号组成的产生式体或右部。产生式体中的成分形容了产生式头上的非终结符号所对应的串的某种构造方法

举个比较简单的示例，假如定义了下边这样的文法（下边的 | 是或的意思）

S -> ABC
A -> c|B
B -> a|r
C -> n|y

在上边定义的文法中，A、B、C 是非终结符号，c、a、r、n、y 是终结符号。上边的每一行都是一个产生式，A 也是开始符号。上边这一组产生式再加上非终结符、终结符、开始符号，就组成了一个上下文无关文法。上边个文法就能够匹配 can、arn、aan、cry、ray 等等

因为理解上边这些是为了后边看 Go 语法分析的实现，我这里就从 Go 的语法解析器中拿到了它的文法，如果你明确了上边提到的文法相干内容，就能够轻松看懂 Go 的语法解析用到的文法（Go 的语法分析源码在：src/cmd/compile/internal/syntax/parser.go）

SourceFile = PackageClause ";" {ImportDecl ";"} {TopLevelDecl ";"} .
PackageClause  = "package" PackageName .
PackageName    = identifier .

ImportDecl       = "import" (ImportSpec | "(" { ImportSpec ";"} ")" ) .
ImportSpec       = ["." | PackageName] ImportPath .
ImportPath       = string_lit .

TopLevelDecl  = Declaration | FunctionDecl | MethodDecl .
Declaration   = ConstDecl | TypeDecl | VarDecl .

ConstDecl = "const" (ConstSpec | "(" { ConstSpec ";"} ")" ) .
ConstSpec = IdentifierList [[ Type] "=" ExpressionList ] .

TypeDecl  = "type" (TypeSpec | "(" { TypeSpec ";"} ")" ) .
TypeSpec  = AliasDecl | TypeDef .
AliasDecl = identifier "=" Type .
TypeDef   = identifier Type .

VarDecl = "var" (VarSpec | "(" { VarSpec ";"} ")" ) .
VarSpec = IdentifierList (Type [ "=" ExpressionList] | "=" ExpressionList ) .

因为每一个 Go 的源文件最终都会被解析成一个形象语法树，语法树的最顶层的构造或开始符号，都是 SourceFile。SourceFile 这个产生式含意也很简略

  1. 首先是有一个 包(package)的定义
  2. 而后是可选的 导入申明(import)。大括号是可选的意思，对于 Go 更多的文法，你能够去这里理解，十分具体，对 Go 中的每一种类型，都有具体的介绍
  3. 最初就是一个可选的 顶层申明（TopLevelDecl）

上边并没有列出 Go 全副的产生式，比方 函数 和办法 的产生式这里没有列，它会更简单一些。这里以 PackageClause 这个产生式为例来说一下它的含意

PackageClause  = "package" PackageName . 
PackageName    = identifier .

它的意思就是，满足一个包申明的，它正确的语法结构应该是以 package 结尾，而后 package 后边跟一个标识符（identifier）

晓得了一门计算机语言的语法分析是通过定义好的文法来解析源文件中的语法的，那语法解析器是如何实现依据文法来进行语法解析的呢？这就须要用到一些算法，就是在上边文法局部提到的那三种，通用的 、 自顶向下的 和自底向上的

形象语法树

其实在语法分析阶段，不仅须要判断给定的字符串是不是满足规定的文法，还须要剖析出这些字符串

合乎哪些构造，也就是说，剖析出这个字符串是怎么通过起始符开始，通过产生式匹配进去的，并根

据这个产生的过程生成语法树

假如有这样一个文法

语句 -> 主 谓 宾
主语 -> 你
主语 -> 我
主语 -> 他
谓语 -> 敲
谓语 -> 写
宾语 -> 代码
宾语 -> bug

比方 ” 我写 bug” 这句话，当咱们晓得了主谓宾别离是哪个词，能力了解这句话的含意。下边是它的语法树

再比方下边这个能匹配表达式的文法

Expr -> Expr op Expr | (Expr) | number
op   -> + - * /

假如有这样一个表达式 6 + (60 – 6)。依照上边的文法，咱们能够失去如下的推倒过程

Expr -> Expr + Expr
Expr -> number + Expr
Expr -> number + (Expr - Expr)
Expr -> number + (number - number)
Expr -> 6 + (60 - 6)

用语法分析树来示意就是：

去掉里边的一些多余的节点，进一步的稀释，就能够失去如下形象语法树。对于这种树状构造，能够采纳递归的形式加以分析，从而生成指标代码

看一个不一样的，假如有这么一个表达式：6+20*3，还是通过上边的文法对它进行解析，你会发现它能够由两种不同的形式推导进去

这个其实是语法中的 歧义，就是指对于一个合乎语法结构的字符串，它能够由两种不同的形式被推导进去。相同，如果有一个文法，任何一个字符串的推导形式都是惟一的，那这个文法就是没有歧义的。那很显然咱们的程序语言应用的文法，必须是没有歧义的

要想打消歧义，咱们能够通过 改写文法来实现，将有歧义的产生式改写成无歧义的。然而，这种改写不仅十分艰难，而且往往改写后的产生式和原产生式相差很大，可读性也比拟差

而另一种形式就是通过 优先级 来实现，不须要改写产生式，当推导过程中呈现歧义的时候，利用符号的优先级来抉择须要的推导形式，编程语言中根本都是用的这种形式，咱们后边要理解的 Go 的语法分析局部，也是用的这种形式，这里不做更加具体的介绍，感兴趣的能够看一下 Go 的语法解析这部分（地位：src/cmd/compile/internal/syntax/parser.go → func fileOrNil）

对于一个给定的文法，从中推导出一个任意的字符串是比较简单和间接的，但须要推导出指定的字符串或者 给定一个字符串，要剖析出它是怎么从起始符号开始推导失去的 ，就没那么简略了，这就是语法分析的工作。剖析能够采纳 自顶向下剖析 或 自底向上剖析 两种办法，因为这两种分析方法波及的内容挺多的，我这里先简略的提一些对咱们后边钻研 Go 语法分析源码有帮忙的局部。对于自顶向下剖析 和 自底向上剖析更具体的内容，能够看《编译原理》的第三章

语法分析办法

通用的语法分析办法

Cocke-Younger-Kasami 算法和 Earley 算法这样的通用语法分析办法能够对任意文法进行语法分析。然而些通用办法效率很低，不能用于编译器产品

这里不具体介绍这两种通用的语法分析办法，理性趣的可自行点击理解

自顶向下的语法分析办法

自顶向下剖析就是从起始符号开始，一直的挑选出适合的产生式，将一个两头字符串中的非终结符开展，最终开展到给定的字符串

以下边这个文法为例，来剖析 code 这个字符串

S –> AB
A –> oA | cA | ε
B –> dB | e

阐明：ε 示意空字符串
  1. 开始时，起始符号只有一个产生式：S –> AB，所以只能抉择这一个产生式，用这个产生式的左边局部代替 S，就失去一个两头字符串 AB
两头字符串 产生式
S S → AB
AB
  1. 对于这个两头字符串，从它的起始符号 A 开始开展，A 开展能够失去三个产生式：A → oA; A→ cA; A→ ε。咱们能够拿咱们要剖析的字符串 code 来和这个两头字符串 AB 比照一下，发现只能抉择 A → cA 这个产生式，否则无奈依据这个两头字符串推导出 code。所以这里抉择将两头句子中的 A，替换成 cA，就失去了两头句子 cAB
两头字符串 产生式
S S → AB
AB A → cA
cAB
  1. 而后持续尝试将 cAB 中的 A 开展。发现只能抉择 A → oA 这个产生式
两头字符串 产生式
S S → AB
AB A → cA
cAB A → oA
coAB
  1. 持续对 A 进行开展，发现 A 只能抉择 A → ε 这个产生式（否则是推导不进去 code 的）
两头字符串 产生式
S S → AB
AB A → cA
cAB A → oA
coAB A → ε
coB
  1. 而后就是开展非终结符 B，B 开展能够失去两个产生式：B → dB; B → e。依照上边雷同的办法，能够失去：
两头字符串 产生式
S S → AB
AB A → cA
cAB A → oA
coAB A → ε
coB B → d
codB B → e
code 实现

以上就是自顶向下的语法分析过程，你当初再回过头去看 上下文无关文法 局部提到的 Go 语言中的文法，是不是就明确了 Go 的语法分析过程。如果你去看 Go 的语法分析源码（地位：src/cmd/compile/internal/syntax/parser.go → func fileOrNil），你会发现 Go 用的就是这种自顶向下的语法分析办法

自底向上的语法分析办法

自底向上剖析的分析方法，是从给定的字符串开始，而后抉择适合的产生式，将两头字符串中的子串折叠为非终结符，最终折叠到起始符号

假如有如下文法，咱们要剖析的字符串是：aaab

S –> AB
A –> Aa | ε
B –> b | bB
  1. 首先从右边第一个字符 a 开始，比照语法中的所有产生式，发现没有产生式的左边能够齐全匹配。但通过察看和思考发现：能够尝试在 aaab 的最后面插入一个空句子 ε，接下来能够利用 A -> ε，之后再利用 A -> Aa，…。因而先插入空句子，失去两头句子 εaaab
两头字符串 产生式
aaab 插入 ε
εaaab
  1. 此时，两头句子的最右边 ε 能够和产生式 A -> ε 匹配。用这个产生式，将 ε 折叠为 A，失去 Aaaab
两头字符串 产生式
aaab 插入 ε
εaaab A → ε
Aaaab
  1. 由两头字符串 Aaaab 能够发现，它的最后面的 Aa 能够和 A -> Aa 匹配上，且只能和这个产生式匹配上，因而利用此产生式，将 Aa 折叠为 A，失去 Aaab
两头字符串 产生式
aaab 插入 ε
εaaab A → ε
Aaaab A → Aa
Aaab
  1. 依照上边雷同的步骤，将两头字符的子串折叠为非终结符，最终折叠到起始符号 S，过程如下：
两头字符串 产生式
aaab 插入 ε
εaaab A → ε
Aaaab A → Aa
Aaab A → Aa
Aab A → Aa
Ab B → b
AB S → AB
S 实现

以上就是自底向上的语法分析大抵过程，这里次要是为了不便了解，没有波及到更多的货色。然而曾经够后边看 Go 语法分析源码应用了

语法分析过程中的回溯和歧义

在前文中举的例子，可能比拟特地，因为在推导的过程中，每一步都只有惟一的一个产生式满足条件。然而在理论的剖析过程中，咱们可能会遇到如下两种状况：

  1. 所有产生式都不可利用
  2. 有多个产生式能够利用

如果呈现第二种状况，往往咱们须要采纳回溯来进行解决。先尝试抉择第一个满足条件的产生式，如果能推导到指标字符串，则示意该产生式是可用的，如果在推导过程中遇到了第一种状况，则回溯到方才那个中央，抉择另一个满足条件的产生式

如果尝试完所有的产生式之后，都遇到了第一种状况，则示意该字符串不满足语法要求。如果有多条产生式都能推导出指标字符串，则阐明语法有歧义

回溯剖析个别都十分慢，因而个别通过精心结构语法来防止回溯

语法分析器生成工具

常见的语法分析器生成工具有 Yacc、bison，它的原理其实跟上边介绍的词法分析器差不多。就是依照对应语法分析器工具的语法编写源文件（文件后缀是.y），（其实就是在源文件代码里边提供一些文法，词法分析器工具，也是咱们提供了正则）而后通过应用对应工具的命令将.y 文件生成成.c 文件

生成的这个.c 文件里边，其实就依据咱们提供的文法规定生成一个语法分析器的代码，咱们只须要编译执行这个.c 文件即可

因为本篇文章曾经很长了，这里就不举例了，对于这两个语法分析器生成工具，你能够点击我上边的链接，进入官网下载安装，本人尝试一下

过程是齐全和上边介绍的词法分析器工具一样的

总结

本文次要是分享了词法剖析中的不确定有穷自动机和确定有穷自动机，并且展现了词法剖析中罕用的词法分析器是如何应用的。而后是语法分析中波及到的文法、形象语法树的生成、以及语法解析的两种解析形式

感激浏览，心愿看完能有所播种

退出移动版