Wolfram Language Paclet Repository
Community-contributed installable additions to the Wolfram Language
A Markdown Inline Parser in Parser Combinators
A Markdown Inline Parser in Parser Combinators
What this note covers
What this note covers
is a parser for inline markdown - the inside-a-paragraph constructs of CommonMark: emphasis (, , , ), code spans (, , ), inline math (, ), links (), images (), HTML and Pandoc sub/sup (, , ), backslash escapes (, , ), and underscore emphasis with CommonMark word-boundary rules (, , but not ).
*italic*
**bold**
***both***
~~strike~~
`code`
literal
<code>...</code>
$...$
$$...$$
[label](url)
<sub>x</sub>
H~2~O
e^2^
\*
\$
\\
_em_
__strong__
snake_case
It returns a flat list of inline atoms; each atom is an with a discriminator plus payload keys - the same convention and M2N's block-level parser use, so downstream code can pattern-match on uniformly across both layers.
"Type"
"Type"
The whole grammar is ~75 lines of / / over the primitives. No , no regex hand-tuning, no per-rule iteration. The PEG order in one resolves the precedence ambiguities ( wins over opened twice; wins over --).
Wolfram`Parser`
**bold**
*italic*
***both***
*
**both**
*
This note has three parts:
1
.The AST - what returns.
MarkdownInlineParse
2
.The grammar - line-by-line walkthrough of the combinator chain.
3
.Recursion and post-processing - how nested emphasis () gets re-parsed and how the CommonMark word-boundary rules for underscore emphasis fall out as a small post-pass.
**bold$x$**
Part 1 - The AST
Part 1 - The AST
"Type"
"Type" | Other keys | Markdown form | |
"Text" | "Text"->str | plain text run | |
"Code" | "Code"->str | `code` | |
"LiteralCode" | "Code"->str | code | |
"HtmlCode" | "Code"->str | <code>...</code> | |
"MathInline" | "Math"->str | $x$ | |
"MathDisplay" | "Math"->str | $$x$$ | |
"Link" | "Label"->[atoms] "Url"->str | [label](url) | |
"Image" | "Alt"->str "Url"->str |  | |
"Sub" | "Children"->[atoms] | <sub>x</sub> ~x~ | |
"Sup" | "Children"->[atoms] | <sup>x</sup> ^x^ | |
"Bold" | "Children"->[atoms] | **x** __x__ | |
"Italic" | "Children"->[atoms] | *x* _x_ | |
"BoldItalic" | "Children"->[atoms] | ***x*** | |
"Strike" | "Children"->[atoms] | ~~x~~ |
The / for spans are themselves s of inline atoms (the body was re-parsed), so lands as . Adjacent atoms are coalesced so consumers see one run per contiguous prose chunk, never one atom per character.
"Children"
"Label"
**bold$x$**
<|"Type"->"Bold","Children"->{<|"Type"->"Text","Text"->"bold "|>,<|"Type"->"MathInline","Math"->"x"|>}|>
"Text"
Using s with a key instead of a sum-type-headed expression matches the convention M2N's block-level parser uses ( etc.), so downstream code reading the parse tree can pattern-match on uniformly across the inline and block layers without learning two AST shapes.
"Type"
<|"Type"->"Heading","Level"->n,"Text"->str|>
atom["Type"]
Plain prose comes out as a single atom:
"Text"
In[1]:=
 | MarkdownInlineParse |
Out[1]=
{TypeText,Textplain text}
Mixed prose, emphasis, math, and code:
In[2]:=
| MarkdownInlineParse |
Out[2]=
{TypeBold,Children{TypeText,Textbold ,TypeMathInline,Mathx},TypeText,Text and ,TypeCode,Codecode}
A link with a code-styled label demonstrates recursive label parsing - the label itself is a list of inline atoms:
In[3]:=
| MarkdownInlineParse |
Out[3]=
{TypeLink,Urlpaclet:ref/Range,Label{TypeCode,CodeRange}}
Part 2 - The grammar
Part 2 - The grammar
The whole parser lives in . The grammar is one big and lots of small arms.
The bounded-content helper
The bounded-content helper
Every paired-delimiter span needs to consume "everything until the closing delimiter". The trick is : at each position, refuse to consume a character if the next characters would form the closing delimiter.
In[4]:=
content[term_]:=
[term]~~anyChar,#2&,StringJoin[{##}]&
 | ParseAction |
 | ParseSome |
 | ParseAction |
 | ParseNotFollowedBy |
