构造一个最简DFA, 接受$\Sigma=\{a, b\}$上所有满足如下条件的字符串: 以 $b$结尾且不含连续的两个$a$, 并给出相应的正规文法和正规式
DFA:
正规文法：
$$ \begin{align} S&\to aA \\ S&\to bB \\ A&\to bB \\ B&\to aA \\ B&\to bB \\ B&\to\epsilon \end{align} $$
正则表达式：
$$ (ab|b)^+, 或者(ab|b)(ab|b)^* $$
推导过程:
$$ \left. \begin{matrix} \left. \begin{matrix} S \to aA | bB \\ A \to bB \end{matrix} \right\} \Rightarrow S \to abB|bB \\ \left. \begin{matrix} B \to aA|bB \\ A \to bB \end{matrix} \right\} \Rightarrow \left. \begin{matrix} B\to abB|bB \\ B \to \epsilon \end{matrix} \right\} \Rightarrow B\to (ab)^|(b)^ \Rightarrow B \to (ab|b)^* \end{matrix} \right\} \Rightarrow S\to (ab|b)(ab|b)^* $$
$$ \begin{align} &B\to aA|bB \\ &B\to abB|bB \\ &B\to (ab)^|(b)^ \\ &B\to(ab|b)^* \\ &S\to abB|bB \\ &S\to (ab|b)(ab|b)^* \end{align} $$
有一台自动售货机, 接收 1 分和 2 分硬币, 出售 3 分一块的硬糖. 顾客每次向机器中投放一个硬币, 当投放硬币额≥3分时, 机器会给顾客一块硬糖(只给硬糖不着钱).
<aside> 💡 存在争议：如果同时投入2个2分，多出来的1分如何处理？
- 不作处理
- 计入多出来的1分，接下来只需要投入2分就会给出另一颗糖 思路二以理解2解题
</aside>
- 写出售货机售糖的正规表达式
- 构造识别上述正规表达式的最简 DFA
- 思路一: 穷举, 然后写出正则表达式, 绘制 DFA
- 思路二:
设有文法
$$ \begin{aligned} G[E]:\quad &E\to ETE | (E)|i \\&T\to+|*\end{aligned} $$
- 证明 $G[E]$是一个非 LL(1) 文法
- 把 $G[E]$等价改为LL(1)文法 $G'[E]$, 并构造其预测分析表
- 对改造后的文法编写递归下降分析程序
- 写出 $i* (i + i)$的预测分析过程
-
由$E\to ETE$可看出存在左递归，故不是$LL(1)$文法
-
消除左递归：
$$ \begin{align} &E\to (E)E'|iE' \\ &E'\to TEE'|\epsilon \\ &T\to +|* \end{align} $$
预测分析表：
| $($ | $)$ | $i$ | $+$ | $*$ | $\#$ | |
|---|---|---|---|---|---|---|
| $E$ | $\to (E)E'$ | $\to iE'$ | ||||
| $E'$ | $\to TEE'$ | $\to TEE'$ | $E\to \epsilon$ | |||
| $T$ | $\to +$ | $\to *$ |
- 分析过程如下：
| 步骤 | 分析栈 | 剩余输入串 | 所用产生式 |
|---|---|---|---|
| 1 | $\#E$ | $i*(i+i)\#$ | $E\to iE'$ |
| 2 | $\#E'i$ | $i*(i+i)\#$ | 匹配 |
| 3 | $\#E'$ | $*(i+i)\#$ | $E'\to TEE'$ |
| 4 | $\#E'ET$ | $*(i+i)\#$ | $T\to *$ |
| 5 | $\#E'E*$ | $*(i+i)\#$ | 匹配 |
| 6 | $\#E'E$ | $(i+i)\#$ | $E\to (E)E'$ |
| 7 | $\#E'E')E($ | $(i+i)\#$ | 匹配 |
| 8 | $\#E'E')E$ | $i+i)\#$ | $E\to iE'$ |
| 9 | $\#E'E')E'i$ | $i+i)\#$ | 匹配 |
| 10 | $\#E'E')E'$ | $+i)\#$ | $E'\to TEE'$ |
| 11 | $\#E'E')E'ET$ | $+i)\#$ | $T\to +$ |
| 12 | $\#E'E')E'E+$ | $+i)\#$ | 匹配 |
| 13 | $\#E'E')E'E$ | $i)\#$ | $E\to iE'$ |
| 14 | $\#E'E')E'E'i$ | $i)\#$ | 匹配 |
| 15 | $\#E'E')E'E'$ | $)\#$ | $E'\to\epsilon$ |
| 16 | $\#E'E')E'$ | $)\#$ | $E'\to\epsilon$ |
| 17 | $\#E'E')$ | $)\#$ | 匹配 |
| 18 | $\#E'E'$ | $\#$ | $E'\to\epsilon$ |
| 19 | $\#E'$ | $\#$ | $E'\to\epsilon$ |
| 20 | $\#$ | $\#$ | 接受 |
对以下中间代码序列
$$ \begin{align} 1\qquad &A=1 \\ 2\qquad &B=2 \\ 3\qquad &C=3 \\ 4\qquad &A=A+B \\ 5\qquad &if\ B>C\ goto\ (10) \\ 6\qquad &B=B+1 \\ 7\qquad &C=10 \\ 8\qquad &goto\ (4) \\ 9\qquad &C=C+1 \\ 10\qquad &write(B) \\ 11\qquad &write(C) \end{align} $$
- 把该中间代码序列划分为基本块, 并画出程序控制流图
- 求出题 1 程序流程图中各节点的支配节点集, 所有的回边和循环
-
划分基本块:
划分的方法: ！！！❌❌❌❌❌
- 条件跳转语句下的第一句是首句
2. 无条件跳转语句下的第一句是首句 - 跳转的目的语句是首句
- 程序的第一句是首句
-
第一块:
$$ A=1 \\ B=2 \\ C=3 $$
-
第二块:
$$ A =A+B\\ if\ B>C\ goto\ (10) $$
-
第三块:
$$ B=B+1 \\ C=10 \\ goto\ (4) $$
-
第四块:$$ C=C+1 $$
-
第五块:
$$ write(B) \\ write(C) $$
- 条件跳转语句下的第一句是首句
-
程序流图:
写出下列语句的三地址中间代码(四元式序列):
$$ \begin{align} 1\qquad&if\ A<C\ goto\ 3\\ 2\qquad&goto\ 17\\ 3\qquad&if\ B<D\ goto\ 5\\ 4\qquad&goto\ 17\\ 5\qquad&if\ A\ge1\ goto\ 9\\ 6\qquad&goto\ 7\\ 7\qquad&if\ false\ goto\ 9\\ 8\qquad&goto\ 12\\ 9\qquad& T_1 := C + 1 \\ 10\qquad& C := T_1 \\ 11\qquad& goto\ 1\\ 12\qquad&if\ A\le D\ goto\ 14\\ 13\qquad&goto\ 1\\ 14\qquad&T_2 := A + 2 \\ 15\qquad&A:=T_2 \\ 16\qquad&goto\ 12\\ 17\qquad& \end{align} $$
设采用自底向上的移进-归约语法分析, 属性文法$G[A]$如下:
$$ \begin{aligned} (0)\qquad&S'\to A\qquad & \{\ print\ "0"\ \} \\ (1)\qquad&A\to aB\qquad & \{\ print\ "1"\ \} \\ (2)\qquad&A\to \epsilon \qquad & \{\ print\ "2"\ \} \\ (3)\qquad&B\to Ab\qquad & \{\ print\ "3"\ \} \\ \end{aligned} $$
- 输入为 $aabb$时, 打印的符号串是什么?
- 写出句子 $aabb$的语法制导分析过程
-
$S'\to A \to aB \to aAb \to aaBb \to aaAbb \to aabb$
所以打印的符号串为 231310
已知一个 SLR(1) 文法的分析表如下所示: