概要

文法类型

0型文法——无限制文法

至少包含一个终结符
识别：图灵机

1型文法——上下文有关文法

左侧的小于等于右侧的
识别：线性界限自动机

2型文法——上下文无关文法

左侧是某一个非终结符
识别：下推自动机

3型文法——正则文法

右侧有终结符
3型文法有分为右线性文法和左线性文法。
右线性文法的右侧终结符在左边（A—>aB）；
左线性文法的右侧的终结符在右边(A—>Ba)
识别：有限状态自动机

语法推导树

每一个句型至少存在一棵语法树，每棵语法树至少存在一个推导

句型

每个树的叶子组成一个句型

短语

每个子树的叶子组成一个短语

简单短语

每棵简单子树的叶子组成一个简单短语

句柄

最左简单子树的叶子组成一个句柄

有穷自动机

不确定的有穷自动机（NFA）

（1）初态不唯一
（2）f是单值映射函数
（3）同一状态射出弧上的标记可以是相同的
（4）每个状态可以有多于n条射出弧
（5）允许初态也是终态

确定的有穷自动机（DFA）

（1）初态唯一
（2）f是单值映射函数
（3）任意状态的出弧上的标记均不相同
（4）任意状态至多只有n条射出弧
（5）若DFA识别空串，则初态也是终态

NFA—>DFA

举个栗子

优先分析算法

自底向上

简单优先分析算法

（1）文法出现在任意符号之间，至多只能有一种优先关系
（2）任何产生式的右侧均不相同
用的是HEAD、TAIL

算符优先分析算法

（1）不含空规则
（2）优先关系至多只能有一种
（3）右侧两个非终结符不能相邻
用的是FIRSTVT，LASTVT