<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_3_Objectives">
<h2 class="hd hd-2 unit-title">Reading 3 Objectives</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_7394516ed26b">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_7394516ed26b">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h4>Software in 6.005</h4>
<table class="table table-striped no-markdown">
<tbody>
<tr>
<th width="33%">Safe from bugs</th>
<th>Easy to understand</th>
<th>Ready for change</th>
</tr>
<tr>
<td>
Correct today and correct in the unknown future.
</td>
<td>
Communicating clearly with future programmers, including future you.
</td>
<td>
Designed to accommodate change without rewriting.
</td>
</tr>
</tbody>
</table>
<h4>Objectives</h4>
<p>After today's class, you should:</p>
<ul>
<li>Understand the ideas of grammar productions and regular expression operators</li>
<li>Be able to read a grammar or regular expression and determine whether it matches a sequence of characters</li>
<li>Be able to write a grammar or regular expression to match a set of character sequences and parse them into a data structure</li>
</ul>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical-grammars">
<h2 class="hd hd-2 unit-title">Grammars</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_58f13bd7c9ff">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_58f13bd7c9ff">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="introduction">Introduction</h2>
<div data-outline="introduction">
<p>Today's reading introduces several ideas:</p>
<ul>
<li>grammars, with productions, nonterminals, terminals, and operators</li>
<li>regular expressions</li>
</ul>
<p>Some program modules take input or produce output in the form of a sequence of bytes or a sequence of characters, which is called a <em>string</em> when it's simply stored in memory, or a <em>stream</em> when it flows into or out of a module. In today's reading, we talk about how to write a specification for such a sequence. Concretely, a sequence of bytes or characters might be:</p>
<ul>
<li>A file on disk, in which case the specification is called the
<em>file format</em></li>
<li>Messages sent over a network, in which case the specification is a <em>wire protocol</em></li>
<li>A command typed by the user on the console, in which case the specification is a <em>command line interface</em></li>
<li>A string stored in memory</li>
</ul>
<p>For these kinds of sequences, we introduce the notion of a <em>grammar</em>, which allows us not only to distinguish between legal and illegal sequences, but also to parse a sequence into a data structure that a program can work with. The data structure produced from a grammar will often be a recursive data type like we talked about in the <a href="/courses/course-v1:MITx+6.005.2x+1T2017/jump_to_id/vertical-recursive-data-types">recursive data type reading</a>.</p>
<p>We also talk about a specialized form of a grammar called a <em>regular expression</em>. In addition to being used for specification and parsing, regular expressions are a widely-used tool for many string-processing tasks that need to disassemble a string, extract information from it, or transform it.</p>
</div>
<h2 id="grammars">Grammars</h2>
<div data-outline="grammars">
<p>To describe a string of symbols, whether they are bytes, characters, or some other kind of symbol drawn from a fixed set, we use a compact representation called a <em>grammar</em>.</p>
<p>A <em>grammar</em> defines a set of strings. For example, our grammar for URLs will specify the set of strings that are legal URLs in the HTTP protocol.</p>
<p>The literal strings in a grammar are called <em>terminals</em>.
<br> They're called terminals because they are the leaves of a tree that represents the structure of the string. They don't have any children, and can't be expanded any further. We generally write terminals in quotes, like <code>'http'</code> or <code>':'</code>.</p>
<p>A grammar is described by a set of <em>productions</em>, where each production defines a <em>nonterminal</em>. You can think of a nonterminal like a variable that stands for a set of strings, and the production as the definition of that variable in terms of other variables (nonterminals), operators, and constants (terminals). Nonterminals are internal nodes of the tree representing a valid string.</p>
<p>A production in a grammar has the form</p>
<blockquote>
<p>nonterminal ::= expression of terminals, nonterminals, and operators </p>
</blockquote>
<p>In 6.005, we will name nonterminals using lowercase identifiers, like <code>x</code> or <code>y</code> or <code>url</code>.</p>
<p>One of the nonterminals of the grammar is designated as the <em>root</em>. The set of strings that the grammar recognizes are the strings that match the root nonterminal. This nonterminal is often called <code>root</code> or <code>start</code>, but in the grammars below we will typically choose more memorable names like <code>url</code>, <code>html</code>, and <code>markdown</code>.</p>
</div>
<h3 id="grammar_operators">Grammar Operators</h3>
<div data-outline="grammar_operators">
<p>The three most important operators in a production expression are:</p>
<ul>
<li>concatenation</li>
</ul><pre><code class="language-java hljs">x ::= y z an x is a y followed by a z </code></pre>
<ul>
<li>repetition</li>
</ul><pre><code class="language-java hljs">x ::= y* an x is zero or more y </code></pre>
<ul>
<li>union</li>
</ul><pre><code class="language-java hljs">x ::= y | z an x is a y or a z </code></pre>
<p>You can also use additional operators which are just syntactic sugar (i.e., they're equivalent to combinations of the big three operators):</p>
<ul>
<li>option (0 or 1 occurrence)</li>
</ul><pre><code class="language-java hljs">x ::= y? an x is a y or is the empty string</code></pre>
<ul>
<li>1+ repetition (1 or more occurrences)</li>
</ul><pre><code class="language-java hljs">x ::= y+ <span class="hljs-function">an x is one or more <span class="hljs-title">y</span>
<span class="hljs-params">(equivalent to x ::= y y* )</span></span></code></pre>
<ul>
<li>character classes</li>
</ul><pre><code class="language-java hljs">x ::= [abc] is equivalent to x ::= <span class="hljs-string">'a'</span> | <span class="hljs-string">'b'</span> | <span class="hljs-string">'c'</span>
x ::= [^b] is equivalent to x ::= <span class="hljs-string">'a'</span> | <span class="hljs-string">'c'</span> | <span class="hljs-string">'d'</span> | <span class="hljs-string">'e'</span> | <span class="hljs-string">'f'</span>
| ... (all other characters)</code></pre>
<p>By convention, the operators <code>*</code>, <code>?</code>, and <code>+</code> have highest precedence, which means they are applied first. Alternation <code>|</code> has lowest precedence, which means it is applied last. Parentheses can be used to override this precedence, so that a sequence or alternation can be repeated:</p>
<ul>
<li>grouping using parentheses</li>
</ul><pre><code class="language-java hljs">x ::= (y z | a b)* an x is zero or more y-z or a-b pairs</code></pre>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_8b4451da3de5">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Reading_a_Grammar">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Reading_a_Grammar">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-51">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-51">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-reading-a-grammar-51" class="problems-wrapper" role="group"
aria-labelledby="03-reading-a-grammar-51-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-51" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-51/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="3"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-reading-a-grammar-51-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-51-problem-progress" tabindex="-1">
Reading a Grammar 1
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-51-problem-progress"></div>
<div class="problem">
<div>
<p>Consider this grammar:</p>
<pre>
S ::= (B C)* T
B ::= M+ | P B P
C ::= B | E+
</pre>
<p>What are the nonterminals in this grammar? (Note that capitalization and quoting won't give you a clue here, so go by the structure of the grammar alone.)</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-reading-a-grammar-51_2_1">
<fieldset aria-describedby="status_03-reading-a-grammar-51_2_1">
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-reading-a-grammar-51_2_1-choice_0-label" for="input_03-reading-a-grammar-51_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> B
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-reading-a-grammar-51_2_1-choice_1-label" for="input_03-reading-a-grammar-51_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> C
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-reading-a-grammar-51_2_1-choice_2-label" for="input_03-reading-a-grammar-51_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> E
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-reading-a-grammar-51_2_1-choice_3-label" for="input_03-reading-a-grammar-51_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> M
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="03-reading-a-grammar-51_2_1-choice_4-label" for="input_03-reading-a-grammar-51_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> P
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="03-reading-a-grammar-51_2_1-choice_5-label" for="input_03-reading-a-grammar-51_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> S
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="03-reading-a-grammar-51_2_1-choice_6-label" for="input_03-reading-a-grammar-51_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> T
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="03-reading-a-grammar-51_2_1-choice_7-label" for="input_03-reading-a-grammar-51_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> |
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="03-reading-a-grammar-51_2_1-choice_8-label" for="input_03-reading-a-grammar-51_2_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> *
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_9" class="field-input input-checkbox" value="choice_9"/><label id="03-reading-a-grammar-51_2_1-choice_9-label" for="input_03-reading-a-grammar-51_2_1_choice_9" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> +
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_10" class="field-input input-checkbox" value="choice_10"/><label id="03-reading-a-grammar-51_2_1-choice_10-label" for="input_03-reading-a-grammar-51_2_1_choice_10" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> (
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_2_1[]" id="input_03-reading-a-grammar-51_2_1_choice_11" class="field-input input-checkbox" value="choice_11"/><label id="03-reading-a-grammar-51_2_1-choice_11-label" for="input_03-reading-a-grammar-51_2_1_choice_11" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_2_1"> )
</label>
</div>
<span id="answer_03-reading-a-grammar-51_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-reading-a-grammar-51_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-reading-a-grammar-51_solution_1"/>
</div><p>What are the terminals in this grammar?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-reading-a-grammar-51_3_1">
<fieldset aria-describedby="status_03-reading-a-grammar-51_3_1">
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-reading-a-grammar-51_3_1-choice_0-label" for="input_03-reading-a-grammar-51_3_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> B
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-reading-a-grammar-51_3_1-choice_1-label" for="input_03-reading-a-grammar-51_3_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> C
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-reading-a-grammar-51_3_1-choice_2-label" for="input_03-reading-a-grammar-51_3_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> E
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-reading-a-grammar-51_3_1-choice_3-label" for="input_03-reading-a-grammar-51_3_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> M
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="03-reading-a-grammar-51_3_1-choice_4-label" for="input_03-reading-a-grammar-51_3_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> P
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="03-reading-a-grammar-51_3_1-choice_5-label" for="input_03-reading-a-grammar-51_3_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> S
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="03-reading-a-grammar-51_3_1-choice_6-label" for="input_03-reading-a-grammar-51_3_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> T
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="03-reading-a-grammar-51_3_1-choice_7-label" for="input_03-reading-a-grammar-51_3_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> |
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="03-reading-a-grammar-51_3_1-choice_8-label" for="input_03-reading-a-grammar-51_3_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> +
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_9" class="field-input input-checkbox" value="choice_9"/><label id="03-reading-a-grammar-51_3_1-choice_9-label" for="input_03-reading-a-grammar-51_3_1_choice_9" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> *
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_10" class="field-input input-checkbox" value="choice_10"/><label id="03-reading-a-grammar-51_3_1-choice_10-label" for="input_03-reading-a-grammar-51_3_1_choice_10" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> (
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_3_1[]" id="input_03-reading-a-grammar-51_3_1_choice_11" class="field-input input-checkbox" value="choice_11"/><label id="03-reading-a-grammar-51_3_1-choice_11-label" for="input_03-reading-a-grammar-51_3_1_choice_11" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_3_1"> )
</label>
</div>
<span id="answer_03-reading-a-grammar-51_3_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-reading-a-grammar-51_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-reading-a-grammar-51_solution_2"/>
</div><p>Which productions are recursive?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 3" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-reading-a-grammar-51_4_1">
<fieldset aria-describedby="status_03-reading-a-grammar-51_4_1">
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_4_1[]" id="input_03-reading-a-grammar-51_4_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-reading-a-grammar-51_4_1-choice_0-label" for="input_03-reading-a-grammar-51_4_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_4_1"> S
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_4_1[]" id="input_03-reading-a-grammar-51_4_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-reading-a-grammar-51_4_1-choice_1-label" for="input_03-reading-a-grammar-51_4_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_4_1"> B
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-51_4_1[]" id="input_03-reading-a-grammar-51_4_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-reading-a-grammar-51_4_1-choice_2-label" for="input_03-reading-a-grammar-51_4_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-51_4_1"> C
</label>
</div>
<span id="answer_03-reading-a-grammar-51_4_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-reading-a-grammar-51_4_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-reading-a-grammar-51_solution_3"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Reading a Grammar 1" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-reading-a-grammar-51" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-reading-a-grammar-51">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-51-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-51-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-51-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-2" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-52">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-52">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-reading-a-grammar-52" class="problems-wrapper" role="group"
aria-labelledby="03-reading-a-grammar-52-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-52" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-52/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-reading-a-grammar-52-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-52-problem-progress" tabindex="-1">
Reading a Grammar 2
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-52-problem-progress"></div>
<div class="problem">
<div>
<p>Which strings match the root nonterminal of this grammar?</p>
<pre>
root ::= 'a'+ 'b'* 'c'?
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-reading-a-grammar-52_2_1">
<fieldset aria-describedby="status_03-reading-a-grammar-52_2_1">
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-52_2_1[]" id="input_03-reading-a-grammar-52_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-reading-a-grammar-52_2_1-choice_0-label" for="input_03-reading-a-grammar-52_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-52_2_1"> aabcc
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-52_2_1[]" id="input_03-reading-a-grammar-52_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-reading-a-grammar-52_2_1-choice_1-label" for="input_03-reading-a-grammar-52_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-52_2_1"> bbbc
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-52_2_1[]" id="input_03-reading-a-grammar-52_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-reading-a-grammar-52_2_1-choice_2-label" for="input_03-reading-a-grammar-52_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-52_2_1"> aaaaaaaa
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-52_2_1[]" id="input_03-reading-a-grammar-52_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-reading-a-grammar-52_2_1-choice_3-label" for="input_03-reading-a-grammar-52_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-52_2_1"> abc
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-52_2_1[]" id="input_03-reading-a-grammar-52_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="03-reading-a-grammar-52_2_1-choice_4-label" for="input_03-reading-a-grammar-52_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-52_2_1"> abab
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-52_2_1[]" id="input_03-reading-a-grammar-52_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="03-reading-a-grammar-52_2_1-choice_5-label" for="input_03-reading-a-grammar-52_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-52_2_1"> aac
</label>
</div>
<span id="answer_03-reading-a-grammar-52_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-reading-a-grammar-52_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-reading-a-grammar-52_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Reading a Grammar 2" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-reading-a-grammar-52" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-reading-a-grammar-52">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-52-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-52-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-52-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-3" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-53">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-53">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-reading-a-grammar-53" class="problems-wrapper" role="group"
aria-labelledby="03-reading-a-grammar-53-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-53" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-53/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-reading-a-grammar-53-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-53-problem-progress" tabindex="-1">
Reading a Grammar 3
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-53-problem-progress"></div>
<div class="problem">
<div>
<p>Which strings match the root nonterminal of this grammar?</p>
<pre>
root ::= (A B)+
A ::= [Aa]
B ::= [Bb]
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-reading-a-grammar-53_2_1">
<fieldset aria-describedby="status_03-reading-a-grammar-53_2_1">
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-53_2_1[]" id="input_03-reading-a-grammar-53_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-reading-a-grammar-53_2_1-choice_0-label" for="input_03-reading-a-grammar-53_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-53_2_1"> aaaBBB
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-53_2_1[]" id="input_03-reading-a-grammar-53_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-reading-a-grammar-53_2_1-choice_1-label" for="input_03-reading-a-grammar-53_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-53_2_1"> abababab
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-53_2_1[]" id="input_03-reading-a-grammar-53_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-reading-a-grammar-53_2_1-choice_2-label" for="input_03-reading-a-grammar-53_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-53_2_1"> aBAbabAB
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-53_2_1[]" id="input_03-reading-a-grammar-53_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-reading-a-grammar-53_2_1-choice_3-label" for="input_03-reading-a-grammar-53_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-53_2_1"> AbAbAbA
</label>
</div>
<span id="answer_03-reading-a-grammar-53_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-reading-a-grammar-53_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-reading-a-grammar-53_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Reading a Grammar 3" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-reading-a-grammar-53" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-reading-a-grammar-53">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-53-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-53-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-53-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
<div class="vert vert-4" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-54">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-54">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-reading-a-grammar-54" class="problems-wrapper" role="group"
aria-labelledby="03-reading-a-grammar-54-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-54" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-54/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-reading-a-grammar-54-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-54-problem-progress" tabindex="-1">
Reading a Grammar 4
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-reading-a-grammar-54-problem-progress"></div>
<div class="problem">
<div>
<p>Which strings match the root nonterminal of this grammar?</p>
<pre>
root ::= integer ('-' integer)+
integer ::= [0-9]+
</pre>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-reading-a-grammar-54_2_1">
<fieldset aria-describedby="status_03-reading-a-grammar-54_2_1">
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-reading-a-grammar-54_2_1-choice_0-label" for="input_03-reading-a-grammar-54_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> 617
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-reading-a-grammar-54_2_1-choice_1-label" for="input_03-reading-a-grammar-54_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> 617-253
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-reading-a-grammar-54_2_1-choice_2-label" for="input_03-reading-a-grammar-54_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> 617-253-1000
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-reading-a-grammar-54_2_1-choice_3-label" for="input_03-reading-a-grammar-54_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> ---
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="03-reading-a-grammar-54_2_1-choice_4-label" for="input_03-reading-a-grammar-54_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> integer-integer-integer
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="03-reading-a-grammar-54_2_1-choice_5-label" for="input_03-reading-a-grammar-54_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> 5--5
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-reading-a-grammar-54_2_1[]" id="input_03-reading-a-grammar-54_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="03-reading-a-grammar-54_2_1-choice_6-label" for="input_03-reading-a-grammar-54_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_03-reading-a-grammar-54_2_1"> 3-6-293-1
</label>
</div>
<span id="answer_03-reading-a-grammar-54_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-reading-a-grammar-54_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-reading-a-grammar-54_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Reading a Grammar 4" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-reading-a-grammar-54" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-reading-a-grammar-54">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-54-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-54-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-reading-a-grammar-54-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Example_URL">
<h2 class="hd hd-2 unit-title">Example: URL</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_e8e0d496467c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_e8e0d496467c">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h3 id="example_url">Example: URL</h3>
<div data-outline="example_url">
<p>Suppose we want to write a grammar that represents URLs. Let's build up a grammar gradually by starting with simple examples and extending the grammar as we go.</p>
<p>Here's a simple URL:</p><pre><code class="language-python hljs">http://mit.edu/</code></pre>
<p>A grammar that represents the set of sentences containing <em>only this URL</em> would look like:</p><pre><code class="language-python hljs">url ::= <span class="hljs-string">'http://mit.edu/'</span></code></pre>
<p>But let's generalize it to capture other domains, as well:</p><pre><code class="language-python hljs">http://stanford.edu/
http://google.com/</code></pre>
<p>We can write this as one line, like this:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/95317c9515fd6724787a092f9a6ed884/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/03-url-simple.png" width="200px" alt="the parse tree produced by parsing 'http://mit.edu' with the one-line URL grammar"></div><pre><code class="language-python hljs">url ::= <span class="hljs-string">'http://'</span> [a-z]+ <span class="hljs-string">'.'</span> [a-z]+ <span class="hljs-string">'/'</span></code></pre>
<p>This grammar represents the set of all URLs that consist of just a two-part hostname, where each part of the hostname consists of 1 or more letters. So <code>http://mit.edu/</code> and <code>http://yahoo.com/</code> would match, but not <code>http://ou812.com/</code>. Since it has only one nonterminal, a <em>parse tree</em> for this URL grammar would look like the picture on the right.</p>
<div class="clearfix"></div>
<p>In this one-line form, with a single nonterminal whose production uses only operators and terminals, a grammar is called a <em>regular expression</em> (more about that later). But it will be easier to understand if we name the parts using new nonterminals:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/16f0cbb067dc7983270246657cf0aa39/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/03-url-with-hostname.png" width="250px" alt="the parse tree produced by parsing 'http://mit.edu' with a grammar with url, hostname, and word nonterminals"></div><pre><code class="language-python hljs">url ::= <span class="hljs-string">'http://'</span> hostname <span class="hljs-string">'/'</span>
hostname ::= word <span class="hljs-string">'.'</span> word
word ::= [a-z]+</code></pre>
<p>The parse tree for this grammar is now shown at right. The tree has more structure now. The leaves of the tree are the parts of the string that have been parsed. If we concatenated the leaves together, we would recover the original string. The <code>hostname</code> and <code>word</code> nonterminals are labeling nodes of the tree whose subtrees match those rules in the grammar. Notice that the immediate children of a nonterminal node like <code>hostname</code> follow the pattern of the <code>hostname</code> rule, <code>word '.' word</code>.</p>
<div class="clearfix"></div>
<p>How else do we need to generalize? Hostnames can have more than two components, and there can be an optional port number:</p><pre><code class="language-python hljs">http://didit.csail.mit.edu:<span class="hljs-number">4949</span>/</code></pre>
<p>To handle this kind of string, the grammar is now:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/6d8d26f69dd17e6a8c09f2821b638612/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/03-url-with-recursive-hostname.png" width="300px" alt="the parse tree produced by parsing 'http://mit.edu' with a grammar with a recursive hostname rule"></div><pre><code class="language-python hljs">url ::= <span class="hljs-string">'http://'</span> hostname (<span class="hljs-string">':'</span> port)? <span class="hljs-string">'/'</span>
hostname ::= word <span class="hljs-string">'.'</span> hostname | word <span class="hljs-string">'.'</span> word
port ::= [<span class="hljs-number">0</span>-<span class="hljs-number">9</span>]+
word ::= [a-z]+</code></pre>
<p><em>Notice how hostname is now defined recursively in terms of itself.</em> Which part of the hostname definition is the base case, and which part is the recursive step? What kinds of hostnames are allowed?</p>
<p>Using the repetition operator, we could also write hostname like this:</p><pre><code class="language-python hljs">hostname ::= (word <span class="hljs-string">'.'</span>)+ word</code></pre>
<p>Another thing to observe is that this grammar allows port numbers that are not technically legal, since port numbers can only range from 0 to 65535. We could write a more complex definition of port that would allow only these integers, but that's not typically done in a grammar. Instead, the constraint 0 <= port <= 65535 would be specified in the program that uses the grammar.</p>
<p>There are more things we should do to go farther:</p>
<ul>
<li>generalizing <code>http</code> to support the additional protocols that URLs can have</li>
<li>generalizing the <code>/</code> at the end to a slash-separated path</li>
<li>allowing hostnames with the full set of legal characters instead of just a-z</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_ed4068f9cebc">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Writing_a_Grammar">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Writing_a_Grammar">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-writing-a-grammar-56">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-writing-a-grammar-56">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-writing-a-grammar-56" class="problems-wrapper" role="group"
aria-labelledby="03-writing-a-grammar-56-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-writing-a-grammar-56" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-writing-a-grammar-56/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-writing-a-grammar-56-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-writing-a-grammar-56-problem-progress" tabindex="-1">
Writing a Grammar
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-writing-a-grammar-56-problem-progress"></div>
<div class="problem">
<div>
<p>Consider the grammar from the reading:</p>
<pre>
url ::= 'http://' hostname (':' port)? '/'
hostname ::= word '.' hostname | word '.' word
port ::= [0-9]+
word ::= [a-z]+
</pre>
<p>Suppose we want this grammar to also match strings of the form:</p>
<pre>
https://websis.mit.edu/
ftp://ftp.athena.mit.edu/
</pre>
<p>but not strings of the form:</p>
<pre>
ptth://web.mit.edu/
mailto:bitdiddle@mit.edu
</pre>
<p>So we change the grammar to:</p>
<pre>
url ::= protocol '://' hostname (':' port)? '/'
protocol ::= TODO
hostname ::= word '.' hostname | word '.' word
port ::= [0-9]+
word ::= [a-z]+
</pre>
<p>What could you put in place of TODO to match the desirable URLs but not the undesirable ones?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-writing-a-grammar-56_2_1">
<fieldset aria-describedby="status_03-writing-a-grammar-56_2_1">
<div class="field">
<input type="checkbox" name="input_03-writing-a-grammar-56_2_1[]" id="input_03-writing-a-grammar-56_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-writing-a-grammar-56_2_1-choice_0-label" for="input_03-writing-a-grammar-56_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-writing-a-grammar-56_2_1"> word
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-writing-a-grammar-56_2_1[]" id="input_03-writing-a-grammar-56_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-writing-a-grammar-56_2_1-choice_1-label" for="input_03-writing-a-grammar-56_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-writing-a-grammar-56_2_1"> 'ftp' | 'http' | 'https'
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-writing-a-grammar-56_2_1[]" id="input_03-writing-a-grammar-56_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-writing-a-grammar-56_2_1-choice_2-label" for="input_03-writing-a-grammar-56_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-writing-a-grammar-56_2_1"> ('http' 's'?) | 'ftp'
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-writing-a-grammar-56_2_1[]" id="input_03-writing-a-grammar-56_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-writing-a-grammar-56_2_1-choice_3-label" for="input_03-writing-a-grammar-56_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-writing-a-grammar-56_2_1"> ('f' | 'ht') 'tp' 's'?
</label>
</div>
<span id="answer_03-writing-a-grammar-56_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-writing-a-grammar-56_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-writing-a-grammar-56_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Writing a Grammar" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-writing-a-grammar-56" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-writing-a-grammar-56">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-writing-a-grammar-56-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-writing-a-grammar-56-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-writing-a-grammar-56-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Example_Markdown_and_HTML">
<h2 class="hd hd-2 unit-title">Example: Markdown and HTML</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_473c01ca9bcf">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_473c01ca9bcf">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h3 id="example_markdown_and_html">Example: Markdown and HTML</h3>
<div data-outline="example_markdown_and_html">
<p>Now let's look at grammars for some file formats. We'll be using two different markup languages that represent typographic style in text. Here they are:</p>
<h4>Markdown</h4><pre><code class="language-java hljs">This is _italic_.</code></pre>
<h4>HTML</h4><pre><code class="language-java hljs">Here is an <i>italic</i> word.</code></pre>
<p>For simplicity, our example HTML and Markdown grammars will only specify italics, but other text styles are of course possible.</p>
<p>Here's the grammar for our simplified version of Markdown:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/a4941c6b4ba25dfcf8342f920c773dca/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/03-markdown.png" width="300px" alt="a parse tree produced by the Markdown grammar"></div><pre><code class="hljs makefile"><span class="hljs-constant">markdown</span> ::= ( normal | italic ) *
<span class="hljs-constant">italic</span> ::= '_' normal '_'
<span class="hljs-constant">normal</span> ::= text
<span class="hljs-constant">text</span> ::= [^_]*</code></pre>
<div class="clearfix"></div>
<p>Here's the grammar for our simplified version of HTML:</p>
<div class="panel panel-figure pull-right pull-margin"><img src="/assets/courseware/v1/b850a69e52431d714292823ddeb1a99f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/03-html.png" width="350px" alt="a parse tree produced by the HTML grammar"></div><pre><code class="hljs makefile"><span class="hljs-constant">html</span> ::= ( normal | italic ) *
<span class="hljs-constant">italic</span> ::= '<i>' html '</i>'
<span class="hljs-constant">normal</span> ::= text
<span class="hljs-constant">text</span> ::= [^<>]*</code></pre>
<div class="clearfix"></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_3c9879f40f04">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_Productions">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Recursive_Productions">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-recursive-productions-54">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-recursive-productions-54">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-recursive-productions-54" class="problems-wrapper" role="group"
aria-labelledby="03-recursive-productions-54-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-recursive-productions-54" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-recursive-productions-54/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="2"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-recursive-productions-54-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-recursive-productions-54-problem-progress" tabindex="-1">
Recursive Grammars
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-recursive-productions-54-problem-progress"></div>
<div class="problem">
<div>
<p>Recall these grammars from the reading:</p>
<pre>
markdown ::= ( normal | italic ) *
italic ::= '_' normal '_'
normal ::= text
text ::= [^_]*
</pre>
<pre>
html ::= ( normal | italic ) *
italic ::= '&lt;i&gt;' html '&lt;/i&gt;'
normal ::= text
text ::= [^&lt;&gt;]*
</pre>
<p>Look carefully at the <i>italic</i> productions in these grammars, and notice that not only do they differ in delimiters (underscores vs. &lt; &gt; tags), but also in the nonterminal that is matched between those delimiters. One grammar is recursive; the other grammar is not.</p>
<p>For each string below, if you match the specified grammar against it, which letters are inside matches to the italic nonterminal? Your answer should be some subset of the letters abcde.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_03-recursive-productions-54_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<label class="problem-group-label" for="input_03-recursive-productions-54_2_1" id="label_03-recursive-productions-54_2_1">markdown: a_b_c_d_e</label>
<input type="text" name="input_03-recursive-productions-54_2_1" id="input_03-recursive-productions-54_2_1" aria-describedby="status_03-recursive-productions-54_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_03-recursive-productions-54_2_1"/>
<span class="status unanswered" id="status_03-recursive-productions-54_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_03-recursive-productions-54_2_1" class="answer"/>
</div>
</div></div>
<p>html: a&lt;i&gt;b&lt;i&gt;c&lt;/i&gt;d&lt;/i&gt;e</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 2" role="group"><div id="inputtype_03-recursive-productions-54_3_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_03-recursive-productions-54_3_1" id="input_03-recursive-productions-54_3_1" aria-describedby="status_03-recursive-productions-54_3_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_03-recursive-productions-54_3_1"/>
<span class="status unanswered" id="status_03-recursive-productions-54_3_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_03-recursive-productions-54_3_1" class="answer"/>
</div>
</div></div>
</div>
<div class="action">
<input type="hidden" name="problem_id" value="Recursive Grammars" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-recursive-productions-54" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-recursive-productions-54">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-recursive-productions-54-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-recursive-productions-54-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-recursive-productions-54-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Regular_Expressions">
<h2 class="hd hd-2 unit-title">Regular Expressions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_194fc254774c">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_194fc254774c">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="regular_expressions">Regular Expressions</h2>
<div data-outline="regular_expressions">
<p>A <em>regular</em> grammar has a special property: by substituting every nonterminal (except the root one) with its righthand side, you can reduce it down to a single production for the root, with only terminals and operators on the right-hand side.</p>
<p>Our URL grammar was regular. By replacing nonterminals with their productions, it can be reduced to a single expression:</p><pre><code class="hljs css"><span class="hljs-rule"><span class="hljs-attribute">url </span>:<span class="hljs-value">:= <span class="hljs-string">'http://'</span> ([a-z]+ <span class="hljs-string">'.'</span>)+ [a-z]+ (<span class="hljs-string">':'</span> [<span class="hljs-number">0</span>-<span class="hljs-number">9</span>]+)? <span class="hljs-string">'/'</span> </span></span></code></pre>
<p>The Markdown grammar is also regular:</p><pre><code class="hljs css"><span class="hljs-rule"><span class="hljs-attribute">markdown </span>:<span class="hljs-value">:= ([^_]* | <span class="hljs-string">'_'</span> [^_]* <span class="hljs-string">'_'</span> )*</span></span></code></pre>
<p>But our HTML grammar can't be reduced completely. By substituting righthand sides for nonterminals, you can eventually reduce it to something like this:</p><pre><code class="hljs css"><span class="hljs-rule"><span class="hljs-attribute">html </span>:<span class="hljs-value">:= ( [^<>]* | <span class="hljs-string">'<i>'</span> html <span class="hljs-string">'</i>'</span> ) *</span></span></code></pre>
<p>…but the recursive use of <code>html</code> on the righthand side can't be eliminated, and can't be simply replaced by a repetition operator either. So the HTML grammar is not regular.</p>
<p>The reduced expression of terminals and operators can be written in an even more compact form, called a <em>regular expression</em>. A regular expression does away with the quotes around the terminals, and the spaces between terminals and operators, so that it consists just of terminal characters, parentheses for grouping, and operator characters. For example, the regular expression for our <code>markdown</code> format is just</p><pre><code class="language-python hljs">([^_]*|_[^_]*_)*</code></pre>
<p>Regular expressions are also called <em>regexes</em> for short. A regex is far less readable than the original grammar, because it lacks the nonterminal names that documented the meaning of each subexpression. But a regex is fast to implement, and there are libraries in many programming languages that support regular expressions.</p>
<p>The regex syntax commonly implemented in programming language libraries has a few more special operators, in addition to the ones we used above in grammars. Here's are some common useful ones:</p><pre><code class="language-python hljs">. any single character
\d any digit, same <span class="hljs-keyword">as</span> [<span class="hljs-number">0</span>-<span class="hljs-number">9</span>]
\s any whitespace character, including space, tab, newline
\w any word character, including letters <span class="hljs-keyword">and</span> digits
\., \(, \), \*, \+, ...
escapes an operator <span class="hljs-keyword">or</span> special character so that it matches literally</code></pre>
<p>Using backslashes is important whenever there are terminal characters that would be confused with special characters. Because our <code>url</code> regular expression has <code>.</code> in it as a terminal, we need to use a backslash to escape it:</p><pre><code class="language-python hljs">http://([a-z]+\.)+[a-z]+(:[<span class="hljs-number">0</span>-<span class="hljs-number">9</span>]+)?/</code></pre>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_2e3aa8625ef7">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Regular_Expressions">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Regular_Expressions">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-regular-expressions-55">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-regular-expressions-55">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-regular-expressions-55" class="problems-wrapper" role="group"
aria-labelledby="03-regular-expressions-55-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-regular-expressions-55" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-regular-expressions-55/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-regular-expressions-55-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-regular-expressions-55-problem-progress" tabindex="-1">
Regular Expressions
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-regular-expressions-55-problem-progress"></div>
<div class="problem">
<div>
<p>Consider the following regular expression.
Assume the regular expression syntax described in this reading, in which <code>^</code> is not a special character unless it's inside square brackets.</p>
<pre>
[a-g]+(_|^)?
</pre>
<p>Which of the following strings match this regular expression?</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_03-regular-expressions-55_2_1">
<fieldset aria-describedby="status_03-regular-expressions-55_2_1">
<div class="field">
<input type="checkbox" name="input_03-regular-expressions-55_2_1[]" id="input_03-regular-expressions-55_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="03-regular-expressions-55_2_1-choice_0-label" for="input_03-regular-expressions-55_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_03-regular-expressions-55_2_1"> a_
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-regular-expressions-55_2_1[]" id="input_03-regular-expressions-55_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="03-regular-expressions-55_2_1-choice_1-label" for="input_03-regular-expressions-55_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_03-regular-expressions-55_2_1"> c^
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-regular-expressions-55_2_1[]" id="input_03-regular-expressions-55_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="03-regular-expressions-55_2_1-choice_2-label" for="input_03-regular-expressions-55_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_03-regular-expressions-55_2_1"> abk_
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-regular-expressions-55_2_1[]" id="input_03-regular-expressions-55_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="03-regular-expressions-55_2_1-choice_3-label" for="input_03-regular-expressions-55_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_03-regular-expressions-55_2_1"> a_b
</label>
</div>
<div class="field">
<input type="checkbox" name="input_03-regular-expressions-55_2_1[]" id="input_03-regular-expressions-55_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="03-regular-expressions-55_2_1-choice_4-label" for="input_03-regular-expressions-55_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_03-regular-expressions-55_2_1"> gfe
</label>
</div>
<span id="answer_03-regular-expressions-55_2_1"/>
</fieldset>
<div class="indicator-container">
<span class="status unanswered" id="status_03-regular-expressions-55_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-regular-expressions-55_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Regular Expressions" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-regular-expressions-55" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-regular-expressions-55">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-regular-expressions-55-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-regular-expressions-55-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-regular-expressions-55-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Using_Regular_Expressions_in_Java">
<h2 class="hd hd-2 unit-title">Using Regular Expressions in Java</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3349bcdf1a92">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3349bcdf1a92">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h3 id="using_regular_expressions_in_java">Using regular expressions in Java</h3>
<div data-outline="using_regular_expressions_in_java">
<p>Regular expressions (“regexes”) are widely used in programming, and you should have them in your toolbox.</p>
<p>In Java, you can use regexes for manipulating strings (see <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#split-java.lang.String-">String.split</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/lang/String.html#matches-java.lang.String-">String.matches</a>, <a href="https://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html">java.util.regex.Pattern</a>). They're built-in as a first-class feature of modern scripting languages like Python, Ruby, and Javascript, and you can use them in many text editors for find and replace. Regular expressions are your friend! Most of the time. Here are some examples.</p>
<p>Replace all runs of spaces with a single space:</p><pre><code class="language-java hljs">String singleSpacedString = string.replaceAll(<span class="hljs-string">" +"</span>, <span class="hljs-string">" "</span>);</code></pre>
<p>Match a URL:</p><pre><code class="language-java hljs">Pattern regex = Pattern.compile(<span class="hljs-string">"http://([a-z]+\\.)+[a-z]+(:[0-9]+)?/"</span>);
Matcher m = regex.matcher(string);
<span class="hljs-keyword">if</span> (m.matches()) {
<span class="hljs-comment">// then string is a url</span>
}</code></pre>
<p>Extract part of an HTML tag:</p><pre><code class="language-java hljs">Pattern regex = Pattern.compile(<span class="hljs-string">"<a href=['\"]([^'\"]*)['\"]>"</span>);
Matcher m = regex.matcher(string);
<span class="hljs-keyword">if</span> (m.matches()) {
String url = m.group(<span class="hljs-number">1</span>);
<span class="hljs-comment">// Matcher.group(n) returns the nth parenthesized part of the regex</span>
}</code></pre>
<p>Notice the backslashes in the URL and HTML tag examples. In the URL example, we want to match a literal period <code>.</code>, so we have to first escape it as <code>\.</code> to protect it from being interpreted as the regex match-any-character operator, and then we have to further escape it as <code>\\.</code> to protect the backslash from being interpreted as a Java string escape character. In the HTML example, we have to escape the quote mark <code>"</code> as <code>\"</code> to keep it from ending the string. The frequency of backslash escapes makes regexes still less readable.</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@vertical_Questions_ed01b6f65a65">
<h2 class="hd hd-2 unit-title">Questions</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Using_Regular_Expressions_in_Java">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@Using_Regular_Expressions_in_Java">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<script src="/assets/courseware/v1/c9cee8830885f59e75b8782f44026226/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/edx-script-v1.js"></script>
</div>
</div>
<div class="vert vert-1" data-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-using-regular-expressions-in-java">
<div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-has-score="True" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="problem" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-using-regular-expressions-in-java">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "Problem"}
</script>
<div id="problem_03-using-regular-expressions-in-java" class="problems-wrapper" role="group"
aria-labelledby="03-using-regular-expressions-in-java-problem-title"
data-problem-id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-using-regular-expressions-in-java" data-url="/courses/course-v1:MITx+6.005.2x+1T2017/xblock/block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-using-regular-expressions-in-java/handler/xmodule_handler"
data-problem-score="0"
data-problem-total-possible="1"
data-attempts-used="0"
data-content="
<h3 class="hd hd-3 problem-header" id="03-using-regular-expressions-in-java-problem-title" aria-describedby="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-using-regular-expressions-in-java-problem-progress" tabindex="-1">
Using regexes in Java
</h3>
<div class="problem-progress" id="block-v1:MITx+6.005.2x+1T2017+type@problem+block@03-using-regular-expressions-in-java-problem-progress"></div>
<div class="problem">
<div>
<p>Write the shortest regex you can to remove single-word, lowercase-letter-only HTML tags from a string:</p>
<pre><code class="language-java hljs">
String input = <span class="hljs-string">"The &lt;b&gt;Good&lt;/b&gt;, the &lt;i&gt;Bad&lt;/i&gt;, and the &lt;strong&gt;Ugly&lt;/strong&gt;"</span>;
String regex = <span class="hljs-string">"TODO"</span>;
String output = input.replaceAll(regex, <span class="hljs-string">""</span>);</code></pre>
<p>If the desired output is <code>"The Good, the Bad, and the Ugly"</code>, what is shortest regex you can put in place of TODO? You may find it useful to <a href="http://www.pythontutor.com/java.html#code=public+class+Regex+%7B%0A++++public+static+void+main(String%5B%5D+args%29+%7B%0A++++++++String+input+%3D+%22The+%3Cb%3EGood%3C/b%3E,+the+%3Ci%3EBad%3C/i%3E,+and+the+%3Cstrong%3EUgly%3C/strong%3E%22%3B+%0A++++++++String+regex+%3D+%22TODO%22%3B%0A++++++++String+output+%3D+input.replaceAll(regex,+%22%22%29%3B%0A++++++++System.out.println(output%29%3B%0A++++%7D%0A%7D&amp;mode=edit&amp;origin=opt-frontend.js&amp;cumulative=false&amp;heapPrimitives=false&amp;textReferences=false&amp;py=java&amp;rawInputLstJSON=%5B%5D">run this example in the Online Java Tutor</a>.</p>
<div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="inputtype_03-using-regular-expressions-in-java_2_1" class=" capa_inputtype textline">
<div class="unanswered ">
<input type="text" name="input_03-using-regular-expressions-in-java_2_1" id="input_03-using-regular-expressions-in-java_2_1" aria-describedby="status_03-using-regular-expressions-in-java_2_1" value="" size="20"/>
<span class="trailing_text" id="trailing_text_03-using-regular-expressions-in-java_2_1"/>
<span class="status unanswered" id="status_03-using-regular-expressions-in-java_2_1" data-tooltip="Not yet answered.">
<span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/>
</span>
<p id="answer_03-using-regular-expressions-in-java_2_1" class="answer"/>
</div>
</div></div>
<div class="solution-span">
<span id="solution_03-using-regular-expressions-in-java_solution_1"/>
</div></div>
<div class="action">
<input type="hidden" name="problem_id" value="Using regexes in Java" />
<div class="submit-attempt-container">
<button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_03-using-regular-expressions-in-java" >
<span class="submit-label">Submit</span>
</button>
<div class="submission-feedback" id="submission_feedback_03-using-regular-expressions-in-java">
<span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span>
</div>
</div>
<div class="problem-action-buttons-wrapper">
</div>
</div>
<div class="notification warning notification-gentle-alert
is-hidden"
tabindex="-1">
<span class="icon fa fa-exclamation-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-using-regular-expressions-in-java-problem-title">
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification warning notification-save
is-hidden"
tabindex="-1">
<span class="icon fa fa-save" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-using-regular-expressions-in-java-problem-title">None
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
<div class="notification general notification-show-answer
is-hidden"
tabindex="-1">
<span class="icon fa fa-info-circle" aria-hidden="true"></span>
<span class="notification-message" aria-describedby="03-using-regular-expressions-in-java-problem-title">Answers are displayed within the problem
</span>
<div class="notification-btn-wrapper">
<button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button>
</div>
</div>
</div>
"
data-graded="True">
<p class="loading-spinner">
<i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i>
<span class="sr">Loading…</span>
</p>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Context-Free_Grammars">
<h2 class="hd hd-2 unit-title">Context-Free Grammars</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_12ed15766a67">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_12ed15766a67">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h3 id="context-free_grammars">Context-Free Grammars</h3>
<div data-outline="context-free_grammars">
<p>In general, a language that can be expressed with our system of grammars is called context-free. Not all context-free languages are also regular; that is, some grammars can't be reduced to single nonrecursive productions. Our HTML grammar is context-free but not regular.</p>
<p>The grammars for most programming languages are also context-free. In general, any language with nested structure (like nesting parentheses or braces) is context-free but not regular. That description applies to the Java grammar, shown here in part:</p><pre><code class="hljs css"><span class="hljs-rule"><span class="hljs-attribute">statement </span>:<span class="hljs-value">:=
<span class="hljs-string">'{'</span> statement* <span class="hljs-string">'}'</span>
| <span class="hljs-string">'if'</span> <span class="hljs-string">'('</span> expression <span class="hljs-string">')'</span> statement (<span class="hljs-string">'else'</span> statement)?
| <span class="hljs-string">'for'</span> <span class="hljs-string">'('</span> forinit? <span class="hljs-string">';'</span> expression? <span class="hljs-string">';'</span> forupdate? <span class="hljs-string">')'</span> statement
| <span class="hljs-string">'while'</span> <span class="hljs-string">'('</span> expression <span class="hljs-string">')'</span> statement
| <span class="hljs-string">'do'</span> statement <span class="hljs-string">'while'</span> <span class="hljs-string">'('</span> expression <span class="hljs-string">')'</span> <span class="hljs-string">';'</span>
| <span class="hljs-string">'try'</span> <span class="hljs-string">'{'</span> statement* <span class="hljs-string">'}'</span> ( catches | catches? <span class="hljs-string">'finally'</span> <span class="hljs-string">'{'</span> statement* <span class="hljs-string">'}'</span> )
| <span class="hljs-string">'switch'</span> <span class="hljs-string">'('</span> expression <span class="hljs-string">')'</span> <span class="hljs-string">'{'</span> switchgroups <span class="hljs-string">'}'</span>
| <span class="hljs-string">'synchronized'</span> <span class="hljs-string">'('</span> expression <span class="hljs-string">')'</span> <span class="hljs-string">'{'</span> statement* <span class="hljs-string">'}'</span>
| <span class="hljs-string">'return'</span> expression? <span class="hljs-string">';'</span>
| <span class="hljs-string">'throw'</span> expression <span class="hljs-string">';'</span>
| <span class="hljs-string">'break'</span> identifier? <span class="hljs-string">';'</span>
| <span class="hljs-string">'continue'</span> identifier? <span class="hljs-string">';'</span>
| expression <span class="hljs-string">';'</span>
| identifier <span class="hljs-string">':'</span> statement
| <span class="hljs-string">';'</span></span></span></code></pre></div>
</div>
</div>
</div>
</div>
</div>
<div class="xblock xblock-public_view xblock-public_view-vertical" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="vertical" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="VerticalStudentView" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@vertical+block@Reading_3_Summary">
<h2 class="hd hd-2 unit-title">Reading 3 Summary</h2>
<div class="vert-mod">
<div class="vert vert-0" data-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3640d881cbef">
<div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-has-score="False" data-runtime-class="LmsRuntime" data-graded="True" data-request-token="890a44c0e9a511efbd7612d4917dea95" data-runtime-version="1" data-block-type="html" data-course-id="course-v1:MITx+6.005.2x+1T2017" data-init="XBlockToXModuleShim" data-usage-id="block-v1:MITx+6.005.2x+1T2017+type@html+block@html_3640d881cbef">
<script type="json/xblock-args" class="xblock-json-init-args">
{"xmodule-type": "HTMLModule"}
</script>
<link href="/assets/courseware/v1/b2188f0a95a7a9062748278f7d5a584f/asset-v1:MITx+6.005.2x+1T2017+type@asset+block/syntax-highlighting.css" rel="stylesheet" type="text/css" />
<h2 id="summary">Summary</h2>
<div data-outline="summary">
<p>Machine-processed textual languages are ubiquitous in computer science. Grammars are the most popular formalism for describing such languages, and regular expressions are an important subclass of grammars that can be expressed without recursion.</p>
<p>The topics of today's reading connect to our three properties of good software as follows:</p>
<ul>
<li>
<p><strong>Safe from bugs.</strong> Grammars and regular expressions are declarative specifications for strings and streams, which can be used directly by libraries and tools. These specifications are often simpler, more direct, and less likely to be buggy then parsing code written by hand.</p>
</li>
<li>
<p><strong>Easy to understand.</strong> A grammar captures the shape of a sequence in a form that is easier to understand than hand-written parsing code. Regular expressions, alas, are often not easy to understand, because they are a one-line reduced form of what might have been a more understandable regular grammar.</p>
</li>
<li>
<p><strong>Ready for change.</strong> A grammar can be easily edited, but regular expressions, unfortunately, are much harder to change, because a complex regular expression is cryptic and hard to understand.</p>
</li>
</ul>
</div>
<div class="license">This reading was collaboratively authored with contributions from: Saman Amarasinghe, Adam Chlipala, Srini Devadas, Michael Ernst, Max Goldman, John Guttag, Daniel Jackson, Rob Miller, Martin Rinard, and Armando Solar-Lezama. This work is licensed under <a rel="license" href="http://creativecommons.org/licenses/by-sa/4.0/">CC BY-SA 4.0</a>.</div>
</div>
</div>
</div>
</div>