上下文无关文法和形式语言
一、文法之间的关系
1、文法=语法。
词法规则：描述单词符号的构成规则。 标识符，常数，符号运算。
工具：正规文法（正规式，有限自动机）
语法规则：描述语法单位构成规则。 表达式，语句，函数，过程。
工具：上下文无关文法。
2、字母表和符号串
3、符号串以及集合的运算
例子：
4、上下文无关文法
规则：又成为产生式。是定义语言语法单位的机构。
->单箭头 表示“定义为”。“由......组成”
推导：用规则（产生式）右部替换左边的过程。
语法树：
二、文法和语言的形式定义
1、产生式：产生式是一个有序对（A，a） ： A->a |A |=1 |a|大于等于0
2、文法：Vn左边 Vt右边
例：
一般描述方式：
3、推导和归约：
4、句型和句子：
5、语言：
6、规范推导和规范归约：就是最右推导~~~
7、等价文法：
8、递归产生式和递归文法：
9、短语、直接短语和句柄：
10、文法二义性：一个文法可以对应两个不同的文法树