0
$\begingroup$

I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc.

The options are:

A.
    a(b+c)*
    b+

B.
    ab 
    b+
    ac*

C.
    c* 
    b+
    ab
    ac*

D.
    b+ 
    ab*
    ac*

I just learned about REGEX, and I'm not sure about this, but to solve this problem would I just be trying see which options can make ab/bb/a/acc?

If that's correct, then would the answer be all four of them?

Since all four of them can match to ab/bb/a/acc:

A.
     a(b+c)* -> a, ab, acc 
     b+ -> bb
B. 
     ab -> ab
     b+ -> bb
     ac* -> a, acc
C.
     c* -> 
     b+ -> bb
     ab -> ab
     ac* -> a, acc
D. 
     b+ -> bb
     ab* -> a, ab
     ac* -> a, acc

I'm not sure if I'm doing this correctly.

$\endgroup$
  • 2
    $\begingroup$ How does one tokenize an input given a lexical specification? Using maximal munch or using some other rule? Please include this information in the question. $\endgroup$ – Yuval Filmus Jan 31 at 4:21
0
$\begingroup$

There's not enough information here to answer the question, but I can prove a pretty good guess based on how tokenizers are typically implemented. Generally the tokenizer will run through the list of patterns, trying each one I sequence. If one of them matches it takes the longest possible match as a token, then starts over at the top of the list. I surmise this is the implicit background for the question.

So forinstance if you have abbbaacc and the rules a(b|c)* and b+ in that order then you'd tokenize that as abbb/a/acc.

$\endgroup$

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.