-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathcompilers.tex
117 lines (114 loc) · 3.29 KB
/
compilers.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
% Created 2020-10-05 Mon 12:55
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage[russian]{babel}
\usepackage{listings}
\usepackage{amsmath}
\usepackage{esint}
\usepackage{mathtools}
\usepackage{amsthm}
\usepackage[top=0.8in, bottom=0.75in, left=0.625in, right=0.625in]{geometry}
\usepackage{float}
\usepackage{dot2texi}
\usepackage{tikz}
\usetikzlibrary{shapes, arrows, positioning}
\def\zall{\setcounter{lem}{0}\setcounter{cnsqnc}{0}\setcounter{th}{0}\setcounter{Cmt}{0}\setcounter{equation}{0}\setcounter{stnmt}{0}}
\newcounter{lem}\setcounter{lem}{0}
\def\lm{\par\smallskip\refstepcounter{lem}\textbf{\arabic{lem}}}
\newtheorem*{Lemma}{Лемма \lm}
\newcounter{th}\setcounter{th}{0}
\def\th{\par\smallskip\refstepcounter{th}\textbf{\arabic{th}}}
\newtheorem*{Theorem}{Теорема \th}
\newcounter{cnsqnc}\setcounter{cnsqnc}{0}
\def\cnsqnc{\par\smallskip\refstepcounter{cnsqnc}\textbf{\arabic{cnsqnc}}}
\newtheorem*{Consequence}{Следствие \cnsqnc}
\newcounter{Cmt}\setcounter{Cmt}{0}
\def\cmt{\par\smallskip\refstepcounter{Cmt}\textbf{\arabic{Cmt}}}
\newtheorem*{Note}{Замечание \cmt}
\newcounter{stnmt}\setcounter{stnmt}{0}
\def\st{\par\smallskip\refstepcounter{stnmt}\textbf{\arabic{stnmt}}}
\newtheorem*{Statement}{Утверждение \st}
\author{Sergey Makarov}
\date{\today}
\title{}
\hypersetup{
pdfauthor={Sergey Makarov},
pdftitle={},
pdfkeywords={},
pdfsubject={},
pdfcreator={Emacs 27.1 (Org mode 9.3)},
pdflang={Russian}}
\begin{document}
\tableofcontents
\section{Контрольная работа}
\label{sec:org6b66717}
Вычислить множества \(Input\) для базовых блоков следующей функции:
\begin{lstlisting}
param p
param q
param r
q0 <- #0
L1: ifTrue q0 >= p goto L2
q0 <- +, q0, r
q1 <- +, p, q
r <- *, r, #2
q2 <- +, p, q
q0 <- +, p, #1
q2 <- +, q0, r
s <- +, q2, q
s <- +, s, q
q2 <- +, p, q
q3 <- -, q2, q1
q3 <- -, q2, q3
q3 <- +, p, q
q1 <- -, q3, s
ifTrue q < #256 goto L1
q3 <- +, q0, q1
s <- +, q2, q3
p <- -, s, p
r <- -, r, #256
goto L1
L2: q <- *, p, q
return q
\end{lstlisting}
\pagebreak
\subsection{Решение}
\label{sec:org44e41c8}
CFG имеет вид:
\begin{figure}[h]
\begin{dot2tex}
digraph G {
node [shape=rectangle];
Entry -> B1;
B1 -> B2
B2 -> B3;
B2 -> B5;
B3 -> B2;
B3 -> B4;
B4 -> B2;
B5 -> Exit;
}
\end{dot2tex}
\end{figure}
Множества достигающих определений для этих блоков имеют вид:
\begin{gather*}
Input(B1) = \emptyset \\
Input(B2) = \{(B1, q), (B4, s), (B1, p), (B4, p), (B4, r), (B4, q3), (B3, q2)\} \\
Input(B3) = \{(B1, q), (B4, s), (B1, p), (B4, p), (B4, r), (B4, q3), (B3, q2)\} \\
Input(B4) = \{(B1, q), (B3, q0), (B3, q1), (B3, q2), (B3, q3), (B3, r), (B3, s)\} \\
Input(B5) = \{(B1, q), (B4, s), (B1, p), (B4, p), (B4, r), (B4, q3), (B3, q2)\}
\end{gather*}
\end{document}