Reading the body: is ; is a zero-width assertion that the next characters do not start . Their sequence consumes one char only when doesn't start there. iterates the assertion-plus-char until fires, at which point stops and the outer joins the accumulated chars into a string.
anyChar
term
term
content[ParseLiteral["**"]]
"foo $x$"
**
"foo $x$**"
**foo$x$**
Paired spans
Paired spans
Every paired span is a literal-open / / literal-close trio. The grammar reads a few private helper constructors (, , , , …) that each build the corresponding -tagged - keeping the AST construction in one place so the grammar arms stay readable.
content[close]
text
codeAtom
mathIn
bold
"Type"
Inline code:
In[5]:=
code=
["`"]~~content
["`"]~~
["`"],codeAtom[#2]&
| ParseAction |
| ParseLiteral |
| ParseLiteral |
| ParseLiteral |
$IterationLimit::itlim:Iterationlimitof4096exceeded.
$IterationLimit::itlim:Iterationlimitof4096exceeded.
Out[5]=
ParseAction[TerminatedEvaluation[IterationLimit],codeAtom[#2]&]
Inline math:
In[6]:=
inlineMath=
["$"]~~content
["$"]~~
["$"],mathIn[#2]&
| ParseAction |
| ParseLiteral |
| ParseLiteral |
| ParseLiteral |
$IterationLimit::itlim:Iterationlimitof4096exceeded.
$IterationLimit::itlim:Iterationlimitof4096exceeded.
Out[6]=
ParseAction[TerminatedEvaluation[IterationLimit],mathIn[#2]&]
Bold:
In[7]:=
boldP=
["**"]~~content
["**"]~~
["**"],bold[#2]&
| ParseAction |
| ParseLiteral |
| ParseLiteral |
| ParseLiteral |
$IterationLimit::itlim:Iterationlimitof4096exceeded.
$IterationLimit::itlim:Iterationlimitof4096exceeded.
Out[7]=
ParseAction[TerminatedEvaluation[IterationLimit],bold[#2]&]
The arm takes the second result (the content; the first is the open literal, the third is the close) and wraps it in the appropriate atom constructor.
#2&
Escapes and the plain-character catch-all
Escapes and the plain-character catch-all
A backslash followed by ASCII punctuation collapses to that punctuation, so becomes a literal instead of opening an italic span:
\*
*
In[8]:=
escape=
["\\"]~~charSat[asciiPunct],text[#2]&
| ParseAction |
| ParseLiteral |
$IterationLimit::itlim:Iterationlimitof4096exceeded.
Out[8]=
ParseAction[TerminatedEvaluation[IterationLimit],text[#2]&]
After every other alternative has had a chance, the catch-all consumes one character and wraps it in a atom:
plainChar
"Text"
In[9]:=
plainChar=
[anyChar,text[#1]&]
| ParseAction |
Out[9]=
ParseAction[anyChar,text[#1]&]
over the outer iterates this until the input is exhausted; the post-process step coalesces consecutive atoms so prose comes out as one run, not one atom per character.
mergeText
"Text"
Links and images
Links and images
The label can contain markdown itself, but capturing it character-by-character at the top level would be wrong (we'd lose the structure). Instead capture the raw label string during parse and re-parse it after:
In[10]:=
linkP=
"["]~~linkLabel~~
["]("]~~linkUrl~~
[")",link[#2,#4]&
| ParseAction |
| ParseLiteral |
| ParseLiteral |
| ParseLiteral |
$IterationLimit::itlim:Iterationlimitof4096exceeded.
Out[10]=
ParseAction[TerminatedEvaluation[IterationLimit],link[#2,#4]&]
linkLabel
content[]
]
linkUrl
)
link[#2,#4]
imageP
!
![
!
PEG ordering: longer prefixes first
PEG ordering: longer prefixes first
The full alternation:
In[11]:=
inlineAtom=
[escape,(*\x*)codeHtml,imageP,linkP,(*HTML/[/![*)dblCode,code,(*```*)displayMath,inlineMath,(*$$$*)strikeP,(*~~*)htmlSub,htmlSup,(*<sub><sup>*)boldItalicP,boldP,italicAst,(********)pandocSub,pandocSup,(*~^*)plainChar(*fallback*)]
| ParseChoice |
Within each opening-character family the longest opener comes first:
Word-bounded asterisk italic
Word-bounded asterisk italic
Part 3 - Recursion and post-processing
Part 3 - Recursion and post-processing
Recursive children
Recursive children
Adjacent-text merging
Adjacent-text merging
Underscore emphasis (CommonMark word boundaries)
Underscore emphasis (CommonMark word boundaries)
Part 4 - The full document parser
Part 4 - The full document parser
Why this matters
Why this matters