lab4 语言与文法3

实验报告封面

课程名称：编译原理课程代码： SS2027

任课老师：彭小娟实验指导老师: 彭小娟

实验报告名称：实验四：语言与文法3

学生姓名：

学号：

教学班：

递交日期：

签收人：

我申明，本报告内的实验已按要求完成，报告完全是由我个人完成，并没有抄袭行为。我已经保留了这份实验报告的副本。

申明人(签名):

实验报告评语与评分：

评阅老师签名：

一、实验名称：语言与文法3

二、实验日期： 年 月 日

三、实验目的：

1. 理解相关概念：乔姆斯基体系、BNF 范式、文法的二义性

2. 理解文法G 的形式化定义，并能根据给定的文法推导出符号串，会画语法树，理解短语、直接短语、句柄。

3. 能够根据语言构造文法

四、实验用的仪器和材料：（操作系统：CPU ：内存：硬盘：软件：） 硬件：PC 人手一台

软件：office

五、实验的步骤和方法：

1. 考虑如下上下文无关文法G[S]，其中(和)为终结符：S->SS|(S)|ε

1. 给出通过此文法生成串((())())的一个归约过程、一个推导

过程和一颗分析树

2. 猜一猜：该文法的语言是什么？

2. 设有上下文无关文法如下： cB

c B bT

b T aU

a U UT A AB

