前后文无关文法和语言

1.1何谓源程序、目标程序、翻译程序、编译程序和解释程序?它们之间可能有何种关系?1.2一个典型的编译系统通常由哪些部分组成?各部分的主要功能是什么?1.3选择一种你所熟悉的程序设计语言，试列出此语言中的全部关键字，并通过上机使用该语言以判明这些关键字是否为保留字。

1.4选取一种你所熟悉的语言，试对它进行分析，以找出此语言中的括号、关键字END以及逗号有多少种不同的用途。

1.5试用你常用的一种高级语言编写一短小的程序，上机进行编译和运行，记录下操作步骤和输出信息，如果可能，请卸出中间代码和目标代码。

第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。

目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。

翻译程序是将某种语言翻译成另一种语言的程序的统称。

编译程序与解释程序均为翻译程序，但二者工作方法不同。

解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。

即边解释边执行，翻译所得的指令序列并不保存。

编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。

即先翻译、后执行。

2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。

3.解：C语言的关键字有：auto break case char const continue default do double else enum externfloat for goto if int long register return short signed sizeof static struct switch typedef union unsigned void volatile while。

第二章文法和语言本章讲述目前广泛使用的上下文无关文法。

即用上下文无关文法作为程序设计语言语法的描述工具。

阐明语法的一个工具是文法。

本章将介绍文法和语言的概念。

本章重点：上下文无关文法及其句型分析中的有关问题。

第一节文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。

以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是大学生”。

是汉语的一个句子。

汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉|〈名词〉〈代词〉∷＝我|你|他〈名词〉∷＝王明|大学生|工人|英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈动词〉∷＝是|学习〈直接宾语〉∷＝〈代词〉|〈名词〉“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。

这些规则成为我们判别句子结构合法与否的依据。

一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。

我们开始去找∷＝左端的带有〈句子〉的规则并把它表示成∷＝右端的符号串，这个动作表示成：〈句子〉⇒〈主语〉〈谓语〉，然后在得到的串〈主语〉〈谓语〉中，选取〈主语〉或〈谓语〉，再用相应的规则∷＝右端代替之。

比如，选取了〈主语〉,并采用规则〈主语〉∷＝〈代词〉，那么得到：〈主语〉〈谓语〉⇒〈代词〉〈谓语〉，重复做下去，我们得到句子：“我是大学生”的全部动作过程是：〈句子〉⇒〈主语〉〈谓语〉⇒〈代词〉〈谓语〉⇒我〈谓语〉⇒我〈动词〉〈直接宾语〉⇒我是〈直接宾语〉⇒我是〈名词〉⇒我是大学生符号⇒的含义是，使用一条规则，代替⇒左边的某个符号，产生⇒右端的符号串。

显然，按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。

《编译原理》教学大纲大纲说明课程代码： 3225003总学时： 64 学时（讲课 48 学时，实验16 学时）总学分： 4课程类别：学科基础课适用专业 : 计算机科学与技术（专业）预修要求： C 语言程序设计、 C++ 程序设计、数据结构课程的性质、任务及地位：《编译原理》是计算机科学与技术专业的一门重要基础课。

通过对该课程的学习，使学生掌握编译过程中的相关原理和编译技术，让学生能初步进行编译程序的开发和维护，同时促进提高学生开发软件的能力。

教学目的与基本要求：本课程的目的，通过向学生讲述编译系统的结构、工作流程及编译程序各部分的设计原理和实现技术，使学生既掌握编译技术理论的基础与基本知识，也具有设计、实现、分析和维护编译程序等方面的初步能力。

本课程理论性较强。

因授课对象为工科学生，所以在强调编译系统的构造原理和实现方法的同时，为培养学生的实际工作能力，通过上机实践进一步加深学生对课堂教学内容的理解。

目的是要使学生牢固掌握相关的基本理论和基本方法，并能初步利用上述理论和方法解决简单实际问题。

教学方法和教学手段的建议：在教学方法上，贯彻理论联系实际、“精讲、多练”的原则，进行案例式、启发式的教学，对于一些实际性较强的问题要多采用课堂讨论等方式，以提高学生的思辨能力和学习的主动性；引导学生读书、理解、体悟、运用相结合；提高学生的学习兴趣与热情，培养与发挥学生的提出、分析及解决问题的能力。

