Commits

Weisi Dai committed 2aef2e5

lots of add

Comments (0)

Files changed (8)

+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{计算机组成原理}
+\def\homeworkid{5}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{multirow}
+\usepackage{graphicx}
+\usepackage[
+    %colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+\usepackage{pstricks}
+\usepackage{pst-node}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{4.14}
+
+    \problem{某8位微型计算机地址码为18位, 若使用4K$\times$4位的RAM芯片组成模块板结构的存储器, 试问:
+        \begin{enumerate}[(1)]
+            \item 该机所允许的最大主存空间是多少?
+            \item 若每个模块板为32K$\times$8位, 共需几个模块板?
+            \item 每个模块板内共有几片RAM芯片?
+            \item 共有多少片RAM?
+            \item CPU如何选择各模块板?
+        \end{enumerate}
+    }
+
+\begin{enumerate}[(1)]
+    \item 该机允许的最大主存空间为$2^{18}\mathrm K\times 8$B$=2$MB.
+    \item 共需要$\frac{256\mathrm K\times 8}{32\mathrm K\times 8}=8$个模块板.
+    \item 每个模块板内有$\frac{32\mathrm K\times 8\mathrm B}{4\mathrm K\times 4\mathrm B}=16$片RAM芯片.
+    \item 共有$16\times 8=128$片RAM.
+    \item 将地址线的低15位和8个模块板的地址线相连, 将剩余的3个高位地址线通过译码器和8个模块板的片选信号端相连.
+\end{enumerate}
+
+\section*{4.15}
+
+    \problem{设CPU共有16根地址线, 8根数据线, 并用$\overline{\rm MREQ}$(低电平有效)作访存控制信号, R/$\overline{\rm W}$作读/写命令信号(高电平为读, 低电平为写). 现有这些存储芯片: ROM(2K$\times$8位, 4K$\times$4位, 8K$\times$8位), RAM(1K$\times$4位, 2K$\times$8位, 4K$\times$8位)及74138译码器和其他门电路(门电路自定).
+
+    试从上述规格中选用合适的芯片, 画出CPU和存储芯片的连接图, 要求如下:
+
+    \begin{enumerate}[(1)]
+        \item 最小4K地址为系统程序区, 4096---16383地址范围为用户程序区.
+        \item 指出选用的芯片类型和数量.
+        \item 详细画出片选逻辑.
+    \end{enumerate}
+
+    }
+
+\begin{enumerate}[(1)]
+    \item 地址空间分配如下:
+
+            \begin{tabular}[h!]{c|c|} \cline{2-2}
+                0 --- 4095 & 4K ROM \\ \cline{2-2}
+                4096 --- 8191 & 4K SRAM \\ \cline{2-2}
+                8192 --- 12287 & 4K SRAM \\ \cline{2-2}
+                12288 --- 16383 & 4K SRAM \\ \cline{2-2}
+                $\cdots$ & 4K SRAM \\ \cline{2-2}
+                $\cdots$ & $\cdots$ \\ \cline{2-2}
+                $\cdots$ & 4K SRAM \\ \cline{2-2}
+                61440 ---  65535 & 4K SRAM \\ \cline{2-2}
+            \end{tabular}
+
+    \item 选用2片4K$\times$4位的ROM, 3片4K$\times$8位的RAM.
+
+    \item \phantom{x}
+
+        \vskip 5cm
+
+        \phantom{x}
+
+\end{enumerate}
+
+\section*{4.22}
+
+    采用多体交叉存取技术:
+
+    \vskip 7cm
+
+\end{document}
+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{计算机组成原理}
+\def\homeworkid{6}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{multirow}
+\usepackage{graphicx}
+\usepackage[
+    %colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+\usepackage{pstricks}
+\usepackage{pst-node}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{4.24}
+
+    CPU启动存储体以访问第64个字的时间$t=\frac{63}{4}T$, 完成一次存取需要$T$的时间, 访问64个字需要$\frac{63}{4}T+T=\frac{67}{4}T$.
+
+\section*{4.37}
+
+    \vskip 5cm
+
+\section*{4.38}
+
+    \begin{enumerate}[(1)]
+        \item 去掉2个保护面, 则还有$6\times 2-2=10$个存储面可用.
+        \item 有效存储区域: $\frac{33-22}{2}=5.5$cm, \\
+            柱面数: $5.5\textrm{cm}\times40\textrm{道/cm}=220$道.
+        \item 最内圈道周长: $22\Pi\approx 69.08$cm \\
+            道容量: $400\textrm{b/cm}\times 69.08\textrm{cm}=3\ 454\textrm{B}$ \\
+            面容量: $3\ 454\textrm{B}\times 220\textrm{道}=759\ 880\textrm{B}$ \\
+            盘组总容量: $759\ 880\textrm{B}\times 10\textrm{面}=7\ 598\ 800\textrm{B}$.
+        \item 转速: $3\ 600\textrm{r}/60\textrm{s}=60\textrm{r/s}$ \\
+            数据传输率: $3\ 454\textrm{B}\times 60\textrm{r/s}=207\ 240\textrm{B/s}$.
+    \end{enumerate}
+
+\section*{4.39}
+
+    \begin{enumerate}[(1)]
+        \item 存储容量: $275\textrm{道}\times 12\ 277\textrm{B/道}\times 4\textrm{面}=13\ 516\ 800\textrm{B}$.
+        \item 最高位密度: $\frac{12288\mathrm{B}}{230\Pi}=17\textrm{B/mm}=136\textrm{b/mm}$, \\
+            最大磁道直径: $230\textrm{mm}+285\textrm{道}/5\textrm{道}\times 2=340\textrm{mm}$, \\
+            最低位密度: $12\ 288\textrm{B}/340\Pi=11\textrm{B/mm}=92\textrm{b/mm}$. 
+        \item 磁盘数据传输率: $12\ 288\textrm{B}\times 3\ 000\textrm{r/min}=12\ 288\times 50\textrm{r/s}=614\ 400\textrm{B/s}$.
+        \item 平均等待时间: $(50\times 2)^{-1}=10\textrm{ms}$.
+    \end{enumerate}
+
+\section*{4.42}
+
+    有效信息$M(x)=1001=x^3+1$. 由$G(x)=x^3+x+1$得知$k+1=4$, 即$k=3$.
+
+    将有效信息左移3位, 用$G(x)$模2除, 即$M(x)\cdot x^3=1001000=x^0+x^3$
+
+    \[\frac{M(x)\cdot x^3}{G(x)}=\frac{1001000}{1011}=1010+\frac{110}{1011}\]
+
+    $\therefore$CRC码是$M(x)\cdot x^3+R(x)=1001000+110=1001110$.
+
+
+\end{document}

compile_hw1.re.tex

+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{编译原理}
+\def\homeworkid{1}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage[
+    colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid\ 订正},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+\usepackage{pstricks}
+\usepackage{pst-node}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid\ \textbf{\underline{Revised}}\\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\newif\ifshoworig \showorigfalse
+
+\section*{3.6}
+
+    \problem{令$A$、$B$和$C$是任意正规式, 证明以下关系成立}
+
+    下面的证明要用到$A^m$这种表示法, 其中$m\in\mathbb{N}, A^m=A^{m-1}A$, 但$A^1=A$. $S^m=L(A^m)$.
+
+    \begin{enumerate}
+            %\ifshoworig
+        \item $A|A=A$ \\
+            \textsf{证}\quad
+            $\because L(A|A)=L(A)\cup L(A)=L(A)\therefore A|A=A \hfill \Box$
+
+        \item $(A^*)^*=A^*$\\
+            \textsf{证}\quad
+            $\because L( (A^*)^*)=(L(A^*))^*=\left( \left( L(A) \right)^* \right)^* \therefore L(A^*)=(L(A))^*$ \\
+            $1^\circ$ 先证 $x\in(A^*)^*\Rightarrow x\in A^*$.  令$S=L(A)$, 则命题变为 $x\in(S^*)^*\Rightarrow x\in S^*$. $\because x\in(S^*)^*$, $\therefore \exists m, x\in(S^*)^m$. 同理$\exists n, x\in(S^n)^m \therefore x\in S^{n\times m} \therefore x\in S^*$. \\
+            $2^\circ$ 再证 $x\in A^*\Rightarrow x\in(A^*)^*$. 令$S=L(A) \because x\in A^* \therefore \exists m, x\in S^m$. 令$n=1$, 则$x\in (S^n)^m \therefore x\in(A^*)^*$.\\
+            综上, 命题得证. \hfill $\Box$
+
+        \item $A^*=\varepsilon|AA^*$ \\
+            \textsf{证}\quad
+            $1^\circ$ 先证$x\in S^*\Rightarrow x\in \{\varepsilon\}\cup (SS^*)$. $\because x\in S^*, \exists m\in \mathbb{N}, x\in S^m$. 若$m=0$, 则$x\in S^0=\{\varepsilon\}\subseteq\{\varepsilon\}\cup(SS^*)$; 否则有$m\geqslant 1$, $x\in S^m=SS^{m-1}\subseteq\{\varepsilon\}\cup(SS^*)$.\\
+            $2^\circ$ 再证$x\in\{\varepsilon\}\cup(SS^*)\Rightarrow x\in S^*$. 若$x\in\{\varepsilon\}$, $x\in S_0\subseteq S^*$; 否则$x\in (SS^*)$, $\exists m\in \mathbb{N}, x\in SS^m=S^{m+1}\subseteq S^* \therefore x\in S^*$.\\
+            综上, 命题得证. \hfill $\Box$
+
+        \item $(AB)^*A=A(BA)^*$ \\
+            \textsf{证}\quad
+            $(AB)^*A$表达的正规式集合是连续的任意多个或零个$AB$串的后面接上$A$得到的正规式全体, $A(BA)^*$表达的正规式集合是连续的任意多个或零个$BA$串的前面加上$A$得到的正规式全体, 它们是相同的.
+            %\fi
+
+            \setcounter{enumi}{4}
+
+        \item $(A|B)^*=(A^*B^*)^*=(A^*|B^*)^*$ \\
+            \textsf{证}\quad
+            它们表达的正规式集合都是$A$和$B$串以任意数目和方式连接得到的正规式全体.
+
+        \item $A=b|aA\iff A=a^*b$
+    \end{enumerate}
+
+\section*{3.7}
+    
+    \problem{构造下列正规式相应的DFA}
+    \begin{enumerate}
+        \item $1(0|1)^*101$
+    \ifshoworig
+            \begin{center}
+                \begin{psmatrix}[colsep=1.5, rowsep=0.3]
+                    \phantom{x} & \pscirclebox{$q_0$} & \pscirclebox{$q_1$} & \pscirclebox{$q_2$} & \pscirclebox{$q_3$} & \pscirclebox[doubleline=true]{$q_4$} \\
+                     \ncline[doubleline=true]{->}{1,1}{1,2}
+                     \ncline{->}{1,2}{1,3}^{1}
+                     \nccircle{->}{1,3}{.5cm}^{0}
+                     \nccircle[angleA=180]{->}{1,3}{.5cm}_{1}
+                     \ncline{->}{1,3}{1,4}^{1}
+                     \ncline{->}{1,4}{1,5}^{0}
+                     \ncline{->}{1,5}{1,6}^{1}
+                 \end{psmatrix}
+            \end{center}
+            \fi
+        \item $1(1010^*|1(010)^*1)^*0$
+    \ifshoworig
+            \begin{center}
+                \begin{psmatrix}[colsep=1.5, rowsep=0.6]
+                    & & & \pscirclebox{$q_2$} & \pscirclebox{$q_3$} & \pscirclebox{$q_4$} \\
+                    \phantom{x} & \pscirclebox{$q_0$} & \pscirclebox{$q_1$} & & & & \pscirclebox[doubleline=true]{$q_9$}\\
+                    & & & \pscirclebox{$q_5$} & \pscirclebox{$q_8$} &  \\
+                    & & \pscirclebox{$q_6$} & & \pscirclebox{$q_7$} \\
+                    \ncline[doubleline=true]{->}{2,1}{2,2}
+                    \ncline{->}{2,2}{2,3}^1
+                    \ncline{->}{2,3}{1,4}^1
+                    \ncline{->}{1,4}{1,5}^0
+                    \ncline{->}{1,5}{1,6}^1
+                    \nccircle{->}{1,6}{.5cm}^0
+                    \ncline{->}{2,3}{3,4}_1
+                    \ncline{->}{3,4}{3,5}^1
+                    \ncline{->}{3,4}{4,3}^0
+                    \ncline{<-}{4,5}{4,3}_1
+                    \ncline{->}{4,5}{3,4}^0
+                    \ncdiag[angleA=270, angleB=270, linearc=.2]{->}{1,6}{1,4}\naput{1}
+                    \ncdiag[angleA=90, angleB=90, arm=.9, linearc=.2]{->}{3,5}{3,4}\naput{1}
+                    \ncline{->}{1,6}{2,7}^0
+                    \ncline{->}{3,5}{2,7}^0
+                 \end{psmatrix}
+            \end{center}
+            \fi
+
+        \item $0^*10^*10^*10^*$
+
+    \ifshoworig
+                \vskip 1cm\begin{center}
+                    \begin{psmatrix}[colsep=1.5, rowsep=0.6]
+                        \phantom{x} & \pscirclebox{$q_0$} & \pscirclebox{$q_1$} & \pscirclebox{$q_2$} & \pscirclebox[doubleline=true]{$q_3$} \\
+                        \ncline[doubleline=true]{->}{1,1}{1,2}
+                        \ncline{->}{1,2}{1,3}_1
+                        \ncline{->}{1,3}{1,4}_1
+                        \ncline{->}{1,4}{1,5}_1
+                        \nccircle{->}{1,2}{.5cm}^0
+                        \nccircle{->}{1,3}{.5cm}^0
+                        \nccircle{->}{1,4}{.5cm}^0
+                        \nccircle{->}{1,5}{.5cm}^0
+                     \end{psmatrix}
+                 \end{center}
+                 \fi
+
+        \item $(00|11)^*((01|10)(00|11)^*(01|10)(00|11)^*)^*$
+    \ifshoworig
+                \vskip 2cm\begin{center}
+                    \begin{psmatrix}[colsep=1.5, rowsep=0.6]
+                        & \pscirclebox{$q_1$} & \pscirclebox{$q_4$} & \pscirclebox{$q_7$} & \pscirclebox{$q_9$} & & \pscirclebox{$q_{12}$}\\
+                        \phantom{x} & \pscirclebox[doubleline=true]{$q_0$} & & \pscirclebox{$q_6$} & & \pscirclebox[doubleline=true]{$q_{11}$} \\
+                        & \pscirclebox{$q_2$} & \pscirclebox{$q_5$} & \pscirclebox{$q_8$} & \pscirclebox{$q_{10}$} & & \pscirclebox{$q_{13}$} \\
+                        \ncline[doubleline=true]{->}{2,1}{2,2}
+                        \ncarc{->}{2,2}{1,2}\naput0
+                        \ncarc{->}{2,2}{3,2}\naput1
+                        \ncarc{->}{1,2}{2,2}\naput0
+                        \ncarc{->}{3,2}{2,2}\naput1
+                        \ncline{->}{2,2}{1,3}_0
+                        \ncline{->}{2,2}{3,3}_1
+                        \ncline{->}{1,3}{2,4}_1
+                        \ncline{->}{3,3}{2,4}_0
+                        \ncarc{->}{2,4}{1,4}\naput0
+                        \ncarc{->}{1,4}{2,4}\naput0
+                        \ncarc{->}{2,4}{3,4}\nbput1
+                        \ncarc{->}{3,4}{2,4}\naput1
+                        \ncline{->}{2,4}{1,5}_0
+                        \ncline{->}{2,4}{3,5}_1
+                        \ncline{->}{1,5}{2,6}_1
+                        \ncline{->}{3,5}{2,6}_0
+                        \ncarc{->}{2,6}{1,7}\naput0
+                        \ncarc{->}{1,7}{2,6}\naput0
+                        \ncarc{->}{2,6}{3,7}\naput1
+                        \ncarc{->}{3,7}{2,6}\naput1
+                        \ncdiag[angleA=90, angleB=90, armA=2, armB=.6, linearc=.2]{->}{2,6}{1,3}\nbput0
+                        \ncdiag[angleA=270, angleB=270, armA=2, armB=.6, linearc=.2]{->}{2,6}{3,3}\nbput1
+                     \end{psmatrix}
+                 \end{center}
+                 \fi
+    \end{enumerate}
+
+\section*{3.8}
+
+    \problem{给出下列正规表达式}
+    
+    \begin{enumerate}[(1)]
+            \ifshoworig
+        \item 以01结尾的二进制整数串: $(0|1)^*01$
+            \fi
+        \setcounter{enumi}{3}
+        \item 英文字母组成的所有符号串, 要求符号串中的字母依照字母序排列: \\(AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz)\\(AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz)$^*$
+    \end{enumerate}
+
+\section*{3.9}
+
+    \problem{对下列情况给出DFA及正规表达式: 
+        \begin{enumerate}[(1)]
+            \item $\{0,1\}$上的含有字串010的所有串;
+            \item $\{0,1\}$上不含子串010的所有串;
+        \end{enumerate}
+    }
+    \ifshoworig
+    \begin{enumerate}[(1)]
+        \item 正规表达式为(0|1)$^*$010(0|1)$^*$, 对应的DFA状态转换图为
+            \vskip 1.5cm\begin{center}
+                \begin{psmatrix}[colsep=1.5, rowsep=0.3]
+                    \phantom{x} & \pscirclebox{$q_0$} & \pscirclebox{$q_1$} & \pscirclebox{$q_2$} & \pscirclebox[doubleline=true]{$q_3$} \\
+                    \ncline[doubleline=true]{->}{1,1}{1,2}
+                    \ncline{->}{1,2}{1,3}^0
+                    \ncline{->}{1,3}{1,4}^1
+                    \ncline{->}{1,4}{1,5}^0
+                    \nccircle[angleA=180]{->}{1,2}{.5cm}^1
+                    \nccircle[angleA=0]{->}{1,2}{.5cm}^0
+                    \nccircle[angleA=0]{->}{1,5}{.5cm}^0
+                    \nccircle[angleA=180]{->}{1,5}{.5cm}^1
+                 \end{psmatrix}
+            \end{center}
+        \item 正规表达式为(0|00|01|1$^*$|10)(000|001|011|100|101|110|1$^*$)$^*$, 对应的DFA状态转换图为
+            \vskip 1cm\begin{center}
+                \begin{psmatrix}[colsep=1.5, rowsep=0.3]
+                    \phantom{x} & \pscirclebox[doubleline=true]{$q_0$} & \pscirclebox[doubleline=true]{$q_1$} & \pscirclebox[doubleline=true]{$q_2$} \\
+                    \ncline[doubleline=true]{->}{1,1}{1,2}
+                    \ncarc{->}{1,2}{1,3}^0
+                    \ncline{->}{1,3}{1,4}_1
+                    \ncarc{->}{1,3}{1,2}_0
+                    \nccircle[angleA=180]{->}{1,2}{.5cm}^1
+                    \ncdiag[angle=90,arm=.6, linearc=.2]{->}{1,4}{1,2}\naput1
+                 \end{psmatrix}
+            \end{center}
+    \end{enumerate}
+    \fi
+\section*{3.12}
+
+    \problem{将图3.18的(a)和(b)分别确定化和最小化}
+    \ifshoworig
+    \begin{enumerate}[(a)]
+        \item 构造状态转换表
+            \begin{center}\begin{tabular}{ccc}\toprule
+                $I$ & $I_a$ & $I_b$ \\ \midrule
+                $\{0\}$ & $\{0,1\}$ & $\{1\}$ \\
+                $\{0,1\}$ & $\{0,1\}$ & $\{1\}$ \\
+                $\{1\}$ & $\{0\}$ & --- \\ \bottomrule
+            \end{tabular}\end{center}
+            最小化后得到如下状态转换表
+            \begin{center}\begin{tabular}{ccc}\toprule
+                $I$ & $a$ & $b$ \\ \midrule
+                0 & 0 & 1 \\
+                1 & 0 & -- \\ \bottomrule
+            \end{tabular}\end{center}
+    \end{enumerate}
+    \fi
+
+    \ifshoworig
+\section*{3.14}
+
+    \problem{构造一个DFA, 它接受$\Sigma=\{0,1\}$上所有满足如下条件的字符串: 每个1都有0直接跟在右边}
+
+    \vskip 1.5cm\begin{center}
+        \begin{psmatrix}[colsep=1.5, rowsep=0.3]
+            \phantom{x} & \pscirclebox[doubleline=true]{$q_0$} & \pscirclebox{$q_1$} \\
+            \ncline[doubleline=true]{->}{1,1}{1,2}
+            \ncarc{->}{1,2}{1,3}^1
+            \ncarc{->}{1,3}{1,2}_0
+            \nccircle{->}{1,2}{.5cm}^0
+         \end{psmatrix}
+    \end{center}
+    \fi
+\end{document}
     消去$G_1$的左递归, 然后对每个非终结符, 写出不带回溯的递归子程序.
     }
 
+    \[S\to a|\wedge|(T)\]
+    \[T\to ST'\]
+    \[T'\to ,ST'|\varepsilon\]
+
+    \begin{verbatim}
+procedure S;
+begin
+    if s='a' or s='^' then
+        advance()
+    else
+        if ch='c' then
+            begin
+                advance();
+                T;
+                if ch=')' then
+                    advance()
+                else
+                    error()
+            end
+        else
+            error();
+end;
+
+procedure T;
+begin
+    S;
+    T';
+end;
+
+procedure T';
+begin
+    if ch=',' then
+        begin
+            advance()
+            S;
+            T';
+        end;
+end;\end{verbatim}
+
+    %FIRST$(S)=\{a,\wedge,(\}$, FIRST$(T)=\{a,\wedge,(\}$, FIRST$(T')=\{,\ ,\varepsilon\}$, FOLLOW$(S)=\{),\,\,\#\}$, FOLLOW$(T)=\{)\}$, FOLLOW$(T')=\{)\}$.
+
+
 \section*{2}
 
     \problem{对下面的文法$G$:
     \end{enumerate}
     }
 
+    \begin{enumerate}
+        \item FIRST$(E)=\{(,a,b,\wedge\}$, FIRST$(E')=\{+,\varepsilon\}$, FIRST$(T)=\{(,a,b,\varepsilon\}$, FIRST$(T')=\{(,a,b,\wedge,\varepsilon\}$, FIRST$(F)=\{(,a,b,\wedge\}$, FIRST$(F')=\{*,\varepsilon\}$, FIRST$(P)=\{(,a,b,\wedge\}$, FOLLOW$(E)=\{\#,)\}$, FOLLOW$(E')=\{\#,)\}$, FOLLOW$(T)=\{+,),\#\}$, FOLLOW$(T')=\{+,),\#\}$, FOLLOW$(F)=\{(,a,b,\wedge,+,),\#\}$, FOLLOW$(F')=\{(,a,b,\wedge,+,),\#\}$, FOLLOW$(P)=\{(,*,a,b,\wedge,+,),\#\}$, 
+            \setcounter{enumi}{2}
+        \item 预测分析表
+
+            \begin{center} \small
+                    \begin{tabular}[h!]{ccccccccc} \toprule
+                        & $+$ & $*$ & $($ & $)$ & $a$ & $b$ & $\wedge$ & $\#$ \\ \midrule
+                        $E$ & & & $E\to TE'$ & & $E\to TE'$ & $E\to TE'$ & $E\to TE'$ \\
+                        $E'$ & $E'\to+E$ & & & $E'\to\varepsilon$ & & & & $E'\to\varepsilon$ \\
+                        $T$ & & & $T\to FT'$ & & $T\to FT'$ & $T\to FT'$ & $T\to FT'$ \\
+                        $T'$ & $T'\to \varepsilon$ & & $T'\to T$ & $T'\to \varepsilon$ & $T'\to T$ & $T'\to T$ & $T'\to T$ & $T'\to \varepsilon$ \\
+                        $F$ & & & $F\to PF'$ & & $F\to PF'$ & $F\to PF'$ & $F\to PF'$ \\
+                        $F'$ & $F'\to \varepsilon$ & $F'\to *F'$ & $F'\to \varepsilon$ & $F'\to \varepsilon$ & $F'\to \varepsilon$ & $F'\to \varepsilon$ & $F'\to \varepsilon$ & $F'\to \varepsilon$ \\
+                        $P$ & & & $P\to (E)$ & & $P\to a$ & $P\to b$ & $P\to \wedge$ \\ \bottomrule
+                    \end{tabular}
+            \end{center}
+            
+    \end{enumerate}
+
 \section*{3}
 
     \problem{下面文法中, 哪些是LL(1)的, 说明理由.
 
     }
 
+    \begin{enumerate}
+        \item 是LL(1)语法, 它满足:
+            \begin{enumerate}[(1)]
+                \item 文法不含左递归,
+                \item 对于文法中每一个$A\in V_N$, 各个产生式的候选首符号集合两两不相交, 即若有
+                    \[A\to \alpha_1|\alpha_2|\cdots|\alpha_n\]
+                    则有FIRST$(\alpha_i)\cap$FOLLOW$(\alpha_k)=\emptyset$, $i\not= j$
+                \item 对于文法中的每个$A\in V_N$, 若它存在某个候选首符号集合包含$\varepsilon$, 则有\\
+                    FIRST$(A)\cap$FOLLOW$(A)=\emptyset$.
+            \end{enumerate}
+                \setcounter{enumi}{2}
+        \item 不是LL(1)语法, 它满足:
+            \begin{enumerate}[(1)]
+                \item 文法不含左递归,
+                \item 对于文法中每一个$A\in V_N$, 各个产生式的候选首符号集合两两不相交, 即若有
+                    \[A\to \alpha_1|\alpha_2|\cdots|\alpha_n\]
+                    则有FIRST$(\alpha_i)\cap$FOLLOW$(\alpha_k)=\emptyset$, $i\not= j$
+            \end{enumerate}
+
+            它的集合$A$, $B$不满足:
+                \setcounter{enumii}{2}
+            \begin{enumerate}[(1)]
+                \item 对于文法中的每个$A\in V_N$, 若它存在某个候选首符号集合包含$\varepsilon$, 则有\\
+                    FIRST$(A)\cap$FOLLOW$(A)=\emptyset$.
+            \end{enumerate}
+    \end{enumerate}
+\iffalse
 \section*{4}
 
     \problem{对以下文法:
     \end{enumerate}
 
     }
-
 \section*{5}
 
 \section*{补充题}
 
     \end{enumerate}
 
+\fi
 
 \end{document}
+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{编译原理}
+\def\homeworkid{4}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage{multicol}
+\usepackage[
+    colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+\usepackage{pstricks}
+\usepackage{pst-node}
+\newcommand\eqdot{=\hskip -.8em\cdot\ }
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{1}
+
+    $\because E\Rightarrow E+T\Rightarrow E+T*F, \therefore E+T*F$是文法$G$的一个句型, 其中短语有$T*F, E+T*F$, 直接短语是$T*F$, 句柄是$T*F$.
+
+\section*{2}
+
+\begin{enumerate}[(1)]
+    \item \begin{itemize}
+            \item $(a,(a,a))$的最左推导:\\
+                $S\Rightarrow (T)\Rightarrow(T,S)\Rightarrow (S,S)\Rightarrow(a,S)\Rightarrow(a,(T))\Rightarrow(a,(T,S))\Rightarrow(a,(S,S))\Rightarrow(a,(a,S))\Rightarrow(a,(a,a))$
+            \item $(a,(a,a))$的最右推导:\\
+                $S\Rightarrow(T)\Rightarrow(T,S)\Rightarrow(T,(T))\Rightarrow(T,(T,S))\Rightarrow(T,(T,a))\Rightarrow(T,(S,a))\Rightarrow(T,(a,a))\Rightarrow(S,(a,a))\Rightarrow(a,(a,a))$
+        \end{itemize}
+    \item 对$( ( (a,a),\wedge,(a)),a)$的最右推导:\\
+        $S\Rightarrow(T)\Rightarrow(T,S)\Rightarrow(T,a)\Rightarrow(S,a)\Rightarrow( (T),a)\Rightarrow( (T,S),a)\Rightarrow( (T,(T)),a)\Rightarrow( (T,(S)),a)\Rightarrow( (T,(a)),a)\Rightarrow( (T,S,(a)),a)\Rightarrow
+        ( (T,\wedge,(a)),a)\Rightarrow(S,\wedge,(a))\Rightarrow( ( (T),\wedge,(a)),a)\Rightarrow
+        ( ( (T,S),\wedge,(a)),a)\Rightarrow( ( (T,a),\wedge,(a)),a)\Rightarrow( ( (S,a),\wedge,(a)),a)\Rightarrow
+        ( ( (a,a),\wedge,(a)),a)$
+
+        \clearpage
+
+    \item 答案见下表 \\
+        \begin{center}
+        \begin{tabular}[h!]{ccc} \toprule
+            句型 & 归约规则 & 句柄 \\ \midrule
+            $( ( (a,a),\wedge,(a)),a)$ & $S\to a$ & $a$ \\
+            $( ( (S,a),\wedge,(a)),a)$ & $T\to S$ & $S$ \\
+            $( ( (T,a),\wedge,(a)),a)$ & $S\to a$ & $a$ \\
+            $( ( (T,S),\wedge,(a)),a)$ & $T\to T,S$ & $T,S$ \\
+            $( ( (T),\wedge,(a)),a)$ & $S\to(T)$ & $(T)$ \\
+            $( (S,\wedge,(a)),a)$ & $T\to S$ & $S$ \\
+            $( (T,\wedge,(a)),a)$ & $S\to \wedge$ & $\wedge$ \\
+            $( (T,S,(a)),a)$ & $T\to T,S$ & $T,S$ \\
+            $( (T,(a)),a)$ & $S\to a$ & $a$ \\
+            $( (T,(S)),a)$ & $T\to S$ & $S$ \\
+            $( (T,(T)),a)$ & $S\to T$ & $(T)$ \\
+            $( (T,S),a)$ & $T\to T,S$ & $T,S$ \\
+            $( (T),a)$ & $S\to (T)$ & $(T)$ \\
+            $(S,a)$ & $T\to S$ & $S$ \\
+            $(T,a)$ & $S\to a$ & $a$ \\
+            $(T,S)$ & $T\to T,S$ & $T,S$ \\
+            $(T)$ & $S\to (T)$ & (T) \\
+            $S$ & --- & --- \\ \bottomrule
+        \end{tabular}
+        \end{center}
+
+        \clearpage
+
+    \item 答案见下表 \\
+        \begin{center}
+        \begin{tabular}[h!]{clrc} \toprule
+            步骤 & \multicolumn{1}{c}{符号栈} & \multicolumn{1}{c}{输入串} & 动作 \\ \midrule
+            --- & $\#$ & $( ( (a,a),\wedge,(a)),a)\#$ & --- \\
+            1 & $\#($ & $( (a,a),\wedge,(a)),a)\#$ & 移入 \\
+            2 & $\#( ($ & $(a,a),\wedge,(a)),a)\#$ & 移入 \\
+            3 & $\#( ( ($ & $a,a),\wedge,(a)),a)\#$ & 移入 \\
+            4 & $\#( ( (a$ & $,a),\wedge,(a)),a)\#$ & 移入 \\
+            5 & $\#( ( (S$ & $,a),\wedge,(a)),a)\#$ & $S\to a$ \\
+            6 & $\#( ( (T$ & $,a),\wedge,(a)),a)\#$ & $T\to S$ \\
+            7 & $\#( ( (T,$ & $a),\wedge,(a)),a)\#$ & 移入 \\
+            8 & $\#( ( (T,a$ & $),\wedge,(a)),a)\#$ & 移入 \\
+            9 & $\#( ( (T,S$ & $),\wedge,(a)),a)\#$ & $S\to a$ \\
+            10 & $\#( ( (T$ & $),\wedge,(a)),a)\#$ & $T\to T,S$ \\
+            11 & $\#( ( (T)$ & $,\wedge,(a)),a)\#$ & 移入 \\
+            12 & $\#( ( S$ & $,\wedge,(a)),a)\#$ & $S\to (T)$ \\
+            13 & $\#( ( T$ & $,\wedge,(a)),a)\#$ & $T\to S$ \\
+            14 & $\#( ( T,$ & $\wedge,(a)),a)\#$ & 移入 \\
+            15 & $\#( ( T,\wedge$ & $,(a)),a)\#$ & 移入 \\
+            16 & $\#( ( T,S$ & $,(a)),a)\#$ & $S\to \wedge$ \\
+            17 & $\#( ( T$ & $,(a)),a)\#$ & $T\to T,S$ \\
+            18 & $\#( ( T,$ & $(a)),a)\#$ & 移入 \\
+            19 & $\#( ( T,($ & $a)),a)\#$ & 移入 \\
+            20 & $\#( ( T,(a$ & $)),a)\#$ & 移入 \\
+            21 & $\#( ( T,(S$ & $)),a)\#$ & $S\to a$ \\
+            22 & $\#( ( T,(T$ & $)),a)\#$ & $T\to S$ \\
+            23 & $\#( ( T,(T)$ & $),a)\#$ & 移入 \\
+            24 & $\#( ( T,S$ & $),a)\#$ & $S\to (T)$ \\
+            25 & $\#( ( T$ & $),a)\#$ & $T\to T,S$ \\
+            26 & $\#( ( T)$ & $,a)\#$ & 移入 \\
+            27 & $\#( S$ & $,a)\#$ & $S\to (T)$ \\
+            28 & $\#( T$ & $,a)\#$ & $T\to S$ \\
+            29 & $\#( T,$ & $a)\#$ & 移入 \\
+            30 & $\#( T,a$ & $)\#$ & 移入 \\
+            31 & $\#( T,S$ & $)\#$ & $S\to a$ \\
+            32 & $\#( T$ & $)\#$ & $T\to T,S$ \\
+            33 & $\#( T)$ & $\#$ & 移入 \\
+            34 & $\#S$ & $\#$ & $S\to(T)$ \\
+            35 & $\#S\#$ & --- & Accept \\ \bottomrule
+        \end{tabular}
+        \end{center}
+\end{enumerate}
+
+\section*{3}
+
+\begin{enumerate}[(1)]
+    \item FIRSTVT$(S)=\{a,\wedge,(\}$, FIRSTVT$(S)=\{a,\wedge,(,,\}$, LASTVT$(S)=\{a,\wedge,)\}$, LASTVT$(S)=\{a,\wedge,),,\}$a
+    \item 答案见下表
+        \begin{center}
+            \begin{tabular}[h!]{ccccccc} \toprule
+                 & $a$ & $\wedge$ & $($ & $)$ & $,$ & $\#$ \\ \midrule
+                 $a$ & --- & --- & --- & $\gtrdot$ & $\gtrdot$ & $\gtrdot$ \\
+                 $\wedge$ & --- & --- & --- & $\gtrdot$ & $\gtrdot$ & $\gtrdot$ \\
+                 $($ & $\lessdot$ & $\lessdot$ & $\lessdot$ & $\eqdot$ & $\lessdot$ & --- \\
+                 $)$ & --- & --- & --- & $\gtrdot$ & $\gtrdot$ & $\gtrdot$ \\
+                 $,$ & $\lessdot$ & $\lessdot$ & $\lessdot$ & $\gtrdot$ & $\gtrdot$ & --- \\
+                 $\#$ & $\lessdot$ & $\lessdot$ & $\lessdot$ & --- & --- & $\eqdot$ \\ \bottomrule
+            \end{tabular}
+        \end{center}
+        该文法是算符优先文法.
+    \item 构造文法的优先函数
+        \begin{center}
+            \begin{tabular}[h!]{ccccccc} \toprule
+                & $a$ & $\wedge$ & $($ & $)$ & $,$ & $\#$ \\ \midrule
+                $f$ & 6 & 6 & 2 & 6 & 4 & 2 \\
+                $g$ & 7 & 7 & 7 & 2 & 3 & 2 \\ \bottomrule
+            \end{tabular}
+        \end{center}
+
+    \item 输入串$(a,(a,a))$的算符优先分析过程如下:
+        \begin{center}
+            \begin{tabular}[h!]{clrc} \toprule
+                步骤 & \multicolumn{1}{c}{符号栈} & \multicolumn{1}{c}{输入串} & 动作 \\ \midrule
+                1 & $\#$ & $(a,(a,a))\#$ & 移入 \\
+                2 & $\#($ & $a,(a,a))\#$ & 移入 \\
+                3 & $\#(a$ & $,(a,a))\#$ & 移入 \\
+                4 & $\#(T$ & $,(a,a))\#$ & $T\to a$ \\
+                5 & $\#(T,$ & $(a,a))\#$ & 移入 \\
+                6 & $\#(T,($ & $a,a))\#$ & 移入 \\
+                7 & $\#(T,(a$ & $,a))\#$ & 移入 \\
+                8 & $\#(T,(T$ & $,a))\#$ & $T\to a$ \\
+                9 & $\#(T,(T,$ & $a))\#$ & 移入 \\
+                10 & $\#(T,(T,a$ & $))\#$ & 移入 \\
+                11 & $\#(T,(T,S$ & $))\#$ & $S\to a$ \\
+                12 & $\#(T,(T$ & $))\#$ & $T\to T,S$\\
+                13 & $\#(T,(T)$ & $)\#$ & 移入 \\
+                14 & $\#(T,S$ & $)\#$ & $S\to(T)$ \\
+                15 & $\#(T$ & $)\#$ & $T\to T,S$ \\
+                16 & $\#(T)$ & $\#$ & 移入 \\
+                17 & $\#S$ & $\#$ & $S\to(T)$ \\ 
+                18 & $\#S\#$ & --- & Accept \\ \bottomrule                
+            \end{tabular}
+        \end{center}
+\end{enumerate}
+
+
+
+\iffalse
+\section*{4}
+
+    \problem{对以下文法:
+    \[Expr\to -Expr\]
+    \[Expr\to(Expr)|var\ ExprTail\]
+    \[ExprTail\to-Expr|\varepsilon\]
+    \[Var\to id\ VarTail\]
+    \[VarTail\to(Expr)|\varepsilon\]
+
+    \begin{enumerate}
+        \item 构造LL(1)分析表;
+        \item 给出对句子$id---id( (id) )$的分析过程.
+    \end{enumerate}
+
+    }
+\section*{5}
+
+\section*{补充题}
+
+    \problem{文法如下:
+    \begin{multicols}{3}
+        \begin{enumerate}
+            \item $E\to TE'$
+            \item $E'\to +TE'|\varepsilon$
+            \item $T\to FT'$
+            \item $T'\to*FT'|\varepsilon$
+            \item $F\to(E)|i$
+        \end{enumerate}
+    \end{multicols}
+
+    对$i_1i_4+i_2*i_3$和$i_1+i_2*i_3i_5$分析器如何动作, 是何结果?
+    }
+
+    \begin{enumerate}
+        \item $i_1i_4+i_2*i_3$
+            \begin{center}
+                \begin{tabular}{lll}\toprule
+                    栈 & 输入 & 输出 \\ \midrule
+                    %$\#E$ & $i_1i_4+i_2*i_3$ &  \\
+                    $\#E$ & $\underline{i_1}i_4+i_2*i_3$ & \\
+                    $\#E'T$ & $\underline{i_1}i_4+i_2*i_3$ & $E\to TE'$\\
+                    $\#E'T'F$ & $\underline{i_1}i_4+i_2*i_3$ & $T\to T'F$\\
+                    $\#E'T'i$ & $\underline{i_1}i_4+i_2*i_3$ & $F\to i$\\
+                    $\#E'T'$ & $\phantom{i_1}\underline{i_4}+i_2*i_3$ & \\
+                    $\#E'\underline{T'}$ & $\phantom{i_1}\underline{i_4}+i_2*i_3$ & error\\
+                    \bottomrule
+                \end{tabular}
+            \end{center}
+
+            匹配失败.
+        \item $i_1+i_2*i_3i_5$
+            \begin{center}
+                \begin{tabular}{lll}\toprule
+                    栈 & 输入 & 输出 \\ \midrule
+                    %$\#E$ & $i_1+i_2*i_3i_5$ & \\
+                    $\#E$ & $\underline{i_1}+i_2*i_3i_5$ & \\
+                    $\#E'T$ & $\underline{i_1}+i_2*i_3i_5$ & $E\to TE'$\\
+                    $\#E'T'F$ & $\underline{i_1}+i_2*i_3i_5$ & $T\to FT'$\\
+                    $\#E'T'$ & $\phantom{i_1}\,\underline{+}\,i_2*i_3i_5$ & $F\to i_1$\\
+                    $\#E'$ & $\phantom{i_1}\,\underline{+}\,i_2*i_3i_5$ & $T'\to\varepsilon$\\
+                    $\#E'T+$ & $\phantom{i_1}\,\underline{+}\,i_2*i_3i_5$ & $E'\to +TE'$\\
+                    $\#E'T$ & $\phantom{i_1+}\,\,\underline{i_2}*i_3i_5$ & 匹配$+$\\
+                    $\#E'T'F$ & $\phantom{i_1+}\,\,\underline{i_2}*i_3i_5$ & $T\to FT'$\\
+                    $\#E'T'$ & $\phantom{i_1+i_2}\,\,\underline{*}i_3i_5$ & $F\to i_2$\\
+                    $\#E'T'F*$ & $\phantom{i_1+i_2}\,\,\underline{*}i_3i_5$ & $T'\to*FT$\\
+                    $\#E'T'F$ & $\phantom{i_1+i_2*}\,\,\underline{i_3}i_5$ & 匹配$*$\\
+                    $\#E'T'$ & $\phantom{i_1+i_2*i_3}\underline{i_5}$ & $F\to i_3$\\
+                    $\#E'\underline{T'}$ & $\phantom{i_1+i_2*i_3}\underline{i_5}$ & error\\
+                    \bottomrule
+                \end{tabular}
+            \end{center}
+
+            匹配失败.
+
+    \end{enumerate}
+
+\fi
+
+\end{document}
+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{编译原理}
+\def\homeworkid{5}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage{multicol}
+\usepackage[
+    colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+\usepackage{pstricks}
+\usepackage{pst-node}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+\def\symnot{\ \mathrm{not}\ }
+\def\symor{\ \mathrm{or}\ }
+\def\symand{\ \mathrm{and}\ }
+\def\uminus{\ \mathrm{uminus}\ }
+
+
+\section*{7.1}
+
+    \[a*(-b+c) \to ab\uminus c+*\]
+    \[a+b*(c+d/e) \to abcde/+*+\]
+    \[-a+b*(-c+d) \to a\uminus bc\uminus d+*+\]
+    \[\symnot A\symor\symnot (C\symor\symnot D)\to A\symnot C D\symnot \symor \symnot \symor\]
+    \[(A\symand B)\symor(\symnot C\symor D)\to A B\symand C\symnot D\symor \symor\]
+    \[(A\symor B)\symand(C\symor\symnot D\symand E)\to AB\symor CD\symnot \symor E\symand\symand\]
+    \[\mathrm{if\ } (x+y)*z=0 \mathrm{\ then\ } (a+b)\wedge c \mathrm{\ else\ } a\wedge b\wedge c \to 
+        xy+z*0=ab+c\wedge ab\wedge c\wedge \textbf{if}
+    \]
+
+\section*{7.3}
+
+    \problem{将表达式$-(a+b)\times(c+d)-(a+b+c)$分别表示成三元式, 间接三元式和四元式序列.}
+
+    间接三元式序列: (1), (2), (3), (4), (1), (5), (6).
+
+    \begin{table}[h!]
+        \centering
+        \caption{三元式序列}
+        \label{tab:tuples}
+        \begin{tabular}{cccc} \toprule
+            \# & operator & operand1 & operand2 \\ \midrule
+            1 & $+$ & $a$ & $b$ \\
+            2 & $+$ & $c$ & $d$ \\
+            3 & $\times$ & (1) & (2) \\
+            4 & $-$(unary) & (3) & \\
+            5 & $+$ & $a$ & $b$ \\
+            6 & $+$ & (5) & $c$ \\
+            7 & $-$ & (4) & (6) \\
+            \bottomrule
+        \end{tabular}
+    \end{table}
+
+    \begin{table}[h!]
+        \centering
+        \caption{间接三元式序列}
+        \label{tab:indirect-tuples}
+        \begin{tabular}{cccc} \toprule
+            \# & operator & operand1 & operand2 \\ \midrule
+            1 & $+$ & $a$ & $b$ \\
+            2 & $+$ & $c$ & $d$ \\
+            3 & $\times$ & (1) & (2) \\
+            4 & $-$(unary) & (3) & \\
+            5 & $+$ & (1) & $c$ \\
+            6 & $-$ & (4) & (6) \\
+            \bottomrule
+        \end{tabular}
+    \end{table}
+
+    \begin{table}[h!]
+        \centering
+        \caption{四元式序列}
+        \label{tab:4-tuples}
+        \begin{tabular}{ccccc} \toprule
+            \# & operator & operand1 & operand2 & operand3 \\ \midrule
+            1 & $+$ & $a$ & $b$ & $T_1$ \\
+            2 & $+$ & $c$ & $d$ & $T_2$ \\
+            3 & $\times$ & $T_1$ & $T_2$ & $T_3$ \\
+            4 & $-$(unary) & $T_3$ & --- & $T_4$ \\
+            5 & $+$ & $T_1$ & $c$ & $T_5$ \\
+            6 & $-$ & $T_4$ & $T_5$ & $T_6$ \\
+            \bottomrule
+        \end{tabular}
+    \end{table}
+
+\section*{7.4}
+
+    \problem{按7.3节所说方法, 写出赋值语句$A:=B\times(-C+D)$的自下而上语法制导翻译过程. 给出所产生的三地址代码.}
+
+    \begin{table}[h!]
+        \centering
+        \caption{语法制导翻译过程}
+        \label{tab:translate}
+        \begin{tabular}{clrlc} \toprule
+            \# & \multicolumn{1}{c}{Stack} & \multicolumn{1}{c}{Input} & \multicolumn{1}{c}{PLACE} & Output \\ \midrule
+            1 & & $A:=B\times(-C+D)$ &  & \\
+            2 & $i$ & $:=B\times(-C+D)$ & $A$ & \\
+            3 & $i:=$ & $B\times(-C+D)$ & $A$--- & \\
+            4 & $i:=i$ & $\times(-C+D)$ & $A$---$B$ & \\
+            5 & $i:=E$ & $\times(-C+D)$ & $A$---$B$ & \\
+            6 & $i:=E\times$ & $(-C+D)$ & $A$---$B$--- & \\
+            7 & $i:=E\times($ & $-C+D)$ & $A$---$B$------ & \\
+            8 & $i:=E\times(-$ & $C+D)$ & $A$---$B$--------- & \\
+            9 & $i:=E\times(-i$ & $+D)$ & $A$---$B$---------$C$ & \\
+            10 & $i:=E\times(-E$ & $+D)$ & $A$---$B$---------$C$ & $(-,C,$---$,T_1)$ \\
+            11 & $i:=E\times(E$ & $+D)$ & $A$---$B$------$C$ & \\
+            12 & $i:=E\times(E+$ & $D)$ & $A$---$B$------$C$--- & \\
+            13 & $i:=E\times(E+i$ & $)$ & $A$---$B$------$T_1$---$D$ & \\
+            14 & $i:=E\times(E+E$ & $)$ & $A$---$B$------$T_1$---$D$ & $(+,T_1,D,T_2)$ \\
+            15 & $i:=E\times(E$ & $)$ & $A$---$B$------$T_2$ & \\
+            16 & $i:=E\times(E)$ & & $A$---$B$------$T_2$--- & \\
+            17 & $i:=E\times E$ & & $A$---$B$---$T_2$ & $(\times,B,T_2,T_3)$ \\
+            18 & $i:=E$ & & $A$---$T_3$ & $(:=,T_3,-,A)$ \\
+            \bottomrule
+        \end{tabular}
+    \end{table}
+
+
+
+
+\iffalse
+\section*{4}
+
+    \problem{对以下文法:
+    \[Expr\to -Expr\]
+    \[Expr\to(Expr)|var\ ExprTail\]
+    \[ExprTail\to-Expr|\varepsilon\]
+    \[Var\to id\ VarTail\]
+    \[VarTail\to(Expr)|\varepsilon\]
+
+    \begin{enumerate}
+        \item 构造LL(1)分析表;
+        \item 给出对句子$id---id( (id) )$的分析过程.
+    \end{enumerate}
+
+    }
+\section*{5}
+
+\section*{补充题}
+
+    \problem{文法如下:
+    \begin{multicols}{3}
+        \begin{enumerate}
+            \item $E\to TE'$
+            \item $E'\to +TE'|\varepsilon$
+            \item $T\to FT'$
+            \item $T'\to*FT'|\varepsilon$
+            \item $F\to(E)|i$
+        \end{enumerate}
+    \end{multicols}
+
+    对$i_1i_4+i_2*i_3$和$i_1+i_2*i_3i_5$分析器如何动作, 是何结果?
+    }
+
+    \begin{enumerate}
+        \item $i_1i_4+i_2*i_3$
+            \begin{center}
+                \begin{tabular}{lll}\toprule
+                    栈 & 输入 & 输出 \\ \midrule
+                    %$\#E$ & $i_1i_4+i_2*i_3$ &  \\
+                    $\#E$ & $\underline{i_1}i_4+i_2*i_3$ & \\
+                    $\#E'T$ & $\underline{i_1}i_4+i_2*i_3$ & $E\to TE'$\\
+                    $\#E'T'F$ & $\underline{i_1}i_4+i_2*i_3$ & $T\to T'F$\\
+                    $\#E'T'i$ & $\underline{i_1}i_4+i_2*i_3$ & $F\to i$\\
+                    $\#E'T'$ & $\phantom{i_1}\underline{i_4}+i_2*i_3$ & \\
+                    $\#E'\underline{T'}$ & $\phantom{i_1}\underline{i_4}+i_2*i_3$ & error\\
+                    \bottomrule
+                \end{tabular}
+            \end{center}
+
+            匹配失败.
+        \item $i_1+i_2*i_3i_5$
+            \begin{center}
+                \begin{tabular}{lll}\toprule
+                    栈 & 输入 & 输出 \\ \midrule
+                    %$\#E$ & $i_1+i_2*i_3i_5$ & \\
+                    $\#E$ & $\underline{i_1}+i_2*i_3i_5$ & \\
+                    $\#E'T$ & $\underline{i_1}+i_2*i_3i_5$ & $E\to TE'$\\
+                    $\#E'T'F$ & $\underline{i_1}+i_2*i_3i_5$ & $T\to FT'$\\
+                    $\#E'T'$ & $\phantom{i_1}\,\underline{+}\,i_2*i_3i_5$ & $F\to i_1$\\
+                    $\#E'$ & $\phantom{i_1}\,\underline{+}\,i_2*i_3i_5$ & $T'\to\varepsilon$\\
+                    $\#E'T+$ & $\phantom{i_1}\,\underline{+}\,i_2*i_3i_5$ & $E'\to +TE'$\\
+                    $\#E'T$ & $\phantom{i_1+}\,\,\underline{i_2}*i_3i_5$ & 匹配$+$\\
+                    $\#E'T'F$ & $\phantom{i_1+}\,\,\underline{i_2}*i_3i_5$ & $T\to FT'$\\
+                    $\#E'T'$ & $\phantom{i_1+i_2}\,\,\underline{*}i_3i_5$ & $F\to i_2$\\
+                    $\#E'T'F*$ & $\phantom{i_1+i_2}\,\,\underline{*}i_3i_5$ & $T'\to*FT$\\
+                    $\#E'T'F$ & $\phantom{i_1+i_2*}\,\,\underline{i_3}i_5$ & 匹配$*$\\
+                    $\#E'T'$ & $\phantom{i_1+i_2*i_3}\underline{i_5}$ & $F\to i_3$\\
+                    $\#E'\underline{T'}$ & $\phantom{i_1+i_2*i_3}\underline{i_5}$ & error\\
+                    \bottomrule
+                \end{tabular}
+            \end{center}
+
+            匹配失败.
+
+    \end{enumerate}
+
+\fi
+
+\end{document}
+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+\documentclass[12pt]{article}
+\def\course{数据库系统原理}
+\def\homeworkid{2}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage[
+    colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{3.1}
+
+\begin{verbatim}
+CREATE TABLE Student (
+    S#      CHAR(10)    NOT NULL,
+    Sname   VARCHAR(20) NOT NULL,
+    gender  CHAR(1),
+    bdate   DATE,
+    height  FLOAT(3),
+    dorm    CHAR(6),
+
+    PRIMARY KEY S#
+)
+
+CREATE TABLE Course (
+    C#      CHAR(5)     NOT NULL,
+    Cname   VARCHAR(15) NOT NULL,
+    period  INT         DEFAULT 0,
+    credit  INT         DEFAULT 0,
+    teacher VARCHAR(20),
+
+    PRIMARY KEY C#
+)
+
+CREATE TABLE SC (
+    S#      CHAR(10)    NOT NULL,
+    C#      CHAR(5)     NOT NULL,
+    grade   DEC(4,1)    DEFAULT NULL,
+
+    PRIMARY KEY (S#, C#),
+
+    FOREIGN KEY (S#)
+        REFERENCES Student
+            ON DELETE CASCADE,
+
+    FOREIGN KEY (C#)
+        REFERENCES Course
+            ON DELETE RESTRICT,
+
+    CHECK (grade IS NULL) OR (grade BETWEEN 0 AND 100)
+)
+\end{verbatim}
+
+\section*{3.2}
+
+\begin{enumerate}[(1)]
+    \item 
+        \begin{verbatim}
+SELECT S#, grade FROM SC WHERE C#='CS-02'
+        \end{verbatim}
+        
+    \item
+        \begin{verbatim}
+SELECT Sname FROM Student NATURE JOIN SC 
+    WHERE gender='f' AND C#='EE-01'
+        \end{verbatim}
+
+    \item 
+        \begin{verbatim}
+SELECT DISTINCT Sname FROM Student NATURE JOIN SC Where C#<>'CS-02'
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+SELECT S#, Sname, (2011-EXTRACT(YEAR FROM bdate) AS Sage
+    WHERE gender='m' AND
+        Height>SOME(SELECT Height FROM Student WHERE Sname='王涛')
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+CREATE VIEW C_CS_01 AS
+    SELECT *  FROM SC WHERE C#='CS-01';
+    SELECT S# FROM SC WHERE SC.grade=MAX(class_CS_01.grade)
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+SELECT Sname, C#, credit, grade FROM Student 
+    NATURE JOIN Course 
+    NATURE JOIN SC
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+SELECT Sname, AVG(grade) As Avg_grade 
+    FROM Student 
+    NATURE JOIN SC 
+    WHERE AVG(grade)>80
+    GROUP BY C#
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+SELECT SUM(credit)
+    FROM Course
+    NATURE JOIN SC
+    WHERE Count(*)>=3
+    ORDER BY S#
+    GROUP BY S#
+        \end{verbatim}
+\end{enumerate}
+
+\section*{3.3}
+\begin{verbatim}
+INSERT INTO Student VALUES('01032005','刘静','男','1983-12-10',1.75,'西14舍312')
+
+INSERT INTO Course VALUES('CS-03','离散数学',64,4,'陈建明')
+\end{verbatim}
+
+\section*{3.5}
+\begin{verbatim}
+UPDATE Course
+    SET period=56, credit=credit+1
+    WHERE teacher='张明' AND Cname='信号与系统'
+\end{verbatim}
+
+\section*{3.7}
+\begin{enumerate}[(1)]
+    \item 
+        \begin{verbatim}
+CREATE VIEW S_w18boys(S#, Sname, bdate, height) AS
+    SELECT S#, Sname, bdate, height FROM Student WHERE dorm LIKE '西18%'
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+CREATE VIEW C_zhangming(C#, Cname, AVGgrade) AS
+    SELECT Course.C#, Course.Cname, AVG(SC.grade) 
+    FROM Course, SC
+    WHERE Course.C#=SC.C# AND Teacher='张明'
+    GROUP BY C#
+        \end{verbatim}
+
+    \item
+        \begin{verbatim}
+CREATE VIEW S_AI AS
+    SELECT Student.S#, Student.Sname, SC.grade
+    FROM Student, SC, Course
+    WHERE Student.S#=SC.S#  AND
+        SC.CH=Course.C#     AND
+        Course.name='人工智能'
+        \end{verbatim}
+\end{enumerate}
+
+\section*{3.14}
+\begin{verbatim}
+DELETE FROM Student
+    WHERE 110<=(SELECT SUM(grade) FROM SC
+                    WHERE SC.S#=Student.S#
+                    GROUP BY S#)
+\end{verbatim}
+
+
+
+
+\end{document}
+% multiple1902 <multiple1902@gmail.com>
+% public on https://bitbucket.org/multiple1902/homework
+% licensed under cc by-sa 3.0
+% NOTE: needs pdfgantt package
+\documentclass[11pt]{article}
+\def\course{操作系统原理}
+\def\homeworkid{5}
+\usepackage{amsthm,amssymb,fullpage}
+\usepackage{enumerate}
+\usepackage[slantfont,boldfont,CJKnumber,CJKtextspaces,CJKmathspaces]{xeCJK}
+\usepackage{tabularx}
+\usepackage{booktabs}
+\usepackage{multicol}
+\usepackage{ulem}
+\usepackage{pgfgantt}
+\usepackage[
+    %colorlinks, %linkcolor=blue,anchorcolor=blue,citecolor=green,
+    pdfcreator={TeX}, pdftitle={\course 作业\homeworkid},
+    pdfauthor={multiple1902@gmail.com}
+    ]{hyperref}
+\def\UrlBreaks{\do-\do_}
+\setCJKmainfont{細明體}
+\setCJKsansfont{微軟正黑體}
+\newcommand{\problem}[1]{
+    \noindent \hskip 0.05\linewidth \fbox{\parbox{0.9\linewidth}{#1}} \\
+}
+
+\begin{document}
+
+\noindent\begin{tabularx}{\linewidth}{|X|}
+\hline \vskip -2mm
+{\sf \course} \hfill \today \\
+{\centering \sf \large
+Homework \homeworkid \\ }
+计算机92班 \hfill 戴唯思 09055029 \\ \hline
+\end{tabularx}
+
+\section*{6.4}
+
+    \problem{Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.}
+
+    \textsf{Spinlocks} are locks where the \textsf{thread} simply \textsl{waits} in a loop (spin) repeatedly checking until the lock becomes available.
+
+    \begin{itemize}
+        \item Spinlocks \textsl{should not be used} on single-processor systems. 
+        \begin{quotation}
+            In the best case, a spin lock on a single processor system will waste resources, slowing down the owner of the lock; in the worst case, it will deadlock the processor.
+        \end{quotation}
+
+        \item Spinlocks \textsl{are not needed} in single-processor systems.
+            \begin{quotation}
+                Generally you should start with a mutex, and if profiling show it to be a bottleneck, you may want to consider a spinlock. 
+            \end{quotation}
+
+        \item Spinlocks are efficient when implemented on multi-processor systems.
+    \end{itemize}
+
+    
+\section*{6.9}
+
+    \problem{Show that, if the \texttt{wait()} and \texttt{signal()} semaphore operations are not executed atomically, when mutual exclusion may be violated.}
+
+    Given semaphore $x=0$, when a \texttt{wait()} and a \texttt{signal()} operation are done atomically, $x$ changes to $1$ then $0$, or $-1$ then $0$. If they are not executed atomically, $x$ gets an uncertain value except at the initial step.
+
+\section*{6.11}
+
+    \problem{\textbf{The Sleeping-Barber Problem}. A barbershop consists of a waiting room with $n$ chairs and a barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.}
+
+\begin{verbatim}
+class customer:
+    def main(self):
+        if barbershop.all_chairs_occupied:
+            self.leave()
+        self.sit_in(pick_one_from(barbershop.free_chairs))
+
+class barber:
+    def main(self):
+        while True:
+            while barbershop.chairs_occupied>0:
+                self.serve(pick_one_from(barbershop.occupied_chairs))
+            self.sleep(until=lambda:(barbershop.chairs_occupied==0))
+\end{verbatim}
+
+\section*{Supplement 1}
+
+    \texttt P, \texttt V described like this would cause starvation, because \texttt V resumes a process from the tail of the waiting queue, ones on the head would never be resumed.
+
+    Initialize \texttt s to 1. Invoke \texttt{P(S)} and \texttt{V(S)} separately before and after visits to the shared variable.
+
+\section*{Supplement 2}
+
+\begin{verbatim}
+def managed_write:
+    Swait(wcount,1,1);
+    Swait(Rcount, R, 0;
+          mutex,1,1);
+    write();
+    Ssignal(mutex,1);
+    Ssignal(wmutex,1);
+
+def managed_read:
+    Swait(wcount,w,0;
+          Rcount,1,1);
+    read();
+    Ssignal(Rcount,1);
+\end{verbatim}
+
+\section*{Supplement 3}
+
+    4 processes: enter the room, students do the exam, students leave the room, the teacher leaves the room
+
+    Semaphores:
+    \begin{itemize}
+        \item gate=1
+        \item exampaper=number of students
+        \item teacher=1
+        \item freeseat=number of students
+        \item pack=0
+    \end{itemize}
+
+    \begin{minipage}[t]{.25\linewidth}
+        \textsf{Enter the room} \\
+        P(gate) \\
+        Enters the room \\
+        V(gate) \\
+        V(freeseat)
+    \end{minipage}
+    \begin{minipage}[t]{.35\linewidth}
+        \textsf{Students do the exam} \\
+        P(teacher)\\
+        Get the exam paper\\
+        P(exampaper)\\
+        V(teacher)\\
+        Write on the exam paper\\
+        P(teacher)\\
+        Hand in the exam paper\\
+        V(exampaper)\\
+        V(teacher)\\
+    \end{minipage}
+    \begin{minipage}[t]{.25\linewidth}
+        \textsf{Leave(S)} \\
+        P(own\_exampaper)\\
+        V(own\_exampaper)\\
+        P(gate)\\
+        Leave the room\\
+        V(gate)
+    \end{minipage}
+    \begin{minipage}[t]{.25\linewidth}
+        \textsf{Leave(T)}\\
+        P(pack)\\
+        V(pack)\\
+        P(gate)\\
+        Leave the room\\
+        V(gate)\\
+    \end{minipage}
+
+\section*{7.3}
+
+    \problem{A possible solution for preventing deadlocks is to have a single, higher-order resource that must be requested before any other resource. For example, if multiple threads attempt to access the synchronization objects $A$ \ldots $E$, deadlock is possible. We can prevent the deadlock by adding a sixth object $F$. Thenever a thread wants to require the lock for any object $A$ \ldots $E$, it must first acquire the lock for object $F$. This solution is known as \textsf{containment}: the locks for objects $A$ \ldots $E$ are contained within the lock for object $F$. Compare this scheme with the circular-wait scheme of section 7.4.4.}
+
+    \begin{table}[h!]
+        \centering
+        \caption{Comparison of containment and circular-wait scheme}
+        \label{tab:comparison-containment-circular-wait}
+        \begin{tabular}{cc}\toprule
+            \textsf{Containment} & \textsf{Circular-Wait} \\ \midrule
+            \multicolumn{2}{c}{Both prevent the deadlock} \\
+            Inefficient & Efficient \\
+            One-at-a-time & Not restricted \\
+            Usually easy to implement & Usually hard to implement \\
+            \bottomrule
+        \end{tabular}
+    \end{table}
+
+\section*{7.11}
+
+    \problem{Consider the following snapshot of a system:
+    \begin{center}
+        \begin{tabular}{cccc}
+            & \uline{\textit{Allocation}} & \uline{\quad\textit{Max}\quad} & \uline{\textit{Available}} \\
+             & $A$ $B$ $C$ $D$ & $A$ $B$ $C$ $D$ & $A$ $B$ $C$ $D$ \\
+            $P_0$ & 0 0 1 2 & 0 0 1 2 & 1 5 2 0 \\
+            $P_1$ & 1 0 0 0 & 1 7 5 0 \\
+            $P_2$ & 1 3 5 4 & 2 3 5 6 \\
+            $P_3$ & 0 6 3 2 & 0 6 5 2 \\
+            $P_4$ & 0 0 1 4 & 0 6 5 6 \\
+        \end{tabular}
+    \end{center}
+    Answer the following questions using the banker's algorithm:
+    \begin{enumerate}[a.]
+        \item What is the context of the matrix \textsl{Need}?
+        \item Is the system in a safe state?
+        \item If a request from process $P_1$ arrives for $(0,4,2,0)$, can the request be greanted immediately?
+    \end{enumerate}
+    }
+
+    \begin{enumerate}[a.]
+        \item \[\textsl{Need:}\quad \begin{array}{ccccc}
+                 & A & B & C & D \\
+                 P_0 & 0 & 0 & 0 & 0 \\
+                 P_1 & 0 & 7 & 5 & 0 \\
+                 P_2 & 1 & 0 & 0 & 2 \\
+                 P_3 & 0 & 0 & 2 & 0 \\
+                 P_4 & 0 & 6 & 4 & 2
+            \end{array}\]
+        \item Yes, the plan $P_0, P_2, P_1, P_3, P_4$ satisfies the safety requirements.
+        \item Yes, one possible sequence is $P_0, P_2, P_3, P_1, P_4$.
+    \end{enumerate}
+
+
+\section*{References}
+
+    \begin{enumerate}
+        \item \url{https://secure.wikimedia.org/wikipedia/en/wiki/Spinlock}
+        \item \url{http://stackoverflow.com/questions/1025859/is-spin-lock-useful-in-a-single-processor-uni-core-architecture}
+        \item \url{http://comp.ist.utl.pt/ec-sc/0405/docs/ecos-2.0b1/doc/html/ref/kernel-spinlocks.html}
+        \item Thomas Anderson.  The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors.  IEEE Transactions on Parallel and Distributed Systems, vol. 1, num. 1, January 1990, pages 6 - 16.  An earlier version appeared in Proc. 1989 International Conference on Parallel Processing (ICPP), August 1989. \url{http://www.cs.washington.edu/homes/tom/pubs/spinlock.pdf}
+        \item \url{http://www.moserware.com/2008/09/how-do-locks-lock.html}
+        \item \url{http://wiki.osdev.org/Atomic_operation}
+        \item \url{http://www.cs.rpi.edu/~moorthy/Courses/os00/soln78.html}
+        \item \url{http://www.cs.umbc.edu/courses/undergraduate/421/spring06/homework1-soln.pdf}
+    \end{enumerate}
+\end{document}