编译原理---第二章

时间:2024-04-08 07:10:04

写在前面的话:自用侵删致谢,图片来自中国大学,国防科技大学老师开设的编译原理。

推荐大家看看!!!

几个概念:

编译原理---第二章

编译原理---第二章 

编译原理---第二章 

V*与V+ 的区别:如果V中原来没有空字,闭包中会包含空字,而正规闭包中不会引入空字。

编译原理---第二章

 上下文无关文法:

编译原理---第二章

在文法中,终结符是不能在分解和定义的单位。

在文法中,非终结符是可以在分解和定义的单位。

非终结符可以由终结符和非终结符构成。

不允许一个符号既是终结符又是非终结符。

编译原理---第二章

S代表所定义的语言最终感兴趣的语法单位。

P中的箭头读作“定义为”,左边是一个非终结符,右边是非终结符和终结符构成的字符串。

开始符号S至少必须在某个产生式的左部出现一次。

举例:

编译原理---第二章

 

巴克斯范式  BNF

定义符不同与上面的描述:

“→”用“::=”表示

 

编译原理---第二章

 编译原理---第二章

 定义文法的目的是描述语言!

编译原理---第二章

“→” 表示定义

“双箭头”表示直接推出

编译原理---第二章

 举例:推导过程不唯一

编译原理---第二章

 两个符号:

编译原理---第二章

 几个概念:

编译原理---第二章

 练习题:

编译原理---第二章

 要证明一个串是给定文法的句子,可以从句子的定义来考虑。一定要保证这个串只有终结符,二是要证明这个串能够从文法的开始符号推出来

编译原理---第二章

 举例:

编译原理---第二章 

 产生的语言:以C开头,后继若干个b

以L(G1)={c,cb,cbb,……}

Ab是递归候选

 

举例:

编译原理---第二章

 编译原理---第二章

 举例:

编译原理---第二章

编译原理---第二章 

 举例:

编译原理---第二章

编译原理---第二章

 

 

最左推导和最右推导:

编译原理---第二章

 语法树:用一张图表示一个句型的推导,称为语法树。

举例:

编译原理---第二章

最左推导:所对应的语法树的生长顺序是从上往下 ,从左往右

最有推导:所对应的语法树的生长顺序是从上往下,从右往左

一颗语法树是不同推导过程的共性抽象

一个句型是否对应唯一一颗语法树?????答案是否

文法的二义性:如果一个文法存在某个句子对应两颗不同的语法树,这说这个文法是二义的。

语言的二义性:一个语言是二义的,如果对他不存在无二义的文法。

编译原理---第二章

 语言的二义性比文法二义性强!

 

存在无二义性:

编译原理---第二章

 二义性问题是不可判定问题,即不存在一个算法,他能在有限步骤内,确切的判定一个文法是否二义。

可以找到一组无二义的充分条件。

 

0,1,2,3型文法:上下文无关文法属于2型文法!

编译原理---第二章

 

编译原理---第二章

 编译原理---第二章

 编译原理---第二章

 四种类型文法描述能力:(3最强)

编译原理---第二章

 

上下文无关文法与上下文有关文法:

编译原理---第二章 

 编译原理---第二章