<html><head><link rel="stylesheet" href="resource://content-accessible/plaintext.css"><style media="screen" id="__markdown-viewer__md_css">/*
* Copyright (c) Sindre Sorhus <sindresorhus@gmail.com> (https://sindresorhus.com)
*
* Permission is hereby granted, free of charge, to any person obtaining a copy of
* this software and associated documentation files (the "Software"), to deal in
* the Software without restriction, including without limitation the rights to
* use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
* of the Software, and to permit persons to whom the Software is furnished to do
* so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
@media (prefers-color-scheme: dark) {
:root {
--color-prettylights-syntax-comment: #8b949e;
--color-prettylights-syntax-constant: #79c0ff;
--color-prettylights-syntax-entity: #d2a8ff;
--color-prettylights-syntax-storage-modifier-import: #c9d1d9;
--color-prettylights-syntax-entity-tag: #7ee787;
--color-prettylights-syntax-keyword: #ff7b72;
--color-prettylights-syntax-string: #a5d6ff;
--color-prettylights-syntax-variable: #ffa657;
--color-prettylights-syntax-brackethighlighter-unmatched: #f85149;
--color-prettylights-syntax-invalid-illegal-text: #f0f6fc;
--color-prettylights-syntax-invalid-illegal-bg: #8e1519;
--color-prettylights-syntax-carriage-return-text: #f0f6fc;
--color-prettylights-syntax-carriage-return-bg: #b62324;
--color-prettylights-syntax-string-regexp: #7ee787;
--color-prettylights-syntax-markup-list: #f2cc60;
--color-prettylights-syntax-markup-heading: #1f6feb;
--color-prettylights-syntax-markup-italic: #c9d1d9;
--color-prettylights-syntax-markup-bold: #c9d1d9;
--color-prettylights-syntax-markup-deleted-text: #ffdcd7;
--color-prettylights-syntax-markup-deleted-bg: #67060c;
--color-prettylights-syntax-markup-inserted-text: #aff5b4;
--color-prettylights-syntax-markup-inserted-bg: #033a16;
--color-prettylights-syntax-markup-changed-text: #ffdfb6;
--color-prettylights-syntax-markup-changed-bg: #5a1e02;
--color-prettylights-syntax-markup-ignored-text: #c9d1d9;
--color-prettylights-syntax-markup-ignored-bg: #1158c7;
--color-prettylights-syntax-meta-diff-range: #d2a8ff;
--color-prettylights-syntax-brackethighlighter-angle: #8b949e;
--color-prettylights-syntax-sublimelinter-gutter-mark: #484f58;
--color-prettylights-syntax-constant-other-reference-link: #a5d6ff;
--color-fg-default: #c9d1d9;
--color-fg-muted: #8b949e;
--color-fg-subtle: #484f58;
--color-canvas-default: #0d1117;
--color-canvas-subtle: #161b22;
--color-border-default: #30363d;
--color-border-muted: #21262d;
--color-neutral-muted: rgba(110,118,129,0.4);
--color-accent-fg: #58a6ff;
--color-accent-emphasis: #1f6feb;
--color-danger-fg: #f85149;
}
}
@media (prefers-color-scheme: light) {
:root {
--color-prettylights-syntax-comment: #6e7781;
--color-prettylights-syntax-constant: #0550ae;
--color-prettylights-syntax-entity: #8250df;
--color-prettylights-syntax-storage-modifier-import: #24292f;
--color-prettylights-syntax-entity-tag: #116329;
--color-prettylights-syntax-keyword: #cf222e;
--color-prettylights-syntax-string: #0a3069;
--color-prettylights-syntax-variable: #953800;
--color-prettylights-syntax-brackethighlighter-unmatched: #82071e;
--color-prettylights-syntax-invalid-illegal-text: #f6f8fa;
--color-prettylights-syntax-invalid-illegal-bg: #82071e;
--color-prettylights-syntax-carriage-return-text: #f6f8fa;
--color-prettylights-syntax-carriage-return-bg: #cf222e;
--color-prettylights-syntax-string-regexp: #116329;
--color-prettylights-syntax-markup-list: #3b2300;
--color-prettylights-syntax-markup-heading: #0550ae;
--color-prettylights-syntax-markup-italic: #24292f;
--color-prettylights-syntax-markup-bold: #24292f;
--color-prettylights-syntax-markup-deleted-text: #82071e;
--color-prettylights-syntax-markup-deleted-bg: #FFEBE9;
--color-prettylights-syntax-markup-inserted-text: #116329;
--color-prettylights-syntax-markup-inserted-bg: #dafbe1;
--color-prettylights-syntax-markup-changed-text: #953800;
--color-prettylights-syntax-markup-changed-bg: #ffd8b5;
--color-prettylights-syntax-markup-ignored-text: #eaeef2;
--color-prettylights-syntax-markup-ignored-bg: #0550ae;
--color-prettylights-syntax-meta-diff-range: #8250df;
--color-prettylights-syntax-brackethighlighter-angle: #57606a;
--color-prettylights-syntax-sublimelinter-gutter-mark: #8c959f;
--color-prettylights-syntax-constant-other-reference-link: #0a3069;
--color-fg-default: #24292f;
--color-fg-muted: #57606a;
--color-fg-subtle: #6e7781;
--color-canvas-default: #ffffff;
--color-canvas-subtle: #f6f8fa;
--color-border-default: #d0d7de;
--color-border-muted: hsla(210,18%,87%,1);
--color-neutral-muted: rgba(175,184,193,0.2);
--color-accent-fg: #0969da;
--color-accent-emphasis: #0969da;
--color-danger-fg: #cf222e;
}
}
:root {
color: var(--color-fg-default);
background-color: var(--color-canvas-default);
}
.markdownroot {
-ms-text-size-adjust: 100%;
-webkit-text-size-adjust: 100%;
margin: 0;
font-family: -apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif,"Apple Color Emoji","Segoe UI Emoji";
font-size: 16px;
line-height: 1.5;
word-wrap: break-word;
}
.markdownroot .octicon {
display: inline-block;
fill: currentColor;
vertical-align: text-bottom;
}
.markdownroot h1:hover .anchor .octicon-link:before,
.markdownroot h2:hover .anchor .octicon-link:before,
.markdownroot h3:hover .anchor .octicon-link:before,
.markdownroot h4:hover .anchor .octicon-link:before,
.markdownroot h5:hover .anchor .octicon-link:before,
.markdownroot h6:hover .anchor .octicon-link:before {
width: 16px;
height: 16px;
content: ' ';
display: inline-block;
background-color: currentColor;
-webkit-mask-image: url("data:image/svg+xml,<svg xmlns='http://www.w3.org/2000/svg' viewBox='0 0 16 16' version='1.1' aria-hidden='true'><path fill-rule='evenodd' d='M7.775 3.275a.75.75 0 001.06 1.06l1.25-1.25a2 2 0 112.83 2.83l-2.5 2.5a2 2 0 01-2.83 0 .75.75 0 00-1.06 1.06 3.5 3.5 0 004.95 0l2.5-2.5a3.5 3.5 0 00-4.95-4.95l-1.25 1.25zm-4.69 9.64a2 2 0 010-2.83l2.5-2.5a2 2 0 012.83 0 .75.75 0 001.06-1.06 3.5 3.5 0 00-4.95 0l-2.5 2.5a3.5 3.5 0 004.95 4.95l1.25-1.25a.75.75 0 00-1.06-1.06l-1.25 1.25a2 2 0 01-2.83 0z'></path></svg>");
mask-image: url("data:image/svg+xml,<svg xmlns='http://www.w3.org/2000/svg' viewBox='0 0 16 16' version='1.1' aria-hidden='true'><path fill-rule='evenodd' d='M7.775 3.275a.75.75 0 001.06 1.06l1.25-1.25a2 2 0 112.83 2.83l-2.5 2.5a2 2 0 01-2.83 0 .75.75 0 00-1.06 1.06 3.5 3.5 0 004.95 0l2.5-2.5a3.5 3.5 0 00-4.95-4.95l-1.25 1.25zm-4.69 9.64a2 2 0 010-2.83l2.5-2.5a2 2 0 012.83 0 .75.75 0 001.06-1.06 3.5 3.5 0 00-4.95 0l-2.5 2.5a3.5 3.5 0 004.95 4.95l1.25-1.25a.75.75 0 00-1.06-1.06l-1.25 1.25a2 2 0 01-2.83 0z'></path></svg>");
}
.markdownroot details,
.markdownroot figcaption,
.markdownroot figure {
display: block;
}
.markdownroot summary {
display: list-item;
}
.markdownroot a {
background-color: transparent;
color: var(--color-accent-fg);
text-decoration: none;
}
.markdownroot a:active,
.markdownroot a:hover {
outline-width: 0;
}
.markdownroot abbr[title] {
border-bottom: none;
-webkit-text-decoration: underline dotted;
text-decoration: underline dotted;
}
.markdownroot b,
.markdownroot strong {
font-weight: 600;
}
.markdownroot dfn {
font-style: italic;
}
.markdownroot h1 {
margin: .67em 0;
font-weight: 600;
padding-bottom: .3em;
font-size: 2em;
border-bottom: 1px solid var(--color-border-muted);
}
.markdownroot mark {
background-color: #ff0;
color: var(--color-text-primary);
}
.markdownroot small {
font-size: 90%;
}
.markdownroot sub,
.markdownroot sup {
font-size: 75%;
line-height: 0;
position: relative;
vertical-align: baseline;
}
.markdownroot sub {
bottom: -0.25em;
}
.markdownroot sup {
top: -0.5em;
}
.markdownroot img {
border-style: none;
max-width: 100%;
box-sizing: content-box;
background-color: var(--color-canvas-default);
}
.markdownroot code,
.markdownroot kbd,
.markdownroot pre,
.markdownroot samp {
font-family: monospace,monospace;
font-size: 1em;
}
.markdownroot figure {
margin: 1em 40px;
}
.markdownroot hr {
box-sizing: content-box;
overflow: hidden;
background: transparent;
border-bottom: 1px solid var(--color-border-muted);
height: .25em;
padding: 0;
margin: 24px 0;
background-color: var(--color-border-default);
border: 0;
}
.markdownroot html [type=button],
.markdownroot [type=reset],
.markdownroot [type=submit] {
-webkit-appearance: button;
}
.markdownroot [type=button]::-moz-focus-inner,
.markdownroot [type=reset]::-moz-focus-inner,
.markdownroot [type=submit]::-moz-focus-inner {
border-style: none;
padding: 0;
}
.markdownroot [type=button]:-moz-focusring,
.markdownroot [type=reset]:-moz-focusring,
.markdownroot [type=submit]:-moz-focusring {
outline: 1px dotted ButtonText;
}
.markdownroot [type=checkbox],
.markdownroot [type=radio] {
box-sizing: border-box;
padding: 0;
}
.markdownroot [type=number]::-webkit-inner-spin-button,
.markdownroot [type=number]::-webkit-outer-spin-button {
height: auto;
}
.markdownroot [type=search] {
-webkit-appearance: textfield;
outline-offset: -2px;
}
.markdownroot [type=search]::-webkit-search-cancel-button,
.markdownroot [type=search]::-webkit-search-decoration {
-webkit-appearance: none;
}
.markdownroot ::-webkit-input-placeholder {
color: inherit;
opacity: .54;
}
.markdownroot ::-webkit-file-upload-button {
-webkit-appearance: button;
font: inherit;
}
.markdownroot a:hover {
text-decoration: underline;
}
.markdownroot hr::before {
display: table;
content: "";
}
.markdownroot hr::after {
display: table;
clear: both;
content: "";
}
.markdownroot table {
border-spacing: 0;
border-collapse: collapse;
display: block;
width: max-content;
max-width: 100%;
overflow: auto;
}
.markdownroot td,
.markdownroot th {
padding: 0;
}
.markdownroot details summary {
cursor: pointer;
}
.markdownroot details:not([open])>*:not(summary) {
display: none !important;
}
.markdownroot kbd {
display: inline-block;
padding: 3px 5px;
font: 11px ui-monospace,SFMono-Regular,SF Mono,Menlo,Consolas,Liberation Mono,monospace;
line-height: 10px;
color: var(--color-fg-default);
vertical-align: middle;
background-color: var(--color-canvas-subtle);
border: solid 1px var(--color-neutral-muted);
border-bottom-color: var(--color-neutral-muted);
border-radius: 6px;
box-shadow: inset 0 -1px 0 var(--color-neutral-muted);
}
.markdownroot h1,
.markdownroot h2,
.markdownroot h3,
.markdownroot h4,
.markdownroot h5,
.markdownroot h6 {
margin-top: 24px;
margin-bottom: 16px;
font-weight: 600;
line-height: 1.25;
}
.markdownroot h2 {
font-weight: 600;
padding-bottom: .3em;
font-size: 1.5em;
border-bottom: 1px solid var(--color-border-muted);
}
.markdownroot h3 {
font-weight: 600;
font-size: 1.25em;
}
.markdownroot h4 {
font-weight: 600;
font-size: 1em;
}
.markdownroot h5 {
font-weight: 600;
font-size: .875em;
}
.markdownroot h6 {
font-weight: 600;
font-size: .85em;
color: var(--color-fg-muted);
}
.markdownroot p {
margin-top: 0;
margin-bottom: 10px;
}
.markdownroot blockquote {
margin: 0;
padding: 0 1em;
color: var(--color-fg-muted);
border-left: .25em solid var(--color-border-default);
}
.markdownroot ul,
.markdownroot ol {
margin-top: 0;
margin-bottom: 0;
padding-left: 2em;
}
.markdownroot ol ol,
.markdownroot ul ol {
list-style-type: lower-roman;
}
.markdownroot ul ul ol,
.markdownroot ul ol ol,
.markdownroot ol ul ol,
.markdownroot ol ol ol {
list-style-type: lower-alpha;
}
.markdownroot dd {
margin-left: 0;
}
.markdownroot tt,
.markdownroot code {
font-family: ui-monospace,SFMono-Regular,SF Mono,Menlo,Consolas,Liberation Mono,monospace;
font-size: 12px;
}
.markdownroot pre {
margin-top: 0;
margin-bottom: 0;
font-family: ui-monospace,SFMono-Regular,SF Mono,Menlo,Consolas,Liberation Mono,monospace;
font-size: 12px;
word-wrap: normal;
}
.markdownroot :-ms-input-placeholder {
color: var(--color-fg-subtle);
opacity: 1;
}
.markdownroot ::-ms-input-placeholder {
color: var(--color-fg-subtle);
opacity: 1;
}
.markdownroot ::placeholder {
color: var(--color-fg-subtle);
opacity: 1;
}
.markdownroot .pl-c {
color: var(--color-prettylights-syntax-comment);
}
.markdownroot .pl-c1,
.markdownroot .pl-s .pl-v {
color: var(--color-prettylights-syntax-constant);
}
.markdownroot .pl-e,
.markdownroot .pl-en {
color: var(--color-prettylights-syntax-entity);
}
.markdownroot .pl-smi,
.markdownroot .pl-s .pl-s1 {
color: var(--color-prettylights-syntax-storage-modifier-import);
}
.markdownroot .pl-ent {
color: var(--color-prettylights-syntax-entity-tag);
}
.markdownroot .pl-k {
color: var(--color-prettylights-syntax-keyword);
}
.markdownroot .pl-s,
.markdownroot .pl-pds,
.markdownroot .pl-s .pl-pse .pl-s1,
.markdownroot .pl-sr,
.markdownroot .pl-sr .pl-cce,
.markdownroot .pl-sr .pl-sre,
.markdownroot .pl-sr .pl-sra {
color: var(--color-prettylights-syntax-string);
}
.markdownroot .pl-v,
.markdownroot .pl-smw {
color: var(--color-prettylights-syntax-variable);
}
.markdownroot .pl-bu {
color: var(--color-prettylights-syntax-brackethighlighter-unmatched);
}
.markdownroot .pl-ii {
color: var(--color-prettylights-syntax-invalid-illegal-text);
background-color: var(--color-prettylights-syntax-invalid-illegal-bg);
}
.markdownroot .pl-c2 {
color: var(--color-prettylights-syntax-carriage-return-text);
background-color: var(--color-prettylights-syntax-carriage-return-bg);
}
.markdownroot .pl-sr .pl-cce {
font-weight: bold;
color: var(--color-prettylights-syntax-string-regexp);
}
.markdownroot .pl-ml {
color: var(--color-prettylights-syntax-markup-list);
}
.markdownroot .pl-mh,
.markdownroot .pl-mh .pl-en,
.markdownroot .pl-ms {
font-weight: bold;
color: var(--color-prettylights-syntax-markup-heading);
}
.markdownroot .pl-mi {
font-style: italic;
color: var(--color-prettylights-syntax-markup-italic);
}
.markdownroot .pl-mb {
font-weight: bold;
color: var(--color-prettylights-syntax-markup-bold);
}
.markdownroot .pl-md {
color: var(--color-prettylights-syntax-markup-deleted-text);
background-color: var(--color-prettylights-syntax-markup-deleted-bg);
}
.markdownroot .pl-mi1 {
color: var(--color-prettylights-syntax-markup-inserted-text);
background-color: var(--color-prettylights-syntax-markup-inserted-bg);
}
.markdownroot .pl-mc {
color: var(--color-prettylights-syntax-markup-changed-text);
background-color: var(--color-prettylights-syntax-markup-changed-bg);
}
.markdownroot .pl-mi2 {
color: var(--color-prettylights-syntax-markup-ignored-text);
background-color: var(--color-prettylights-syntax-markup-ignored-bg);
}
.markdownroot .pl-mdr {
font-weight: bold;
color: var(--color-prettylights-syntax-meta-diff-range);
}
.markdownroot .pl-ba {
color: var(--color-prettylights-syntax-brackethighlighter-angle);
}
.markdownroot .pl-sg {
color: var(--color-prettylights-syntax-sublimelinter-gutter-mark);
}
.markdownroot .pl-corl {
text-decoration: underline;
color: var(--color-prettylights-syntax-constant-other-reference-link);
}
.markdownroot [data-catalyst] {
display: block;
}
.markdownroot g-emoji {
font-family: "Apple Color Emoji","Segoe UI Emoji","Segoe UI Symbol";
font-size: 1em;
font-style: normal !important;
font-weight: 400;
line-height: 1;
vertical-align: -0.075em;
}
.markdownroot g-emoji img {
width: 1em;
height: 1em;
}
.markdownroot::before {
display: table;
content: "";
}
.markdownroot::after {
display: table;
clear: both;
content: "";
}
.markdownroot>*:first-child {
margin-top: 0 !important;
}
.markdownroot>*:last-child {
margin-bottom: 0 !important;
}
.markdownroot a:not([href]) {
color: inherit;
text-decoration: none;
}
.markdownroot .absent {
color: var(--color-danger-fg);
}
.markdownroot .anchor {
float: left;
padding-right: 4px;
margin-left: -20px;
line-height: 1;
}
.markdownroot .anchor:focus {
outline: none;
}
.markdownroot p,
.markdownroot blockquote,
.markdownroot ul,
.markdownroot ol,
.markdownroot dl,
.markdownroot table,
.markdownroot pre,
.markdownroot details {
margin-top: 0;
margin-bottom: 16px;
}
.markdownroot blockquote>:first-child {
margin-top: 0;
}
.markdownroot blockquote>:last-child {
margin-bottom: 0;
}
.markdownroot sup>a::before {
content: "[";
}
.markdownroot sup>a::after {
content: "]";
}
.markdownroot h1 .octicon-link,
.markdownroot h2 .octicon-link,
.markdownroot h3 .octicon-link,
.markdownroot h4 .octicon-link,
.markdownroot h5 .octicon-link,
.markdownroot h6 .octicon-link {
color: var(--color-fg-default);
vertical-align: middle;
visibility: hidden;
}
.markdownroot h1:hover .anchor,
.markdownroot h2:hover .anchor,
.markdownroot h3:hover .anchor,
.markdownroot h4:hover .anchor,
.markdownroot h5:hover .anchor,
.markdownroot h6:hover .anchor {
text-decoration: none;
}
.markdownroot h1:hover .anchor .octicon-link,
.markdownroot h2:hover .anchor .octicon-link,
.markdownroot h3:hover .anchor .octicon-link,
.markdownroot h4:hover .anchor .octicon-link,
.markdownroot h5:hover .anchor .octicon-link,
.markdownroot h6:hover .anchor .octicon-link {
visibility: visible;
}
.markdownroot h1 tt,
.markdownroot h1 code,
.markdownroot h2 tt,
.markdownroot h2 code,
.markdownroot h3 tt,
.markdownroot h3 code,
.markdownroot h4 tt,
.markdownroot h4 code,
.markdownroot h5 tt,
.markdownroot h5 code,
.markdownroot h6 tt,
.markdownroot h6 code {
padding: 0 .2em;
font-size: inherit;
}
.markdownroot ul.no-list,
.markdownroot ol.no-list {
padding: 0;
list-style-type: none;
}
.markdownroot ol[type="1"] {
list-style-type: decimal;
}
.markdownroot ol[type=a] {
list-style-type: lower-alpha;
}
.markdownroot ol[type=i] {
list-style-type: lower-roman;
}
.markdownroot div>ol:not([type]) {
list-style-type: decimal;
}
.markdownroot ul ul,
.markdownroot ul ol,
.markdownroot ol ol,
.markdownroot ol ul {
margin-top: 0;
margin-bottom: 0;
}
.markdownroot li>p {
margin-top: 16px;
}
.markdownroot li+li {
margin-top: .25em;
}
.markdownroot dl {
padding: 0;
}
.markdownroot dl dt {
padding: 0;
margin-top: 16px;
font-size: 1em;
font-style: italic;
font-weight: 600;
}
.markdownroot dl dd {
padding: 0 16px;
margin-bottom: 16px;
}
.markdownroot table th {
font-weight: 600;
}
.markdownroot table th,
.markdownroot table td {
padding: 6px 13px;
border: 1px solid var(--color-border-default);
}
.markdownroot table tr {
background-color: var(--color-canvas-default);
border-top: 1px solid var(--color-border-muted);
}
.markdownroot table tr:nth-child(2n) {
background-color: var(--color-canvas-subtle);
}
.markdownroot table img {
background-color: transparent;
}
.markdownroot img[align=right] {
padding-left: 20px;
}
.markdownroot img[align=left] {
padding-right: 20px;
}
.markdownroot .emoji {
max-width: none;
vertical-align: text-top;
background-color: transparent;
}
.markdownroot span.frame {
display: block;
overflow: hidden;
}
.markdownroot span.frame>span {
display: block;
float: left;
width: auto;
padding: 7px;
margin: 13px 0 0;
overflow: hidden;
border: 1px solid var(--color-border-default);
}
.markdownroot span.frame span img {
display: block;
float: left;
}
.markdownroot span.frame span span {
display: block;
padding: 5px 0 0;
clear: both;
color: var(--color-fg-default);
}
.markdownroot span.align-center {
display: block;
overflow: hidden;
clear: both;
}
.markdownroot span.align-center>span {
display: block;
margin: 13px auto 0;
overflow: hidden;
text-align: center;
}
.markdownroot span.align-center span img {
margin: 0 auto;
text-align: center;
}
.markdownroot span.align-right {
display: block;
overflow: hidden;
clear: both;
}
.markdownroot span.align-right>span {
display: block;
margin: 13px 0 0;
overflow: hidden;
text-align: right;
}
.markdownroot span.align-right span img {
margin: 0;
text-align: right;
}
.markdownroot span.float-left {
display: block;
float: left;
margin-right: 13px;
overflow: hidden;
}
.markdownroot span.float-left span {
margin: 13px 0 0;
}
.markdownroot span.float-right {
display: block;
float: right;
margin-left: 13px;
overflow: hidden;
}
.markdownroot span.float-right>span {
display: block;
margin: 13px auto 0;
overflow: hidden;
text-align: right;
}
.markdownroot code,
.markdownroot tt {
padding: .2em .4em;
margin: 0;
font-size: 85%;
background-color: var(--color-neutral-muted);
border-radius: 6px;
}
.markdownroot code br,
.markdownroot tt br {
display: none;
}
.markdownroot del code {
text-decoration: inherit;
}
.markdownroot pre code {
font-size: 100%;
}
.markdownroot pre>code {
padding: 0;
margin: 0;
word-break: normal;
white-space: pre;
background: transparent;
border: 0;
}
.markdownroot .highlight {
margin-bottom: 16px;
}
.markdownroot .highlight pre {
margin-bottom: 0;
word-break: normal;
}
.markdownroot .highlight pre,
.markdownroot pre {
padding: 16px;
overflow: auto;
font-size: 85%;
line-height: 1.45;
background-color: var(--color-canvas-subtle);
border-radius: 6px;
}
.markdownroot pre code,
.markdownroot pre tt {
display: inline;
max-width: auto;
padding: 0;
margin: 0;
overflow: visible;
line-height: inherit;
word-wrap: normal;
background-color: transparent;
border: 0;
}
.markdownroot .csv-data td,
.markdownroot .csv-data th {
padding: 5px;
overflow: hidden;
font-size: 12px;
line-height: 1;
text-align: left;
white-space: nowrap;
}
.markdownroot .csv-data .blob-num {
padding: 10px 8px 9px;
text-align: right;
background: var(--color-canvas-default);
border: 0;
}
.markdownroot .csv-data tr {
border-top: 0;
}
.markdownroot .csv-data th {
font-weight: 600;
background: var(--color-canvas-subtle);
border-top: 0;
}
.markdownroot .footnotes {
font-size: 12px;
color: var(--color-fg-muted);
border-top: 1px solid var(--color-border-default);
}
.markdownroot .footnotes ol {
padding-left: 16px;
}
.markdownroot .footnotes li {
position: relative;
}
.markdownroot .footnotes li:target::before {
position: absolute;
top: -8px;
right: -8px;
bottom: -8px;
left: -24px;
pointer-events: none;
content: "";
border: 2px solid var(--color-accent-emphasis);
border-radius: 6px;
}
.markdownroot .footnotes li:target {
color: var(--color-fg-default);
}
.markdownroot .footnotes .data-footnote-backref g-emoji {
font-family: monospace;
}
.markdownroot [hidden] {
display: none !important;
}
.markdownroot ::-webkit-calendar-picker-indicator {
filter: invert(50%);
}
</style><style media="print" id="__markdown-viewer__md_print_css">:root {
background: white;
color: black;
font: 8pt serif;
line-height: 1.5;
vertical-align: baseline;
}
body, .markdownRoot {
max-width: 100%;
margin: 0;
padding: 0;
}
* {
margin: 0;
padding: 0;
}
p {
margin: 0 0 .3rem 0;
}
ul, ol {
padding-left: 2em
}
a {
color: #666;
text-decoration: underline;
}
a[href]:after {
content: ' (' attr(href) ')';
font-size: 1rem;
}
img {
max-width: 100%;
}
h1, h2, h3, h4, h5, h6 {
padding: 0 0 .2em 0;
}
h1, h2, h3, h4, h5, h6, dt {
/* break-after: avoid; */
break-inside: avoid;
}
/* Hack to fix break-after: https://stackoverflow.com/a/53742871 */
h1:after, h2:after, h3:after, h4:after, h5:after, h6:after, dt:after {
content: "";
display: block;
/* .2em of padding + 3em for 2 full lines */
height: 3.2em;
margin-bottom: -3.2em;
}
blockquote, pre, li, dt, dd {
break-inside: avoid;
}
</style><style id="__markdown-viewer__hljs_css">
@media (prefers-color-scheme: light) { .hljs-comment,.hljs-quote{color:#696969}.hljs-deletion,.hljs-name,.hljs-regexp,.hljs-selector-class,.hljs-selector-id,.hljs-tag,.hljs-template-variable,.hljs-variable{color:#d91e18}.hljs-built_in,.hljs-builtin-name,.hljs-link,.hljs-literal,.hljs-meta,.hljs-number,.hljs-params,.hljs-type{color:#aa5d00}.hljs-attribute{color:#aa5d00}.hljs-addition,.hljs-bullet,.hljs-string,.hljs-symbol{color:green}.hljs-section,.hljs-title{color:#007faa}.hljs-keyword,.hljs-selector-tag{color:#7928a1}.hljs{display:block;overflow-x:auto;background:#fefefe;color:#545454;padding:.5em}.hljs-emphasis{font-style:italic}.hljs-strong{font-weight:700}@media screen and (-ms-high-contrast:active){.hljs-addition,.hljs-attribute,.hljs-built_in,.hljs-builtin-name,.hljs-bullet,.hljs-comment,.hljs-link,.hljs-literal,.hljs-meta,.hljs-number,.hljs-params,.hljs-quote,.hljs-string,.hljs-symbol,.hljs-type{color:highlight}.hljs-keyword,.hljs-selector-tag{font-weight:700}} }
@media (prefers-color-scheme: dark) { .hljs-comment,.hljs-quote{color:#d4d0ab}.hljs-deletion,.hljs-name,.hljs-regexp,.hljs-selector-class,.hljs-selector-id,.hljs-tag,.hljs-template-variable,.hljs-variable{color:#ffa07a}.hljs-built_in,.hljs-builtin-name,.hljs-link,.hljs-literal,.hljs-meta,.hljs-number,.hljs-params,.hljs-type{color:#f5ab35}.hljs-attribute{color:gold}.hljs-addition,.hljs-bullet,.hljs-string,.hljs-symbol{color:#abe338}.hljs-section,.hljs-title{color:#00e0e0}.hljs-keyword,.hljs-selector-tag{color:#dcc6e0}.hljs{display:block;overflow-x:auto;background:#2b2b2b;color:#f8f8f2;padding:.5em}.hljs-emphasis{font-style:italic}.hljs-strong{font-weight:700}@media screen and (-ms-high-contrast:active){.hljs-addition,.hljs-attribute,.hljs-built_in,.hljs-builtin-name,.hljs-bullet,.hljs-comment,.hljs-link,.hljs-literal,.hljs-meta,.hljs-number,.hljs-params,.hljs-quote,.hljs-string,.hljs-symbol,.hljs-type{color:highlight}.hljs-keyword,.hljs-selector-tag{font-weight:700}} }</style><style id="__markdown-viewer__katex_css">@font-face{font-family:KaTeX_AMS;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Caligraphic;font-style:normal;font-weight:700}@font-face{font-family:KaTeX_Caligraphic;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Fraktur;font-style:normal;font-weight:700}@font-face{font-family:KaTeX_Fraktur;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Main;font-style:normal;font-weight:700}@font-face{font-family:KaTeX_Main;font-style:italic;font-weight:700}@font-face{font-family:KaTeX_Main;font-style:italic;font-weight:400}@font-face{font-family:KaTeX_Main;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Math;font-style:italic;font-weight:700}@font-face{font-family:KaTeX_Math;font-style:italic;font-weight:400}@font-face{font-family:"KaTeX_SansSerif";font-style:normal;font-weight:700}@font-face{font-family:"KaTeX_SansSerif";font-style:italic;font-weight:400}@font-face{font-family:"KaTeX_SansSerif";font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Script;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Size1;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Size2;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Size3;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Size4;font-style:normal;font-weight:400}@font-face{font-family:KaTeX_Typewriter;font-style:normal;font-weight:400}.katex{text-rendering:auto;font:normal 1.21em KaTeX_Main,Times New Roman,serif;line-height:1.2;text-indent:0}.katex *{-ms-high-contrast-adjust:none!important;border-color:currentColor}.katex .katex-version:after{content:"0.13.13"}.katex .katex-mathml{clip:rect(1px,1px,1px,1px);border:0;height:1px;overflow:hidden;padding:0;position:absolute;width:1px}.katex .katex-html>.newline{display:block}.katex .base{position:relative;white-space:nowrap;width:-webkit-min-content;width:-moz-min-content;width:min-content}.katex .base,.katex .strut{display:inline-block}.katex .textbf{font-weight:700}.katex .textit{font-style:italic}.katex .textrm{font-family:KaTeX_Main}.katex .textsf{font-family:KaTeX_SansSerif}.katex .texttt{font-family:KaTeX_Typewriter}.katex .mathnormal{font-family:KaTeX_Math;font-style:italic}.katex .mathit{font-family:KaTeX_Main;font-style:italic}.katex .mathrm{font-style:normal}.katex .mathbf{font-family:KaTeX_Main;font-weight:700}.katex .boldsymbol{font-family:KaTeX_Math;font-style:italic;font-weight:700}.katex .amsrm,.katex .mathbb,.katex .textbb{font-family:KaTeX_AMS}.katex .mathcal{font-family:KaTeX_Caligraphic}.katex .mathfrak,.katex .textfrak{font-family:KaTeX_Fraktur}.katex .mathtt{font-family:KaTeX_Typewriter}.katex .mathscr,.katex .textscr{font-family:KaTeX_Script}.katex .mathsf,.katex .textsf{font-family:KaTeX_SansSerif}.katex .mathboldsf,.katex .textboldsf{font-family:KaTeX_SansSerif;font-weight:700}.katex .mathitsf,.katex .textitsf{font-family:KaTeX_SansSerif;font-style:italic}.katex .mainrm{font-family:KaTeX_Main;font-style:normal}.katex .vlist-t{border-collapse:collapse;display:inline-table;table-layout:fixed}.katex .vlist-r{display:table-row}.katex .vlist{display:table-cell;position:relative;vertical-align:bottom}.katex .vlist>span{display:block;height:0;position:relative}.katex .vlist>span>span{display:inline-block}.katex .vlist>span>.pstrut{overflow:hidden;width:0}.katex .vlist-t2{margin-right:-2px}.katex .vlist-s{display:table-cell;font-size:1px;min-width:2px;vertical-align:bottom;width:2px}.katex .vbox{align-items:baseline;display:inline-flex;flex-direction:column}.katex .hbox{width:100%}.katex .hbox,.katex .thinbox{display:inline-flex;flex-direction:row}.katex .thinbox{max-width:0;width:0}.katex .msupsub{text-align:left}.katex .mfrac>span>span{text-align:center}.katex .mfrac .frac-line{border-bottom-style:solid;display:inline-block;width:100%}.katex .hdashline,.katex .hline,.katex .mfrac .frac-line,.katex .overline .overline-line,.katex .rule,.katex .underline .underline-line{min-height:1px}.katex .mspace{display:inline-block}.katex .clap,.katex .llap,.katex .rlap{position:relative;width:0}.katex .clap>.inner,.katex .llap>.inner,.katex .rlap>.inner{position:absolute}.katex .clap>.fix,.katex .llap>.fix,.katex .rlap>.fix{display:inline-block}.katex .llap>.inner{right:0}.katex .clap>.inner,.katex .rlap>.inner{left:0}.katex .clap>.inner>span{margin-left:-50%;margin-right:50%}.katex .rule{border:0 solid;display:inline-block;position:relative}.katex .hline,.katex .overline .overline-line,.katex .underline .underline-line{border-bottom-style:solid;display:inline-block;width:100%}.katex .hdashline{border-bottom-style:dashed;display:inline-block;width:100%}.katex .sqrt>.root{margin-left:.27777778em;margin-right:-.55555556em}.katex .fontsize-ensurer.reset-size1.size1,.katex .sizing.reset-size1.size1{font-size:1em}.katex .fontsize-ensurer.reset-size1.size2,.katex .sizing.reset-size1.size2{font-size:1.2em}.katex .fontsize-ensurer.reset-size1.size3,.katex .sizing.reset-size1.size3{font-size:1.4em}.katex .fontsize-ensurer.reset-size1.size4,.katex .sizing.reset-size1.size4{font-size:1.6em}.katex .fontsize-ensurer.reset-size1.size5,.katex .sizing.reset-size1.size5{font-size:1.8em}.katex .fontsize-ensurer.reset-size1.size6,.katex .sizing.reset-size1.size6{font-size:2em}.katex .fontsize-ensurer.reset-size1.size7,.katex .sizing.reset-size1.size7{font-size:2.4em}.katex .fontsize-ensurer.reset-size1.size8,.katex .sizing.reset-size1.size8{font-size:2.88em}.katex .fontsize-ensurer.reset-size1.size9,.katex .sizing.reset-size1.size9{font-size:3.456em}.katex .fontsize-ensurer.reset-size1.size10,.katex .sizing.reset-size1.size10{font-size:4.148em}.katex .fontsize-ensurer.reset-size1.size11,.katex .sizing.reset-size1.size11{font-size:4.976em}.katex .fontsize-ensurer.reset-size2.size1,.katex .sizing.reset-size2.size1{font-size:.83333333em}.katex .fontsize-ensurer.reset-size2.size2,.katex .sizing.reset-size2.size2{font-size:1em}.katex .fontsize-ensurer.reset-size2.size3,.katex .sizing.reset-size2.size3{font-size:1.16666667em}.katex .fontsize-ensurer.reset-size2.size4,.katex .sizing.reset-size2.size4{font-size:1.33333333em}.katex .fontsize-ensurer.reset-size2.size5,.katex .sizing.reset-size2.size5{font-size:1.5em}.katex .fontsize-ensurer.reset-size2.size6,.katex .sizing.reset-size2.size6{font-size:1.66666667em}.katex .fontsize-ensurer.reset-size2.size7,.katex .sizing.reset-size2.size7{font-size:2em}.katex .fontsize-ensurer.reset-size2.size8,.katex .sizing.reset-size2.size8{font-size:2.4em}.katex .fontsize-ensurer.reset-size2.size9,.katex .sizing.reset-size2.size9{font-size:2.88em}.katex .fontsize-ensurer.reset-size2.size10,.katex .sizing.reset-size2.size10{font-size:3.45666667em}.katex .fontsize-ensurer.reset-size2.size11,.katex .sizing.reset-size2.size11{font-size:4.14666667em}.katex .fontsize-ensurer.reset-size3.size1,.katex .sizing.reset-size3.size1{font-size:.71428571em}.katex .fontsize-ensurer.reset-size3.size2,.katex .sizing.reset-size3.size2{font-size:.85714286em}.katex .fontsize-ensurer.reset-size3.size3,.katex .sizing.reset-size3.size3{font-size:1em}.katex .fontsize-ensurer.reset-size3.size4,.katex .sizing.reset-size3.size4{font-size:1.14285714em}.katex .fontsize-ensurer.reset-size3.size5,.katex .sizing.reset-size3.size5{font-size:1.28571429em}.katex .fontsize-ensurer.reset-size3.size6,.katex .sizing.reset-size3.size6{font-size:1.42857143em}.katex .fontsize-ensurer.reset-size3.size7,.katex .sizing.reset-size3.size7{font-size:1.71428571em}.katex .fontsize-ensurer.reset-size3.size8,.katex .sizing.reset-size3.size8{font-size:2.05714286em}.katex .fontsize-ensurer.reset-size3.size9,.katex .sizing.reset-size3.size9{font-size:2.46857143em}.katex .fontsize-ensurer.reset-size3.size10,.katex .sizing.reset-size3.size10{font-size:2.96285714em}.katex .fontsize-ensurer.reset-size3.size11,.katex .sizing.reset-size3.size11{font-size:3.55428571em}.katex .fontsize-ensurer.reset-size4.size1,.katex .sizing.reset-size4.size1{font-size:.625em}.katex .fontsize-ensurer.reset-size4.size2,.katex .sizing.reset-size4.size2{font-size:.75em}.katex .fontsize-ensurer.reset-size4.size3,.katex .sizing.reset-size4.size3{font-size:.875em}.katex .fontsize-ensurer.reset-size4.size4,.katex .sizing.reset-size4.size4{font-size:1em}.katex .fontsize-ensurer.reset-size4.size5,.katex .sizing.reset-size4.size5{font-size:1.125em}.katex .fontsize-ensurer.reset-size4.size6,.katex .sizing.reset-size4.size6{font-size:1.25em}.katex .fontsize-ensurer.reset-size4.size7,.katex .sizing.reset-size4.size7{font-size:1.5em}.katex .fontsize-ensurer.reset-size4.size8,.katex .sizing.reset-size4.size8{font-size:1.8em}.katex .fontsize-ensurer.reset-size4.size9,.katex .sizing.reset-size4.size9{font-size:2.16em}.katex .fontsize-ensurer.reset-size4.size10,.katex .sizing.reset-size4.size10{font-size:2.5925em}.katex .fontsize-ensurer.reset-size4.size11,.katex .sizing.reset-size4.size11{font-size:3.11em}.katex .fontsize-ensurer.reset-size5.size1,.katex .sizing.reset-size5.size1{font-size:.55555556em}.katex .fontsize-ensurer.reset-size5.size2,.katex .sizing.reset-size5.size2{font-size:.66666667em}.katex .fontsize-ensurer.reset-size5.size3,.katex .sizing.reset-size5.size3{font-size:.77777778em}.katex .fontsize-ensurer.reset-size5.size4,.katex .sizing.reset-size5.size4{font-size:.88888889em}.katex .fontsize-ensurer.reset-size5.size5,.katex .sizing.reset-size5.size5{font-size:1em}.katex .fontsize-ensurer.reset-size5.size6,.katex .sizing.reset-size5.size6{font-size:1.11111111em}.katex .fontsize-ensurer.reset-size5.size7,.katex .sizing.reset-size5.size7{font-size:1.33333333em}.katex .fontsize-ensurer.reset-size5.size8,.katex .sizing.reset-size5.size8{font-size:1.6em}.katex .fontsize-ensurer.reset-size5.size9,.katex .sizing.reset-size5.size9{font-size:1.92em}.katex .fontsize-ensurer.reset-size5.size10,.katex .sizing.reset-size5.size10{font-size:2.30444444em}.katex .fontsize-ensurer.reset-size5.size11,.katex .sizing.reset-size5.size11{font-size:2.76444444em}.katex .fontsize-ensurer.reset-size6.size1,.katex .sizing.reset-size6.size1{font-size:.5em}.katex .fontsize-ensurer.reset-size6.size2,.katex .sizing.reset-size6.size2{font-size:.6em}.katex .fontsize-ensurer.reset-size6.size3,.katex .sizing.reset-size6.size3{font-size:.7em}.katex .fontsize-ensurer.reset-size6.size4,.katex .sizing.reset-size6.size4{font-size:.8em}.katex .fontsize-ensurer.reset-size6.size5,.katex .sizing.reset-size6.size5{font-size:.9em}.katex .fontsize-ensurer.reset-size6.size6,.katex .sizing.reset-size6.size6{font-size:1em}.katex .fontsize-ensurer.reset-size6.size7,.katex .sizing.reset-size6.size7{font-size:1.2em}.katex .fontsize-ensurer.reset-size6.size8,.katex .sizing.reset-size6.size8{font-size:1.44em}.katex .fontsize-ensurer.reset-size6.size9,.katex .sizing.reset-size6.size9{font-size:1.728em}.katex .fontsize-ensurer.reset-size6.size10,.katex .sizing.reset-size6.size10{font-size:2.074em}.katex .fontsize-ensurer.reset-size6.size11,.katex .sizing.reset-size6.size11{font-size:2.488em}.katex .fontsize-ensurer.reset-size7.size1,.katex .sizing.reset-size7.size1{font-size:.41666667em}.katex .fontsize-ensurer.reset-size7.size2,.katex .sizing.reset-size7.size2{font-size:.5em}.katex .fontsize-ensurer.reset-size7.size3,.katex .sizing.reset-size7.size3{font-size:.58333333em}.katex .fontsize-ensurer.reset-size7.size4,.katex .sizing.reset-size7.size4{font-size:.66666667em}.katex .fontsize-ensurer.reset-size7.size5,.katex .sizing.reset-size7.size5{font-size:.75em}.katex .fontsize-ensurer.reset-size7.size6,.katex .sizing.reset-size7.size6{font-size:.83333333em}.katex .fontsize-ensurer.reset-size7.size7,.katex .sizing.reset-size7.size7{font-size:1em}.katex .fontsize-ensurer.reset-size7.size8,.katex .sizing.reset-size7.size8{font-size:1.2em}.katex .fontsize-ensurer.reset-size7.size9,.katex .sizing.reset-size7.size9{font-size:1.44em}.katex .fontsize-ensurer.reset-size7.size10,.katex .sizing.reset-size7.size10{font-size:1.72833333em}.katex .fontsize-ensurer.reset-size7.size11,.katex .sizing.reset-size7.size11{font-size:2.07333333em}.katex .fontsize-ensurer.reset-size8.size1,.katex .sizing.reset-size8.size1{font-size:.34722222em}.katex .fontsize-ensurer.reset-size8.size2,.katex .sizing.reset-size8.size2{font-size:.41666667em}.katex .fontsize-ensurer.reset-size8.size3,.katex .sizing.reset-size8.size3{font-size:.48611111em}.katex .fontsize-ensurer.reset-size8.size4,.katex .sizing.reset-size8.size4{font-size:.55555556em}.katex .fontsize-ensurer.reset-size8.size5,.katex .sizing.reset-size8.size5{font-size:.625em}.katex .fontsize-ensurer.reset-size8.size6,.katex .sizing.reset-size8.size6{font-size:.69444444em}.katex .fontsize-ensurer.reset-size8.size7,.katex .sizing.reset-size8.size7{font-size:.83333333em}.katex .fontsize-ensurer.reset-size8.size8,.katex .sizing.reset-size8.size8{font-size:1em}.katex .fontsize-ensurer.reset-size8.size9,.katex .sizing.reset-size8.size9{font-size:1.2em}.katex .fontsize-ensurer.reset-size8.size10,.katex .sizing.reset-size8.size10{font-size:1.44027778em}.katex .fontsize-ensurer.reset-size8.size11,.katex .sizing.reset-size8.size11{font-size:1.72777778em}.katex .fontsize-ensurer.reset-size9.size1,.katex .sizing.reset-size9.size1{font-size:.28935185em}.katex .fontsize-ensurer.reset-size9.size2,.katex .sizing.reset-size9.size2{font-size:.34722222em}.katex .fontsize-ensurer.reset-size9.size3,.katex .sizing.reset-size9.size3{font-size:.40509259em}.katex .fontsize-ensurer.reset-size9.size4,.katex .sizing.reset-size9.size4{font-size:.46296296em}.katex .fontsize-ensurer.reset-size9.size5,.katex .sizing.reset-size9.size5{font-size:.52083333em}.katex .fontsize-ensurer.reset-size9.size6,.katex .sizing.reset-size9.size6{font-size:.5787037em}.katex .fontsize-ensurer.reset-size9.size7,.katex .sizing.reset-size9.size7{font-size:.69444444em}.katex .fontsize-ensurer.reset-size9.size8,.katex .sizing.reset-size9.size8{font-size:.83333333em}.katex .fontsize-ensurer.reset-size9.size9,.katex .sizing.reset-size9.size9{font-size:1em}.katex .fontsize-ensurer.reset-size9.size10,.katex .sizing.reset-size9.size10{font-size:1.20023148em}.katex .fontsize-ensurer.reset-size9.size11,.katex .sizing.reset-size9.size11{font-size:1.43981481em}.katex .fontsize-ensurer.reset-size10.size1,.katex .sizing.reset-size10.size1{font-size:.24108004em}.katex .fontsize-ensurer.reset-size10.size2,.katex .sizing.reset-size10.size2{font-size:.28929605em}.katex .fontsize-ensurer.reset-size10.size3,.katex .sizing.reset-size10.size3{font-size:.33751205em}.katex .fontsize-ensurer.reset-size10.size4,.katex .sizing.reset-size10.size4{font-size:.38572806em}.katex .fontsize-ensurer.reset-size10.size5,.katex .sizing.reset-size10.size5{font-size:.43394407em}.katex .fontsize-ensurer.reset-size10.size6,.katex .sizing.reset-size10.size6{font-size:.48216008em}.katex .fontsize-ensurer.reset-size10.size7,.katex .sizing.reset-size10.size7{font-size:.57859209em}.katex .fontsize-ensurer.reset-size10.size8,.katex .sizing.reset-size10.size8{font-size:.69431051em}.katex .fontsize-ensurer.reset-size10.size9,.katex .sizing.reset-size10.size9{font-size:.83317261em}.katex .fontsize-ensurer.reset-size10.size10,.katex .sizing.reset-size10.size10{font-size:1em}.katex .fontsize-ensurer.reset-size10.size11,.katex .sizing.reset-size10.size11{font-size:1.19961427em}.katex .fontsize-ensurer.reset-size11.size1,.katex .sizing.reset-size11.size1{font-size:.20096463em}.katex .fontsize-ensurer.reset-size11.size2,.katex .sizing.reset-size11.size2{font-size:.24115756em}.katex .fontsize-ensurer.reset-size11.size3,.katex .sizing.reset-size11.size3{font-size:.28135048em}.katex .fontsize-ensurer.reset-size11.size4,.katex .sizing.reset-size11.size4{font-size:.32154341em}.katex .fontsize-ensurer.reset-size11.size5,.katex .sizing.reset-size11.size5{font-size:.36173633em}.katex .fontsize-ensurer.reset-size11.size6,.katex .sizing.reset-size11.size6{font-size:.40192926em}.katex .fontsize-ensurer.reset-size11.size7,.katex .sizing.reset-size11.size7{font-size:.48231511em}.katex .fontsize-ensurer.reset-size11.size8,.katex .sizing.reset-size11.size8{font-size:.57877814em}.katex .fontsize-ensurer.reset-size11.size9,.katex .sizing.reset-size11.size9{font-size:.69453376em}.katex .fontsize-ensurer.reset-size11.size10,.katex .sizing.reset-size11.size10{font-size:.83360129em}.katex .fontsize-ensurer.reset-size11.size11,.katex .sizing.reset-size11.size11{font-size:1em}.katex .delimsizing.size1{font-family:KaTeX_Size1}.katex .delimsizing.size2{font-family:KaTeX_Size2}.katex .delimsizing.size3{font-family:KaTeX_Size3}.katex .delimsizing.size4{font-family:KaTeX_Size4}.katex .delimsizing.mult .delim-size1>span{font-family:KaTeX_Size1}.katex .delimsizing.mult .delim-size4>span{font-family:KaTeX_Size4}.katex .nulldelimiter{display:inline-block;width:.12em}.katex .delimcenter,.katex .op-symbol{position:relative}.katex .op-symbol.small-op{font-family:KaTeX_Size1}.katex .op-symbol.large-op{font-family:KaTeX_Size2}.katex .accent>.vlist-t,.katex .op-limits>.vlist-t{text-align:center}.katex .accent .accent-body{position:relative}.katex .accent .accent-body:not(.accent-full){width:0}.katex .overlay{display:block}.katex .mtable .vertical-separator{display:inline-block;min-width:1px}.katex .mtable .arraycolsep{display:inline-block}.katex .mtable .col-align-c>.vlist-t{text-align:center}.katex .mtable .col-align-l>.vlist-t{text-align:left}.katex .mtable .col-align-r>.vlist-t{text-align:right}.katex .svg-align{text-align:left}.katex svg{fill:currentColor;stroke:currentColor;fill-rule:nonzero;fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:block;height:inherit;position:absolute;width:100%}.katex svg path{stroke:none}.katex img{border-style:none;max-height:none;max-width:none;min-height:0;min-width:0}.katex .stretchy{display:block;overflow:hidden;position:relative;width:100%}.katex .stretchy:after,.katex .stretchy:before{content:""}.katex .hide-tail{overflow:hidden;position:relative;width:100%}.katex .halfarrow-left{left:0;overflow:hidden;position:absolute;width:50.2%}.katex .halfarrow-right{overflow:hidden;position:absolute;right:0;width:50.2%}.katex .brace-left{left:0;overflow:hidden;position:absolute;width:25.1%}.katex .brace-center{left:25%;overflow:hidden;position:absolute;width:50%}.katex .brace-right{overflow:hidden;position:absolute;right:0;width:25.1%}.katex .x-arrow-pad{padding:0 .5em}.katex .cd-arrow-pad{padding:0 .55556em 0 .27778em}.katex .mover,.katex .munder,.katex .x-arrow{text-align:center}.katex .boxpad{padding:0 .3em}.katex .fbox,.katex .fcolorbox{border:.04em solid;box-sizing:border-box}.katex .cancel-pad{padding:0 .2em}.katex .cancel-lap{margin-left:-.2em;margin-right:-.2em}.katex .sout{border-bottom-style:solid;border-bottom-width:.08em}.katex .angl{border-right:.049em solid;border-top:.049em solid;box-sizing:border-box;margin-right:.03889em}.katex .anglpad{padding:0 .03889em}.katex .eqn-num:before{content:"(" counter(katexEqnNo) ")";counter-increment:katexEqnNo}.katex .mml-eqn-num:before{content:"(" counter(mmlEqnNo) ")";counter-increment:mmlEqnNo}.katex .mtr-glue{width:50%}.katex .cd-vert-arrow{display:inline-block;position:relative}.katex .cd-label-left{display:inline-block;position:absolute;right:calc(50% + .3em);text-align:left}.katex .cd-label-right{display:inline-block;left:calc(50% + .3em);position:absolute;text-align:right}.katex-display{display:block;margin:1em 0;text-align:center}.katex-display>.katex{display:block;text-align:center;white-space:nowrap}.katex-display>.katex>.katex-html{display:block;position:relative}.katex-display>.katex>.katex-html>.tag{position:absolute;right:0}.katex-display.leqno>.katex>.katex-html>.tag{left:0;right:auto}.katex-display.fleqn>.katex{padding-left:2em;text-align:left}body{counter-reset:katexEqnNo mmlEqnNo}
</style><style id="__markdown-viewer__texmath_css">/* style for html inside of browsers */
.katex { font-size: 1em !important; } /* align KaTeX font-size to surrounding text */
eq { display: inline-block; }
eqn { display: block}
section.eqno {
display: flex;
flex-direction: row;
align-content: space-between;
align-items: center;
}
section.eqno > eqn {
width: 100%;
margin-left: 3em;
}
section.eqno > span {
width:3em;
text-align:right;
}
</style><style id="__markdown-viewer__menu_css">/* Style for the menu, possible positions/visibility */
#__markdown-viewer__tools {
margin:0;
padding:0;
background:#555;
color:#eee;
box-shadow:0 -1px rgba(0,0,0,.5) inset;
border-radius: .5em;
max-width: 25%;
min-width: 2.8em;
min-height: 3em;
z-index: 2147483647;
position: relative;
}
#__markdown-viewer__tools.floating {
float:right;
margin: 0 0 .5em .5em;
}
#__markdown-viewer__tools.fixed {
max-height: calc(100vh - 1em);
overflow-y: auto;
position:fixed;
top:.5em;
right:1em;
}
#__markdown-viewer__tools.hidden {
display:none;
}
@media print {
#__markdown-viewer__tools {
display: none;
}
}
#__markdown-viewer__tools a[href]:after {
content: "";
}
/* Style for the menu top */
label[for=__markdown-viewer__show-tools] {
display:block;
padding:0 18px 0 12px;
line-height:3em;
background:#333;
cursor:pointer;
border-radius: .5em;
min-height: 3em;
width: .9em;
position: absolute;
right: 0;
}
input#__markdown-viewer__show-tools:not(:checked) ~ label {
margin-left: -.9em;
}
input#__markdown-viewer__show-tools:checked ~ label {
}
label[for=__markdown-viewer__show-tools]:before{
}
label[for=__markdown-viewer__show-tools]:after {
content:"";
display:inline-block;
float:right;
margin-top:1.5em;
right:5px;
width:0;
height:0;
border-style: solid;
border-color: rgba(255,255,255,.5) transparent;
border-width: 4px 4px 0 4px;
transition:border-bottom .1s, border-top .1s .1s;
}
input#__markdown-viewer__show-tools:checked ~ label:after {
border-top-width:0;
border-bottom-width:4px;
transition:border-top .1s, border-bottom .1s .1s;
}
/* hide the input that tracks the menu's visibility */
input#__markdown-viewer__show-tools {
display:none;
}
/* style, and hide/show menu items based on the input being checked */
#__markdown-viewer__tools > .toggleable {
overflow:hidden;
transition-property:max-height, max-width, padding-top, padding-bottom, margin-top, margin-bottom;
transition-duration:0.5s;
}
input#__markdown-viewer__show-tools:checked ~ .toggleable {
/* maxes should be 'none' or infinite values, however those are not aniimatable, so just put something big enough. */
max-width: 2000px;
max-height: 2000px;
overflow-y: auto;
transition-timing-function:ease-in;
}
input#__markdown-viewer__show-tools:not(:checked) ~ .toggleable {
max-height:0;
max-width:0;
transition-timing-function:ease-out;
padding-top:0;
padding-bottom:0;
margin-top:0;
margin-bottom:0;
}
/* style the table of contents and its items */
#__markdown-viewer__toc {
display:block;
padding: .5em;
border:0;
}
#__markdown-viewer__toc::before {
content: "Table of Contents";
text-align: center;
display: block;
font-weight: bold;
text-decoration: underline;
}
#__markdown-viewer__toc {
margin-top: 2em;
}
#__markdown-viewer__tools.fixed input#__markdown-viewer__show-tools:checked ~ #__markdown-viewer__toc {
max-height: calc(100vh - 16em);
}
input#__markdown-viewer__show-tools:checked ~ #__markdown-viewer__toc::before {
position: absolute;
top: .5em;
left: 0;
right: 3em;
}
#__markdown-viewer__tools select {
max-width: 40%;
margin: 0 .5em;
}
#__markdown-viewer__tools select,
#__markdown-viewer__toc * {
white-space: nowrap;
overflow-x: hidden;
text-overflow: ellipsis;
}
#__markdown-viewer__tools a {
color: white;
text-decoration: none;
}
#__markdown-viewer__toc ul {
list-style: inside "• ";
padding: 0;
margin: 0;
}
#__markdown-viewer__toc ul ul {
padding-left: 1.5em;
}
/* Style the "Download Source" button at the end of the menu */
#__markdown-viewer__tools > p {
text-align:center;
padding: 0 .5em;
}
#__markdown-viewer__download {
/* appearance: button; */
-moz-appearance: button !important;
display:inline-block;
text-align: center;
text-decoration:none;
margin: .5em auto;
}
</style><style id="__markdown-viewer__custom_css"></style><meta name="viewport" content="width=device-width, initial-scale=1"><title>Chapter 4: Automatically Generating the AST and Using Regex in Grammars</title></head><body><div id="__markdown-viewer__tools" class="floating"><input type="checkbox" id="__markdown-viewer__show-tools"><label for="__markdown-viewer__show-tools"></label><div id="__markdown-viewer__toc" class="toggleable"><ul><li><a href="#chapter-4-automatically-generating-the-ast-and-using-regex-in-grammars">Chapter 4: Automatically Generating the AST and Using Regex in Grammars</a><ul><li><a href="#automatically-adding-new-rules-with-and">Automatically Adding New Rules with *, + and ?</a></li><li><a href="#invoking-the-parser">Invoking the Parser</a></li><li><a href="#json-parser">JSON Parser</a></li><li><a href="#rules-of-ast-generation">Rules of AST Generation</a></li><li><a href="#overriding-types-and-actions">Overriding Types and Actions</a></li></ul></li></ul></div><p class="toggleable">Pick a markdown and code style:<br><select id="__markdown-viewer__mdselect"><option value="sss">default</option><option value="github">github</option></select><select id="__markdown-viewer__hlselect"><option value="a11y-dark">a11y-dark</option><option value="a11y-light">a11y-light</option><option value="a11y-auto">a11y-auto</option><option value="agate">agate</option><option value="androidstudio">androidstudio</option><option value="an-old-hope">an-old-hope</option><option value="arduino-light">arduino-light</option><option value="arta">arta</option><option value="ascetic">ascetic</option><option value="atelier-cave-dark">atelier-cave-dark</option><option value="atelier-cave-light">atelier-cave-light</option><option value="atelier-cave-auto">atelier-cave-auto</option><option value="atelier-dune-dark">atelier-dune-dark</option><option value="atelier-dune-light">atelier-dune-light</option><option value="atelier-dune-auto">atelier-dune-auto</option><option value="atelier-estuary-dark">atelier-estuary-dark</option><option value="atelier-estuary-light">atelier-estuary-light</option><option value="atelier-estuary-auto">atelier-estuary-auto</option><option value="atelier-forest-dark">atelier-forest-dark</option><option value="atelier-forest-light">atelier-forest-light</option><option value="atelier-forest-auto">atelier-forest-auto</option><option value="atelier-heath-dark">atelier-heath-dark</option><option value="atelier-heath-light">atelier-heath-light</option><option value="atelier-heath-auto">atelier-heath-auto</option><option value="atelier-lakeside-dark">atelier-lakeside-dark</option><option value="atelier-lakeside-light">atelier-lakeside-light</option><option value="atelier-lakeside-auto">atelier-lakeside-auto</option><option value="atelier-plateau-dark">atelier-plateau-dark</option><option value="atelier-plateau-light">atelier-plateau-light</option><option value="atelier-plateau-auto">atelier-plateau-auto</option><option value="atelier-savanna-dark">atelier-savanna-dark</option><option value="atelier-savanna-light">atelier-savanna-light</option><option value="atelier-savanna-auto">atelier-savanna-auto</option><option value="atelier-seaside-dark">atelier-seaside-dark</option><option value="atelier-seaside-light">atelier-seaside-light</option><option value="atelier-seaside-auto">atelier-seaside-auto</option><option value="atelier-sulphurpool-dark">atelier-sulphurpool-dark</option><option value="atelier-sulphurpool-light">atelier-sulphurpool-light</option><option value="atelier-sulphurpool-auto">atelier-sulphurpool-auto</option><option value="atom-one-dark">atom-one-dark</option><option value="atom-one-dark-reasonable">atom-one-dark-reasonable</option><option value="atom-one-light">atom-one-light</option><option value="brown-paper">brown-paper</option><option value="codepen-embed">codepen-embed</option><option value="color-brewer">color-brewer</option><option value="darcula">darcula</option><option value="dark">dark</option><option value="default">default</option><option value="docco">docco</option><option value="dracula">dracula</option><option value="far">far</option><option value="foundation">foundation</option><option value="github">github</option><option value="github-gist">github-gist</option><option value="gml">gml</option><option value="googlecode">googlecode</option><option value="gradient-dark">gradient-dark</option><option value="grayscale">grayscale</option><option value="gruvbox-dark">gruvbox-dark</option><option value="gruvbox-light">gruvbox-light</option><option value="gruvbox-auto">gruvbox-auto</option><option value="hopscotch">hopscotch</option><option value="hybrid">hybrid</option><option value="idea">idea</option><option value="ir-black">ir-black</option><option value="isbl-editor-dark">isbl-editor-dark</option><option value="isbl-editor-light">isbl-editor-light</option><option value="isbl-editor-auto">isbl-editor-auto</option><option value="kimbie">kimbie</option><option value="kimbie">kimbie</option><option value="lightfair">lightfair</option><option value="lioshi">lioshi</option><option value="magula">magula</option><option value="mono-blue">mono-blue</option><option value="monokai">monokai</option><option value="monokai-sublime">monokai-sublime</option><option value="night-owl">night-owl</option><option value="nnfx">nnfx</option><option value="nnfx-dark">nnfx-dark</option><option value="nord">nord</option><option value="obsidian">obsidian</option><option value="ocean">ocean</option><option value="paraiso-dark">paraiso-dark</option><option value="paraiso-light">paraiso-light</option><option value="paraiso-auto">paraiso-auto</option><option value="pojoaque">pojoaque</option><option value="purebasic">purebasic</option><option value="qtcreator_dark">qtcreator_dark</option><option value="qtcreator_light">qtcreator_light</option><option value="qtcreator_auto">qtcreator_auto</option><option value="railscasts">railscasts</option><option value="rainbow">rainbow</option><option value="routeros">routeros</option><option value="school-book">school-book</option><option value="shades-of-purple">shades-of-purple</option><option value="solarized-dark">solarized-dark</option><option value="solarized-light">solarized-light</option><option value="solarized-auto">solarized-auto</option><option value="srcery">srcery</option><option value="sunburst">sunburst</option><option value="tomorrow">tomorrow</option><option value="tomorrow-night">tomorrow-night</option><option value="tomorrow-night-blue">tomorrow-night-blue</option><option value="tomorrow-night-bright">tomorrow-night-bright</option><option value="tomorrow-night-eighties">tomorrow-night-eighties</option><option value="vs">vs</option><option value="vs2015">vs2015</option><option value="xcode">xcode</option><option value="xt256">xt256</option><option value="zenburn">zenburn</option></select></p><p class="toggleable"><a id="__markdown-viewer__download" download="markdown.html" style="display: none;" href="blob:null/2d355107-0649-459c-a656-f01ee84364ef">Download as HTML</a></p></div><div class="markdownRoot"><h2 id="chapter-4-automatically-generating-the-ast-and-using-regex-in-grammars">Chapter 4: Automatically Generating the AST and Using Regex in Grammars</h2>
<p>Rustlr is capable of automatically generating the data types
(enums and structs) for the abstract syntax of a language as well as
the semantic actions required to create instances of those types.
For beginners new to writing grammars and parsers, we <strong>do not</strong>
recommend starting with an automatically generated AST. The user must
understand clearly the relationship between concrete and abstract
syntax and the best way to learn this relationship is by writing ASTs
by hand, as demonstrated in the previous chapters. Even with Rustlr
capable of generating nearly everything one might need from a parser,
it is still possible that careful fine tuning will be required.</p>
<p>Rustlr Version 0.3.0 has significantly upgraded the ability to generate abstract syntax from earlier versions.</p>
<p>We redo the enhanced calculator example from <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter2.html">Chapter 2</a>.
Although some form of abstract syntax can be generated for any
grammar, the format of the grammar can greatly influence the form of
the AST types. To illustrate the various choices, this grammar is a
hybrid between the purely unambiguous grammar of <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter1.html">Chapter
1</a> and the one in <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter2.html">Chapter 2</a> in that operator
precedence declarations are only given for the binary arithmetic
operators. For the unary minus and the <code>=</code> sign in let-expressions,
we choose to define different syntactic categories in the form of
extra non-terminal symbols <code>UnaryExpr</code> and <code>LetExpr</code>. Along with
<code>Expr</code> they define three levels of precedence from weakest to
strongest: <code>LetExpr</code>, <code>Expr</code>, and <code>UnaryExpr</code>. Writing ambiguous
grammars with operator precedence/associativity declarations is
convenient and can make the grammar more readable. They also lead to
more reasonable abstract syntax. Symbols such as <code>T</code> in <code>E --> T</code>
often have no meaning at the abstract syntax level. However, when
there are a large number of operators and precedence levels, using such
declarations alone may be problematic (See the original <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/cparser/cauto.grammar">ANSI C</a> grammar).
Besides, these categories sometimes have genuine semantic meaning,
such as the distinction between lvalues and rvalues.</p>
<p>The following grammar is found
<a href="https://cs.hofstra.edu/~cscccl/rustlr_project/autocalc/calcauto.grammar">here</a>.</p>
<pre><code># the auto directive means AST types and semantic actions will be generated
auto
lifetime <span class="hljs-symbol">'lt</span>
terminals + - * / ( ) = ;
terminals <span class="hljs-keyword">let</span> <span class="hljs-keyword">in</span>
valueterminal int ~ <span class="hljs-built_in">i64</span> ~ Num(n) ~ n
valueterminal var ~ &<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span> ~ Alphanum(n) ~ n
lexattribute set_line_comment(<span class="hljs-string">"#"</span>)
nonterminals Expr ExprList
nonterminal UnaryExpr : Expr
nonterminal LetExpr : Expr
topsym ExprList
resync ;
left * <span class="hljs-number">500</span>
left / <span class="hljs-number">500</span>
left + <span class="hljs-number">400</span>
left - <span class="hljs-number">400</span>
UnaryExpr:Val --> int
UnaryExpr:Var --> var
UnaryExpr:Neg --> - UnaryExpr
UnaryExpr --> ( LetExpr )
Expr --> UnaryExpr
Expr:Plus --> Expr + Expr
Expr:Minus --> Expr - Expr
Expr:Div --> Expr / Expr
Expr:Times --> Expr * Expr
LetExpr --> Expr
LetExpr:Let --> <span class="hljs-keyword">let</span> var = Expr <span class="hljs-keyword">in</span> LetExpr
ExprList:nil -->
ExprList:cons --> LetExpr ; ExprList
EOF
</code></pre>
<p>Note the following, further differences between this grammar and the one presented in <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter2.html">Chapter 2</a>:</p>
<ol>
<li>
<p>There are no semantic actions</p>
</li>
<li>
<p>There is no "absyntype" or "valuetype" declaration; any such declaration would be ignored when using the <code>auto</code> option, which is enabled by the <code>auto</code>
directive at the top of the grammar, or by the <code>-auto</code> flag given to the
rustlr executable.</p>
</li>
<li>
<p>Only the types of values carried by certain terminal symbols must be declared (with <code>typedterminal</code> or <code>valueterminal</code>).
A <code>valueterminal</code> declaration is
just a combination of a <code>typedterminal</code> and a <code>lexvalue</code> declaration, with <code>~</code> separating the components. The other terminals all have type () (unit).</p>
</li>
<li>
<p>The non-terminal symbol on the left-hand side of a production rule may carry a label. These labels will become the names of enum variants to be created.</p>
</li>
</ol>
<p>Process the grammar with <strong><code>rustlr calcauto.grammar</code></strong> (without the <code>auto</code> directive inside the grammar, run rustlr with the <code>-auto</code> option). Two files are created. Besides <strong><a href="https://cs.hofstra.edu/~cscccl/rustlr_project/autocalc/src/calcautoparser.rs">calcautoparser.rs</a></strong> there will be, in the
same folder as the parser, a <strong><a href="https://cs.hofstra.edu/~cscccl/rustlr_project/autocalc/src/calcauto_ast.rs">calcauto_ast.rs</a></strong> with the following (principal) contents:</p>
<pre><code class="language-rust"><span class="hljs-meta">#[derive(Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">enum</span> <span class="hljs-title">ExprList</span></span><<span class="hljs-symbol">'lt</span>> {
nil,
cons(Expr<<span class="hljs-symbol">'lt</span>>,LBox<ExprList<<span class="hljs-symbol">'lt</span>>>),
ExprList_Nothing,
}
<span class="hljs-keyword">impl</span><<span class="hljs-symbol">'lt</span>> <span class="hljs-built_in">Default</span> <span class="hljs-keyword">for</span> ExprList<<span class="hljs-symbol">'lt</span>> { <span class="hljs-function"><span class="hljs-keyword">fn</span> <span class="hljs-title">default</span></span>()-><span class="hljs-keyword">Self</span> { ExprList::ExprList_No
thing } }
<span class="hljs-meta">#[derive(Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">enum</span> <span class="hljs-title">Expr</span></span><<span class="hljs-symbol">'lt</span>> {
Plus(LBox<Expr<<span class="hljs-symbol">'lt</span>>>,LBox<Expr<<span class="hljs-symbol">'lt</span>>>),
Minus(LBox<Expr<<span class="hljs-symbol">'lt</span>>>,LBox<Expr<<span class="hljs-symbol">'lt</span>>>),
Div(LBox<Expr<<span class="hljs-symbol">'lt</span>>>,LBox<Expr<<span class="hljs-symbol">'lt</span>>>),
Times(LBox<Expr<<span class="hljs-symbol">'lt</span>>>,LBox<Expr<<span class="hljs-symbol">'lt</span>>>),
Var(&<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>),
Neg(LBox<Expr<<span class="hljs-symbol">'lt</span>>>),
Val(<span class="hljs-built_in">i64</span>),
Let(&<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>,LBox<Expr<<span class="hljs-symbol">'lt</span>>>,LBox<Expr<<span class="hljs-symbol">'lt</span>>>),
Expr_Nothing,
}
<span class="hljs-keyword">impl</span><<span class="hljs-symbol">'lt</span>> <span class="hljs-built_in">Default</span> <span class="hljs-keyword">for</span> Expr<<span class="hljs-symbol">'lt</span>> { <span class="hljs-function"><span class="hljs-keyword">fn</span> <span class="hljs-title">default</span></span>()-><span class="hljs-keyword">Self</span> { Expr::Expr_Nothing } }
</code></pre>
<p>Compare these types with the manually written ones in <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter2.html">Chapter 2</a>: they
are not so different.
For example, the expression <code>5 - 7 - -9</code> will be represented in
abstract syntax as <code>Minus(Minus(Val(5), Val(7)), Neg(Val(9)))</code>. This is
exactly what we want.</p>
<p>Generally speaking, a new type is created for each non-terminal symbol
of the grammar, which will also share the same name as the
non-terminal itself. But this would mean that separate types would be
created for <code>LetExpr</code> and <code>UnaryExpr</code> as well, which would lead to
convoluted types that serve no purpose. Their creation was avoided
with the following declarations:</p>
<pre><code><span class="hljs-attr">nonterminal UnaryExpr :</span> <span class="hljs-string">Expr</span>
<span class="hljs-attr">nonterminal LetExpr :</span> <span class="hljs-string">Expr</span>
</code></pre>
<p>The syntax means that instead of generating new types, the ASTs representing
the rules for <code>UnaryExpr</code> and <code>LetExpr</code> would <em>extend</em> the enum that would
be created for <code>Expr</code>. The type created for Expr must be an enum for this
to work (it would not work if it was a struct).
Leave out the <code>: Expr</code> portion from the declarations and we will get
<a href="https://cs.hofstra.edu/~cscccl/rustlr_project/autocalc/src/calcb_ast.rs">these types</a> instead. They would be more cumbersome to work with.</p>
<h4 id="rules-of-ast-generation">Rules of AST Generation</h4>
<p>An enum is created for each non-terminal symbol of the grammar that appears on the left-hand side of multiple production rules, unless the type of the non-terminal is declared to "extend" another type as explained above. The name of the enum is the
same as the name of the non-terminal.
The names of the variants are derived from the labels given to the left-hand side nonterminal, or are automatically generated from the nonterminal name and the rule number (e.g. <code>Expr_8</code>). A special <code>Nothing</code> variant is also created to represent a default.
There is normally an enum variant for each production rule of this non-terminal. Each variant is composed of the right-hand side
symbols of the rule that are associated with non-unit types. Unit typed values
can also become part of the enum if the symbol is given a label. For example:
<strong><code>E:acase --> a E</code></strong> where terminal symbol <code>a</code> is of unit type, will result in a enum variant
<code>acase(LBox<E>)</code>. whereas
<strong><code>E:acase --> a:m E</code></strong>
will result in a variant <code>acase((),LBox<E>)</code></p>
<p>A struct is created for any non-terminal symbol that appears on the
left-hand side of exactly one production rule, unless the type of that
nonterminal is declared to extend another type.
You can also force an enum to be created instead of a struct by
giving the singleton rule a left-hand side label, in which case the label
will name the sole variant of the enum (besides the <code>_Nothing</code> default).
This would be required when you know that the type will be extended with
other variants, as demonstrated above.</p>
<p>The name of the struct is the same as the non-terminal. If any of the grammar symbols
on the right-hand side of the rule is given a label, it would create a struct
with the fields of each struct named by these labels, or
with <code>_item{i}_</code> if
no labels are given. For example, a nonterminal <code>Ifelse</code> with a singleton rule</p>
<pre><code>Ifelse --> <span class="hljs-keyword">if</span> Expr:condition Expr <span class="hljs-keyword">else</span> Expr
</code></pre>
<p>will result in the generation of:</p>
<pre><code><span class="hljs-meta">#[derive(Default,Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">Ifelse</span></span> {
<span class="hljs-keyword">pub</span> condition: LBox<Expr>,
<span class="hljs-keyword">pub</span> _item2_: LBox<Expr>,
<span class="hljs-keyword">pub</span> _item4_: LBox<Expr>,
}
</code></pre>
<p>The <code>_item{i}_</code> labels are generated from the positions of the corresponding
symbols on the right-hand side of the production rule.
If none of the symbols on the right have labels, rustlr creates a tuple
struct. For Example a singleton rule such as <strong><code>whileloop --> while ( expr ) expr</code></strong>
will produce an a <code>struct whileloop(expr,expr);</code> Be careful to avoid
using Rust keywords as the names of non-terminals.</p>
<p>The struct may be empty if all right-hand-side symbols of the single production
rule are associated with the unit type and do not have labels. Rustlr will
generate code to derive the Debug and Default traits for all structs (this
works fine for recursive structs).</p>
<p>Rustlr also calculates a reachability closure so it is aware of which
non-terminals are mutually recursive. It uses this information to
determine where smart pointer are required when defining these
recursive types. Rustlr always uses its <a href="https://docs.rs/rustlr/latest/rustlr/generic_absyn/struct.LBox.html">LBox</a> custom smartpointer
to also include line/column information. Notice that the variant
<code>enum::cons</code> has only the second component in an LBox. One can, for
the sake of recording position information, always create an LBox
regardless of reachability by giving the component a "boxed label".
That is, <code>ExprList:cons --> Expr:[car] SEMICOLON ExprList</code> will
generate a variant that also has its first component in an LBox. The
reachability relation also determines if a type requires a lifetime
parameter.</p>
<p>Although the generated parser may not be very readable, rustlr also generated semantic actions that create instances of these AST types. For example, the rule <code>Expr:Plus --> Expr + Expr</code> will have semantic action equivalent to one created from:</p>
<pre><code><span class="hljs-selector-tag">Expr</span> <span class="hljs-selector-tag">--</span>> <span class="hljs-selector-tag">Expr</span>:<span class="hljs-selector-attr">[a]</span> + <span class="hljs-selector-tag">Expr</span>:<span class="hljs-selector-attr">[b]</span> {<span class="hljs-selector-tag">Plus</span>(a,b)}
</code></pre>
<p>Recall from <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter2.html">Chapter 2</a> that a label of the form <code>[a]</code> means that the semantic value associated with the symbol is enclosed in an <a href="https://docs.rs/rustlr/latest/rustlr/generic_absyn/struct.LBox.html">LBox</a>.</p>
<p>There are three production rules in the grammar that do not
correspond to enum variants: <code>Expr --> UnaryExpr</code>, <code>LetExpr --> Expr</code>
and <code>UnaryExpr --> ( LetExpr )</code>.
Rustlr infers from the fact that</p>
<ol>
<li>there is no left-hand side label for any of these rules</li>
<li>There is exactly one grammar symbol on the right-hand side that has a non-unit
type, and that type is the same as the type of the left-hand side symbol.
The other symbols, if any, are of unit type</li>
<li>There are no labels nor operator precedence/associativity declarations for the other symbols.</li>
</ol>
<p>For the rule <code>UnaryExpr --> ( LetExpr )</code>, it therefore infers that the parentheses on the right hand side carry no meaning at the AST level, and thus generates a semantic action for this rule
that would be equivalent to:</p>
<pre><code> <span class="hljs-selector-tag">UnaryExpr</span> <span class="hljs-selector-tag">--</span>> ( <span class="hljs-attribute">LetExpr</span>:e ) { <span class="hljs-selector-tag">e</span> }
</code></pre>
<p>We refer to such cases as "pass-thru" cases. If the automatically
inferred "meaning" of this rule is not what's desired, it can be
altered by using an explicit left-side label: this will generate a
separate enum variant (at the cost of an extra LBox) that
distinguishes the presence of the parentheses. Note that the
rule <code>UnaryExpr:Neg --> - UnaryExpr</code>, was not recognized as a pass-thru
case by virtue of the left-hand side label <code>Neg</code>. Unlike the parentheses,
the minus symbol certain has meaning beyond the syntactic level.
We can also force the minus sign to be
included in the AST by giving it an explicit lable such as <code>-:minus UnaryExpr</code>.
This would create an enum variant that includes a unit type value.</p>
<p>In general, the usage of labels greatly affect how the AST datatype is
generated. Labels on the left-hand side of a production rule give
names to enum variants. Their presence also cancel "pass-thru"
recognition by always generating an enum variant for the rule.
A left-hand side label will also prevent a struct from being generated even
when a nonterminal has but a single production rule.
Labels on the right-hand side give names to struct components. Their
presence on unit-typed grammar symbols means that the symbols won't be
ignored and will be included in the the type. If a non-terminal has a
single production rule, the lack of any labels left or right leads
to the creation of a simpler tuple struct. Finally, the use of box
labels such as [e] forces the semantic value to be wrapped inside an LBox
whether or not it is required to define recursive types.</p>
<h4 id="overriding-types-and-actions">Overriding Types and Actions</h4>
<p>It is always possible to override the automatically generated types and actions.
In case of ExprList, the labels 'nil' and 'cons' are sufficient for rustlr to create a linked-list data structure. However, the right-recursive grammar rule is slightly non-optimal for LR parsing (the parse stack grows until the last element of the list before ExprList-reductions take place). One might wish to use a left-recursive rule and a Rust vector to represent a sequence of expressions. This can be done in several ways, one of which is by making the following changes to the grammar. First, change the declaration of the non-terminal symbol <code>ExprList</code> as follows:</p>
<pre><code>nonterminal <span class="hljs-type">ExprList</span> <span class="hljs-type">Vec</span><<span class="hljs-type">LBox</span><<span class="hljs-type">Expr</span><'lt>>>
</code></pre>
<p>You probably want to use an LBox even inside a Vec to record the line/column
position information.
Then replace the two production rules for <code>ExprList</code> with the following:</p>
<pre><code class="language-rust">ExprList --> { <span class="hljs-built_in">vec!</span>[] }
ExprList --> ExprList:ev LetExpr:[e] ; { ev.push(e); ev }
</code></pre>
<p>When writing your own types and actions alongside automatically generated ones,
it's best to examine the types that are generated to determine their correct
usage: for example, whether a lifetime parameter is required for <code>Expr</code>.</p>
<p>The presence of a non-empty semantic action will override automatic AST generation. It is also possible to inject custom code into the
automatically generated code:</p>
<pre><code>ExprList --> {<span class="hljs-built_in">println!</span>(<span class="hljs-string">"starting a new ExprList sequence"</span>); ... }
</code></pre>
<p>The ellipsis are allowed only before the closing right-brace. This indicates
that the automatically generated portion of the semantic action should follow.
The ellipsis cannot appear anywhere else.</p>
<p>An easier way to parse a sequence of expressions separated by ; and to
create a vector is to
use the special suffixes <code>+</code>, <code>*</code>, <code>?</code>, <code><_*></code> and <code><_+></code>. These are described below.</p>
<pre><code>
</code></pre>
<hr>
<h3 id="automatically-adding-new-rules-with-and">Automatically Adding New Rules with *, + and ?</h3>
<p>Rustlr allows the use of regular-expression style symbols *, + and ?
to automatically generate new production rules. However, these
symbols cannot be used unrestrictedly to form arbitrary regular
expressions. They cannot be nested. They are also guaranteed to only
fully work in the -auto mode.</p>
<p>Another way to achieve the same effects as the above (to derive a vector for symbol ExprList) is to use the following alternative grammar declarations:</p>
<pre><code>nonterminal ExprList <span class="hljs-built_in">Vec</span><LBox<Expr<<span class="hljs-symbol">'lt</span>>>>
ExprList --> (LetExpr ;)*
</code></pre>
<p>This would lead to the generation of a tuple struct for type ExprList:</p>
<pre><code><span class="hljs-meta">#[derive(Default,Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">ExprList</span></span><<span class="hljs-symbol">'lt</span>>(<span class="hljs-keyword">pub</span> <span class="hljs-built_in">Vec</span><LBox<Expr<<span class="hljs-symbol">'lt</span>>>>,);
</code></pre>
<p>You can also eliminate the extra type for <code>ExprList</code> entirely by manually
defining the type as:</p>
<pre><code>nonterminal <span class="hljs-type">ExprList</span> <span class="hljs-type">Vec</span><<span class="hljs-type">LBox</span><<span class="hljs-type">Expr</span><'lt>>>
</code></pre>
<p>This would cause</p>
<p>The operator <strong><code>*</code></strong> means a sequence of zero or more. This is done by generating several new non-terminal symbols internally. Essentially, these correspond to</p>
<pre><code>ES0 --> Expr:e ; {e}
ES1 --> { Vec::<span class="hljs-built_in">new</span>() }
ES1 --> ES1:v ES0:[e] { v.<span class="hljs-built_in">push</span>(e); v }
ExprList --> ES1:v {v}
</code></pre>
<p>These rules replace the original in the grammar. In the -auto mode,
rustlr also infers that symbols such as ; has no meaning at the
AST level (because it has the unit type and noprecedence/associativity
declaration). It therefore infers that the type of the nonterminal ES0
is the same as Expr, and automatically generates the appropriate semantic action.
If override of this behavior is required, one can manually rewrite the grammar
as</p>
<pre><code>ES0:SEMI <span class="hljs-comment">--> Expr ; </span>
ExprList <span class="hljs-comment">--> ES0*</span>
</code></pre>
<p>The presence of the left-hand side label will cause the AST generator to
create an AST representation for the semicolon (assuming that is what's
desired). Another situation where the user has to write the ES0 rule
manually is if <code>-auto</code> (or <code>-genabsyn</code>) is not specified, which implies
that a rule with an explicit semantic action is required. Generally speaking,
the *, + and ? symbols will still work without <code>-auto</code> if it follows a
single grammar symbol.</p>
<p>The type rustlr associates with the new non-terminal ES1
will be <code>Vec<LBox<Expr<'lt>></code> and semantic actions are generated to
create the vector for both ES1 rules. A <strong><code>+</code></strong> means one or more
<code>ES1</code> derivations, producing the same vector type, and a <strong><code>?</code></strong> will
mean one or zero derivations with type <code>Option<LBox<Expr<'lt>>></code>.</p>
<p>Other alternatives are possible:</p>
<pre><code>nonterminal ExprList
ExprList:Sequence --> (Expr ;)*
</code></pre>
<p>This would generate a new struct type for the AST of ExprList, with a component of
type
<code>Vec<LBox<Expr<'lt>>></code>. If the type of ExprList is declared manually
as above, rustlr infers that the appropriate semantic action is equivalent to
<code>ExprList --> (Expr ;)*:v {v}</code> because there is only one symbol (the internally
generated ES1) on the right-hand side, and it is of the same type.
<strong>The label given for such an expression cannot be a pattern that includes <code>@...@</code>.</strong> It can only be a simple alphanumeric label or a boxed label (<code>[x]</code>). These restrictions may eventually be eliminated in future releases.</p>
<p>Another restriction is that the symbols <code>(</code>, <code>)</code>, <code>?</code>, <code>*</code> and <code>+</code> may not
be separated by white spaces since that would confuse their interpretation
as independent terminal symbols. For example, <code>( Expr ; ) *</code> is not valid.</p>
<p>Yet another alternative is to manually define the type of ExprList, from which Rustlr will infer that no struct/enum needs to be created for it:</p>
<pre><code>nonterminal ExprList <span class="hljs-built_in">Vec</span><LBox<Expr<<span class="hljs-symbol">'lt</span>>>>
ExprList --> (LetExpr ;)*
</code></pre>
<p>This is because rustlr generates an internal non-terminal to represent the right-hand side <code>*</code> expression and assigns it type <code>Vec<LBox<Expr<'lt>>></code>.
It then recognizes that this is the only symbol on the
right, which is of the same type as the left-hand side nonterminal <code>ExprList</code>
as declared. This rule will again be given an action equivalent to
<code>ExprList --> (Expr ;)*:v {v}</code></p>
<p>In addition to the <code>*</code>, <code>+</code> and <code>?</code> suffixes, rustlr also recognizes (non-nested)
suffixes such as <strong><code><Comma*></code></strong> or <strong><code><;+></code></strong>. Assuming that
<code>Comma</code> is a declared terminal symbol of the grammer, the expression
<code>Expr<Comma+></code> represents a sequence of one or more Expr separated by Comma,
but not ending in Comma, e.g <em>a,b,c</em> but not <em>a,b,c,</em>. In contrast,
<code>(Expr Comma)+</code> means that the expression must end in a Comma. <Comma*>
allows the sequence to be empty. The AST generator will also create vectors
as the semantic values of such expressions. Please avoid whitespaces in
these expressions: <code><Comma *></code> is not recognized.</p>
<p>Be warned that overusing <code>+</code>, <code>*</code> and <code>?</code>, especially in the same
production rule, can easily lead to new ambiguities in the grammar, especially
with <code>*</code> and <code>?</code>. The new productions generated for these operators
could lead to additional Shift-Reduce and even
Reduce-Reduce conflicts. For example, a production with right-hand side
<strong><code>Expr<Comma*> Comma?</code></strong> will lead to a shift-reduce conflict. However,
<strong><code>Expr<Comma+> Comma?</code></strong> will not.</p>
<p>Generally speaking, context free grammars do not have the same
properties as regular expressions. Regex operators including
<code>*</code>, <code>+</code> and <code>?</code> can be used in any combination such as <code>(a+a?)*</code> and we
can always create an optimized, deterministic finite state machine to
recognize it. But grammars cannot be composed without losing their
properties. A rule like <code>A --> B* B*</code> is hopelessly ambiguous as
there is no way to determine where the first sequence should stop and
the second one begins. In such a situation, rustlr will still create a
parser by using defaults such as shift-over-reduce, but not before printing
out a warning.</p>
<p>The motivation for adding regex-like operators to a parser generator
are both usability and improved ability in creating abstract syntax
automatically. But much work needs to be done before we can parse
arbitrary EBNF syntax. We are currently exploring extensions of LR
parsing including <em>delayed reductions</em>, which can potentially allow
non-ambiguous grammars to be more easily composed without running into
new conflicts: see the <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/appendix.html">Appendix</a> of this tutorial for experimental
features.</p>
<h3 id="invoking-the-parser">Invoking the Parser</h3>
<p>Since the grammar also contains lexer generation directives, all we need to do is to write the procedures that interpret the AST (see <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/autocalc/src/main.rs">main</a>). The procedure to invoke the parser is the same as described in <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/chapter3.html">Chapter 3</a>, using the <strong><code>parse_with</code></strong> or <strong><code>parse_train_with</code></strong> functions:</p>
<pre><code class="language-rust"> <span class="hljs-keyword">let</span> <span class="hljs-keyword">mut</span> scanner = calcautoparser::calcautolexer::from_str(<span class="hljs-string">"2*3+1;"</span>);
<span class="hljs-keyword">let</span> <span class="hljs-keyword">mut</span> parser = calcautoparser::make_parser();
<span class="hljs-keyword">let</span> result = calcautoparser::parse_with(&<span class="hljs-keyword">mut</span> parser, &<span class="hljs-keyword">mut</span> scanner);
<span class="hljs-keyword">let</span> tree = result.unwrap_or_else(|x|{<span class="hljs-built_in">println!</span>(<span class="hljs-string">"Parsing errors encountered; results are partial.."</span>); x});
<span class="hljs-built_in">println!</span>(<span class="hljs-string">"\nAST: {:?}\n"</span>,&tree);
</code></pre>
<p>The <code>parse_with</code> and <code>parse_train_with</code> functions were also backported for
grammars with a single <em>absyntype.</em></p>
<p>Please note that using <a href="https://docs.rs/rustlr/latest/rustlr/generic_absyn/struct.LBox.html">LBox</a> is already included in all parsers generated with the <code>-genabsyn</code> or <code>-auto</code> option, so do not use <code>!use ...</code> to include
it again.</p>
<hr>
<h3 id="json-parser">JSON Parser</h3>
<p>To give another, complete example of the features described in this chapter,
we build a parser for JSON. The grammar is as follows</p>
<pre><code># Rustlr grammar <span class="hljs-keyword">use</span> with -auto
lifetime <span class="hljs-symbol">'lt</span>
lexterminal LBRACE {
lexterminal RBRACE }
lexterminal LBRACK [
lexterminal RBRACK ]
lexterminal LPAREN (
lexterminal RPAREN )
lexterminal COLON :
lexterminal COMMA ,
lexterminal NULL null
lexterminal MINUS -
valueterminal TRUE~ <span class="hljs-built_in">bool</span>~ Alphanum(<span class="hljs-string">"true"</span>)~ <span class="hljs-literal">true</span>
valueterminal FALSE~ <span class="hljs-built_in">bool</span>~ Alphanum(<span class="hljs-string">"false"</span>)~ <span class="hljs-literal">false</span>
valueterminal STRING~ &<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>~ Strlit(n)~ &n[<span class="hljs-number">1</span>..n.len()-<span class="hljs-number">1</span>]
valueterminal NUM~ <span class="hljs-built_in">i64</span>~ Num(n)~ n
valueterminal FLOAT~ <span class="hljs-built_in">f64</span>~ Float(n)~ n
valueterminal BIGNUM~ &<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>~ BigNumber(n)~ n
nonterminal Integer <span class="hljs-built_in">i64</span>
nonterminal Floatpt <span class="hljs-built_in">f64</span>
nonterminal Boolean <span class="hljs-built_in">bool</span>
nonterminals Number Value KeyValPair
nonterminal List <span class="hljs-built_in">Vec</span><LBox<Value<<span class="hljs-symbol">'lt</span>>>>
nonterminal Object <span class="hljs-built_in">Vec</span><LBox<KeyValPair<<span class="hljs-symbol">'lt</span>>>>
topsym Value
resync COMMA RBRACK RBRACE
Integer --> MINUS?:m NUM:n {<span class="hljs-keyword">if</span> m.is_some() {n*-<span class="hljs-number">1</span>} <span class="hljs-keyword">else</span> {n}}
Floatpt --> MINUS?:m FLOAT:n {<span class="hljs-keyword">if</span> m.is_some() {-<span class="hljs-number">1.0</span>*n} <span class="hljs-keyword">else</span> {n}}
Number:Bignum --> MINUS?:m BIGNUM
Number:Int --> Integer
Number:Float --> Floatpt
Boolean --> TRUE | FALSE
Value:Number --> Number
Value:Bool --> Boolean
Value:Str --> STRING
Value:Object --> Object
Value:List --> List
Value --> NULL
Value --> LPAREN Value RPAREN
KeyValPair --> STRING COLON Value
List --> LBRACK Value<COMMA*> RBRACK
Object --> LBRACE KeyValPair<COMMA*> RBRACE
</code></pre>
<p>This grammar uses the latest variations on Rustlr syntax that were introduced
in more recent versions.
Note that the <strong><code>valueterminal</code></strong> lines, which combine <code>typedterminal</code> with
<code>lexvalue</code> declarations, requires that their components be separated by
a <strong><code>~</code></strong>. The line for terminal STRING strips the string literal returned
by the tokenizer of this enclosing double quotes.</p>
<p>The grammar is a hybrid with some manually defined types and actions
along with mostly automatically generated ones.
The AST types that are created by this grammar are</p>
<pre><code><span class="hljs-meta">#[derive(Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">enum</span> <span class="hljs-title">Number</span></span><<span class="hljs-symbol">'lt</span>> {
Int(<span class="hljs-built_in">i64</span>),
Bignum(<span class="hljs-built_in">Option</span><()>,&<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>),
Float(<span class="hljs-built_in">f64</span>),
Number_Nothing,
}
<span class="hljs-keyword">impl</span><<span class="hljs-symbol">'lt</span>> <span class="hljs-built_in">Default</span> <span class="hljs-keyword">for</span> Number<<span class="hljs-symbol">'lt</span>> { <span class="hljs-function"><span class="hljs-keyword">fn</span> <span class="hljs-title">default</span></span>()-><span class="hljs-keyword">Self</span> { Number::Number_Nothing } }
<span class="hljs-meta">#[derive(Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">enum</span> <span class="hljs-title">Value</span></span><<span class="hljs-symbol">'lt</span>> {
Str(&<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>),
List(<span class="hljs-built_in">Vec</span><LBox<Value<<span class="hljs-symbol">'lt</span>>>>),
NULL,
Object(<span class="hljs-built_in">Vec</span><LBox<KeyValPair<<span class="hljs-symbol">'lt</span>>>>),
Bool(<span class="hljs-built_in">bool</span>),
Number(Number<<span class="hljs-symbol">'lt</span>>),
Value_Nothing,
}
<span class="hljs-keyword">impl</span><<span class="hljs-symbol">'lt</span>> <span class="hljs-built_in">Default</span> <span class="hljs-keyword">for</span> Value<<span class="hljs-symbol">'lt</span>> { <span class="hljs-function"><span class="hljs-keyword">fn</span> <span class="hljs-title">default</span></span>()-><span class="hljs-keyword">Self</span> { Value::Value_Nothing } }
<span class="hljs-meta">#[derive(Default,Debug)]</span>
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">KeyValPair</span></span><<span class="hljs-symbol">'lt</span>>(<span class="hljs-keyword">pub</span> &<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>,<span class="hljs-keyword">pub</span> LBox<Value<<span class="hljs-symbol">'lt</span>>>,);
</code></pre>
<p>Notice that we explicitly defined the types of <code>List</code> and <code>Object</code> to be
the type that we know will be generated by <code><COMMA*></code>. This avoided the
creation of redundant new types, which would have been:</p>
<pre><code><span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">Object</span></span><<span class="hljs-symbol">'lt</span>>(<span class="hljs-keyword">pub</span> <span class="hljs-built_in">Vec</span><LBox<KeyValPair<<span class="hljs-symbol">'lt</span>>>>,);
<span class="hljs-keyword">pub</span> <span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">List</span></span><<span class="hljs-symbol">'lt</span>>(<span class="hljs-keyword">pub</span> <span class="hljs-built_in">Vec</span><LBox<Value<<span class="hljs-symbol">'lt</span>>>>,);
</code></pre>
<p>These new types would mean, for example, that <code>[1,2,3]</code> would be represented
as <code>List(List([Number(Int(1)),Number(Int(2)),Number(Int(3))]))</code> instead of
just <code>List([Number(Int(1)),Number(Int(2)),Number(Int(3))])</code>. With the explicit
type declarations Rustlr was able to recognize that the only non-unit
typed symbol on the right-hand side of the rule has the same
type as the left-side-side symbol, and thus generated the semantic
action correctly without creating another type.</p>
<p>The following is the Debug-output of a sample AST produced by the parser,
from which anyone familiar with JSON can surely discern the original source:</p>
<pre><code><span class="hljs-keyword">Object</span>([KeyValPair(<span class="hljs-string">"firstName"</span>, Str(<span class="hljs-string">"John"</span>)), KeyValPair(<span class="hljs-string">"lastName"</span>, Str(<span class="hljs-string">"Smith"</span>)), KeyValPair(<span class="hljs-string">"isAlive"</span>, <span class="hljs-keyword">Bool</span>(<span class="hljs-literal">true</span>)), KeyValPair(<span class="hljs-string">"age"</span>, Number(<span class="hljs-keyword">Int</span>(<span class="hljs-number">30</span>))), KeyValPair(<span class="hljs-string">"address"</span>, <span class="hljs-keyword">Object</span>([KeyValPair(<span class="hljs-string">"streetAddress"</span>, Str(<span class="hljs-string">"121 2nd Street"</span>)), KeyValPair(<span class="hljs-string">"city"</span>, Str(<span class="hljs-string">"New York"</span>)), KeyValPair(<span class="hljs-string">"state"</span>, Str(<span class="hljs-string">"NY"</span>)), KeyValPair(<span class="hljs-string">"postalCode"</span>, Str(<span class="hljs-string">"10021-3100"</span>))])), KeyValPair(<span class="hljs-string">"phoneNumbers"</span>, <span class="hljs-keyword">List</span>([<span class="hljs-keyword">Object</span>([KeyValPair(<span class="hljs-string">"type"</span>, Str(<span class="hljs-string">"home"</span>)), KeyValPair(<span class="hljs-string">"number"</span>, Str(<span class="hljs-string">"212 555-1234"</span>))]), <span class="hljs-keyword">Object</span>([KeyValPair(<span class="hljs-string">"type"</span>, Str(<span class="hljs-string">"office"</span>)), KeyValPair(<span class="hljs-string">"number"</span>, Str(<span class="hljs-string">"646 555-4567"</span>))])])), KeyValPair(<span class="hljs-string">"children"</span>, <span class="hljs-keyword">List</span>([Str(<span class="hljs-string">"Catherine"</span>), Str(<span class="hljs-string">"Thomas"</span>), Str(<span class="hljs-string">"Trevor"</span>)])), KeyValPair(<span class="hljs-string">"spouse"</span>, <span class="hljs-literal">NULL</span>)])
</code></pre>
<p>Finally, here is an alternative way to parse JSON objects into
Rust HashMaps. We can override not only the type to be generated but the
semantic action as well. Modify the declarations and rules for Object as
follows:</p>
<pre><code>$<span class="hljs-keyword">use</span> std::collections::HashMap;
nonterminal Object HashMap<&<span class="hljs-symbol">'lt</span> <span class="hljs-built_in">str</span>,LBox<Value<<span class="hljs-symbol">'lt</span>>>>
Object ==> LBRACE KeyValPair<COMMA*>:entries RBRACE {
<span class="hljs-keyword">let</span> <span class="hljs-keyword">mut</span> kvmap = HashMap::new();
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">mut</span> lbx) <span class="hljs-keyword">in</span> entries {
<span class="hljs-keyword">if</span> <span class="hljs-keyword">let</span> KeyValPair(k,v) = lbx.take() { kvmap.insert(k,v); }
}
kvmap
} <==
</code></pre>
<p>The <code>$</code> directive is similar to <code>!</code>, except that it adds the verbatim line
only to the generated AST file as opposed to parser file. Each key-value
pair inside the vector created by <code><COMMA*></code> is wrapped inside an LBox.
We can take the value from the box with <a href="https://docs.rs/rustlr/latest/rustlr/generic_absyn/struct.LBox.html#method.take">LBox::take</a> (which leaves
a default value inside the box).</p>
<p>The debug output of the AST from the same JSON source would now be:</p>
<pre><code><span class="hljs-selector-tag">Object</span>({"age": <span class="hljs-built_in">Number</span>(<span class="hljs-built_in">Int</span>(<span class="hljs-number">30</span>)), <span class="hljs-string">"isAlive"</span>: <span class="hljs-built_in">Boolean</span>(true), <span class="hljs-string">"children"</span>: <span class="hljs-built_in">List</span>([<span class="hljs-built_in">Str</span>(<span class="hljs-string">"Catherine"</span>), <span class="hljs-built_in">Str</span>(<span class="hljs-string">"Thomas"</span>), <span class="hljs-built_in">Str</span>(<span class="hljs-string">"Trevor"</span>)]), <span class="hljs-string">"firstName"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"John"</span>), <span class="hljs-string">"address"</span>: <span class="hljs-built_in">Object</span>({<span class="hljs-string">"state"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"NY"</span>), <span class="hljs-string">"streetAddress"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"121 2nd Street"</span>), <span class="hljs-string">"postalCode"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"10021-3100"</span>), <span class="hljs-string">"city"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"New York"</span>)}), "spouse": NULL, <span class="hljs-string">"lastName"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"Smith"</span>), <span class="hljs-string">"phoneNumbers"</span>: <span class="hljs-built_in">List</span>([<span class="hljs-built_in">Object</span>({<span class="hljs-string">"type"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"home"</span>), <span class="hljs-string">"number"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"212 555-1234"</span>)}), <span class="hljs-selector-tag">Object</span>({"number": <span class="hljs-built_in">Str</span>(<span class="hljs-string">"646 555-4567"</span>), <span class="hljs-string">"type"</span>: <span class="hljs-built_in">Str</span>(<span class="hljs-string">"office"</span>)})])})
</code></pre>
<p>Although we may at times want to insert such overrides, most of the
automatically generated portions remain usable.</p>
<p>Here are links to the <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/jsontypes/json.grammar">grammar</a>, <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/jsontypes/src/jsonparser.rs">parser</a>, <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/jsontypes/src/json_ast.rs">ast types</a> and <a href="https://cs.hofstra.edu/~cscccl/rustlr_project/jsontypes/src/main.rs">main</a> of the project, which may differ slightly
from the above.</p>
<hr>
<p><em>The former section named "Generating a Parser for C" is being updated and
moved to a new chapter.</em></p>
<hr>
</div></body></html>