内容发布更新时间 : 2024/12/23 9:29:40星期一 下面是文章的全部内容请认真阅读。
第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开头的非负整数? 第3题
为只包含数字、加号和减号的表达式,例如9-2+5,3-1,7等构造一个文法。答案: 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|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
试给出下述表达式的推导及语法树。 (5)i+(i+i) (6)i+i*i
答案:
(5)<表达式>
=><表达式>+<项> =><表达式>+<因子>
=><表达式>+(<表达式>)
=><表达式>+(<表达式>+<项>) =><表达式>+(<表达式>+<因子>) =><表达式>+(<表达式>+i) =><表达式>+(<项>+i) =><表达式>+(<因子>+i) =><表达式>+(i+i) =><项>+(i+i) =><因子>+(i+i) =>i+(i+i) (6)<表达式>
=><表达式>+<项>
=><表达式>+<项>*<因子> =><表达式>+<项>*i =><表达式>+<因子>*i =><表达式>+i*i =><项>+i*i =><因子>+i*i =>i+i*i <表达式>
<表达式>+<项> <因子> <表达式>
<表达式>+<项> <因子> i <项>
<因子> i <项> <因子> i ()
<表达式>
<表达式>+<项> <项>*<因子> <因子>i <项> <因子> i i
第7题
证明下述文法G[〈表达式〉]是二义的。 〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉 〈运算符〉∷=+|-|*|/ 答案:
可为句子a+a*a构造两个不同的最右推导: 最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉a 〈表达式〉*a 〈表达式〉〈运算符〉〈表达式〉*a 〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a+a*a
最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉a 〈表达式〉〈运算符〉〈表达式〉*a 〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a+a*a
第8题
文法G[S]为: S→Ac|aB A→ab B→bc
该文法是否为二义的?为什么? 答案: 对于串abc
(1)S=>Ac=>abc(2)S=>aB=>abc
即存在两不同的最右推导。所以,该文法是二义的。 或者:
对输入字符串abc,能构造两棵不同的语法树,所以它是二义的。 第9题
考虑下面上下文无关文法: S→SS*|SS+|a
(1)表明通过此文法如何生成串aa+a*,并为该串构造语法树。 (2)G[S]的语言是什么? 答案:
(1)此文法生成串aa+a*的最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)该文法生成的语言是:*和+的后缀表达式,即逆波兰式。 S A c a b S a B b c S S S* S S+a a a 第10题
文法S→S(S)S|ε
(1)生成的语言是什么?
(2)该文法是二义的吗?说明理由。 答案:
(1)嵌套的括号
(2)是二义的,因为对于()()可以构造两棵不同的语法树。 第11题
令文法G[E]为: E→T|E+T|E-T T→F|T*F|T/F F→(E)|i
证明E+T*F是它的一个句型,指出这个句型的所有短语、直接短语和句柄。 答案:
此句型对应语法树如右,故为此文法一个句型。 或者:因为存在推导序列:E=>E+T=>E+T*F,所 以E+T*F句型
此句型相对于E的短语有:E+T*F;相对于T的短语 有T*F
直接短语为:T*F 句柄为:T*F 第13题
一个上下文无关文法生成句子abbaa的推导树如下: (1)给出串abbaa最左推导、最右推导。
(2)该文法的产生式集合P可能有哪些元素? (3)找出该句子的所有短语、直接短语、句柄。 B a S A B S a S B A εb b a