-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathpython_interpreter.tex
More file actions
154 lines (142 loc) · 17 KB
/
python_interpreter.tex
File metadata and controls
154 lines (142 loc) · 17 KB
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
\section*{Interpreter Support}
\begin{itemize}
\item \lstinline{apply_in_underlying_python(f, xs)}: \textit{primitive}, calls the function \lstinline{f}
with arguments \lstinline{xs}. For example:
\begin{lstlisting}
def times(x, y):
return x * y
apply_in_underlying_python(times, linked_list(2, 3)) # returns 6
\end{lstlisting}
\item \lstinline{tokenize(x)}: \textit{primitive}, returns the literal linked list of tokens that results from tokenizing
the string \lstinline{x} as a Python program. Each token is a string that contains the characters of
the token as they appear in the program. Comments are ignored.
\item \lstinline{parse(x)}: \textit{primitive}, returns the parse tree that results from parsing
the string \lstinline{x} as a Python program. The following two pages describe the shape of the parse tree.
The tree is represented by the tagged linked lists on the right; the angle brackets denote recursive application
of the transformation rules. Implementations are allowed to support more of Python than listed.
\end{itemize}
In addition, the Source Academy frontend predeclares the name \lstinline{__program__} in all Python languages to
refer to the string representation of the entrypoint file of the program in the editor that is being run using ``Run''.
The entrypoint file is the file containing the code that acts as the entrypoint of the program being run.
If \lstinline{__program__} is used in the REPL, it refers to the string representation of the editor content
at the time when ``Run'' was last pressed.
\newpage
\KOMAoptions{paper=landscape,pagesize}
\recalctypearea
\addtolength{\oddsidemargin}{-6cm}
\addtolength{\evensidemargin}{-6cm}
\addtolength{\textwidth}{13cm}
\begin{alignat*}{9}
&& \textit{program} && ::= &\quad && \textit{statement}\ \ldots
&& \texttt{linked\_list("sequence", linked\_list of } \langle \textit{statement}\rangle \texttt{)} \\[1mm]
&& \textit{statement} && ::= &\quad && \textit{name}\ \textbf{\texttt{=}}\ \textit{expression}
&& \texttt{linked\_list("variable\_declaration", } \langle \textit{name}\rangle \textit{, } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textit{declared\_name}\ \textbf{\texttt{=}}\ \textit{expression}
&& \texttt{linked\_list("assignment", } \langle \textit{declared\_name}\rangle \textit{, } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{def}}\ \textit{name} \ \textbf{\texttt{(}}\ \textit{names} \ \textbf{\texttt{)}}\ \textit{: block} \quad
&& \texttt{linked\_list("function\_declaration", } \langle \textit{name}\rangle \textit{, } \langle \textit{names}\rangle \textit{,}\ \langle \textit{block}\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{return}}\ \textit{expression}
&& \texttt{linked\_list("return\_statement", } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textit{if-statement} \quad
&& \textrm{see below} \\
&& && | &\quad && \textbf{\texttt{while}}\ \textbf{\texttt{(}}\ \textit{expression} \ \textbf{\texttt{)}} \ \textit{: block}
&& \texttt{linked\_list("while\_loop", } \langle \textit{expression}\rangle \textit{, } \langle \textit{block}\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{for}}\ \textit{name}\ \textbf{\texttt{in range}}\ \textit{( range-args ) : block}
&& \texttt{linked\_list("for\_loop", } \langle \textit{range\_args}\rangle \textit{, } \langle \textit{block}\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{break}}
&& \texttt{linked\_list("break\_statement")} \\
&& && | &\quad && \textbf{\texttt{continue}}
&& \texttt{linked\_list("continue\_statement")} \\
&& && | &\quad && \textbf{\texttt{nonlocal}}
&& \texttt{linked\_list("nonlocal\_statement")} \\
&& && | &\quad && \textit{block}
&& \textrm{see below} \\
&& && | &\quad && \textit{expression}
&& \textrm{see below} \\[1mm]
&& \textit{range\_args} && ::= &\quad && \textit{expression}_1 \textbf{\texttt{[}} \textit{, expression}_2 \textbf{\texttt{]}} \textbf{\texttt{[}} \ \textit{, expression}_3 \textbf{\texttt{]}} \
&& \texttt{linked\_list("range\_args", } \langle \textit{expression}_1\rangle \textit{, } \langle \textit{expression}_2\rangle \textit{,}\ \langle \textit{expression}_3\rangle \texttt{)} \\
&& \textit{names} && ::= &\quad && \epsilon\ | \ \textit{name} \ (\ \textbf{\texttt{,}} \ \textit{name}\ )\ \ldots
&& \texttt{linked\_list of } \langle \textit{name}\rangle \\
&& \textit{if-statement} && ::= &\quad && \term{if}\ \textit{expression}_1\ \term{:}\ \textit{block}_1 \\
&& && &\quad && (\ \term{elif}\ \textit{expression}_2\ \term{:}\ \textit{block}_2\ )... \\
&& && &\quad && \term{else}\ \term{:}\ \textit{block}_3
&& \texttt{linked\_list("conditional\_statement", } \langle \textit{expression}_1\rangle \textit{, } \\
&&&&&&&&&\ \ \ \ \ \ \texttt{ } \langle \textit{block}_1\rangle \textit{, } \langle \textit{block}_3\rangle \ \textrm{or}\ \langle \textit{if-statement} \rangle \texttt{)} \\
&& \textit{block} && ::= &\quad && \textit{statement}... \quad
&& \texttt{linked\_list("block", } \langle \textit{statement}\rangle \textit{)} \\
&& \textit{declaration} && ::= &\quad && \textit{name}\ \textbf{\texttt{=}}\ \textit{expression}
&& \texttt{linked\_list("variable\_declaration", } \langle \textit{name}\rangle \textit{, } \langle \textit{expression}\rangle \texttt{)} \\
&& \textit{assignment} && ::= &\quad && \textit{declared\_name}\ \textbf{\texttt{=}}\ \textit{expression}
&& \texttt{linked\_list("assignment", } \langle \textit{declared\_name}\rangle \textit{, } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textit{expression}_1 \textbf{\texttt{[}} \textit{expression}_2 \textbf{\texttt{]}} \ \textbf{\texttt{=}}\ \textit{expression}_3\
&& \texttt{linked\_list("object\_assignment", } \langle \textit{expression}_1 \textbf{\texttt{[}} \textit{expression}_2 \textbf{\texttt{]}} \rangle \textit{, } \langle \textit{expression}_3\rangle \texttt{)}
\end{alignat*}
\begin{alignat*}{9}
&& \textit{expression}. && ::= &\quad && \textit{integer}
&& \texttt{linked\_list("literal",}\ \textit{integer}\texttt{)} \\
&& && | &\quad && \textit{float}
&& \texttt{linked\_list("literal",}\ \textit{float}\texttt{)} \\
&& && | &\quad && \textit{complex}
&& \texttt{linked\_list("literal",}\ \textit{complex}\texttt{)} \\
&& && | &\quad && \term{True}\ |\ \term{False}
&& \texttt{linked\_list("literal",}\ \textit{True}\texttt{)} \\
&& && | &\quad && \term{None}
&& \texttt{linked\_list("literal",}\ \textit{None}\texttt{)} \\
&& && | &\quad && \textit{string}
&& \texttt{linked\_list("literal",}\ \textit{string}\texttt{)} \\
&& && | &\quad && \textit{name}
&& \texttt{linked\_list("name", string)} \\
&& && | &\quad && \textit{expression}_1 \ \textit{log-op} \ \textit{expression}_2 \qquad
&& \texttt{linked\_list("logical\_composition", } \langle \textit{log-op}\rangle \textit{, } \langle \textit{expression}_1\rangle \textit{, } \langle \textit{expression}_2\rangle \texttt{)} \\
&& && | &\quad && \textit{expression}_1 \ \textit{bin-op} \ \textit{expression}_2 \qquad
&& \texttt{linked\_list("binary\_operator\_combination", } \langle \textit{bin-op}\rangle \textit{, } \langle \textit{expression}_1\rangle \textit{, } \langle \textit{expression}_2\rangle \texttt{)} \\
&& && | &\quad && \textit{un-op} \ \textit{expression}
&& \texttt{linked\_list("unary\_operator\_combination", } \langle \textit{un-op}\rangle \textit{, } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textit{expression} \ \textbf{\texttt{(}}\ \textit{expressions}\ \textbf{\texttt{)}}
&& \texttt{linked\_list("application", } \langle \textit{expression}\rangle \textit{, linked\_list of } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{lambda}}\ (\ \textit{name}\ | \ \textit{names}\ )\ \texttt{\textbf{:}}\ \textit{expression}
&& \texttt{linked\_list("lambda\_expression", } \langle \textit{name}\rangle \textit{, } \langle \textit{names}\rangle \texttt{)} \\
&& && | &\quad && \textit{expression}_1 \ \textbf{\texttt{if}}\ \textit{expression}_2 \ \textbf{\texttt{else}}\ \textit{expression}_3\
&& \texttt{linked\_list("conditional\_expression", } \langle \textit{expression}_1\rangle \textit{,} \\
&&&&&&&&&\ \ \ \ \ \ \texttt{ } \langle \textit{expression}_2\rangle \textit{, } \langle \textit{expression}_3\rangle \texttt{)} \\
&& && | &\quad && \textit{expression}_1 \textbf{\texttt{[}}
\textit{expression}_2 \textbf{\texttt{]=}}\ \textit{expression}_3
&& \texttt{linked\_list("list\_assignment", } \langle \textit{expression}_1\rangle \textit{, } \langle \textit{expression}_2\rangle \textit{, } \langle \textit{expression}_3\rangle \texttt{)} \\
&& && | &\quad && \textit{expression}_1 \textbf{\texttt{[}} \textit{expression}_2 \textbf{\texttt{]}}
&& \texttt{linked\_list("list\_access", } \langle \textit{expression}_1\rangle \textit{, } \langle \textit{expression}_2\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{[}}\ \textit{expressions}\ \textbf{\texttt{]}}
&& \texttt{linked\_list("list\_expression", linked\_list of } \langle \textit{expression}\rangle \texttt{)} \\
&& && | &\quad && \textbf{\texttt{(}}\ \textit{expression} \ \textbf{\texttt{)}} && \textrm{parenthesised}\ \textit{expression} \\[1mm]
&& \textit{log-op}. && ::= &\quad && \textbf{\texttt{and}}\ |\ \texttt{\textbf{or}}
&& \textit{string representing operator} \\[1mm]
&& \textit{bin-op} && ::= &\quad && \textbf{\texttt{+}}\ |\ \textbf{\texttt{-}}\ |\ \textbf{\texttt{*}}\ |\ \textbf{\texttt{/}}\ |\ \textbf{\texttt{**}}\ |\ \textbf{\texttt{\%}}\ |\ \textbf{\texttt{is}}\
&& \textit{string representing operator} \\[1mm]
&& && | &\quad && \textbf{\texttt{== }} |\ \texttt{\textbf{!=}}\ |\ \texttt{\textbf{>}}\ |\ \texttt{\textbf{<}}\ |\ \texttt{\textbf{>= }} |\ \texttt{\textbf{<=}}
&& \textit{string representing operator} \\[1mm]
&& \textit{un-op} && ::= &\quad && \textbf{\texttt{not }} |\ \textbf{\texttt{-}}
&& \texttt{"-unary"} \\
&& && | &\quad && \textbf{\texttt{+}}
&& \texttt{"+unary"} \\
&& \textit{expressions} && ::= &\quad && \epsilon\ | \ \textit{expression}\ ( \ \textbf{\texttt{,}} \ \textit{expression} \ )\ \ldots
&& \texttt{linked\_list of } \langle \textit{expression}\rangle \\
\end{alignat*}
\newpage
\KOMAoptions{paper=portrait}
\recalctypearea
% ALIGN EVEN- AND ODD-NUMBERED PAGES.
\evensidemargin 35pt
% HORIZONTAL MARGINS
% Left margin 1 inch (0 + 1)
\setlength{\oddsidemargin}{0in}
% Text width 6.5 inch (so right margin 1 inch).
\setlength{\textwidth}{6.5in}
% ----------------
% VERTICAL MARGINS
% Top margin 0.5 inch (-0.5 + 1)
\setlength{\topmargin}{-0.5in}
% Head height 0.25 inch (where page headers go)
\setlength{\headheight}{0.25in}
% Head separation 0.25 inch (between header and top line of text)
\setlength{\headsep}{0.25in}
% Text height 8.5 inch (so bottom margin 1.5 in)
\setlength{\textheight}{10.0in}