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
: STRINGtext
{rr-- text --}
: FORMAT_START{rr--
(FORMAT=rr
), STRINGtext
, FORMAT_END--}
{bbb--text
: STRING{bbb--text
, because there are too manyb
{r/b*--text{--inner--}
: FORMAT_START{r*b/--
(FORMAT=r*b/
), STRINGtext
, FORMAT_START{--
(FORMAT empty), STRINGinner
, FORMAT_END--}
. Note, that order of*/
doesn't matter, while order ofrb
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