Assignment Description

This assignment asks you to implement a basic parser for our dj2dism compiler. You will use bison to generate the parser.

First, download this CFG-less dj.y - in the attachment- Modify that dj.y by declaring appropriate precedence directives in the first section and a correct CFG for DJ in the second section. For this assignment, leave the actions in your CFG empty, except for the {return 0;} action for the CFG's starting symbol (Assignment IV will ask you to fill in the CFG actions to build an AST).

For full credit, your parser must have no conflicts (shift/reduce or reduce/reduce). To make it easier for you to complete Assignment IV in the future, you may want (but are not required) to declare your DJ grammar rules to be left recursive.

Hints

When you find that your parser has conflicts (like I did on my first attempt at this assignment), please examine your bison output file to find the cause of the conflict and then think calmly and carefully about how to modify the CFG to remove the conflict. Please do not just try to "hack" through the problem! Hacked-up grammars are normally complicated and hard to understand. Part of your grade on this assignment will be determined by the simplicity/elegance of your grammar.

My DJ CFG uses 12 nonterminals (e.g., pgm for a program, cdl for a class-declaration list, vdl for a variable-declaration list, t for a typename, id for an identifier, el for an expression list, expr for an expression, and ael for an argument-expression list).

Precedence and Associativity of Operators

A key challenge of this assignment is to declare precedence directives correctly and only in ways that immediately make sense to outside readers of your code.

Consider the following DJ expression (from file good11.dj):

n = n>6+3 && !2+3 && n = !c.n*!3 && 1+3==4

A correct and complete DJ parser (as yours should be after you complete Assignment IV) would produce the following AST for the good11.dj expression above:

A correct declaration of precedence directives (%left, %nonassoc, %right) in this assignment will help produce these groupings. Notice, for instance that the DOT operator has the highest precedence, while the (right-associative) ASSIGN operator has the lowest precedence. The (left-associative) PLUS and MINUS operators should have equal precedences. The (nonassociative) EQUALITY and GREATER operators should also have equal precedences, though their precedences differ from those of PLUS and MINUS. Although the NOT operator is unary (i.e., only has one operand), you can declare it to be right associative for the sake of ordering its precedence.

Attachment:- dj.txt