【编译原理

2024-05-02 13:00| 来源: 网络整理| 查看: 265

目录考点一：文法，推导 1.按指定类型，给出语言的文法。解： 2．构造一文法，使其描述的语言L = {ω |ω ∈ (a, b)*，且ω中含有相同个数的a和b}。解：考点二：最左推导，最右推导 3．令文法G[N]为解：考点三：语法树，二义文法 4.已知文法 G[S] 为 S→aSb|Sb|b，试证明文法 G[S] 为二义文法。解： 5.已知文法 G[S] 为 S→SaS|ε，试证明文法 G[S]为二义文法。解： 6．已知文法G[S]: S→aSbS|bSaS|ε 证明： 7．设有文法G[S]: 解考点四：短语，直接短语，句柄，素短语 8．对于文法G[E]: 解： 9．设有文法G[E]: 解：考点五：消除左递归，提取公共左因子 10．已知文法G(S)：解： 11.下述文法描述了c语言整数变量的声明语句： 12.考虑文法 13.G[A] 题4 考点一：文法，推导 1.按指定类型，给出语言的文法。

(1) L={ai bj|j ＞i≥0} 的上下文无关文法； (2) 字母表 Σ={a,b} 上的同时只有奇数个 a 和奇数个 b 的所有串的集合的正规文法； (3) 由相同个数 a 和 b 组成句子的无二义文法。

解：

(1) 由 L={ai bj|j ＞i≥0} 知，所求该语言对应的上下文无关文法首先应有 S→aSb 型产生式，以保证 b 的个数不少于 a 的个数；其次，还需有 S→Sb 或 S→b 型的产生式，用以保证 b 的个数多于 a 的个数。因此，所求上下文无关文法 G[S]为 G[S] ：S→aSb|Sb|b (2) 为了构造字母表 Σ={a,b} 上同时只有奇数个 a 和奇数个 b 的所有串集合的正规式，我们画出如图 3-3 所示的 DFA，即由开始符 S 出发，经过奇数个 a 到达状态 A，或经过奇数个 b 到达状态 B；而由状态 A 出发，经过奇数个 b 到达状态 C(终态 )；同样，由状态 B 出发经过奇数个 a 到达终态 C。由图 3-3 可直接得到正规文法 G[S]如下： G[S] ：S→ aA|bB A→aS|bC|b B→bS|aC|a C→bA|aB|ε (3) 我们用一个非终结符 A 代表一个 a(即有 A →a)，用一个非终结符 B 代表一个 b(即有 B→ b)；为了保证 a 和 b 的个数相同，则在出现一个 a 时应相应地出现一个 B，出现一个 b 时则相应出现一个 A 。假定已推导出 bA ，如果下一步要推导出连续两个 b 时，则应有 bAbbAA 。也即为了保证 b 和 A 的个数一致，应有 A→bAA ；同理有 B→aBB。此外，为了保证递归地推出所要求的 ab 串，应有 S→aBS 和 S→bAS。由此得到无二义文法 G[S] 为 G[S] ：S→aBS|bAS|ε A→bAA|a B→aBB|b

2．构造一文法，使其描述的语言L = {ω |ω ∈ (a, b)*，且ω中含有相同个数的a和b}。解： S→ ε| aA|bB A→ b| bS| aAA B→ a| aS| bBB 考点二：最左推导，最右推导 3．令文法G[N]为 G[N]: N→D|ND D→0|1|2|3|4|5|6|7|8|9

给出句子568的最左、最右推导。

解：

最左推导：N => ND=> NDD=> DDD=> 5DD=> 56D=> 568 最右推导：N => ND => N8=> ND8=> N68=> D68=> 568

考点三：语法树，二义文法 4.已知文法 G[S] 为 S→aSb|Sb|b，试证明文法 G[S] 为二义文法。解：

由文法 G[S] ：S→ aSb|Sb|b，对句子 aabbbb 可对应如图 3-1 所示的两棵语法树。因此，文法 G[S] 为二义文法 (对句子 abbb 也可画出两棵不同语法树 )。

5.已知文法 G[S] 为 S→SaS|ε，试证明文法 G[S]为二义文法。解：

由文法 G[S] ：S→ SaS|ε，句子 aa 的语法树如图 3-2 所示由图 3-2 可知，文法 G[S]为二义文法。

6．已知文法G[S]: S→aSbS|bSaS|ε 试证明G[S]是二义文法证明：

该文法产生的语言是a的个数和b的个数相等的串的集合。该文法二义，

例如句子abab有两种不同的最左推导。

S=> aSbS=> abS=> abaSbS=> ababS=> abab S=> aSbS=> abSaSbS=> abaSbS=> ababS=> abab 7．设有文法G[S]:

S→S*S|S+S|(S)|i 该文法是否为二义文法,并说明理由？

解

该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图所示。

考点四：短语，直接短语，句柄，素短语 8．对于文法G[E]: G[E]:E→E+T | T T→T+P | P P→(E) | i 写出句型P+T+(E+i)的所有短语、直接短语、句柄。解：

短语：P、P+T、i、E+i、(E+i )、P+T+(E+i )；直接短语：P、i；句柄：P；

9．设有文法G[E]: 解：

考点五：消除左递归，提取公共左因子 10．已知文法G(S)： S→S*aP| aP| *aP P→+aP| +a

将文法G(S)改写为确定的文法G’(S)；

解：原式消除左递归后 A->Aa|B A—>BA’ A‘—>aA’|ε 原式消除公共左因子后 A->aB1|aB2 A—>aA’ A‘—>B1|B2

1）消除左递归，文法变为：

S→aPS’| *aPS’ S’→ *aPS’ | ε P→+aP| +a

2）提取公共左因子，文法变为G’(S)：

S→aPS’| *aPS’ S’→ *aPS’ |ε P→+aP’ P’→P| ε 11.下述文法描述了c语言整数变量的声明语句：

（1）查看这个文法有没有不确定因素：公共左因子，左递归

（2）

12.考虑文法

13.G[A]

（1）第一步：消除公共左因子第二部：绘制表格求first,follow集，判断是否是LL(1)

第三步：判定有或的产生式（2）构造分析表 (3)描述分析过程

栈输入串动作 #A aadl# A->aA’ #A’a aadl# 匹配 #A’ adl# A‘->ABl #lBA adl# A->aA’ #lBA’a adl# 匹配 #lBA’ dl# A’->null #lB dl# B->dB’ #lB’d dl# 匹配 #lB’ l# B’->null #l l# 匹配 # # 分析成功题4

V->NV' V->NULL|[E] E->VE' E'->NULL|+E N->i FIRST([E])^FOLLOW(V')=NULL FIRST(+E)^FOLLOW(E')=NULL 因为都为空集，所是LL1文法

【本文地址】

【编译原理

【编译原理

今日新闻

推荐新闻