Assume that I want to be able to parse strings that follow those rules:

  | ? any string of (let's say ascii) characters ?

  '{' FORMAT '--'


  | ? string consisting of:
      - at most one occurrence of characters from set [*/_]
      - at most two occurrences of characters [rgb;] with information telling me what first and second letter was, in order

that language would accept all strings. It would eagerly match FORMAT_START, then FORMAT_END and if it fails - a string of characters. Examples include:

  • text: STRING text
  • {rr-- text --}: FORMAT_START {rr-- (FORMAT=rr), STRING text, FORMAT_END --}
  • {bbb--text: STRING {bbb--text, because there are too many b
  • {r/b*--text{--inner--}: FORMAT_START {r*b/-- (FORMAT=r*b/), STRING text, FORMAT_START {-- (FORMAT empty), STRING inner, FORMAT_END --}. Note, that order of */ doesn't matter, while order of rb matters.
  • {--}: FORMAT_START {-- (FORMAT empty), STRING }
  • {x----}: STRING {x--, FORMAT_END --}
  • --}: FORMAT_END --}

I'm asking out of curiosity that was sparked when I wrote myself a (similar to above) stream processor, that translates FORMAT_START and FORMAT_END of markdown-like formats to ANSII sequences, which gives me a nice way of coloring stuff in my terminal.

(TL;DR why such weird language -- it't markdown + mnemonics -- *:adds bold, /:italic, _:underline, and [rgb;] set first foreground color and next background color, with ; using default)

  • Can this language be formalized or written in some common parser grammar language, to be able to parse it? Can I parse it and
  • What is the type of this language? What I observed: the amount of formats is finite, so any valid format can be matched. Is it context sensitive?
  • What machine can parse/process this language - I was thinking a simple pushdown automaton could suffice, but matching numbers of letters smells.
  • What if I wanted to make the format brackets balanced (VALID_FORMAT = FORMAT_START STRING FORMAT_END)? How much harder does it get?
  • Could I parse the text with this language in stream (using corresponding machine for this type of language)?
  • What if I add a special format character #, that strips leading and trailing whitespaces from it's immediate inner text (assuming it's a valid formatting)
  • What about nondeterminism (anything could be matched to STRING, but we want to eagerly "eat" FORMAT_*)

(When thinking about formatting - first met letter is setting the foreground color, second one is setting background, so {gb-- would make green foreground blue background). I noticed that there is only a finite amount of valid formats, so the rules to match all possible formats could be enumerated, but this probably grows to some sick sizes for all the combinations (BOLD_ITALIC_FORMAT = */ | /*). They are still enumerable though so... could it be a context free grammar with pushdown automaton?

I'm a newbie in theory of formal languages, so I'm sorry if this doesn't make much sense.

Why do I think about that? Because I wonder how I can reuse existing tools to


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.