语法分析简介

大家好，欢迎来到IT知识分享网。

前言

这里介绍的是针对【形式语言】而非【自然语言】的语法分析。
【形式语言】指人为设定语法规则的语言，例如各种编程语言。

目地：

将文本解析成符合语法规则的形式，进而可以理解其意图。

概念：

字元(token)：组成语言的不可再分元素，例如C#的关键字、括号、标识符、字面量等等。
语法：规定字元之间如何组合、匹配的规则集合。
语法元素：由字元组合成的符合语法的结构，如变量声明、表达式等等。
上下文无关语法：指定语法元素如何由更简单的语法元素组成的规则集合。

可以看出，语法结构是以字元为基础构建出的树形结构。因此，字元也被称为【终结符】，由字元构成的语法元素被称为【非终结符】

前置任务

因为语法是以字元为基础的，因此我们需要先对原始文本进行预处理，让它成变一个一个的字元，这个称为字元化，或者词法分析。它主要内容是忽略掉所有的空格、换行、注释，并且识别出每一种类型的字元，生成字元序列。
字元有两个信息需要关注：类型（是关键字、符号还是标识符等等）、文本值
然后就是以字元序列为输入，进行语法分析。

一种分析方法：递归下降分析

分析方法有多种，这种是比较简单的。
从名字看，它有两个特征：1、递归的。2、从整体到局部的。
因为上面提到了的【上下文无关语法】本身就是规定复杂结构如何由简单结构组成的规则，因此这种方法就按照定义，为语法中的每一个【非终结符】规则提供一个解析方法，如果该【非终结符】仅由【终结符】构成当然很好处理，如果它由其它【非终结符】组成，则在它的解析方法中再调用其它【非终结符】的解析方法。
这样就形成了一个递归的调用，直至最终解析到的全是【终结符】再返回。

作用

语法分析可以得到语法元素形成的树形结构，称为语法树。它可以用于代码编译（源语言到目标语言的翻译）、语法高亮、语法提示、错误提示等等。

举例：Json解析

因为语法分析也可以用于特定规则的数据集分析，因此这里用json格式来举个例子，它的语法简单。
假设我们没有现成的json解析库，那我们可以这样：

0、约定

‘xxx’表示字元xxx
()表示分组
x|y表示x或y
x?表示x出现0次或1次
x*表示x出现0次或多次

1、 归纳出字元类型

json的字元类型有:
关键字：'true' | 'false' | 'null'
符号：'{' | '}' | '[' | ']' | ',' | ':'
字符串常量：'"' 一系列字符 '"'
数字常量：任意数值

2、进行字元化

不断读入一个字符，与字元模式匹配生成字元，忽略空格、换行，最终输出字元序列。

3、 归纳出上下文无关语法

4、 进行递归下降分析

然后我们需要对上面语法中的每一条语法元素规则提供一个解析函数。
这种函数可以从字元流中依次取出或查看下一个字元，由于每一个语法元素已经定义好其模式，因此我们不断取出字元，就可以判断其能否开始一个语法元素或满足当前的语法元素中的当前终结符。
如果存在无法靠当前取出的字元判断的时候，还可以向前查看n个字符直至可以做出判断。
当均不满足的时候，就可以判断文本存在语法错误。
这样的解析函数就可以生成语法树中的一个节点，把节点按递归的层级父子相连就可以得到整个语法树了。