0
$\begingroup$

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

$\endgroup$

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.