编译原理文法生成语言

第3章文法和语言 第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc

写出L(G[S])的全部元素。 答案：

L(G[S])={abc} 第2题

文法G[N]为： N→D|ND

D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD....=>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]:

S->S+D|S-D|D

D->0|1|2|3|4|5|6|7|8|9 第4题

已知文法G[Z]： Z→aZb|ab

写出L(G[Z])的全部元素。 答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb L(G[Z])={anbn|n>=1} 第5题

写一文法，使其语言是偶正整数的集合。要求： (1)允许0打头； (2)不允许0打头。 答案：

(1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D

N→D|1|3|5|7

第3章文法和语言

第1题

文法G＝({A,B,S},{a,b,c},P,S)其中P为：

S→Ac|aB

A→ab

B→bc

写出L(G[S])的全部元素。

答案：

L(G[S])={abc}

第2题

文法G[N]为：

N→D|ND

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

G[N]的语言是什么？

答案:

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9}

N=>ND=>NDD....=>NDDDD...D=>D......D

或者：允许0开头的非负整数？

第３题

为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。

答案：

G[S]:

S->S+D|S-D|D

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

第4题

已知文法G[Z]：

Z→aZb|ab

写出L(G[Z])的全部元素。

答案：

Z=>aZb=>aaZbb=>aaa..Z...bbb=>aaa..ab...bbb

L(G[Z])={anbn|n>=1}

第5题

写一文法，使其语言是偶正整数的集合。要求：

(1)允许0打头；

(2)不允许0打头。

答案：

(1)允许0开头的偶正整数集合的文法

E→NT|D

T→NT|D

N→D|1|3|5|7|9

D→0

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

编译原理：文法与语言的基本知识

实验七：LL(1)文法的判断

一：要求

输入：任意的上下文无关文法。 输出：判断是否为LL（1）文法

二：实验目的

1． 掌握LL(1)的判断，掌握求first和follow集合的算法 2． 熟悉运用C/C++语言对求first和follow集合进行实现

三：实验原理

设α＝x1x2…xn，FIRST（α）可按下列方法求得： 令FIRST（α）＝Φ，i＝1；

（1） 若xi∈VT，则xi∈FIRST（α）； （2） 若xi∈VN； ① 若ε FIRST（xi），则FIRST（xi）∈FIRST（α）； ② 若ε∈FIRST（xi），则FIRST（xi）－{ε}∈FIRST（α）； （3） i＝i+1，重复（1）、（2），直到xi∈VT，（i＝2，3，…，n）或xi∈VN且若ε FIRST（xi）或i>n为止。

当一个文法中存在ε产生式时，例如，存在A→ε，只有知道哪些符号可以合法地出现在非终结符A之后，才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。

设文法G[S]＝（VN，VT，P，S），则

