2
$\begingroup$

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult.

My Regular Expression experience is profoundly in JavaScript and I'm concerned that it poisoned my thinking of Regular Expressions. For the life of me I can't figure this out. Answer A and Answer B I can rationalize, though my logic might be inherently flawed somehow. Being unable to understand how Answer C works brings me to the conclusion that I am profoundly missing something.

The Problem:

Consider the string abbbaacc Which of the following lexical specifications produces the tokenization ab/bb/a/acc ?

Answer A
a(b + c*) 
b+

Answer B
ab
b+
ac*

Answer C
c*
b+
ab
ac*

The two ways that I have tried to resolve Answer C

removing tokens(which I assumed is the correct way.)

abbbaacc

c* passes and returns token **cc**  //abbbaa
b+ passes and returns token **bbb** //aaa
ab passes and returns no token //aaa
ac* passes and returns no token //aaa
ending tokens: 
[cc, bbb]

Keeping String Whole:

abbbaacc

c* passes and returns **cc**
b+ passes and returns **bbb**
ab passes and returns **ab**
ac* passes and returns **acc**
ending tokens:
[cc, bbb, ab, acc]

I've tried other random ways as well but nothing turns out. I really am frustrated with this problem and I've been working on it for quite some time. I've reviewed the coursework that I have and I'm just at a loss. I am convinced that I must be conflating the more common Regular Expressions with this but I don't see where I'm doing so in any way that would make this answer correct. If anyone could provide any assistance I would greatly appreciate it!

$\endgroup$
  • $\begingroup$ Regular expressions are a concept from formal language theory. Most (if not all) language libraries implement some expanded pattern language which no longer has guaranteed linear-time/constant-space performance; we usually call these "regexes" to distinguish them from the mathematical concept. $\endgroup$ – rici Dec 5 '17 at 4:16
4
$\begingroup$

Tokenisation does not search. [Note 1]. At each step, it matches (and consumes) a match of one of the patterns starting precisely at the current input point.

Although there are other tokenisation algorithms, the most common one -- usually called maximal munch -- works as follows.

At each step:

  • Find the longest match of each pattern starting at the current input point. (This can be done in a single linear-time left-to-right scan of the input.)

  • Select the longest of all these matches. If more than one pattern has the same longest match, select the pattern which comes first in the list of patterns. Report the selected pattern and the corresponding matched prefix as the next token.

  • Remove the matched prefix from the input, and continue from the first step.

In effect, the match in the first step is a match of a regular expression created from the disjunction of all the patterns. The regular expression matching algorithm is modified so that:

  • It also reports which alternative matched, and

  • It leaves unmatched input in the input strean, rather than insisting that the regular expression match the entire input.

For your answer C, the regular expression created is $c^*+b^++ab+ac^*$. (Some tokenisers would correct the first pattern to $c^+$ because selecting an empty match would cause the above algorithm to fall into an endless loop.)

The longest prefixes successively matched by this disjunction are:

  • $ab$ (3rd alternative). The 4th alternative matches $a$, but that us shorter.

  • $bb$ (2nd alternative) The second alternative will also match $b$, but that's not the longest prefix matched by this pattern.

  • $a$ (4th alternative)

  • $acc$ (4th alternative)


Notes

  1. This should be intuitive. After all, most programs are read left to right and token order matters: $a = b + c;$ cannot be written as $a b c =+ ;$, and the parser will expect to see the tokens in left-to-right order, so if the lexer produced the stream, $a b c =+ ;$, the parser would get confused.
$\endgroup$
  • $\begingroup$ This is incredibly helpful. Thank you! I read it over about five times. It clicked. The course mentioned max munch for about two minutes in one of the lessons. The problem I think was that it referenced the old C++ error where two closing tags were viewed as an io operation and that was it. That alone isn't really an explanation but it's referenced quite frequently in a lot of places as though it were. Before you had posted this I thought I had solved it by extrapolating that the order was dictated by the least number of possible matches. ab=2, b+=1, a=1, ac*=1, c*=0. Saved me quite a headache $\endgroup$ – iwannawriteacompiler Dec 5 '17 at 7:05
  • $\begingroup$ @iwanna: >> is a bitshift, which --like any other operator-- can be overridden polymorphically. Letting it be parsed as two close template brackets is most conveniently done by using a slightly different pattern set (without the >> token) in a lexical contextin which > is a close template bracket. Alternatively, you can accept >> as a close template bracket and stuff a > back into the token stream. Both are hacks, but if you are going to parse C++ you'll need a strong stomach for hackery. The one exception to maximum munch is <::; m.m. would produce <: : but it's < ::. $\endgroup$ – rici Dec 5 '17 at 7:16
  • $\begingroup$ ... unless followed by >: <::> is <: :> just as maximal munch would produce. <:: can only be special cased by accepting it and <::> as single tokens (with naximal munch) and then sending the appropriate pair of tokens. $\endgroup$ – rici Dec 5 '17 at 7:23
  • 1
    $\begingroup$ I'm definitely not looking to parse C++ haha, and from what you've stated I'm a little glad that's the case. I'm taking in introductory course from Stanford's free online courses. It's CS1 Compilers. The idea is to build a very simple compiler(sans any true optimization) for the COOL language which is built just for classwork and learning. It's well done and is helping me learn but the quizzes seem to require answers dealing with glanced over topics and it's a bit annoying. I really do appreciate your answer because it was very clear and really helped settle my frustration. $\endgroup$ – iwannawriteacompiler Dec 5 '17 at 7:36

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.