语言及其文法
词法语法分析基本概念
字母表∑是一个有穷符号集合
符号：字母、 数字、标点符号
例如：二进制字母表：{0,1} ASCll字符集
字母表的运算（其中ε表示空串）
串（String）
- 假设∑是一个字母表，∀x∈∑* ，x称为是∑上的一个串，串是字母表中
符号的一个有穷序列 - 串s的
长度，通常记作|s|，是指s中符号的个数
例如：|aab|=3 - 空串是长度为0的串，用
ε（epsilon）表示空串，|ε|=0
串上的运算——连接
如果x和y是串，那么x和y的连接（concatenation）是把y附加到x后面而形成的串，记作xy
- 例如，如果x=Sakura且y=Li，那么xy=SakuraLi
空串是连接运算的单位元（identity），即对任何串s都有，εs=sε=s
假设x，y，z是三个字符串，如果x=yz，则称y是x的前缀，z是x的后缀
文法
首先举了一个简单的小例子
其中用<>括起来的部分称为是语法成分，未用<>括起来的部分表示语言的基本符号
文法的形式化定义
VT：终结符集合终结符（terminal symbol）是文法所定义的语言的基本符号，有时也成为token
例：VT={apple,boy,eat,little}
VN：非终结符集合
非终结符（nonterminal）使用来表述语法成分的符号，有时也称为“语法变量”
例如：VN={<句子>,<名词短语>,<动词短语>,<名词>，……}
其中VT∩VN=Φ，VT∪VN：文法符号集
P：产生式集合
产生式（production）描述了将终结符和非终结符组合成串的方法
S:开始符号
所以文法的所有形式与定义
约定：在不引起歧义的前提下，可以只写产生式
产生式的简写
符号约定
- 下述符号是
终结符：
- 字母表中排在前面的小写字母，如a，b，c
- 运算符，如+、*等
- 标点符号，如括号，逗号等
- 数字0、1、……、9
- 粗体字符串，如id，if等
- 下述符号是
非终结符
- 字母表中排在前面的大写字母，如A，B，C
- 字母S，通常表示开始符号
- 小写，斜体的名字，如expr，stmt等
- 代表程序构造的大写字母，如E（表达式），T（项）和F（因子）
- 字母表中
排在后面的大写字母（如X，Y，Z）表示文法符号（即终结符或非终结符） - 字母表中排在后面的小写字母（主要是u、v、……、z）表示
终结符号串（包括空串） 小写希腊字母，如α，β，γ，表示文法符号串（包括空串）- 除非特别说明，
第一个产生式的左部就是开始符号
语言的定义
推导（Derivation）和规约（Reduction）
给定文法G=（VT,VN,P,S），如果α→β∈P，那么可以将符号串γαδ中的α替换为β，也就是说，将γαδ重写(rewrite)为γβδ，记作γαδ=>γβδ。此时，称文法中的符号串直接推导(directly derive)出γβδ
- 直接推导：用产生式的右部替换产生式的左部
接下来举了一个例子，讲了推导和规约的区别（这里其实和我最近写的fuzzingbook上的知识点重合了）
那么，有了文法（语言规则），如何判定某一词串是否是符合该语言的句子？
- 句子的
推导（派生）——从生成语言的角度 - 句子的
规约——从识别语言的角度
句子和句型
这里简单解释一下这两句：
- 如果从文法的开始符号S经过若干步可以推导出一个文法符号串α，且α称为是G的一个
句型 - 如果从S开始推导若干步得到一个终结符号串w，那么则称w是G的一个
句子
这里我们可以得出，句子是句型的一种特殊形式，且句子中无非终结符
语言的形式化定义
此处L为Language
文法解决了无穷语言的有穷表示问题
文法分类
Chomsky文法分类体系
- 0型文法（Type-0 Grammar）
- 1型文法（Type-1 Grammar）
- 2型文法（Type-2 Grammar）
- 3型文法（Type-3 Grammar）
0型文法（Type-0 Grammar）
1型文法（Type-1 Grammar）
当A的上下文分别是α1和α2时才可以替换为β，所以称之为上下文有关语法，其中β不为空串，因为α至少含有一个非终结符，所以|β|必须大于等于1
2型文法（Type-2 Grammar）
其中产生式的左部必须是一个非终结符
3型文法（Type-3 Grammar）
在产生式的右部最多有一个非终结符
四种文法之间的关系
上下文无关语法（CFG）的分析树
其实这里已经可以参考我之前的fuzzingbook博文的5,6两章，上面有完整分析树的python表示方式
（句型的）短语
- 给定一个句型，其分析树中的每一个棵
子树的边缘称为该句型的一个短语（phrase） - 如果子树只有父子两代结点，那么这棵子树的边缘成为该句型的一个直接短语（immediate phrase）
以下是一个简单的例子
直接短语一定是某个产生式的右部，但反过来未必成立。
二义性文法（Ambiguous Grammar）
- 如果一个问法可以为某个句子生成
多棵分析树，则称这个文法是二义性的
这里也就是为什么python对缩进要求严格，而其他语言在多重判断时也必须加上对应的{}的原因，不然程序运行出来的结果将和你想的完全不一致
当然，为了解决这个分歧，语言本身也会提供一种消歧规则。
比如上面的if-else程序本身也有一种消歧规则：每个else和距离最近的尚未匹配的if匹配。当然这也就容易造成了如果我们对缩进疏忽而导致的程序运行结果与预计不一致的错误。
所以上述程序，在C语言中，运行的方式都是左侧。
二义性文法的判定
