Comments on C for Coding: Markdown Headings, Grief and Unknown Elements to t...

Let me also include a pointer to BableMark, a mark...

2010-01-23T19:17:29.255+08:00

Let me also include a pointer to BableMark, a markdown implementation testbed: http://babelmark.bobtfish.net/?markdown=x%3Cmax(a,b)%0D%0A&normalize=on

You may find the grammar linked to for the "PEG Markdown" implementation useful.

Right; Markdown seems full of fallback cases. In ...

2010-01-23T18:46:38.073+08:00

Right; Markdown seems full of fallback cases.

In fact, I wonder if that isn't the right way to specify it, as a series of less-specific constructs. There was a parsing approach I read a paper on a while ago that I unfortunately can't remember the name of - it was slightly heavy on memory usage, but maybe that's OK. Rather than the traditional lexer/parser split, this approach was based on one uniform approach to the whole document, which was a series of functions:

String -> [(ParsedStructure, restOfString)]

where I'm using Haskell notation there to mean a list of pairs. The first element of the list would be the most preferred parse, then the second-most-preferred parse, etc. So as an example. The paper's example implementation language was Haskell, so all these lists were being constructed lazily; in Java you'd probably have to construct something that returned Iterators>. The paper showed how to chain together different definitions so that if you had a high-level construct that was something like:

INLINESTUFF = '*' TEXTRUN '*' | TEXTRUN

you could then chain together a "recognize '*'" function and a "recognize TEXTRUN" function into a "recognize INLINESTUFF" function. I wish I could remember the name of this approach so that I could find it because the details of how you combined stuff so that the whole result was efficient escape me at the moment. Throwing seemingly related terms at Google isn't helping.

@dtm: I haven't seen the Markdown Extra one but ye...

2010-01-23T09:25:52.992+08:00

@dtm: I haven't seen the Markdown Extra one but yes I've seen the other. Markdown Extra is incomplete (and probably use some examples).

Reading the token definitions it's pretty much dead on what I'd derived anyway.

Unfortunately Markdown is a really poor candidate for EBNF and the like because there are a lot of "else" clauses like:

<http://example.com>

is clearly a URL but to a lexer it could be:

- a URL
- a tag (although the rule for this would fail); or
- a "textrun" (in MDE-speke)

But the textrun is a fallback case. And there are lots of these fallback cases like:

> blockquote

which could reasonably be scanned as QUOTE TEXTRUN but the fallback case of TEXTRUN which is needed for

sometext

also covers the block quote, which leads to ambiguity unless you specifically enumerate all the possible start characters which is possible but I've had issues along that line too.

What are you using as the canonical source of what...

2010-01-23T09:00:21.527+08:00

What are you using as the canonical source of what Markdown should be? The original spec of John Gruber (found at http://daringfireball.net/projects/markdown/syntax) is known to be a bit ambiguous and troublesome in some details. Are you aware of the "Markdown Extra" spec at http://michelf.com/specs/markdown-extra/ ?

Your four articles are well worth reading - thank ...

2010-01-22T07:43:26.768+08:00

Your four articles are well worth reading - thank you!

You have hinted along the way that there are certain portions of Markdown that are either troublesome, conflicting or in some way cause grief. I would love to see a wrap up article with a summary of what you would like to see as a "Markdown Mark II", complete with a sensible lexer/parser and spec.

@Daniel: You're probably not going to get EBNF out...

2010-01-22T06:54:25.881+08:00

@Daniel: You're probably not going to get EBNF out of this. Context-sensitivity is the issue. Perhaps that can be unrolled to a CFG but I'm not entirely convinced of that. The code so far makes decisions and looks for tokens based on context.

It'll be something to discuss once I get the first cut out there.

I think you are on the right track treating each l...

2010-01-22T02:22:37.415+08:00

I think you are on the right track treating each line as a token from the lexical analysis. It seems to me that markdown "grammar" is much more concerned with vertical elements than horizontal elements. The horizontal elements -- emphasis, bold, code, hyperlinks -- are rather easily handled.

On the vertical, however, you have normal blocks, quote blocks, code blocks, item blocks, numbered blocks, block separators and whatever combinations might be valid.

My suggestion, in fact, is for you to do two grammars: one at the document level, and one at the block level. You get two lexers. The first will return block tokens. Depending on the type of block, a different second lexer will be applied. Likewise, two grammars.

Once you have such thing working, you can probably reduce it to a single complex lexer/grammar much more easily than do it right from the start.

As a side note, I'm very interested in this project, because I'd like to try doing it with Scala and either the backtracking parser or the ratpack parser. And ADTs instead of visitor patterns. :-) So I have a vested interested in having an EBNF for it. :-)

Java is first. C# will be second. Javascript is a...

2010-01-21T20:17:09.620+08:00

Java is first. C# will be second.

Javascript is an interesting one. Because the regex library might be faster than the hand-coded solution. We'll see when it gets to that stage.

Love this set of articles. Are you just working in...

2010-01-21T19:51:39.295+08:00

Love this set of articles. Are you just working in Java, or will the final code be easily portable to Javascript, PHP, etc?

Part of the problem has been that obviously there'...

2010-01-18T06:26:54.775+08:00

Part of the problem has been that obviously there's no formal grammar to follow so I've had to play it by ear. Add to that that you have choices about how to handle certain cases (eg do you treat something as a lexical or parsing issue?) and I've had to stop and rethink my approach several times.

Last night I came to the realization that I am going to have to have an extra line-level step that I was otherwise hoping to avoid. I started to realize my previous single-pass approach was going to end up with some hideous corner cases that were simply too complex to reasonably deal with whereas an extra pass would much more reasonable deal with them and let me better handle the inline parsing to boot.

To clarify, I think Markdown has 2 syntaxes: 1) A ...

2010-01-18T04:04:20.186+08:00

To clarify, I think Markdown has 2 syntaxes: 1) A block-level syntax that should tokenize whole lines as particular kinds of lines; and, 2) an in-line syntax that can be parsed separately.

I think you could reasonably do something like:

line-grammar:
regular-line
| block-line
| empty-line
| heading-line-block
| heading-line-inline

regular-line: << any line starting with regular characters >>
block-line: << line starting with spaces >>
empty-line: << >>
heading-line-block: << full line of '###' heading characters>>
heading-inline-block: << '##' with text >>

With that, the inline-checking at the start of lines would be fairly minimal and could be easily put into lexing rules (or hand written).

Once you have all of the lines, a block-level parser could collate and segment blocks, producing a line-oriented stream of tokens that could then be parsed by the in-line lexer/parser.

It's certainly more work, but I think it better reflects the syntax of the language. Indeed, I have a feeling that Markdown is unparseable in LL(k) where k is any sane number.