编译原理---第二章
写在前面的话：自用侵删致谢，图片来自中国大学，国防科技大学老师开设的编译原理。
推荐大家看看！！！
几个概念：
V*与V+ 的区别：如果V中原来没有空字，闭包中会包含空字，而正规闭包中不会引入空字。
上下文无关文法：
在文法中，终结符是不能在分解和定义的单位。
在文法中，非终结符是可以在分解和定义的单位。
非终结符可以由终结符和非终结符构成。
不允许一个符号既是终结符又是非终结符。
S代表所定义的语言最终感兴趣的语法单位。
P中的箭头读作“定义为”，左边是一个非终结符，右边是非终结符和终结符构成的字符串。
开始符号S至少必须在某个产生式的左部出现一次。
举例：
巴克斯范式 BNF
定义符不同与上面的描述：
“→”用“：：=”表示
定义文法的目的是描述语言！
“→” 表示定义
“双箭头”表示直接推出
举例：推导过程不唯一
两个符号：
几个概念：
练习题：
要证明一个串是给定文法的句子，可以从句子的定义来考虑。一定要保证这个串只有终结符，二是要证明这个串能够从文法的开始符号推出来
举例：
产生的语言：以C开头，后继若干个b
以L（G1）={c,cb,cbb,……}
Ab是递归候选
举例：
举例：
举例：
最左推导和最右推导：
语法树：用一张图表示一个句型的推导，称为语法树。
举例：
最左推导：所对应的语法树的生长顺序是从上往下 ，从左往右
最有推导：所对应的语法树的生长顺序是从上往下，从右往左
一颗语法树是不同推导过程的共性抽象
一个句型是否对应唯一一颗语法树？？？？？答案是否
文法的二义性：如果一个文法存在某个句子对应两颗不同的语法树，这说这个文法是二义的。
语言的二义性：一个语言是二义的，如果对他不存在无二义的文法。
语言的二义性比文法二义性强！
存在无二义性：
二义性问题是不可判定问题，即不存在一个算法，他能在有限步骤内，确切的判定一个文法是否二义。
可以找到一组无二义的充分条件。
0,1,2,3型文法：上下文无关文法属于2型文法！
四种类型文法描述能力：（3最强）
上下文无关文法与上下文有关文法：