Reference no: EM132706825

Assignment - Parsing and Semantic Actions

Dice notation is a system to represent di?erent combi- nations of dice in role-playing games using simple algebra-like notation. The syntax of dice notation follows the following grammar, where all symbols in typewritter font (+, x, d, and int) are terminal symbols:
Rolls → Roll | Sum
Sum → Sum1 + Rolls | Roll
Roll → Dice | int | Dice x int
Dice → int1 d int2 | d int
A sample string of the language is 42 + 4d7x3 + d20
1. Is the grammar ambiguous? If it is, give an example. Otherwise, justify why it is not.
2. Give a leftmost derivation for the sample string.
3. Draw a parse tree for the sample string.

4. Write semantic actions to calculate the result of a dice roll expressed in dice notation. You may assume that in your actions you can also call the function random(n) which returns an integer between 1 and n (inclusive). You can execute arbitrary code in semantic actions (e.g., a for loop might come in handy), as long as you also assign some value to the left-hand side symbol. The final result should be stored as the value of the start symbol (i.e., Rolls.val).
5. Label/number your semantic actions. Describe an evaluation of the sample input, using the tree from question 3 and mentioning the order in which the actions are executed (use arbitrary random values for the results of calls to random).

2 LL(1) Grammars

In the following context-free grammar, which describes expressions in a simplified functional language, the symbols +, (, ), ->, and <id> are terminals and S is the initial symbol.
S → F + S | <id> -> S | F F → A V
A → F | ?
V → <id> | ( S )

1. Explain briefly why this grammar cannot be directly parsed by an LL(1) parser.

2. Convert this grammar to an equivalent one that has a better chance to be LL(1).

3. Write the First and Follow sets for all non-terminal symbols of the new grammar.

4. Construct the complete LL(1) parsing table for the new grammar.

5. Consider the tokens x and f to belong to the <id> token class. Show all the steps required to parse the input string: f(x -> x + f f x).

Attachment:- CSE_assignment 2.rar