教学手段：运用多媒体教学手段 +黑板 +上机实验的手段。

采取课堂讲授、课堂讨论、课后练习与自学等形式。

大纲的使用说明：大纲对课程性质、目的等作简单说明，同时列出各章节要学习的知识点、重点、难点，便于教学时教授重点的安排和学生自学安排。

大纲正文第一章引论学时： 4 学时（讲课 4 学时，实验 0 学时）了解编译的概念；理解编译程序的各组成部分及功能。

本章讲授要点：介绍程序设计语言与编译程序间的关系，主要内容包括：各级程序设计语言的定义、源程序的执行、编译程序的构造、编译程序的分类、形式语言理论与编译实现技术的联系。

第二章前后文无关文法和语言1设有字母表A1={a,b,…,z}，A2={0,1,…,9}，试回答下列问题：(1)字母表A1上长度为2的符号串有多少个?(2)集合A1A2含有多少个元素?(3)列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。

2试分别构造产生下列语言的文法。

(1){anbn|n≥0}；(2){anbmcp|n,m,p≥0}；(3){an#bn|n≥0}∪{cn#dn|n≥0}；(4){w#wr#|w∈{0,1}*，wr 是将w 中的符号按逆序排列所得的符号串}；(5)任何不是以0开始的所有奇整数所组成的集合；(6)所有由偶数个0和偶数个1所组成的符号串的集合。

3试描述由下列文法所产生的语言的特点(文法的开始符号均为S)。

(1)S→10S0S→aAA→bAA→a (2)S→SSS→1A0A→1A0A→ε(3)S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε(4)S→bAdcA→AGSG→εA→a (5)S→aSSS→a4设已给文法G=(VN,VT,P,S)，其中：VN={S}VT={a1,a2,…,an,∨,∧,~,［,］}P={S→ai|i=1,2,…,n}∪{S→~S,S→［S∨S］,S→［S∧S］}，试指出此文法所产生的语言。

5考察文法G=(VN,VT,P,S)，其中：VN={S,A,B,C,D,E,F,G}VT={a},P={S→ABC,C→BC,C→A,BA→GE,BG→GBF,AG→AD,DB→BD,DE→AE,FB→BF,FE→Ea,AA→ε}(1)指出此文法的类型；(2)证明此文法所产生的语言为L(G)={at(n)|n≥1}t(n)=∑n[]i=1i6设已给文法G［〈程序〉］：〈程序〉→〈分程序〉|〈复合语句〉〈分程序〉→〈无标号分程序〉|〈标号〉：〈分程序〉〈复合语句〉→〈无标号复合语句〉|〈标号〉：〈复合语句〉〈无标号分程序〉→〈分程序首部〉；〈复合尾部〉〈无标号复合语句〉→begin〈复合尾部〉〈分程序首部〉→begin〈说明〉|〈分程序首部〉；〈说明〉〈复合尾部〉→〈语句〉end|〈语句〉；〈复合尾部〉〈说明〉→d 〈语句〉→s 〈标号〉→Lw w w .k h da w .c o m课后答案网(1)给出句子L:L:begin d;d;s;s end 的最左推导和最右推导。

乔姆斯基⽂法
根据对产⽣式施加的限制不同，乔姆斯基（Chomsky）定义了四类⽂法和语⾔。

0型⽂法:短语结构⽂法或⽆限制⽂法，，其描述能⼒相当于图灵机，可使⽤任何的语法描述形式;
1型⽂法:也叫上下⽂有关⽂法，其描述能⼒相当于线性有界⾃动机，语法形式如下:xSy -> xAy。

也就是说，S推导出A是和上下⽂x, y相关的，即S只有在上下⽂x, y的环境中才能推导出A;
2型⽂法:也叫上下⽂⽆关⽂法，其描述能⼒相当于下推⾃动机，语法形式如下:S -> A。

S可以⽆条件的推导出A，和上下⽂⽆关，上下⽂⽆关⽂法因此得名;
3型⽂法:也叫正则⽂法，等价于正则表达式，其描述能⼒相当于有穷⾃动机，语法形式如下:S -> Aa。

其中最后⼀个a必须为⾮终结符。

编译原理a二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1．词法分析器的输出结果是_____。

A．( ) 单词的种别编码 B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2．正规式 M 1 和 M 2 等价是指_____。

A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等3．文法G：S→xSx|y所识别的语言是_____。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx*4．如果文法G是无二义的，则它的任何句子α_____。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握______。

A．( )源程序 B．( ) 目标语言C．( ) 编译方法 D．( ) 以上三项都是6．四元式之间的联系是通过_____实现的。

A．( ) 指示器B．( ) 临时变量C．( ) 符号表 D．( ) 程序变量7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。

A. ( ) ┐AB∨∧CD∨B．( ) A┐B ∨CD∨∧C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨8. 优化可生成_____的目标代码。

A．( ) 运行时间较短B．( ) 占用存储空间较小C．( ) 运行时间短但占用内存空间大D．( ) 运行时间短且占用存储空间小9．下列______优化方法不是针对循环优化进行的。

A. ( ) 强度削弱B. ( ) 删除归纳变量C. ( ) 删除多余运算D. ( ) 代码外提10．编译程序使用_____区别标识符的作用域。

编译原理复习题(含考试)————————————————————————————————作者：————————————————————————————————日期：*编译原理复习题一．简答题：1) 什么是句子？ 什么是语言?解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T *），则称x 是文法的一个句子。

