Homework_IV_term/grammar.tex at main · Nigma-Ks/Homework_IV_term · GitHub

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
\documentclass[12pt]{article}
\title{Definition Homework}
\usepackage {amsmath}
\usepackage {amssymb}
\usepackage{enumerate}
\usepackage{cmap}
\usepackage{mathtext}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{indentfirst}

\setlength{\textwidth}{7.0in}
\setlength{\oddsidemargin}{-0.35in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9.0in}
\setlength{\parindent}{0.3in}
\usepackage{alltt}
\begin{document}
\indent
\section{Определение грамматики}
\begin{enumerate}
    \item $\Sigma = \{[a-zA-Z],.,\backslash, let, =, (, ),\backslash n\}$
    \item $N = \{application, definition, defname, term, lambda-abstraction, variable, input\}$
    \item $S = input$
    \item $P:$
        \begin{enumerate} [1)]
            \item $<definition> ::= let <defname> = <term>$.
            \item $<defname> ::= A | B | ... | Z  \{a | b | ... | z | A | B | ... | Z \}$.
            \item $<term> ::= <application> | (<term>) | <lambda-abstraction> | <variable> | <~defname>$
            \item $<variable> ::= a | b | ... | z \{a | b | ... | z | A | B | ... | Z \}$
            \item $<lambda-abstraction> = \backslash<variable>\{<variable>\}.<term>$
            \item $<application> = <term> <term>$
            \item $<input> = \{<definition> \backslash n\} <term>$.
        \end{enumerate}
\end{enumerate}
\section{Пример}
    \begin{verbatim}
        let S = \ x y z.x z (y z)
        let K = \ x y.x
        S K K
    \end{verbatim}
    $$<input> \Rightarrow <definition> \backslash n \{<definition> \backslash n\} <term> \Rightarrow$$
    Первое $definition$:
            \begin{eqnarray}
            <definition>\Rightarrow \\
            let <termname> = <term> \Rightarrow \\
            let\ S = <term> \Rightarrow \\
            let \  S = <lambda-abstraction> \Rightarrow \\
            let \  S = \backslash<variable>\{<variable>\}.<term> \Rightarrow \\
            let \  S = \backslash<variable><variable><variable>.<term> \Rightarrow \\
            let \  S = \backslash x <variable><variable>.<term> \Rightarrow \\
            let \  S = \backslash x y <variable>.<term> \Rightarrow \\
            let \  S = \backslash x y z.<term> \Rightarrow \\
            let \  S = \backslash x y z.<application> \Rightarrow \\
            let \  S = \backslash x y z.<term> <term> \Rightarrow \\
            let \  S = \backslash x y z.<application> <term> \Rightarrow \\
            let \  S = \backslash x y z.<term> <term> <term> \Rightarrow \\
            let \  S = \backslash x y z.<variable> <term> <term> \Rightarrow \\
            let \  S = \backslash x y z.x <term> <term> \Rightarrow \\
            let \  S = \backslash x y z.x <variable> <term> \Rightarrow \\
            let \  S = \backslash x y z.x z <term> \Rightarrow \\
            let \  S = \backslash x y z.x z (<term>) \Rightarrow \\
            let \  S = \backslash x y z.x z (<application>) \Rightarrow \\
            let \  S = \backslash x y z.x z (<term> <term>) \Rightarrow \\
            let \  S = \backslash x y z.x z (<variable> <term>) \Rightarrow \\
            let \  S = \backslash x y z.x z (y <term>) \Rightarrow \\
            let \  S = \backslash x y z.x z (y z) \Rightarrow
        \end{eqnarray}
    Итог:
        \begin{verbatim}
            let S = \ x y z.x z (y z)
        \end{verbatim}
    Второе $definition$:
        \begin{eqnarray}
            <definition>\Rightarrow \\
            let <termname> = <term> \Rightarrow \\
            let \  K = <term> \Rightarrow \\
            let \  K = <lambda-abstraction> \Rightarrow \\
            let \  K = \backslash<variable>\{<variable>\}.<term> \Rightarrow \\
            let \  K = \backslash<variable><variable>.<term> \Rightarrow \\
            let \  K = \backslash x <variable>.<term> \Rightarrow \\
            let \  K = \backslash x y.<term> \Rightarrow \\
            let \  K = \backslash x y z.<variable> \Rightarrow \\
            let \  K = \backslash x y z.x \Rightarrow
        \end{eqnarray}
    Итог:
        \begin{verbatim}
            let S = \ x y z.x z (y z)
            let K = \ x y.x
        \end{verbatim}
    $term$:
        \begin{eqnarray}
            <term>\Rightarrow \\
            <application> \Rightarrow \\
            <term> <term> \Rightarrow \\
            <application> <term>\Rightarrow \\
            <term> <term> <term> \Rightarrow \\
            <defname> <defname> <defname> \Rightarrow \\
            S K K \Rightarrow
        \end{eqnarray}
    Итог:
        \begin{verbatim}
            let S = \ x y z.x z (y z)
            let K = \ x y.x
            S K K
        \end{verbatim}
\end{document}