5

Could you explain how parsers search for token patterns like in markdown?

I probably could come up with something matching only the braces pattern []() as soon as nested patterns are involved it blows my mind.

For example in something like this

foo [**baz**](baz) qux

the tokenizer probably explodes the string into these tokens

"foo ", "[", "**", "baz", "**", "]", "(", "baz", ")", " qux"

and passes it to the parser to recognize the patterns, that it's a link and that the braces match and then even understand the bold style inside the label.

I guess it's some kind of a state machine but does it really think that as soon as a [ ocurrs it might mean something so store the token and if the subsequent tokens don't match then discard this state and turn the separator tokens into a normal literal. This would mean that it had to go back change the meaning of everything else if there was no ( after the closing ]. Do I think too complex?

It looks like it was easy to implement when I look at it, but if I should invent an algorithm for it, I couldn't.

Improve this question
6
  • 2
    Markdown is actually a very complicated language, and can't be parsed with a simplistic lexer/LR-parser approach. E.g. a reference link [foo] is only parsed as a link if that reference is defined. Otherwise, the square brackets are just literals. And nested links are impossible. And ***foo** bar* is a strong emphasis within an emphasis, whereas ***foo* bar** is an emphasis in a strong emphasis. That is far more complicated than a normal programming language. There's an attempt at a spec that tries to approach these problems. Commented Nov 6, 2016 at 18:28
  • 1
    I think your question mixes two things. It seems like you want to know how to parse arbitrary nested patterns such as ([]([]())), but then you talk about Markdown. If you want to know how Markdown parser works, look at the source code and/or the spec of Markdown. If you want to know more about nested patterns, independently of Markdown, then edit your question to remove the reference to Markdown. Commented Nov 6, 2016 at 20:56
  • @ArseniMourzenko well, matching braces pairs is relatively easy but finding patterns like []() doesn't seem to be so obvious. I mentioned markdown because it uses a very interesing syntax (language?) and I believe most visitors are already familiar with this one. Commented Nov 7, 2016 at 12:36
  • @t3chb0t : >"I probably could come up with something matching only the braces pattern []() as soon as nested patterns are involved it blows my mind." >"It looks like it was easy to implement when I look at it, but if I should invent an algorithm for it, I couldn't." --- Do you feel like you could, or at least have an idea of how to, implement an algorithm to parse that line now? Commented Nov 14, 2016 at 9:31
  • @Pod yes, I thought I could detect all patterns at once (single pass) but now I understand that I need to run them multiple times to detect each pattern separately that would be much easier - at least the more complex ones like [][] or [](). On each pass I need to upgrade a group of tokens to the next level that now stand for a concrete object not just random tokens. This way I think it should possible to build a tree step by step. Commented Nov 14, 2016 at 9:38

1 Answer 1

Reset to default
3

It looks like it was easy to implement when I look at it, but if I should invent an algorithm for it, I couldn't.

Thankfully some people already have :)

  1. https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form
  2. https://en.wikipedia.org/wiki/Context-free_grammar
  3. https://en.wikipedia.org/wiki/Recursive_descent_parser

It's a complicated topic, and there's a lot out there, but a quick run-down is:

You're correct that the tokeniser explodes the string into the tokens. Then the parser will have a grammar defined inside of it, usually using something like BNF, to fit the pieces together.

"foo ", "[", "**", "baz", "**", "]", "(", "baz", ")", " qux"

could be parsed by a grammar such as :

line = <rounds> | <squares> | <markdown_stuff> | <line>
rounds = '(' <line> ')'
squares = '[' <line> ']'
markdown_stuff = <italics> | <bold> | <word_text>
italics = '*' <word_text> '*' 
bold = '**' <word_text> '**'
word_text = <word_char> | <word_char> <word_text>
word_char= 'a', 'b', 'c', 'd'... etc 'A', 'B', 'C', etc '0', '1', '2', '3', etc '_'

Notice that it's recursive. Some rules like word_text refer directly to themselves, others, like <line> refer to something that refers back to <line>. (The python language doc is full of such examples)

After making a grammar for your language, you would write e.g. a recursive descent parser to 'read' it. Or more commonly, use a tool like YACC or ANTLR to make the parser for you based directly on the grammar.

As for a state machine: I think YACC implements its parsers in terms of giant state tables -- thought I might be wrong on that. It's been a while since I used it.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.