下载文档原格式
编译原理复习总结⼀、编译器概述1、名词解释1.1解释下列名词源语⾔：被翻译器翻译的语⾔，⽤于书写源程序的语⾔。
⽬标语⾔：被翻译器翻译之后得到的语⾔，⽤于书写⽬标程序的语⾔翻译器：能够完成从⼀种语⾔到另⼀种语⾔的变换的软件编译器：⼀种特殊的翻译器，要求⽬标语⾔⽐源语⾔低级解释器：解释器是不同于编译器的另⼀种语⾔处理器。
解释器不像编译器那样通过翻译来⽣成⽬标程序，⽽是直接执⾏源程序所指定的运算。
2、编译阶段1.2典型的编译器可以划分成⼏个主要的逻辑阶段？各阶段的主要功能是什么？典型的编译器可以划分成七个主要的逻辑阶段，分别是词法分析器、语法分析器、语义分析器、中间代码⽣成器、独⽴于机器的代码优化器、代码⽣成器、依赖于机器的代码优化器。
各阶段的主要功能：（1）词法分析器：词法分析阅读构成源程序的字符流，按编程语⾔的词法规则把它们组成词法记号流。
（2）语法分析器：按编程语⾔的语法规则检查词法分析输出的记号流是否符合这些规则，并依据这些规则所体现出的该语⾔的各种语⾔构造的层次性，⽤各记号的第⼀元建成⼀种树形的中间表⽰，这个中间表⽰⽤抽象语法的⽅式描绘了该记号流的语法情况。
（3）语义分析器：使⽤语法树和符号表中的信息，依据语⾔定义来检查源程序的语义⼀致性，以保证程序各部分能有意义地结合在⼀起。
它还收集类型信息，把它们保存在符号表或语法树中。
（4）中间代码⽣成器:为源程序产⽣更低级的显⽰中间表⽰，可以认为这种中间表⽰是⼀种抽象机的程序。
（5）独⽴于机器的代码优化器：试图改进中间代码，以便产⽣较好的⽬标代码。
通常，较好是指执⾏较快，但也可能是其他⽬标，如⽬标代码较短或⽬标代码执⾏时能耗较低。
（6）代码⽣成器：取源程序的⼀种中间表⽰作为输⼊并把它映射到⼀种⽬标语⾔。
如果⽬标语⾔是机器代码，则需要为源程序所⽤的变量选择寄存器或内存单元，然后把中间指令序列翻译为完成同样任务的机器指令序列。
（7）依赖于机器的代码优化器：试图改进⽬标机器代码，以便产⽣较好的⽬标机器代码。
编译原理复习重点含答案编译原理复习重点编译原理是计算机科学中的一门重要课程，它研究的是如何将高级语言程序转化为机器语言的过程。
在编译原理的学习中，我们需要掌握一些重要的概念和技术，以便能够理解和应用编译器的工作原理。
本文将重点介绍编译原理的几个重要主题，并提供相应的答案供参考。
一、词法分析词法分析是编译器的第一个阶段，它的任务是将输入的字符序列划分为一个个有意义的词素（token）。
词法分析器通常使用有限自动机（DFA）来实现，其工作原理是将输入字符序列逐个读入，并根据事先定义好的词法规则进行匹配和识别。
常见的词法单元包括关键字、标识符、常量、运算符等。
常见的词法规则包括：1. 关键字：例如if、while、for等。
2. 标识符：由字母、数字和下划线组成，且以字母或下划线开头。
3. 常量：包括整数常量、浮点数常量、字符常量和字符串常量等。
4. 运算符：例如加法运算符+、减法运算符-等。
5. 分隔符：例如逗号、分号等。
词法分析的结果是一个个词法单元，每个词法单元包含一个词素和对应的词法单元类型。
例如，对于输入程序"int a = 10;"，词法分析的结果可能是[("int", "关键字"), ("a", "标识符"), ("=", "运算符"), ("10", "整数常量"), (";", "分隔符")]。
二、语法分析语法分析是编译器的第二个阶段，它的任务是将词法分析器输出的词法单元序列转化为抽象语法树（AST）。
语法分析器通常使用上下文无关文法（CFG）来描述语言的语法结构，并使用递归下降、LL(1)分析、LR分析等算法进行分析。
常见的语法规则包括：1. 表达式：例如算术表达式、布尔表达式等。
编译原理期末总结复习（经典版）编制人：__________________审核人：__________________审批人：__________________编制单位：__________________编制时间：____年____月____日序言下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。
文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!并且，本店铺为大家提供各种类型的经典范文，如公文写作、报告体会、演讲致辞、党团资料、合同协议、条据文书、诗词歌赋、教学资料、作文大全、其他范文等等，想了解不同范文格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you!In addition, this shop provides you with various types of classic sample essays, such as official document writing, report experience, speeches, party and group materials, contracts and agreements, articles and documents, poems and songs, teaching materials, essay collections, other sample essays, etc. Learn about the different formats and writing styles of sample essays, so stay tuned!编译原理期末总结复习编译原理期末总结复习（精选3篇）编译原理期末总结复习篇1一、简答题1.什么是编译程序？答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？答编译程序总框架（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。
语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。
任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。
任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。
任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
编译原理复习最终版第⼀章⼀.单项选择1.将编译程序分成若⼲“遍”，是为了（）A.提⾼程序的执⾏效率B.使程序的结构更为清晰C.利⽤有限的机器内存并提⾼机器的执⾏效率D.利⽤有限的机器内存但降低了机器的执⾏效率2.⼀个编译程序在编译时，⼤多数时间花在（）上A.出错处理B.词法分析C.⽬标代码⽣成D.表格管理及处理3. 下⾯代码不可能是⽬标代码的是（）A. 汇编指令代码B. 可重定位指令代码C. 中间代码D. 绝对指令代码4. 解释程序和翻译程序的根本区别A. 是否⽣成中间代码B. 是否有语义分析阶段C. 是否⽣成⽬标代码D. 是否有语法分析阶段5. 下⾯编译阶段既可以作为编译器的前端，也可以作为编译器的后端的是：（）A. 语法分析阶段B. 语义分析阶段C. 中间代码⽣成阶段D. 中间代码优化阶段⼆.多项选择1. ⼀个编译器可能有的阶段为（）A. 词法分析B. 语法分析C. 语义分析2. 编译器的各个阶段的⼯作都涉及到（）A. 表格处理B. 词法分析C. 语法分析D. 语义分析E. 出错处理3. ⼀般来说，编译器可分为前端和后端，下列编译阶段可被划分为编译的前端的有：（）A. 词法分析B. 语法分析C. 语义分析D. 中间代码⽣成E. 中间代码优化三.判断题1.⼀个编译器就是⼀个程序，该程序的输⼊是源程序，输出是与之等价的⽬标程序。
2.编译与解释程序的根本区别是：是否⽣成⽬标代码。
3.解释程序和编译程序的前端是相同的，其实现技术基本上也是相通的。
4.⼀般⽽⾔，中间代码是⼀种独⽴于具体硬件的记号系统。
四.综合题1.请画出编译程序的总体框图。
2.源程序的解释和和编译执⾏的主要区别是什么？第三章⼀.单项选择题1.词法分析器的输出是：（）A.单词在符号表中的位置B.单词的⾃⾝值C.单词的⾃⾝值和单词的种类码D.单词的种类码2.词法分析的依据是：（）A.语义规则B.构词规则C.语法规则D.等价变换规则3. 两个DFA等价是指：（）A. 这两个DFA的状态数相同B. 这两个DFA的状态数和有向弧条数都相等C. 这两个DFA的有向弧条数相等D. 这两个DFA接受的语⾔相同4. 词法分析器的输⼊是：（）A. Token序列B. 源程序C. ⽬标程序D. 符号表5.下列符号串不可以由符号集∑＝{a,b}上的正闭包运算产⽣的是：（）A. εB. aD.ab⼆.多项选择1. 令∑＝{a,b}，则∑上的符号串的全体可⽤下⾯的正规式表⽰。
编译原理复习题及答案一、选择题1．一个正规语言只能对应( B )A 一个正规文法B 一个最小有限状态自动机2．文法G[A] ：A→εA→aB B→Ab B→a是( A )A 正规文法B 二型文法3．下面说法正确的是( A ) A一个SLR（1）文法一定也是LALR （1）文法B一个LR （1）文法一定也是LALR （1）文法4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL （1）文法的( A )A 必要条件B 充分必要条件5．下面说法正确的是( B )A 一个正规式只能对应一个确定的有限状态自动机B 一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是( A )A 归约速度快B 对文法限制少7．一个LR （1）文法合并同心集后若不是LALR （1）文法( B )A 则可能存在移进/归约冲突B 则可能存在归约/归约冲突C 则可能存在移进/归约冲突和归约/ 归约冲突8．下面说法正确的是( A )A Lex 是一个词法分析器的生成器B Yacc 是一个语法分析器9．下面说法正确的是( A )A一个正规文法也一定是二型文法B一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C) 。
A 、机器语言的执行B、汇编语言的翻译C、高级语言的翻译D、高级语言程序的解释执行11．(A) 是一种典型的解释型语言。
A ．BASICB ．CC．FORTRAN D．PASCAL12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B) 完成的。
A. 编译器B. 汇编器C. 解释器D. 预处理器13．用高级语言编写的程序经编译后产生的程序叫(B) A ．源程序B ．目标程序C．连接程序 D ．解释程序14．(C) 不是编译程序的组成部分。
A. 词法分析程序B. 代码生成程序C.设备管理程序D. 语法分析程序15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优目标代码生成等六个部分，还应包括(C)A ．模拟执行器B ．解释器C．表格处理和出错处理D ．符号执行器16．编译程序绝大多数时间花在(D) A ．出错处理B．词法分析C．目标代码生成D．表格管理17．源程序是句子的集A. 线性表(B) 可以较好地反映句子的结构。
复习汇总一、第一章概述1.文法与自动机的等价1)0型文法—图灵机2)1型文法—线性有界非确定图灵机3)2型文法—非确定下推自动机4)3型文法—有限状态自动机2.编译技术的应用1)语法制导的结构化编辑器2)程序格式化工具3)软件测试工具4)程序理解工具5)高级语言的翻译工具6)等等3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解）1)面向机器的语言：机器指令，汇编语言2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述语言（正规式,产生式）等等。
4.各语言的分类（结合第二章第9小点理解）1)过程式语言，面向对象语言：通用程序设计语言。
2)函数语言：面向特点领域的，递归特性。
例如LISP语言3)说明性，非算法式语言：LEX/YACC,SQL。
4)脚本式语言：Shell语言5.语言之间的转换（李静PPT41）1)高级语言之间的转换一般称为预处理或转换。
2)高级语言翻译成汇编语言或机器语言称之为编译。
3)把汇编语言翻译成机器语言称之为汇编。
4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之为交叉汇编。
5)把机器语言翻译成汇编语言称之为反汇编。
6)把汇编语言翻译成高级语言称之为反编译。
6.编译器和解释器1)编译器●源程序的翻译和翻译后的程序的运行是两个不同的阶段。
◆编译阶段：用户输入源程序，经过编译器的处理，生成目标程序。
◆目标程序的运行阶段：根据要求输入数据，得出结果。
2)解释器（凡是可以采用编译器的地方均可以采用解释器）●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执行它。
这种方式称为解释。
7.解释器的优点（对比与编译器）1)具有较好的动态特性。
2)具有较好的移植特性。
8.解释器的缺点（对比于编译器）1)相比于编译器需花费大量的时间。
2)占用更多的内存空间。
9.编译器的工作阶段（结合第二章6小点红色部分理解）1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器->代码优化器->目标代码生成器->目标代码2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。
第一章1、将编译程序分成若干个“遍”是为了。
a．提高程序的执行效率b．使程序的结构更加清晰c．利用有限的机器内存并提高机器的执行效率d．利用有限的机器内存但降低了机器的执行效率2、构造编译程序应掌握。
a．源程序b．目标语言c．编译方法d．以上三项都是3、变量应当。
a．持有左值b．持有右值c．既持有左值又持有右值d．既不持有左值也不持有右值4、编译程序绝大多数时间花在上。
a．出错处理b．词法分析c．目标代码生成d．管理表格5、不可能是目标代码。
a．汇编指令代码b．可重定位指令代码c．绝对指令代码d．中间代码6、使用可以定义一个程序的意义。
a．语义规则b．语法规则c．产生规则d．词法规则7、词法分析器的输入是。
a．单词符号串b．源程序c．语法单位d．目标程序8、中间代码生成时所遵循的是- 。
a．语法规则b．词法规则c．语义规则d．等价变换规则9、编译程序是对。
a．汇编程序的翻译b．高级语言程序的解释执行c．机器语言的执行d．高级语言的翻译10、语法分析应遵循。
a．语义规则b．语法规则c．构词规则d．等价变换规则解答1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3、对编译而言，变量既持有左值又持有右值，故选c。
4、编译程序打交道最多的就是各种表格，因此选d。
5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。
6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。
因此选a。
7、b 8、c 9、d 10、c二、多项选择题1、编译程序各阶段的工作都涉及到。
a．语法分析b．表格管理c．出错处理d．语义分析e．词法分析2、编译程序工作时，通常有阶段。
a．词法分析b．语法分析c．中间代码生成d．语义检查e．目标代码生成解答1．b、c 2. a、b、c、e三、填空题1、解释程序和编译程序的区别在于。
2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。
3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。
4、编译程序是指将程序翻译成程序的程序。
解答是否生成目标程序2、词法分析中间代码生成3、源程序目标代码生成4、源程序目标语言第二章一、单项选择题1、文法G：S→xSx|y所识别的语言是。
a. xyxb. (xyx)*c. x n yx n(n≥0)d. x*yx*2、文法G描述的语言L(G)是指。
a. L(G)={α|S+⇒α , α∈V T*}b. L(G)={α|S*⇒α, α∈V T*}c. L(G)={α|S*⇒α,α∈(V T∪V N*)}d. L(G)={α|S+⇒α, α∈(V T∪V N*)}3、有限状态自动机能识别。
a. 上下文无关文法b. 上下文有关文法c.正规文法d. 短语文法4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。
a. 若f(a)>g(b)，则a>bb.若f(a)<g(b)，则a<bc. a~b都不一定成立d. a~b一定成立5、如果文法G是无二义的，则它的任何句子α。
a. 最左推导和最右推导对应的语法树必定相同b. 最左推导和最右推导对应的语法树可能不同c. 最左推导和最右推导必定相同d. 可能存在两个不同的最左推导，但它们对应的语法树相同6、由文法的开始符经0步或多步推导产生的文法符号序列是。
a. 短语b.句柄c. 句型d. 句子7、文法G：E→E+T|TT→T*P|PP→(E)|I则句型P+T+i的句柄和最左素短语为。
a.P+T和ib. P和P+Tc. i和P+T+id.P和T8、设文法为：S→SA|AA→a|b则对句子aba，下面是规范推导。
a. S⇒SA⇒SAA⇒AAA⇒aAA⇒abA⇒abab. S⇒SA⇒SAA⇒AAA⇒AAa⇒Aba⇒abac. S⇒SA⇒SAA⇒SAa⇒Sba⇒Aba⇒abad. S⇒SA⇒Sa⇒SAa⇒Sba⇒Aba⇒aba9、文法G：S→b|∧|(T)T→T,S|S则FIRSTVT(T) 。
a. {b,∧,(}b. {b,∧,)}c.{b,∧,(,，}d.{b,∧,),，}10、产生正规语言的文法为。
a. 0型b. 1型c. 2型d. 3型11、采用自上而下分析，必须。
a. 消除左递归b. 消除右递归c. 消除回溯d. 提取公共左因子12、在规范归约中，用来刻画可归约串。
a. 直接短语b. 句柄c. 最左素短语d. 素短语13、有文法G：E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约，其值为。
a. 23 B. 42 c. 30 d. 1714、规范归约指。
a. 最左推导的逆过程b. 最右推导的逆过程c. 规范推导d. 最左归约的逆过程[解答]1、选c。
2、选a。
3、选c。
4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。
所以，由f(a)>g)(b)或f(a)<g(b)并不能判定原来的a与b之间是否存在优先关系：故选c。
5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左推导，则必然有二义性。
故选a。
6、选c。
7、由图2-8-1的语法树和优先关系可以看出应选b。
8、规范推导是最左推导，故选d。
9、由T→T,…和T→(…得FIRSTVT(T))={(,，)}；由T→S得FIRSTVT(S)⊂FIRSTVT(T)，而FIRSTVT(S)={b,∧,(}；即FIRSTVT(T)={b,∧,(,，}；因此选c。
10、d 11、c 12、b 13、b 14、b二、多项选择题1、下面哪些说法是错误的。
a. 有向图是一个状态转换图b. 状态转换图是一个有向图c.有向图是一个DFAd. DFA可以用状态转换图表示2、对无二义性文法来说，一棵语法树往往代表了。
a. 多种推导过程b. 多种最左推导过程c.一种最左推导过程d.仅一种推导过程e.一种最左推导过程3、如果文法G存在一个句子，满足下列条件之一时，则称该文法是二义文法。
a. 该句子的最左推导与最右推导相同b. 该句子有两个不同的最左推导c. 该句子有两棵不同的最右推导d. 该句子有两棵不同的语法树e.该句子的语法树只有一个4、有一文法G：S→ABA→aAb|εB→cBd|ε它不产生下面集合。
a. {a n b m c n d m|n,m≥0}b. {a n b n c m d m|n,m>0}c. {a n b m c m d n|n,m≥0}d. {a n b n c m d m|n,m≥0}e. {a n b n c n d n|n≥0}5、自下而上的语法分析中，应从开始分析。
a. 句型b. 句子c. 以单词为单位的程序d. 文法的开始符e. 句柄6、对正规文法描述的语言，以下有能力描述它。
a.0型文法b.1型文法c.上下文无关文法d.右线性文法e.左线性文法解答1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e三、填空题1、文法中的终结符和非终结符的交集是。
词法分析器交给语法分析器的文法符号一定是，它一定只出现在产生式的部。
2、最左推导是指每次都对句型中的非终结符进行扩展。
3、在语法分析中，最常见的两种方法一定是分析法，另一是分析法。
4、采用语法分析时，必须消除文法的左递归。
5、树代表推导过程，树代表归约过程。
6、自下而上分析法采用、归约、错误处理、等四种操作。
7、Chomsky把文法分为种类型，编译器构造中采用和文法，它们分别产生和语言，并分别用和自动机识别所产生的语言。
解答1、空集终结符右2、最左3、自上而上自下而上4、自上而上5、语法分析6、移进接受7、4 2 型3型上下文无关语言正规语言下推自动机有限四、判断题1、文法S→aS|bR|ε描述的语言是(a|bc)* ( )R→c S2、在自下而上的语法分析中，语法树与分析树一定相同。
（）3、二义文法不是上下文无关文法。
（）4、语法分析时必须先消除文法中的左递归。
（）5、规范归约和规范推导是互逆的两个过程。
（）6、一个文法所有句型的集合形成该文法所能接受的语言。
（）解答1、对2、错3、错4、错5、错6、错五、简答题1、句柄2、素短语3、语法树4、归约5、推导[解答]1、句柄：一个句型的最左直接短语称为该句型的句柄。
2、素短语：至少含有一个终结符的素短语，并且除它自身之外不再含任何更小的素短语。
3、语法树：满足下面4个条件的树称之为文法G[S]的一棵语法树。
①每一终结均有一标记，此标记为V N∪V T中的一个符号；②树的根结点以文法G[S]的开始符S标记；③若一结点至少有一个直接后继，则此结点上的标记为V N中的一个符号；④若一个以A为标记的结点有K个直接后继，且按从左至右的顺序，这些结点的标记分别为X1,X2,…,X K，则A→X1,X2,…,X K，必然是G的一个产生式。
4、归约：我们称αγβ直接归约出αAβ，仅当A→γ是一个产生式，且α、β∈(V N∪V T)*。
归约过程就是从输入串开始，反复用产生式右部的符号替换成产生式左部符号，直至文法开始符。
5、推导：我们称αAβ直接推出αγβ，即αAβ⇒αγβ，仅当A→γ是一个产生式，且α、β∈(V N∪V T)*。
如果α1⇒α2⇒…⇒αn，则我们称这个序列是从α1至α2的一个推导。
若存在一个从α1αn的推导，则称α1可推导出αn。
推导是归约的逆过程。
六、问答题1、给出上下文无关文法的定义。
[解答]一个上下文无关文法G是一个四元式（V T,V N,S, P），其中：●V T是一个非空有限集，它的每个元素称为终结符号；●V N是一个非空有限集，它的每个元素称为非终结符号，V T∩V N=Φ；●S是一个非终结符号，称为开始符号；●P是一个产生式集合（有限），每个产生式的形式是P→α，其中，P∈V N，α∈(V T∪V N)*。
开始符号S至少必须在某个产生式的左部出现一次。
2、文法G[S]：S→aSPQ|abQQP→PQbP→bbbQ→bccQ→cc（1）它是Chomsky哪一型文法？（2）它生成的语言是什么？[解答]（1）由于产生式左部存在终结符号，且所有产生式左部符号的长度均小于等于产生式右部的符号长度，所以文法G[S]是Chomsky1型文法，即上下文有关文法。
（2）按产生式出现的顺序规定优先级由高到低（否则无法推出句子），我们可以得到：S⇒abQ⇒abcS⇒aSPQ⇒aabQPQ⇒aabPQQ⇒aabbQQ⇒aabbcQ⇒aabbccS⇒aSPQ⇒aaSPQPQ⇒aaabQPQPQ⇒aaabPQQPQ⇒aaabPQPQQ⇒aaaPPQQQ⇒aaabbPqqq⇒aaabbQQQ⇒aaabbbcQQ⇒aaabbbccQ⇒aaabbbccc……于是得到文法G[S]生成的语言L={a n b n c n|n≥1}3、按指定类型，给出语言的文法。
