空字符：εa = a
正闭包：A+ = ∪A^n (n ≥ 1)
克林闭包：A* = A^0 ∪ A+
字母表
符号串：字符的有序序列
语言L
句子 字母表的闭包的子集
语法
语法规则示例：
根据语法规则后可以推导出句子，将每个非终结符号（如上图主语谓语）开始向下推导至全为终结符号
最后用规则的右部替换左部得到一个具体的句子
一般遵循最左推导原则
推导过程可以可视化为一颗语法（推导）树
文法的形式定义
文法G=（Vn，Vt，P，Z）
Vn：非终结符号集
Vt：终结符号集
P：产生式或规则的集合
Z：开始符号（识别符号，即识别它是否为句子时的起始符号） Z∈Vn
(V = Vt + Vn，称为语言的符号)
构造文法：对于一个语言L，找到文法四要素
技巧
- 枚举
- 对有限集合适用
- 重复构造
- S → bS | b
- 对无穷且数量无关适用
- 对称
- S → 0S1
- 控制数量
递归语法
句型
由语法规则规范推导出来的东西（VT和VN混在一起的东西）
只含有终结符VT的句型叫句子
短语
对于句型xuy，若句型xUy 可以多步(+)推导出xuy，则u为U的短语
简单短语
短语的多部推导 → 单步推导
句柄
对于句型的最左简单短语
一般用语法推导树来找，即圈出句型构成的node，从根节点开始遍历每个节点是否为句型中某个成分的公共祖先节点
规范（最左）规约：从最左终结符开始向上还原为上层（最右推导的逆过程）
文法二义性
对同一句子，可能有不同的推导树可以推导出来，这种现象称为文法的二义性
若对于一个文法的某一句子（或句型）存在两棵不同的语法树，则有二义性
对于一个文法，若该文法推导出来的同一规范句型的句柄不同，则有二义性
文法二义性是不可判定的，只能提出一些限制条件（无二义性的充分条件）
eg. 按照优先级从低到高，添加符号层次
多余规则
始终用不到的
加上其他规则，迭代下去也永远推不出终结符号的
乔姆斯基文法定义
四要素同，语法规则有区别
语法规则分为几类，数字越大越严格
- 0型：u ::= v, u ∈ V+, v ∈ V*
- 短语结构文法，符号串 → 符号串
- 1型：xUy ::= xuy, U∈Vn, x、y、u∈V*
- 上下文有关，仅在xUy结构下可以产生U → u
- 2型：U::=u, U ∈ Vn, u∈V*
- 上下文无关语法，等价于BNF表示
- 3型：U::=t 或 U::=tW（右线性） 或 Wt（左线性），其中U, W ∈ Vn，t∈Vt
- 正则文法，可以被有穷状态机接受