1
$\begingroup$

I'm struggling to understand why this piece of lexical grammar works for multi-line comments in JavaCC (posted here):

 "/*" (~["*"])* "*" (~["*","/"] (~["*"])* "*" | "*")* "/"

As I read it, the parser scans the input /*, and then zero or more optional occurrences of * can appear, followed by a *, and then zero or more optional occurrences of * and /, then zero or more occurrences of * followed by * or *, ended by a /. Specifically, this part boggles my mind:

 (~["*","/"] (~["*"])* "*" | "*")*

I'd appreciate some help understanding this.

$\endgroup$
2
  • $\begingroup$ Try writing an expression yourself. Starts with /*, ends with */, and no */ in between. $\endgroup$
    – gnasher729
    May 10, 2020 at 19:17
  • $\begingroup$ In JavaCC, ~ is used to negate the following character class. So ~["*"]* means "zero more characters other than *. $\endgroup$
    – rici
    May 10, 2020 at 20:23

1 Answer 1

1
$\begingroup$

Let's write this in a more manageable way. I'll use $x$ for any symbol other than $/$ and $*$. Your expression is $$ /* (/+x)^* * (x(/+x)^** + *)^* / $$ Now let us apply the following identity to the part "$*(x(/+x)^**+*)^*$": $$ r(sr)^* = (rs)^*r $$ We get $$ /* (/+x)^* (*x(/+x)^*+*)^* */ $$ It's clear what the outer parts $/*$ and $*/$ do, so let's focus on the inner part $$ (/+x)^* (*x(/+x)^*+*)^* $$ which captures all strings not containing the substring $*/$. Using the identity $$ (rs+r)^* = (r^+s)^* $$ we can simply it to $$ (/+x)^* (*^+x(/+x)^*)^* $$ Essentially, each run of stars is "guarded" by a following $x$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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