I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question.

Here is the question:

Given the following lexical specification:


Which strings are NOT successfully processed by this specification?

  1. $0111110$
  2. $01100110$
  3. $0001101$
  4. $01100100$

The correct answers are 1 and 2. But I can't figure out why. How do I interpret this lexical specification? Can someone help me out with this.

  • 1
    $\begingroup$ Hint: the "specification" is probably intended to mean $(00)^* + 01^+ + 10^+$ (plus priorities, which you don't need to care about for this exercise). So the question reduces to "which strings match this regular expression?" (which I'd expect you to be able to do yourself if you want to take this course). $\endgroup$
    – Raphael
    Jun 26 '15 at 15:22
  • $\begingroup$ I do not see why the question is downvoted. It is interesting and well stated. It could contain some more details on why the poster could not figure out why the correct answers are 1 and 2. But then, no one said anything about that in the comments. $\endgroup$
    – babou
    Jun 30 '15 at 21:20

The strings not processed successfully are 1, 2, and 3. Only string 4 is processed successfully.

I think your problem is not with interpreting the meaning of regular expressions, but in understanding the process of lexical analysis, at least as intended in your course.

Normally, a regular expression is supposed to match a string from beginning to end. But when doing lexical analysis of a program, you are supposed to cut the program text in small chunks coresponding to the lexical elements of the language, which in turn can be taken (up to some details not relevant here) as the terminal alphabet of the (usually Context-Free) grammar used to define the language you are parsing.

So, during lexical analysis, you have nothing to indicate the end of a lexical element, as the program text goes on to give the next lexical element. For example, if you are scanning the string $foobar$, is it the identifier $f$ followed by $oobar$, or $foo$ followed by $bar$, or $fo$ followed by $oba$ and $r$. For a strict lexical point of view, all these possibilities would be correct ... though the grammatical parser that will use the lexical element can be unhappy with some choices.

To simplify matters, a simple rule is often followed by scanners performing lexical analysis, called maximal munch rule, or longest match rule. It works as follows:

While recognizing a lexical element, the lexical analyzer will keep reading the input string as long as it is reading a prefix of a lexical element, according to the lexical specification, and will halt when the next symbol to be read would no longer constitute such a prefix if added to the part of the input already scanned. At that point, if the scanned string corresponds to a complete lexical element (i.e. the scanning automaton is in an accepting state), this lexical element has been recognized. If it is only a prefix of a lexical element that cannot be completed with what follows into a proper lexical element, you have a lexical analysis error.

Thus with your example 1, $0111110$, the lexical analyser will start recognizing the second regular expression $01^+$, and will scan $011111$ as one lexical element. Then it is left with only $0$ which is the prefix of a word in the first two regular expression $(00)^*$ and $01^+$. But then the string stops, so that it cannot be part of a complete lexical element. hence the lexical analysis fails with an error at that point.

You could say that if you had stopped the first lexical element one symbol earlier, thus recognizing $01111$. Then you would be left with $10$ which is recognizable by the third regular expression $10^+$. But that is not how things work. There is no backtracking (actually, some scanners have more complex rules allowing for some backtrack, for example for the programming language C). Allowing this would also make thigs a lot more ambiguous as I explained in the $foobar$ example.

In the second example $01100110$, you get $011$, then $00$, and you are left with $110$. The first $1$ is a prefix for the regex $10^+$, but it should then be followed by at least one $0$, which is not there. Hence lexical analysis fails.

However, the third example $0001101$ should fail too. The reason is that symbols are read one by one. The first $0$ is a prefix for both regex $(00)^*$ and $01^+$. But, on scanning the second $0$, we know we are looking for a lexical element defined by the forst regex $(00)^*$. Then the third $0$ is ok too, since $000$ is a prefix of $0000$ which is recognized by the first regex. So it is scanned. But now we need a $0$, and we find a $1$. So the lexical analysis fails.

My guess is that the designer of the exercise recognize too quickly that it could work, by stopping one $0$ early (and I did too the first time I read this). But the computer does not have this global perception, and proceeds one symbol at a time.

The fourth example $01100100$ works fine, yielding $011$, $00$, and $100$.

If backtracking were allowed, all four strings could be scanned into lexical elements.

But the fourth string could then be scanned as:

  • $011$, $00$, $100$, or

  • $01$, $10$, $01$, $00$

Though you can use a rule that you backtrack only in case of failure, to avoid such an ambiguous situation.

Of course, there is the possibility that your instructor defined things differently, but this is the best I can do with the information I have.

  • $\begingroup$ You nailed it. I did have a problem understanding lexical analysis process. This is a great explanation. My understanding is that there is also a priority involved. The expressions above have a higher priority than the expressions below. But even using these rules I still can't come up with the answer the professor gave. $\endgroup$
    – flashburn
    Jun 29 '15 at 14:54
  • $\begingroup$ I am not sure I understand how priority can work well, with an efficient and intuitive algorithm (intuitive is needed for people to be able to read programs). Can you ask what the precise rules are, as this can vary somewhat, as I explain in the answer? There is also the possibility that he goofed on one example (third?), we all do on occasion. $\endgroup$
    – babou
    Jun 29 '15 at 15:20
  • $\begingroup$ I posted a question asking for a proper explanation on the MOOC website but as this is a self-paced course, I doubt I'll get an answer to it any time soon. $\endgroup$
    – flashburn
    Jun 29 '15 at 15:29
  • $\begingroup$ Here is another question that I was not able to answer. It is similar to the one I asked Given the following lexical specification: $a(ba)^*$<br /> $b*(ab)^*$<br /> $abd$<br /> $d^+$<br /> Which of the following statements is true? 1. $babad$ will be tokenized as: $bab/a/d$ 2. $ababdddd$ will be tokenized as: $abab/dddd$ 3. $dddabbabab$ will be tokenized as: $ddd/a/bbabab$ 4. $ababddababa$ will be tokenized as: $ab/abd/d/ababa$. Correct answers are 1 and 2. Maybe collectively we will be able to derive a correct set of rules. $\endgroup$
    – flashburn
    Jun 29 '15 at 15:38
  • $\begingroup$ @flashburn This seems in agreement with my answer, using longest match rule. Did you see a discrepancy? $\endgroup$
    – babou
    Jun 29 '15 at 15:57

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.