# Which type of language and machine can parse the following string

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

STRING =
epsilon
| FORMAT_START STRING
| FORMAT_END STRING
| ? any string of (let's say ascii) characters ?

FORMAT_START =
'{' FORMAT '--'

FORMAT_END =
'--}'

FORMAT =
epsilon
| ? 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