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