第2章形式语言概论字母表和符号串符号串的运算文法文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9}S=<标识符>习惯上只将产生式写出。并有如下约定：1、第一条产生式的左部是开始符号；2、用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符；3、G可写成G[S]，其中S是开始符号；0型文法：对任一产生式α→β，都有α(VN∪VT)+，β(VN∪VT)*。1型文法（上下有关文法）：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外。2型文法（上下无关文法）：对任一产生式α→β，都有αVN，β(VN∪VT)*。3型文法（正规文法）：任一产生式α→β的形式都为A→aB或A→a，其中AVN，BVN，aVT。文法举例推导最左推导最右推导句型、句子和语言文法和语言语法树上下文无关文法的语法树产生式树文法和语言的几点说明化简文法问题：一个句型是否对应唯一的一棵语法树？自上而下分析方法自上而下的语法分析自下而上分析方法自下而上的语法分析句型分析的有关问题产生式表小结