S S G |||:

][>->->->->-，写出该文法生成的语言L(S)。 3. 构造一个上下文无关文法G ，使其描述的语言L(G)是能够被5整除的无符号整数集合。

4. 证明下面的文法是二义的：S->iSeS|iS|i 见课本P36 T9

5. 构造产生如下语言的上下文无关文法各一个：1. {0|>n b a n n } 2.

{0|>≥n m b a n m } 3. }0,1|{1≥≥=i n c b a L i n n

六、数据记录和计算：

七、实验结果或结论：（总结）

八、备注或说明：可写上实验成功或失败的原因，实验后的心得体会、建议等。

九、引用参考文献：即在本实验中所引用的之資料。

编译第3章习题(文法和语言)_09级

习题第3章文法和语言 1．写一文法，使其语言是偶整数集合，但不允许由0打头。3．写一文法G，使得L(G) = { a m b n| m≥0, n≥1 } 4．写一文法G，使得L(G) = { a m b n c p| m≥0, n≥0, p≥0 } 5．设有文法G1：S → AaB S → a A → AB A → b A →ε B → bB B →ε 写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。6．写一文法，使其语言是十位数不是0的整数集合。 7．写出以下文法G所定义的语言L(G)。 G：S → SaS S → b S → d 8．设有文法G1：S → Sab S → c S → d 将其改写成以下形式的文法G2，每条规则形如： V → xW 或V → y 其中V和W为非终结符，x和y为终结符串。 9．设有文法G1：S → abcdB B → efgB B → b 将其改写成以下形式的3型文法G2，每条规则形如： V → pW 或V → q 其中V和W为非终结符，p和q为终结符。 10．设有文法G1：S → aBBaS B → bbAA A → aAbBc A → a 将其改写成以下形式的文法G2，每条规则形如： V → pX1X2…X n 或V → q 其中V和X i为非终结符，p和q为终结符。 11．已知C语言的下标变量形如： a[E][E]…[E] 按第10题要求的文法G2的形式写出下标变量文法。12．设有文法G1：S → aBcA

S → aBdB A → bA A → aB B → Bd B → a 将其改写成文法G2，使得对每个非终结符均无两个不同规则能导出相同的终结开头符。13．设有文法G：S → aBbD B → bSD B → aDa B → bb D → aBD 证明L(G)为空语言。 14．设有文法G1：S → 0Y | 1X | 1Y | 1S |ε X → 1Y | 1S |ε Y → 1Z Z → 1S |ε 将其改写成不含空规则的文法G2，且L(G1) = L(G2)∪{ε}。 15．设有文法G：E → E+T | T T → T*F | F F → i | (E) （1）构造句子(i*i+i)*i的语法树，并写出该句子的规范推导过程； （2）构造句型F*(T+i)+i的语法树，并求出该句型的所有短语、简单短语和句柄。16．构造一个二义性文法。 17. 课本P49. 第14题（1）（2） 18. 课本P49. 第16题（2）

形式语言参考答案

2．1回答下面的问题： （周期律 02282067） （1）在文法中，终极符号和非终极符号各起什么作用？ ? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语 言中字符的范围。 ? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至 少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。 （2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式 中关于A 的产生式推导实现的 ? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ） ={w S T w w * * |?∈且} （3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ ? 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句 型的语言。 （4）文法中的归约和推导有什么不同？ ? 推导：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γαδ在G 中 推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归 约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义： εε,}{0 ∑ =为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义

形式语言理论

形式语言理论 形式语言理论（formal language theory）用数学方法研究自然语言（如英语）和人工语言（如程序设计语言）的产生方式、一般性质和规则的理论。形式语言是模拟这些语言的一类数学语言，它采用数学符号，按照严格的语法规则构成。从广义上说，形式语言是符号取自某个字母表的字符串的集合。 如同自然语言具有语法规则一样，形式语言也是由形式文法生成的。一个形式文法是一个有穷变元集合，这些变元也称为非终结符或语法范畴。每个变元都可以用来定义语言，定义方式可以是递归的，即通过一些称为终结符的原始符号，加上变元自身，递归地加以定义。和变元有关的规则称为生成式，生成式决定了语言是如何构造出来的。一个典型的生成式表示：给定变元所代表的语言包含这样一些字符串，它们是通过连结运算，将另外某些变元语言中的字符串和若干终结符连结起来而得到的。 形式文法被严格地定义为四元组G＝（V，T，P，S），其中V和T分别是变元和终结符的有穷集合，并且V和T分别是变元和终结符的有穷集合，并且V和T没有公共元素，即V∩T=?。S是一个特殊变元，称为开始符号。P是生成式的有穷集合，生成式的基本形式是：a→β，这里a和β，这里a和β都是（V∪T）*中的元素，即它们都是由变元和终结符组成的符号串，但要求a至少含有一个非终结符。在形式文法定义中，生成式集合P是至关重要的。在对使用符号的惯例作某些约定后，仅仅考查生成式，就能推断出一个文法的变元、终结符和开始符号，故可以通过列出生成式来定义一个形式文法。 形式文法G＝（V，T，P，S）产生的形式语言记为L（G）。L（G）中的字符串ω都具有如下特点：①该字符串仅由终结符组成，即ω∈T*；②该字符串能由开始符号S派生出来，即从S出发，通过应用零个或多个P中的生成式，由S可以推导出ω。 根据P中生成式a→β的特点，可以将形式文法及其产生的形式语言分类，构成所谓的形式语言谱系。形式语言理论中重点研究四类文法和语言：①0型文法。又称为无限制文法。这种文法对生成式a→β不作特殊限制，a和β可以是任意的文法符号串，当然a不能是空字符串。0型文法是形式语言谱系中最大的文法类。由0型文法产生的形式语言恰是图灵机所识别的语言类，即递归可枚举语言。②1型文法。又称为上下文有关文法。这种文法要求生成式a→β满足｜a｜≤｜β｜，即β要至少和a 一样长。由1型文法产生的语言称为1型语言或上下文有关语言。1型语言恰是非确定型线性有界自动机所识别的语言类。③2型文法。又称为上下文无关文法。这种文法要求生成式a→β中的a必须是变元。由2型文法产生的语言称为2型语言或上下文无关语言。2型语言恰是由下推自动机所识别的语言类。④3型文法。又称为正则文法。这种文法分为两种类型：第一类要求生成式的形式必须是A→ωB或A→ω，其中A，B都是变元，ω是终结符串（可以是空串），这种特殊的正则文法称为右线性文法。第二类正则文法称为左线性文法，它要求生成式必须是A→Bω，或A→ω的形式。由正则文法生成的语言称为正则语言，它恰是有穷自动机所识别的语言类。

(完整版)编译原理习题及答案(整理后)

第一章 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、编译程序各阶段的工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于。 2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。

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

习题第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 →ε 写一文法G2，使得L(G1) = L(G2)，并且G2不含空规则。 解：G2:S→BaB|Ba|aB|a 或G2:S→bB|Sb|a B→bB|b 6．写一文法，使其语言是十位数不是0的整数集合。 解：G：N→SA S→+|-|ε A→D|CD|BCD B→B D|C C→1|2|3|4|5|6|7|8|9 D→0|1|2|3|4|5|6|7|8|9

7．写出以下文法G所定义的语言L(G)。 G：S → SaS S → b S → d 解：L(G)={(xa)n x|n≥0, x∈{b,d}} ={((b|d)a)n(b|d)|n≥0} ={(b|d)(a(b|d))n|n≥0} 8．设有文法G1：S → Sab | c | d 将其改写成以下形式的文法G2，每条规则形如： V → xW 或V → y 其中V和W为非终结符，x和y为终结符串。 解：G：S→cT|dT|c|d T→abT|ab 9．设有文法G1：S → abcdB B → efgB B → b 将其改写成以下形式的3型文法G2，每条规则形如： V → pW 或V → q 其中V和W为非终结符，p和q为终结符。 解：G：S→aA A→bB B→cC C→dD D→eE|b E→fF F→gD 10．设有文法G1：S → aBBaS B → bbAA A → aAbBc A → a 将其改写成以下形式的文法G2，每条规则形如： V → pX1X2…X n 或V → q 其中V和X i为非终结符，p和q为终结符。 解：G：S→aBBPS P→a B→bQAA Q→b A→aAQBR|a R→c

第三章 文法和语言课后习题参考答案

第三章文法和语言课后习题参考答案 1. L(G)={abc} 2. L(G[N])是无符号整数。 3.G3: E→D+E | D-E | D D→0|1|2|3|4|5|6|7|8|9 4. L(G[Z])={a n b n | n>0} 5. 写一文法，使其语言是偶正整数的集合 要求： (1)允许0打头 (2)不允许0打头 解： (1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) P: S→PD|D P->NP|N D→0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) P: S→PD|P0|D P->NR|N R->QR|Q D→2|4|6|8 N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9 6. 已知文法G： <表达式>::=<项>|<表达式>+<项>|<表达式>-<项> <项>::=<因子>|<项>*<因子>|<项>/<因子> <因子>::=(<表达式>)|i。 试给出下述表达式的推导及语法树。 (1)i; (2)(i) (3)i*i; (4)i*i+i; (5)i+(i+i);(6)i+i*i。 解： (1)<表达式>=><项>=><因子>=>i (2)<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(<因子>)=>(i) (3)<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i (4)<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项> =><因子>*<因子>+<因子>=>i*i+i=w (5)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>) => i+(<表达式>+<项>)=>i+(<项>+<项>)=> i+(<因子>+<因子>)=>i+(i+i) (6)<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项> =>i+<项>*<因子>=> i+<因子>*<因子>=> i+i*i

