CODEWITHSUNDEEP
grammar
user3252299
user3252299

Reputation: 15

Theory of computation - grammar and parsing

I am working on grammar and parsing (Theory of computation). What is the grammar for C style comments that start with /*, end with */ and contain no */ in between. What is the parse tree for the string /**a/*a**/?

Upvotes: 0

Views: 419

Answers (1)

digenishjkl
digenishjkl

Reputation: 164

Ensure that a * inside the comment text will either:

  • <text> ::= "*": Appear last on the comment text (terminal symbol), eg /*969969**/. Notice the last * before */ belongs to the comment text.

  • <text> ::= "*" "[not a slash]" <text>: Precede anything but a slash so that */ can only be captured by the parent rule and treated as a terminal symbol.

More formally:

<comment> ::= "/*" <text> "*/"
<text> ::=  <starless> <text> | "*" <slashless> <text> | "*" | ""

<starless> ::= "a" | "b" | "c" |... all printable except "*"
<slashless> ::= "a" | "b" | "c" |... all printable except "/"

As you see, a * is allowed to appear in the text only when the two given rules are satisfied.

The parse tree of /**a/*a**/ is generated as shown:

                    comment
              +--------+----+
             /       text    \
            /          |      \
           /  +--------+       \
          /  /        /|        \
         /  /        / |         \
        /  /        /  |          \
       /  / slashless text        :
      /  /   /         |          :     
     /  /   /       +--+          :      
    /  /   /       /   |          :       
   /  /   /  starless text        :             
  /  /   /    /        |          :                 
 /  /   /    /     +---+---+      :             
 :  :  :    :     /    |    \     :      
 :  :  :    :    / slashless text :       
 :  :  :    :    :    :      :    : 
/*  *  a    /    *    a      *   */

These rules do not apply to real C source code. You need to define rules that may "compete" for such symbols ( str = "/*Not a comment*/" ): Derive double quoted strings, inline comments, preprocessor directives etc.

Upvotes: 1

Related Questions