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
|
#+TITLE: Assignment Six
#+AUTHOR: Lizzy Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notga \usepackage{ dsfont } \usepackage[utf8]{inputenc} \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
#+LATEX: \setlength\parindent{0pt}
#+LATEX_COMPILER: lualatex
#+OPTIONS: toc:nil
* Question One
\begin{verbatim}
A -> BcDA'
A' -> eD | ε
B -> xBB'
B' -> yD | zD | ε
D -> Z
\end{verbatim}
* Question Two
\begin{verbatim}
A -> wA'
A' -> xA' | yA' | ε
\end{verbatim}
* Question Three
\begin{verbatim}
A -> wA' | yzA'
A' -> xA' | ε
\end{verbatim}
* Question Four
\begin{verbatim}
A -> Bx
B -> Cy | Dz
C -> Awp | z
D -> t
For i = 1, there is no immediate left recursion
When i = 2 there is also no immediate left recursion
When i = 3 we substituted A in C:
A -> Bx
B -> Cy | Dz
C -> Bxwp | z
D -> t
Then B:
A -> Bx
B -> Cy | Dz
C -> Cyxwp | Dzxwp | z
D -> t
And remove the immediate left recursion in C:
A -> Bx
B -> Cy | Dz
C -> Dzxwp | zC'
C' -> yxwpC' | ε
D -> t
When i = 4, there's no left recursion
\end{verbatim}
* Question Five
\begin{verbatim}
A -> Bx | Cy
B -> Cz
C -> Bw | v
When i = 1, no immediate left recursion
When i = 2, no immediate left recursion
When i = 3, we substitute B in C
A -> Bx | Cy
B -> Cz
C -> Czw | v
, which we remove the immediate left recursion from
A -> Bx | Cy
B -> Cz
C -> vC'
C' -> zwC' | ε
\end{verbatim}
* Question Six
\begin{verbatim}
first(A) = first(B) \ ε U first(x) U first(y) = {t, w, u, x, y}
first(B) = first(C) U first(u) U {ε} = {t, w, u, ε}
first(C) = first(t) U first(w) = {t, w}
follow(A) = {$} U follow(B) = {$, x}
follow(B) = {x}
follow(C) = follow(A) U {z} = {$, x, z}
\end{verbatim}
* Question Seven
\begin{verbatim}
first(A) = first(C) = first(E) = {x, z}
first(B) = first(a) U {ε} = {a, ε}
first(C) = first(E) = {x, z}
first(D) = first(b) U {ε} = {b, ε}
first(E) = first(x) U first(z) = {x, z}
follow(A) = {$} U first(y) = {$, y}
follow(B) = follow(A) = {$, y}
follow(C) = first(B) \ ε U follow(B)= {a, $, y}
follow(D) = follow(C) = {a, $, y}
follow(E) = first(D) \ ε U follow(D) = {b, a, $, y}
\end{verbatim}
|
