ZUCC_编译语言原理与编译_实验04 语言与文法

编译语言原理与编译实验报告

课程名称	编程语言原理与编译
实验项目	语言与文法

实验目的

• 了解文法的历史
• 理解产生式规则
• 掌握最左推导，最右推导
• 掌握文法的二义性
• 掌握文法的分类与层次

实验内容

一、阅读课件完成课后习题

1、给出语言 L2={a^n b^m| m≥n≥1} 的文法

$$\begin{gathered} P_1:S\to AB \\ A\to aAb\mid ab \\ B\to bB\mid \epsilon \end{gathered}$$

2、给出语言 L1={a^(2n+1)|n≥0} 的文法

$$P_2:A\to aAa\mid a$$

3、给出语言L3={a^n b^m c^k| n,m,k≥0}的文法

$$\begin{gathered} P_3:S\to ABC \\ A\to AA\mid a\mid \epsilon \\ B\to BB\mid b\mid \epsilon \\ C\to CC\mid c\mid \epsilon \end{gathered}$$

4、写一个文法,使其语言是正偶数的集合,每个偶数不以0开头

$$\begin{gathered} P_4:S\to N \\ N\to 2\mid 4\mid 6\mid 8\mid NM \\ M\to 0\mid 2\mid 4\mid 6\mid 8 \end{gathered}$$

5、给出语言L={1^n 0^m 1^m 0^n | n,m≥0}的文法

$$\begin{gathered} P_5:S\to 1S0\mid 0A1\mid \epsilon \\ A\to 0A1\mid \epsilon \end{gathered}$$

6、给出语言L={ WaW^t | W∈{0|1}* }，其中W^t表示W的逆的文法

$$P_6:S\to a\mid 0S0\mid 1S1$$

7、文法G[A]=({A},{a,b},{A→bA | a}, A) 所生成的语言是什么？

$$L(G[A])=\left\{b^{n}a\mid n\ge 0\right\}$$

8、文法G[N]为:

$$\begin{gathered} N\to ND\mid D \\ D\to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 \end{gathered}$$

(1) G[N]所生成的语言是什么？

$$L(G[A])=\left\{\alpha \mid \alpha 为数字串\right\}$$

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

最左推导
$$N*ND*NDD*NDDD*DDDD*0DDD*01DD*012D*0127$$
最右推导
$$N*ND*N7*ND7*N27*ND27*N127*D127*0127$$

9、已知文法G[S]=( {A,B},{a,b,c,d}, P, S ) , 其中 P 为:

$$\begin{gathered} S\to AB \\ A\to aAb\mid ab \\ B\to cBd\mid cd \end{gathered}$$

该文法 所生成的语言是什么？
$$L(G[S])=\left\{a^n{b}^n{c}^m{d}^m\mid n,m\ge 1\right\}$$

10、已知文法G[E]：

$$\begin{gathered} E\to E+T\mid E-T\mid T \\ T\to T\ast F\mid T/F\mid F \\ F\to (E)\mid i \end{gathered}$$

证明 E+T*F 是它的一个句型,指出这个句型的短语、直接短语和句柄
$$\begin{gathered} E*E+T*E+T\ast F \\ 短语:E+T\ast F、T\ast F \\ 直接短语:T\ast F \\ 句柄:T\ast F \end{gathered}$$

11、已知文法G[S]：

$$\begin{gathered} S\to (AS)\mid (b) \\ A\to (SaA)\mid (a) \end{gathered}$$

试找出符号串(a)和(A((SaA)(b)))的短语﹑直接短语和句柄(如果有的话)

• 符号串(a))不是文法的句型，因此它没有短语﹑直接短语和句柄

• $$\begin{gathered} S*(AS)*(A(AS))*(A(A(b)))*(A((SaA)(b))) \\ 短语:(A((SaA)(b)))、((SaA)(b))、(SaA)、(b) \\ 直接短语：(SaA)、(b) \\ 句柄：(SaA) \end{gathered}$$

12、设有文法G[S]: S→iSeS| iS | i，试证明文法G[S]有二义性。

13、设有文法G[N]:

$$\begin{gathered} N\to SE\mid E \\ S\to SD\mid D \\ E\to 0\mid 2\mid 4\mid 6\mid 8\mid 10 \\ D\to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 \end{gathered}$$

(1)试证明文法G[N]有二义性。

(2)此文法所描述的语言是什么？

该文法所描述的语言是所有无符号偶数的集合(可以0开头)。

(3)试写出另一文法G’使L(G’)=L(G)且G’是无二义性的

$$\begin{gathered} N\to SE\mid E \\ S\to SD\mid D \\ E\to 0\mid 2\mid 4\mid 6\mid 8 \\ D\to 0\mid 1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9 \end{gathered}$$

二、阅读教材了解直线式语言SPL

代码与文法的对应关系

将代码等价转换为树形结构来描述，只注重语句和表达式，形成了直线式程序。

文法的产生式规则

与type 类型定义的关系

可以将文法直接翻译成数据结构的定义，其中每个文法符号对应这个数据结构中的一个typedef，例如：

而其中的A_stm其实是一个结构体。

与解释器interp的关系

通过解释器，利用构造器来解释执行语言，并对其环境、抽象语法、树数据结构的递归性予以展示。

三、参考简单语言解释器 Naive.fs 代码，尝试写出其文法

四、下面文法生成的语言分别是什么

G1 : S-> AB
    A -> aA|ε
    B->bc|bBc

G2: S ->aA|a
    A ->aS

G1：任意a个字符（包括0个）后跟着n个b和c，n至少为1

G2：任意奇数个a（至少一个）组成的字符串