语言——语言是句子的集合。

或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │Sx,x ∈V T *} 。

2) DFA 与NFA 有何区别 ?解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个开始状态。

另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。

3) 自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。

4) 自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。

5) 一个上下文无关文法G 包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。

6) 在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。

7) 在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。

8）什么是属性文法？答：是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。

在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。

［收稿时间］2020-05-17［基金项目］聊城大学重点教学改革项目（新工科背景下计算机类专业人才培养模式的探索与实践，教研项目，项目编号：G201905）。

［作者简介］韩玉艳（1985-），女，山东德州人，工学博士，副教授，系主任，研究方向：智能优化算法，主持国家自然科学青年基金1项，山东省自然科学基金1项，校级博士基金1项。

王玉亭（1981-），男，山东淄博人，硕士，副教授，研究方向：人工智能、演化计算。

李成友（1968-），男，山东聊城人，硕士，副教授，副院长，研究方向：网络安全。

［摘要］编译原理课程具有较强的理论性和逻辑性，该课程涉及的模型比较抽象，学生学习起来会感觉枯燥。

如何提高学生的学习兴趣、高效组织理论教学内容，使学生奠定坚实的理论基础，可以通过多样化的线上教学来实现，具体教学实施过程为：线上准备、学生自主学习、教师辅助教学、习题+作业巩固、组织保障等。

这种线上教学模式提升了学生学习的主动性、积极性以及独立解决问题的能力。

［关键词］编译原理；线上教学；互联网；以学生为中心［中图分类号］G642［文献标识码］A ［文章编号］2095-3437（2021）07-0095-03University Education一、背景2020年注定是不平凡的一年，疫情的爆发给教师和学生带来了极大的挑战。

根据山东省教育厅和学校教务处的安排，高校教师在“停课不停教，停课不停学”的总要求下，积极利用互联网和信息化技术开展线上教学。

“互联网+教学”成为现阶段教师的主要授课方式，它的出现使得师生在疫情当前的教与学游刃有余。

教师通过互联网以及各种软件资源，将教学方式多样化、信息化。

学生通过线上平台，使用优质教学资源提高自我主动学习新知识、新技术以及解决实际问题的能力。

线上教学是疫情防控时期特殊的教学模式，它所带来的优势是：1.此模式打破了传统教学壁垒和教学观念[1]；2.将多样化的信息技术融入教学中，为今后的混合式教学模式、现实课堂和虚拟课堂相融合奠定了基础；3.打破了空间和时间的约束，学生的学习时间更灵活；4.培养了学生主动学习和自学的能力等[2]。