-
Notifications
You must be signed in to change notification settings - Fork 0
/
lr0epsilonstatemachine.html
126 lines (126 loc) · 6.43 KB
/
lr0epsilonstatemachine.html
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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
<head>
<title>RIPAL: Responsive and Intuitive Parsing for the Analysis of Language</title>
<link href="styles/styles.css" rel="stylesheet" type="text/css" media="all"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
</head>
<body>
<h1>RIPAL: Responsive and Intuitive Parsing for the Analysis of Language</h1>
<h2>Pages</h2>
<nav aria-label="Pages">
<ul>
<li><a href="index.html">Home</a></li>
<li><a href="theory.html">Theory</a></li>
<li><a href="contact.html">Contact</a></li>
</ul>
</nav>
<h2>LR(0) ε state machine</h2>
<div class="section">
<h3>Background</h3>
<p>We've seen all of the constructs involved in performing a closure calculation.</p>
<p>In this section, we will construct our first LR(0) state machine.</p>
</div>
<div class="section">
<h3>Our grammar</h3>
<p>The language we will be analyzing is specified by the following grammar:</p>
<p>
S → ε
</p>
<p>This grammar has the following augmented grammar:</p>
<p>
S' → S $<br/>
S → ε
</p>
</div>
<div class="section">
<h3>Our parse table</h3>
<p>This language has the following LR(0) parse table:</p>
<table class="parsetable">
<tr>
<td></td>
<td>$</td>
<td>S</td>
<td>S'</td>
</tr>
<tr>
<td>state<sub>1</sub></td>
<td>reduce<sub>2</sub></td>
<td>goto<sub>2</sub></td>
<td></td>
</tr>
<tr>
<td>state<sub>2</sub></td>
<td>accept</td>
<td></td>
<td></td>
</tr>
</table>
<p>Parsing input string ε:</p>
<table class="parsetrace">
<tr>
<th>Input queue</th>
<th>Parse stack</th>
<th>Action</th>
</tr>
<tr>
<td></td>
<td>1</td>
<td>reduce<sub>2</sub></td>
</tr>
<tr>
<td></td>
<td>1 S</td>
<td>goto<sub>2</sub></td>
</tr>
<tr>
<td></td>
<td>1 S 2</td>
<td>accept</td>
</tr>
</table>
<p>This parsing procedure corresponds to the following derivation of the empty string (ε):</p>
<div class="derivation">S
→ ε</div>
</div>
<div class="section">
<h3>Initial state</h3>
<p>To begin our parser state machine (DFA) construction, we should first compute our initial closure.</p>
<p>To do so, we qualify our initial production rule by adding a dot at the start of the right-hand side:</p>
<p>S' → · S $</p>
<p>Our initial set of qualified productions is:</p>
<p>{S' → · S $}</p>
<p>Calculating the closure of this set, we end up with:</p>
<p>{S' → · S $, S → · ε, S → ε ·}</p>
<p>Observe here how our initial parse state contains qualified production S → ε ·, which corresponds to the observed parsing behaviour of reducing via the rule S → ε.</p>
<p>We can visualize this initial parse state as:</p>
<img src="assets/epsilondfaparsestate1.png" alt="DFA state 1. This state contains the following productions: S prime produces dot S $, S produces dot ε, S produces ε dot."/>
</div>
<div class="section">
<h3>Extending the DFA</h3>
<p>We've reached the production S → ε in our initial parse state.</p>
<p>However, after we've performed the reduction via the rule S → ε, as shown above, the parser needs to transition into a state to indicate that S has been fully processed.</p>
<p>In particular, we want to reach the qualified production: S → S · $. The corresponding state is:</p>
<img src="assets/epsilondfaparsestate2.png" alt="DFA state 2. This state contains the following production: S prime produces S dot $."/>
<p>There are no additional qualified productions to be reached through a closure here, since our next symbol is $ and not a nonterminal.</p>
<p>Since this state is reached from a goto action corresponding to nonterminal S, we can link our two states with a transition on nonterminal S:</p>
<img src="assets/epsilondfa2parsestates.png" alt="DFA containing two states. State 1 contains the following productions: S prime produces dot S $, S produces dot ε, S produces ε dot. State 2 contains the following production: S prime produces S dot $. State 1 transitions to state 2 on nonterminal symbol S."/>
</div>
<div class="section">
<h3>Handling end of string</h3>
<p>Continuing on with this pattern, we can induce that we want to use the same construct to process the end of string symbol $.</p>
<p>In particular, we want to transition from qualified production S' → S · $ to S' → S $ ·. We can update our DFA to be:</p>
<img src="assets/epsilondfa3parsestates.png" alt="DFA containing three states. State 1 contains the following productions: S prime produces dot S $, S produces dot ε, S produces ε dot. State 2 contains the following production: S prime produces S dot $. State 1 transitions to state 2 on nonterminal symbol S. State 3 contains the following production: S prime produces S $ dot. State 2 transitions to state 3 on end of string symbol $. State 3 is an accepting state."/>
<p>The $ transition here illustrates that we are moving into an accepting state once we reach the end of our input string. Note that state<sub>3</sub> is marked as an accepting state with a double border.</p>
<p>Although state<sub>3</sub> is not explicitly used in our parsing process, we treat the transition to state<sub>3</sub> as the accept action because this state is an accepting state.</p>
</div>
<div class="section">
<h3>Conclusion</h3>
<p>We've seen the LR(0) DFA construction process for a grammar that derives the empty string ε.</p>
<p>Next, we will extend this process to handle a grammar that derives a simple string.</p>
</div>
<hr/>
<p>GitHub Repository: <a href="https://github.com/bprollinson/ripal">https://github.com/bprollinson/ripal</a></p>
<p>Copyright © 2017 Brendan Rollinson-Lorimer</p>
</body>
</html>