《编译原理》学习总结--第二章
一 知识点
1 语法:一组规则,用这组规则可以产生形式上正确的程序。
(1)词法规则:合法单词的构成规则
(2)语法规则:合法程序的构成规则
2 语义:一组规则,使用它可以定义一组程序的意义
3 高级语言的一般特征
(1)高级语言的分类
(2)高级语言的一般特征
4 上下文无关文法
(1)文法:描述语言的语法结构的形式规则
(2)特点:它所定义的语法范畴是完全独立于这种范畴可能出现的环境的(独立性)
(3)组成:一组终结符号,一组非终结符,一个开始符号,一组产生式
5 语法分析树与二义性
(1)语法分析树:简称语法树,用来表示推导过程
(2)二义性:如果一个问法存在某个句子对应两颗不同的语法树,则称这个文法是二义的。
6 形式语言
(1)0型文法:也称短语文法,左部和右部都既可含有终结符,也可含有非终结符,但左部至少含有一个非终结符。
(2)1型文法:也称上下文有关文法,在0型文法的基础上,左部长度必修小于等于右部长度(右部为空字除外)。
(3)2型文法:也称上下文无关文法,在0型文法的基础上,左部只可含非终结符,右部既可含终结符也可含非终结符。
(4)3型文法:也称正规文法,在0型文法的基础上,左部只含非终结符,右部只含终结符或既含终结符又含非终结符。若右部终结符在非终结符左侧,则称右线性文法;反之,则称左线性文
二 课后题
6. (1)、L(G6)是数字构成的字符串。
(2)、N->ND->NdD->NDDD->DDDD->0DDD->01DD->012D->0127
N->ND->DD->3D->34
N->ND->NDD->DDD->5DD->56D->568
7.L(G7):
S->BO|O
O->1|3|5|7|9
D->2|4|6|8|O
B->BA|O
A->0|D
8.
(1) i+i*i最左推导:
E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i
最右推导:
E=>E+T=>E+T*F=>E+T*i=>E+F*i=>E+i*i=>T+i*i=>F+i*i=>i+i*i
i*(i+i) 最左推导:
E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(F+T)=>i*(i+T)
=>i*(i+F)=>i*(i+i)
最右推导:
E=>T=>T*F=>T*(E)=>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)
=>T*(F+i)=>T*(i+i)=>F*(i+i)=>i*(i+i)
(2)语法树
i+i+i i+i*i i-i-i
9.
句子iiiei有两个语法树
S->iSeS->iiSeS->iiieS->iiiei
S->iS->iiSeS->iiieS->iiiei
10.
S->TS|T
T->(S)|( )
11.(1)S->A|C
A->abA|ab
C->cC|c|∑
(2)S->A|C
A->bcA|bc
C->aC|a|∑
(3)S->A
A->ab|abA|∑
(4)S->A
A->10|10A|∑
三 个人感悟
经过这一周多的学习,我充分理解到老师所说的这门课程的不好学之处,内容十分的抽象,概念性的东西非常多,很多时候不能及时的理解,课后也很容易遗忘,最后总结的时候比较吃力。但是通过习题的学习以及及时的总结,总算能够掌握本章的内容。感觉总结一下对每一章的学习都有帮助。