编译原理第三章答案

第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])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题

已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i

第二章节形式语言与自动机理论参考测试答案

2．1回答下面的问题： （周期律 02282067） （1）在文法中，终极符号和非终极符号各起什么作用？ ? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语 言中字符的范围。 ? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至 少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。 （2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式 中关于A 的产生式推导实现的 ? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ） ={w S T w w **|?∈且} （3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ ? 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句 型的语言。 （4）文法中的归约和推导有什么不同？ ? 推导：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γαδ在G 中推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义

编译原理第三章答案

第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])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题

已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i

北邮形式语言与自动机二三章答案

形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c

(3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。 (3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略）

编译原理文法和语言答案

练习1. 文法和语言 1. 文法: Z → U0 | V1 U → Z1 | 1 V → Z0 | 0 (1) 请写出全部由此文法描述的只含有四个符号的句子. (2) 该文法是 Chomsky 几型文法? Answer ： (1) 1010, 0110, 1001, 0101 (2) 3型文法 2. 给定前缀表示的表达式文法 G : (1) E → -EE (2) E → -E (3) E → a (4) E → b (5) E → c 试问 --a-bc 是否 L(G) 的句子?若是,请给出该句子所有可能的分析树;若不是,请说明理由. Answer : --a-bc 是L(G)的句子。所有可能的分析树如下。 (1) (2) (3) E -E E -E c -E b E -E E -E -E E E -- E E c -E E 3. 考虑文法： S → ( L ) | a L → L, S | S 写出句型 ( a , ( a , a ) ) 的最左推导和最右推导。 Answer : (1) 最左推导： S lm =>(L)lm =>(L,S)lm =>(S,S)lm =>(a,S)lm =>(a,(L))lm =>(a,(L,S))lm =>(a,(S,S))lm =>(a,(a,S))lm =>(a,(a,a)) (2) 最右推导： S rm =>(L)rm =>(L,S)rm =>(L,(L))rm =>(L,(L,S))rm =>(L,(L,a))rm =>(L,(S,a))rm =>(L,(a,a))rm =>(S,(a,a))rm =>(a,(a,a)) 4. 考虑文法：

第三章文法和语言

第三章文法和语言 3.1 文法的直观概念和语言概述 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 1、语言概述 语言是由句子组成的集合，是由一组符号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体 程序设计语言--所有该语言的程序的全体 每个句子构成的规律 2、研究语言每个句子的含义 每个句子和使用者的关系 3、研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 4、语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics 语法 -- 表示构成语言句子的各个记号之间的组合规律 语义 -- 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。 语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。 形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。 是程序设计语言语法分析研究的基础。 3.2符号与符号串 1、字母表∑：符号（元素）的非空有穷集合。 2、符号串：由字母表∑中的符号组成的任何有穷序列称为该字母表上的符号串。1.空符号串ε (没有符号的符号串)是∑上的符号串 2.若x是∑上的符号串,a是∑的元素,则xa是∑上的符号串 3. y是∑上的符号串,当且仅当它可以由1和2导出。 例如：Σ={a,b} ε,a,b,aa,ab,aabba…都是∑上的符号串 3、符号串的运算 符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 如001110的长度是6。 空符号串，即不包含任何符号的符号串，用ε表示，其长度为0，即｜ε｜=0。 符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串. 由于ε的含义，显然有ε x=x ε =x。 例如 x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5 符号串的方幂符号串自身连接n次得到的符号串a n 定义为 aa…aa n个a a1=a, a2=aa且a0=ε4、符号串集合：若集合A中所有元素都是某字母表∑上的符号串，则称A为字母表∑上的符号串

形式语言第二章参考答案(蒋宗礼)

2．1回答下面的问题： （1）在文法中，终极符号和非终极符号各起什么作用？ ? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语 言中字符的范围。 ? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至 少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。 （2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式 中关于A 的产生式推导实现的 ? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ） ={w S T w w * * |?∈且} （3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ ? 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句 型的语言。 （4）文法中的归约和推导有什么不同？ ? 推导：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γαδ在G 中 推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归 约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义： εε,}{0 ∑ =为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义

《编译原理》课后习题答案第三章第3章文法和语言第1

《编译原理》课后习题答案第三章 第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])的全部元素。 盛威网（https://www.wendangku.net/doc/dc235358.html,）专业的计算机学习网站 1 《编译原理》课后习题答案第三章 答案： 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|2|4|6|8

