《编译原理》期中及期末习题 下载本文

3.5.7 按指定类型,给出语言的文法。 (1)L={aidj>i≥l}的上下文无关文法。

(2)字母表∑={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法。 (3)由相同个数a和b组成句子的无二义文法。

3.5.8 下面的二义文法描述命题演算公式,为它写一个等价的非二义文法。 S→SandS|S or S|not S|p|q|(S)

3.5.9 有文法G:S→aAcB|Bd A→AaB|c B→bScA|b

(1)试求句型aAaBcbbdcc和aAcbBdcc的句柄; (2)写出句子acabcbbdcc的最左推导过程。

3.5.10 对文法G:E→E+T|T T→T*P|P P→i

(1)构造该文法的优先关系表(不考虑语句括号#),并指出此文法是否为算符优先文法;

(2)构造文法G的优先函数

3.5.11 在上一题中,如果将文法改为E→E+E|E*E|i,在不改动文法的情况下是否同样能构造出优先关系表?此外,针对例3.14中的文法与本例中的文法,对算符优先分析快于规范归约进行说明。

3.5.12 对于文法G[S]:

S→(L)|aS|a L→L,S|S (1)画出句型(s,(a))的语法树。

(2)写出上述句型的所有短语、直接短语、句柄和素短语。

3.5.13 构造算符文法G[H]的算符优先关系(含#)。 G[H]:H→H;M|M M→d|aHb

3.5.14 设有文法G[S]为: S→a|b|(A) A→SdA|S

(1) 完成下列算符优先关系表,见表3.6.并判断G[S]是否为算符优先文法。

(2)给出句型(SdSdS)的短语、简单短语、句柄、素短语和最左素短语。 (3)给出输入串(adb)#的分析过程。

3.5.15 下面映射if语句的文法G[S]是算符优先文法吗?若是,则构造其优先关系矩阵。若不是,请按照多数程序设计语言(如Pascal)的习惯,给出一个相应的算符优先文法。

G[S]:S→iBtS|iBtSeS|a B→b

3.5.16 文法G[]不是LL(l)的,请说明理由,并给出其等价的LL(1)文法。 G[]:

→i=e

3.5.17 已知文法G[A]为: A→aAB1|a B→Bb|d

(I)试给出与G[A]等价的LL(I)文法G’[A]。 (2)构造G’[A]的预测分析表。 (3)给出输入串aadl#分析过程。

3.5.18 将G[V]改造为LL(1)文法。 G[V]: V→N|N[E] E→V|V+E N→i

3.5.19 有文法G[S]: S-BA A--BS|d B~aA|bS|c

(I)证明文法G是LL(I)文法。 (2)构造LL(1)分析表。

(3)写出句子adccd的分析过程。

3.5.20 考虑文法G[T]:

T→T*F|F F→F↑P|P P→(T)|i

(1)证明T*P↑(T*F)是该文法的一个句型,并指出其直接短语和句柄。 (2)构造文法G的优先关系表(要求写出步骤)。

3.5.21 给出算符优先文法的分析算法。

3.5.22 文法G的产生式集为:S→S+S|S*S|i|(s),对于输入串i+i*i;

(1)给出一个推导; (2)画出一棵语法树;

(3)文法G是否是二义性的,请证明你的结论。

3.5.23 已给文法G[E]:

E→EOE|(E)|i 0→+|*

试将其改造为可进行不带回溯的自顶向下分析的文法,并给出其相应的LL(1)分析表。

3.5.24 考虑文法G(S):

S→(T)|a+S|a T→T,S|S

消除文法的左递归及提取公共左因子,然后,对每个非终结符,写出不带回溯的递归子程序。

3.5.25 有映射程序设计语言if-the-else语句的文法G[S]: S→iEtSeS|EtS|a

E→b 其中,else遵从最近匹配原则。

(1)试改造文法,并为之构造LL(1)分析表。 (2)利用构造的分析表分析句子ibtibtaea,要求给出分析过程中每一步的分析栈和输入串的变化以及输出信息。

3.5.26 下述文法描述了C语言整数变量的声明语句: D→TL T→int|long|short L→id|L,id

(1)改造上述文法,使其接受相同的输入序列,但文法是右递归的。 (2)分别用上述文法和改造文法,为输入序列int a,b,c构造分析树。

3.5.27 设有文法G[W]:

W→AO

A→AO|W1|0

请改写文法,消除规则左递归和文法左递归。

3.5.28 文法G[P]及相应翻译方案为:

P→bQb {print:”1”} Q→cR {print:”2”} Q→a {print:”3”} R→Qad (print:”4”}

(1)该文法是不是算符优先文法,请构造算符优先关系表证实之。 (2)输入串为bcccaadadadb时,该翻译方案的输出是什么。

3.5.29 设有文法G[S]: S→SAS|b A→bSb|b

试构造一个与其等价的算符文法。

3.5.30 在算符优先分析法中,为什么要在找到最左素短语的尾时,才返回来确定其对应的头,能否按扫描顺序先找到头后找到对应的尾,为什么?

3.5.31 试证明在算符文法中,任何句型都不包含两个相邻的非终结符。

3.5.32假定文法包含产生式A→α,α∈V*(V是文法的词汇表,由终结符和非终结符组成的集合),证明:如果FIRST(α)∩FOLLOW(A)≠φ,则该文法不是LL(1)文法。

3.5.33 给出文法G1:

S→aSb|P A→bPc|bQc B→Qa|a

(1)它是Chomsky哪一型文法? (2)它生成的语言是什么?

(3)它是不是算符优先文法?请构造算符优先关系表证实之。

(4)请证实所有①左递归文法②有公共左因子的文法均不是LL(1)文法。 (5)文法G1消除左递归、提取公共左因子后是不是LL (1)文法?请证实。

3.5.34 简答题

(1)什么是文法的二义性?二义性问题的不可判定指的是什么? (2)在规范句型中,句柄以右的符号有什么特征?为什么?

3.5.35 写正规文法G,它产生的语言是L(G)={ anibncp|m,n,p≥0}