Question

1. Write a CFG to generate identifiers (IDs) in the Java Programming Language. An ID in Java is a string of characters consisting of letters (upper-level or lower-level), digits, underscore _ , or dollar sign $. It cannot start with a digit.

Answer 1

Answer:

Explanation:

From the given condition in the question, An ID in Java is a string of characters consisting of letters (upper-level or lower-level), digits, underscore _ , or dollar sign $. It cannot start with a digit. Let C be a sequence of characters consisting of letters (upper-level or lower-level), digits, underscore _ , or dollar sign $ with no restriction on starting character. We can observe that it is the ID except first character. So, ID can be defined as $ followed by C, _ followed by C, digits followed by C and alphabets followed by C. Let N be a digit, and A be an alphabet, we define ID as  follows

S ------> $C / _C   / AC

N ------->0/1/2/3/4/5/6/7/8/9

A -------->a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X/Y/Z

We need to define C also, which is nothing but the string of character consisting of letters (upper-level or lower-level), digits, underscore _ , or dollar sign $. So, C can be defined as

C --------> $C / _C  /  NC  / AC / N / A

Hence our grammar for ID in java is:

S ------> $C / _C   / AC

C --------> $C / _C  /  NC  / AC / N / A

N ------->0/1/2/3/4/5/6/7/8/9

A -------->a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q/r/s/t/u/v/w/x/y/z/A/B/C/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X/Y/Z

In a leftmost derivation, we start with the start symbol and put the value of Non terminal that appers in the leftmost position and move gradually to right.

Here is the leftmost derivation of string $$_1uP

S

$C ...........using S--->$C

$$C ............using C---->$C

$$_C .........using C------->_C

$$_NC ........using C------->NC

$$_1C ........using N----->1

$$_1AC ........using C----->AC

$$_1uC .......using A------>u

$$_1uA ......using C----->A

$$_1uP ........using A----->P