(2)不允许0 开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6 题 已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i 盛威网（https://www.wendangku.net/doc/dc235358.html,）专业的计算机学习网站 2 《编译原理》课后习题答案第三章 答案： <表达式> <表达式> + <项> <因子> <表达式> <表达式> + <项> <因子> i <项> <因子> i <项> <因子> i （ ) (5) <表达式> =><表达式>＋<项> =><表达式>＋<因子> =><表达式>＋（<表达式>） =><表达式>＋（<表达式>＋<项>） =><表达式>＋（<表达式>＋<因子>） =><表达式>＋（<表达式>＋i） =><表达式>＋（<项>＋i） =><表达式>＋（<因子>＋i） =><表达式>＋（i＋i） =><项>＋（i＋i） =><因子>＋（i＋i）

第二章文法和形式语言

第二章文法和形式语言 《编译原理》课程组 计算机工程学院 第二章文法和形式语言 2.1 文法的直观概念 2.2 符号和符号串 2.3 文法和语言的形式定义 2.4 文法的类型 2.5 上下文无关文法机器语法树 2.6 句型分析 2.7 文法的实用限制 第2章文法和语言 【学习目标】 本章目的是为语言的语法描述寻求工具 ◇掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一——文法。 ◇对形式语言的理论有一个初步基础 ◇根据语言文法的特点指导语法分析的过程 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 第2章文法和语言 【教学重点】 概念：文法，推导，直接推导，最左(右)推导，产生式，句型，短语，直接短语，句柄，语法树，规范推导，二义文法等 4种文法的定义、文法的构造和文法的推导 语法树的构造和最左（右）推导； 二义文法、二义性的证明； 句型分析； 2.1 文法的直观概念 一、语言概述 语言是由符合语法的句子组成的集合。 –汉语-- 所有符合汉语语法的句子的全体 –英语-- 所有符合英语语法的句子的全体 –程序设计语言-- 所有该语言的程序的全体

每个句子构成的规律 研究语言每个句子的含义 每个句子和使用者的关系 一、语言概述（续1） 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法Syntax 语义Semantics 语用Pragmatics 一、语言概述（续2） 语法：指语言的一组规则，用它可以形成和产生一个合适的程序。 –如何由基本字符构成一个个单词； –如何由一系列单词构成程序 语法只定义什么样的符号序列是合法的，而不表达这些符号及符号序列的含义 语义：明确程序各部分的含义 –静态语义：由一系列限定规则组成，并确定哪些合乎语法的程序是合适的； –动态语义：表明程序要做些什么，要计算什么 一、语言概述（续3） 形式语言：只考虑语法而不考虑语义的符号语言。 每种语言具有两个可识别的特性， –语言的形式 –该形式相关联的意义 “形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。 形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。 语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。 二、文法的直观概念 表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述 例：汉语句子的构成规则： 〈句子〉∷=〈主语〉〈谓语〉 〈主语〉∷=〈代词〉|〈名词〉 〈代词〉∷= 我| 你| 他 〈名词〉∷= 王明| 大学生| 工人| 英语 〈谓语〉∷=〈动词〉〈直接宾语〉 〈动词〉∷= 是| 学习 〈直接宾语〉∷=〈代词〉|〈名词〉

形式语言与自动机理论精彩试题

形式语言与自动机理论试题 一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ? A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( T ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc 推导一： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC