Reference no: EM133259634

Question 1: Regular Expressions

Write down regular expressions in JFlex syntax for each of the following string patterns:

a. Real numbers written to at most 2 decimal places (NB: zero d.p. means the number is an integer). So, 10, 1.5, 2.25 are all allowed, but 1.875, 0.0001 are not. For simplicity, you should require that there is at least 1 digit before any decimal point in the string.

b. Strings of upper case letters in which each of the vowels (A, E, I, O, U) may appear at most once, and if it does, it must appear only after any vowels that alphabetically precede it. The vowels do not necessarily have to appear consecutively within the string. Examples of permissible strings are "BAKER", "LACKING", "BENIGN", "ASCENSION", "ALVIOLUS"; examples of forbidden strings are "INSTEAD, "ALARMING", "AVOID"

Question 2: Parsing [50] In the following CFG, the symbols {a, b, c, d, e, $} are terminals. All others are non-terminals. X → Y Z Y → Y d|cY |e Z → aZb|XY

a. Draw the LR(0) state diagram for the CFG

b. Determine the first and follow sets for each non-terminal in the CFG.

c. Giving reasons for your answer, determine whether the CFG is:

(i) LR(0)

(ii) SLR(1)

d. The CFG is clearly not LL(1) because it is left-recursive.

(i) Rewrite the CFG to obtain an equivalent CFG that is no longer left-recursive (also ensure that your new CFG is fully left-factored).

(ii) Compute the first and follow sets for each non-terminal of your new CFG.

(iii) Construct the LL(1) parser table for your new CFG.

(iv) Determine from your table, whether the new CFG is LL(1) or not (give reasons for your answer).