FOLLOW（A）＝{a | S … Aa …

实验二：压缩文法的等价变换

一：要求

输入：任意的上下文无关文法 输出：等价的压缩了的文法

要求：除了可查看压缩了的文法，还可查看删除了哪些规则 二：实验目的 了解文法的简化 三：实验原理

删除文法中的有害规则和多余规则 有害规则：

若文法中有如U::=U的规则，则这就是有害规则，它会引 起二义性，而无任何用处。 多余规则：

（1）某条规则U::=u的左部非终结符U（U不是识别符号），不在任何其他规则右部出现，即所有的推导始终不会用到此规则。【不可到达】

（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。【不可终止】

四：数据结构与算法 struct Chomsky {

string left; string right; };

void apart(Chomsky *p,int i) //分开产生式左右部 void VNVT(Chomsky *p)//求VN和VT int zero(Chomsky *p)//0型文法 int one(Chomsky *p)//1型文法 int two(Chomsky *p)//2型文法

void shanchu(Chomsk

一、实验目的及要求

1．掌握LL(1)分析法的基本原理； 2．掌握LL(1)分析表的构造方法；

3．用LL（1）分析法分析高级语言表达式。 4、了解LL（1）分析器的工作过程。 文法：无二义性的算术表达式的文法

（1）把词法分析作为语法分析的子程序实现（5分） （2）独立的语法分析程序（4分）

（3）对表达式文法消除左递归、构造LL（1）分析表 （4）LL（1）分析表可以直接输入（4分），也可以用程序实现（5分） （5）给一个表达式，给出分析过程（分析栈、输入串、所用规则）（4分） （6）生成一个棵语法树（5分）用二叉树的形式表示出来

二、实验内容及原理 1、 实验原理

（1）、LL（1）文法的定义

LL(1)分析法属于确定的自顶向下分析方法。LL(1)的含义是：第一个L表明自顶向下分析是从左向右扫描输入串，第2个L表明分析过程中将使用最左推导，1表明只需向右看一个符号便可决定如何推导，即选择哪个产生式(规则)进行推导。

LL(1)文法的判别需要依次计算FIRST集、FOLLOW集和SELLECT集,然后判断是否为LL(1)文法,最后再进行句子分析。

需要预测分析器对所给句型进行识别。即在LL(1)分析法中，每当在符号栈的栈顶

安 徽 大 学

实验一 名称 Chomsky文法类型判断（Recognizing the type of the Chomsky grammar） 一、背景资料 1956年，N.Chomsky首先对形式语言进行了描述。N.Chomsky在对某些自然语言进行研究的基础上，提出了一种用于描述语言和文法的数学系统，按照对文法规则的不同定义形式，对语言和文法分成了4类，对每一类语言，让它与一种特定种类的自动机那样的识别器联系起来。形式语言理论的形成与发展，对计算机科学的发展是一个推动，在程序设计语言的设计与编译实现以及计算复杂性等方面都有着重大影响。 二、实验目的要求 输入：一组任意的规则。 输出：相应的Chomsky 文法的类型。 三、实验原理 1．0型文法（短语文法） 如果对于某文法G，P中的每个规则具有下列形式： u:: = v 其中u∈V＋，v∈V*，则称该文法G为0型文法或短语文法，简写为PSG。 0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。这种语言可由图灵机（Turnin

习题第3章文法和语言参考答案

1．写一文法，使其语言是偶整数集合。

解：允许以0打头

G：N→+A|-A|A

A→DA|E

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

E→0|2|4|6|8

2．写一文法，使其语言是偶整数集合，但不允许由0打头。

解：0除外

G：N→+A|-A|A

A→CB|E

B→DB|E

C→1|2|3|4|5|6|7|8|9

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

E→0|2|4|6|8

3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 }

解：G1:S→aS|T或 G2:S→aS|bT 或 G3:S→aS|Sb|b

T→bT|b T→bT|ε

4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 }

解：G1:S→ABC 或G2:S→Sc|T 或 G3:A→aA|bB|cC|εA→aA|ε T→Tb|R B→bB|cC|ε

B→bB|ε R→Ra|ε C→cC|ε

C→cC|ε

5．设有文法G1：S → AaB

S → a

A → AB

A → b

A →ε

B → bB

B →ε

写一

《编译原理》综合性

实 验 报 告

实验学期 2016 至 2017 学年 第 1 学期 专业 计算机科学与技术 班级 1403 学生姓名 黄世增 学号 1411640305 任课教师 赵曦 实验成绩

1

《编译原理》课程综合性实验报告

开课实验室：C210 2016年 12月 6日 实验题目 词法分析器的设计 一、实验目的 通过设计、编制、调试一个具体的词法分析程序，实现对高级程序设计语言源程序进行扫描， 并将其分解为各种单词的词法分析方法；加深对课堂教学的理解；提高词法分析方法的实践能力。 二、实验要求 任选一种高级程序设计语言编程完成词法分析器。词法分析器应以教材所述分词原理为依据，使用恰当的数据结构和方法，结构清晰、高效。 编制一个读单词过程，源程序保存在文本文件中（也可键盘输入），读取该文件，识别出各个具有独立意义的单词，即关键字、标识符、常数

《编译原理》综合性

实 验 报 告

实验学期 2016 至 2017 学年 第 1 学期 专业 计算机科学与技术 班级 1403 学生姓名 黄世增 学号 1411640305 任课教师 赵曦 实验成绩

1

《编译原理》课程综合性实验报告

开课实验室：C210 2016年 12月 6日 实验题目 词法分析器的设计 一、实验目的 通过设计、编制、调试一个具体的词法分析程序，实现对高级程序设计语言源程序进行扫描， 并将其分解为各种单词的词法分析方法；加深对课堂教学的理解；提高词法分析方法的实践能力。 二、实验要求 任选一种高级程序设计语言编程完成词法分析器。词法分析器应以教材所述分词原理为依据，使用恰当的数据结构和方法，结构清晰、高效。 编制一个读单词过程，源程序保存在文本文件中（也可键盘输入），读取该文件，识别出各个具有独立意义的单词，即关键字、标识符、常数