0
$\begingroup$

I need to create a simple text parser that replaces {tokens} with text from a table. The more complicated bit is the {?text?} tag where text must be included only if the preceding AND the following tokens exist and are not empty. You could do {?text} where it looks for a non-empty neighbouring tag only on that side.

I am not a CS student and I don't have any formal education, but I am interested in this stuff.

I know I can bodge this via common sense and general logic but I would like to approach this in a more systematic manner, as this seems simple enough and like an excellent learning opportunity.

I am aware of the concept of formal languages and grammars, but I'm not sure where to start apart from randomly jumping over wikipedia pages that seem relevant(like Context-free grammars and Parse trees), until something starts making sense.

$\endgroup$
  • 1
    $\begingroup$ You seem to be designing a template language. What you build is then not (only) a parser but a compiler. It may make sense, though, to split the work into three steps: parse the input into some representation, manipulate this representation, write the output. That's how most compilers work. $\endgroup$ – Raphael Jun 27 '17 at 13:30
  • $\begingroup$ Or are you trying to extend, say, EBNF by this question-mark syntax? $\endgroup$ – Raphael Jun 27 '17 at 13:30
  • $\begingroup$ As I noted, I have no formal CS education, so I may be unknowingly misusing the terms. Including calling it a "parser" when it's not. Template language seems correct. I have no idea what EBNG is. $\endgroup$ – martixy Jun 27 '17 at 13:45
  • $\begingroup$ EBNF, sorry. I mistyped $\endgroup$ – Raphael Jun 27 '17 at 15:47
  • $\begingroup$ @Raphael EBNF would be used to describe this syntax, wouldn't it? So still not sure what your second comment means. $\endgroup$ – martixy Jun 28 '17 at 11:32
1
$\begingroup$

As far as I can tell, you can model this easily using any number of formalisms. Of course, if you insist on the specific syntax you have invented, you may be out of luck and may have to build your own engine.

I wouldn't to that if I were you: you have both forward and backward references, and your "data access" tokens closely resemble your "logic" tokens, so processing may become troublesome.

Consider this instead:

{if weight}; Weight is: {weight}kg{endif}

This can easily be parsed using standard techniques, and is immediately familiar to many people. It also supports nesting (if you use a context-free parser).


That all said, here is a sketch of an algorithm that will parse your syntax, assuming that there is no nesting at all (which you don't seem to specify).

We simply work in two phases:

  1. Lex the input into tokens: regular text, and your special tokens. Represent the former by text(text) latter by two types, data(name) and conditional(left, right, text).

    1. Go over the token list, evaluating each token according to these rules:

       eval text(t) ==> t
       eval data(n) ==> value(n)
       eval conditional(left, right, text) ==>  
          if   (!left || (eval predecessor) != "")  
            && (!right || (eval successor) != "") {
              text
          } else {
              ""
          }
      

You see that you have to keep two copies in memory, at least for a time.

I think it's straight forward to transform this solution so that you move a three-token window over the token stream; this way, you can forget old tokens, and only need to lex one token in advance. So, as long as your conditional tokens only depend on their immediate neighbours, this can be efficiently parsed.

$\endgroup$
  • 1
    $\begingroup$ I did 2 versions of this - one sorta worked, then I discovered a kink in the processing and redid the whole thing more or less as you described. I basically break it down to tokenization and the compiling. The tokenization is straightfoward, and then on compilation I remember the last valid for the lookbehind tag and when I encounter a lookahead, I stop appending and start remembering till I reach a normal tag and either discard my remembered stuff or append it(if it's normal text I append it anyway). This approach also allows me to create nested tags(I can recursively compile the tokens). $\endgroup$ – martixy Jul 5 '17 at 15:48
  • $\begingroup$ @martixy Nice! Question, though: how do you tokenize in the presence of nesting? $\endgroup$ – Raphael Jul 5 '17 at 22:45
  • $\begingroup$ Well, the tokens are an array containing entries of type/text. I just add a third - nested, which is the same - an array of type/text. Then when compiling, when I encounter nested tag, I just recursively call compile again. Decided its too much effort to have lookahead/behinds look outside of their own scope. $\endgroup$ – martixy Jul 6 '17 at 14:53
  • $\begingroup$ @martixy You evaded the question. How do you determine where a token ends? Without nesting, a token starts with { and ends with the next }; that's no longer true if you allow nesting. $\endgroup$ – Raphael Jul 6 '17 at 15:00
  • $\begingroup$ Sorry. Tokens end with } and are always the laziest consumption(i.e. in {tk}} the token is {tk} and the last } is text). For example {{nested} {?con}}?} the last ?} end up being considered plain text. $\endgroup$ – martixy Jul 9 '17 at 14:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.