前言

2023-5-10 13:08:16

以下内容源自《编译原理》

仅供学习交流使用

推荐

第一章 总结及作业【编译原理】

第二章 总结

2.1程序语言的定义

2.1.1语法

任何语言程序都可看成是一定字符集(称为字母表)上的一字符串(有限序列)。

所谓一个语言的语法是指这样的一组规则,用它可以形成和产生一个合式的程序。这些规则的一部分称为词法规则,另一部分称为语法规则(或产生规则)。

2.1.2语义

对于一个语言来说,不仅要给出它的词法、语法规则,而且要定义它的单词符号和语法单位的意义。这就是语义问题。

2.2高级语言的—般特性

2.2.1高级语育的分类

2.2.2程序结构

2.2.3 数据类型与操作

2.2.4语句与控制结构

2.3程序语言的语法描述

空集、连接、闭包

2.3.1上下文无关文法

文法是描述语言的语法结构的形式规则(即语法规则)。
一个上下文无关文法G包括四个组成部分:一组终结符号,一组非终结符号,一个开始符号,以及一组产生式。

巴科斯范式

形式上说,一个上下文无关文法G是一个四元式(VT, VN,S,ξ),其中

VT是一个非空有限集,它的每个元素称为终结符号;

VN是一个非空有限集,它的每个元素称为非终结符号,VT∩ VN=φ;

S是一个非终结符号.称为开始符号;

ξ是一个产生式集合(有限)，每个产生式的形式是P→α,其中,P∈VN,α∈(VT∪VN)*。开始符号S至少必须在某个产生式的左部出现一次。

推导

句型、句子、语言：

假定G是一个文法,S是它的开始符号。如果S=*>α,则称α是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言,将它记为L(G)。

L(G)= {α|S=+>α&α∈V_T^*}

例2.1、例2.2、例2.3：


最左推导、最右推导

2.3.2语法分析树与二义性

如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。也就是说,若一个文法中存在某个句子,它有两个不同的最左(最右)推导,则这个文法是二义的。

人们已经证明,二义性问题是不可判定的。即,不存在一个算法,它能在有限步骤内，确切地判定一个文法是否为二义的。

2.3.3形式语言鸟瞰

0型语法、1型语法、2型语法、3型语法：

总结：

• 0型文法：短语文法，递归可枚举
• 1型文法：上下文有关文法，一般不允许替换成空串ε
• 2型文法：上下文无关文法，非终结符的替换不必考虑上下文
• 3型文法：线性文法、正规文法，单词结构，左/右

第二章 作业

6

6.令文法G₆为

N→D|ND

D→0|1|2|3|4|5|6|7|8|9

(1)G₆的语言L(G₆)是什么?

(2)给出句子0127、34和568的最左推导和最右推导。

（1）L(G~6~)={0,1,2,3,4,5,6,7,8,9}^+^
（2）
①0127
左 N=>ND=>NDD=>NDDD=>DDDD=0DDD=>01DD=>012D=>0127
右 N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127.
②34
左 N=>ND=>DD=>3D=>34
右 N=>ND=>N4=>D4=>34
③568
左 N=>ND=>NDD=>DDD=>5DD=>56D=>568
右 N=>ND=>N8=>ND8=>N68=>D68=>568

7

7.写一个文法,使其语言是奇数集,且每个奇数不以0开头。

G~7~(S):
    S->NZO|O
    N->1|2|3|4|5|6|7|8|9
    Z->XZ|ε
    X->0|1|2|3|4|5|6|7|8|9
    O->1|3|5|7|9

8

8.令文法为

E→T|E+T|E-T

T→F|T*FIT/F

F→(E)|i

(1）给出i+ i * i、i * (i+i)的最左推导和最右推导;

(2）给出i+i+ i、i+i *i和i-i- i的语法树。

①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*(T+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）语法树如图

9

9.证明下面的文法是二义的:

S→iSeS|iS|i

需证明：存在一个句子的语法树是不同的
iiiei的语法树如图
所以S→iSeS|iS|i是二义的

扩展：

上面这个就是条件语句的文法啊

可以在2.3.3形式语言鸟瞰（P35）中找到

S->   if 条件 then 语句 
  | if 条件 then 语句 else 语句
  |   其他语句
这是一个二义文法。例如，下面的语句
if C1 then if C2 then S1 else S2
就对应有两棵不同的语法树。

11

11.给出下面语言的相应文法

L₁= {aⁿbⁿcⁱ|n≥1, i≥0}

L₂= {aⁱbⁿcⁿ|n≥1,i≥0}

L₃= {aⁿbⁿa^mb^m|n, m≥0}

L₄= {1ⁿ0^m1^m0ⁿ|n,m≥0}

①G1(S):
    S->XC
    X->aXb
    C->cC|ε
②G2(S):
    S->AX
    X->bXc
    A->aA|ε
③G3(S):
    S->XY
    X->aXb|ε
    Y->aYb|ε
④G4(S):
    S->1S0|0S1|ε

修正：

①G1(S):
    S->XC
    X->aXb|ab 此处需有ab，因n≥1
    C->cC|ε
②G2(S):
    S->AX
    X->bXc|bc 此处需有bc，因n≥1
    A->aA|ε   

第二章作业 参考答案

来源：编译原理习题讲解PPT

通过参考答案，修正作业解答

6

7

8

9

11

最后

2023-5-10 13:35:40

祝大家逢考必过

点赞收藏关注哦