CSCE-Homework 01 Solution

Description

• Instructions

In this assignment, you will be required to scan, parse, and check the semantics of a le that encodes the state of a variation of basic train Dominoes. The de nition of a properly formatted input le is given in Section 1.1.

You will be submitting one .java le and two .g4 (ANTLR) les via web hand-in.

1.1 File Speci cation

• The le contains two (2) labeled sections: Trains and Hands . Each section is enclosed by start and end tags (<< and >>, respectively).

• Trains is a pound-separated (#) list of lists (the dominoes that an individual has played) that appear between { and } tokens. Valid dominoes are of the form [N,N] where N is an integer.

• Hands is a pound-separated (#) list of lists (the dominoes that an individual holds) that appear between { and } tokens. Valid dominoes are of the form [N,N] where N is an integer.

An example of a properly formatted le is shown in Figure 1.

<T r a i n s <<

g

f [ 6 , 9 ]

[9 ,9]

g

#

f

[0 ,1]

[1 ,1]

#

f [ 2 , 1 1 ]

[11 ,11]

g

#

f

[10 ,10]

[10 ,12]

g

#

f [ 5 , 5 ]

[5 ,12]

g

#

f

[4 ,4]

[4 ,11]

g

g #

f [ 1 , 8 ]

[8 ,8]

>>

f

<Hands

<<

g #

[3 ,7]

[1 ,10]

[2 ,5]

[1 ,2]

[4 ,5]

[11 ,12]

[5 ,7]

[3 ,8]

[0 ,12]

[3 ,3]

[7 ,11]

f [ 6 , 8 ]

[0 ,0]

[2 ,6]

[7 ,10]

[2 ,12]

[8 ,9]

[1 ,7]

[4 ,9]

[1 ,5]

[3 ,12]

[1 ,4]

g #

f

[3 ,5]

[0 ,9]

[4 ,7]

[6 ,10]

[3 ,11]

[0 ,10]

[2 ,10]

[7 ,8]

[1 ,12]

[2 ,2]

[0 ,5]

g #

f [ 4 , 8 ]

[3 ,9]

[5 ,6]

[9 ,11]

[2 ,4]

[0 ,6]

[0 ,7]

[0 ,3]

[9 ,10]

[7 ,7]

[0 ,8]

g

#

g

f

[4 ,6]

[3 ,4]

[3 ,6]

[1 ,6]

[6 ,7]

[0 ,11]

[6 ,6]

[5 ,8]

[10 ,11]

[7 ,12]

[0 ,4]

#

f

[3 ,10]

[8 ,11]

[4 ,12]

[2 ,7]

[7 ,9]

[8 ,12]

[8 ,10]

[2 ,3]

[1 ,9]

[4 ,10]

[5 ,9]

g

#

f

[6 ,11]

[1 ,11]

[2 ,8]

[6 ,12]

[2 ,9]

[1 ,3]

[9 ,12]

[5 ,11]

[5 ,10]

[12 ,12]

[0 ,2]

g

>>

Figure 1: A properly formatted DOmino Con guration (doc) encoding

The assignment is made up of two parts: scanning the text of the input le and parsing the information contained in the input le.

1.2 Scanning

Construct a combined grammar in a .g4 le that ANTLR can use to scan a supplied Domino Con guration encoding. The logic in this le should be robust enough to identify tokens in the encoding and accurately process any correctly formatted encoding. The rules in your .g4 le will be augmented with actions that display information about the input le. An example of that output is speci ed in Section 2.

The purpose of the scanner is to extract tokens from the input and pass those along to the parser. For the Domino Con guration encoding, the types of tokens that you will need to consider are given in Table 1.

Type	Form
Section Beginning	<<
Section Ending	>>
Section Title	<Trains and <Hands
Domino Symbol	One or more Numerical Symbols
Numerical Symbol	0, 1, 2, 3, 4, 5, 6, 7, 8, or 9
Row Ending	#
List Beginning	{
List Ending	}
White Space (to be ignored)	spaces, tabs, newlines

Table 1: Tokens to Consider

1.2.1 Invalid Encodings

For invalid Domino Con guration encodings, the output Notification: Problem on Line L should dis-play. L would be the line of input where the unknown symbol was read. Your scanner should stop scanning the le after an unrecognized token is found.

1.3 Parsing

Construct a combined grammar in a .g4 le that ANTLR can use to parse a supplied Domino Con guration encoding. In addition to the rules for scanning, there are several parsing rules:

• There must be more than one (1) player (hand) in a game

• There must be more than one (1) player (train) in a game

The semantics of a properly formatted Domino Con guration encoding are:

1. There must be between 3 and 10 (inclusive) hands in a game

2. The number of played dominoes (dominoes in trains) must not exceed 20% of all dominoes in a game

3. Extra Credit (10 points or Honors contract): No train may be more than one (1) domino longer than any other train in the game

• Output

2.1 Scanner

Your .g4 le should produce output for both correctly formatted les and incorrectly formatted les. For the correctly formatted le in Figure 1, the output would have the form of the output presented in Figure 2

Portion : Trains

Begin Section

Begin List

Begin Domino

Half : 6

Half : 9

Conclude Domino

Begin Domino

Half : 9

Half : 9

Conclude Domino

Conclude List

Conclude Row

Begin List

Begin Domino

Half : 0

…

Begin Domino

Half : 8

Half : 8

Conclude Domino

Conclude List

Conclude Section

Portion : Hands

Begin Section

Begin List

Begin Domino

Half : 3

Half : 7

Conclude Domino

Begin Domino

Half : 1

…

Begin Domino

Half : 0

Half : 2

Conclude Domino

Conclude List

Conclude Section

Conclude File

Figure 2: Truncated Output of Scanner for File in Figure 1

For a correctly formatted le in Part 2, the output would be: d dominoes have been played where d is the number of dominoes that have been played in the Trains . For the le in Figure 1, the output would be

14 dominoes have been played.

2.2 Invalid Syntax & Semantics in Parsing

For invalid encodings in Part 2, a message describing the error should be displayed. For a syntax error (violation of the syntax rules), the output

Notification: Problem on Line L should be displayed, where L is the line number where the unrec-ognized token was found. For that error, the parser should stop processing the le. For a semantic rule violation, the output

Notification: Semantic Problem R should be displayed, where R is the number of the rule (from List 1.3) that was violated, but parsing should continue.

Syntax errors in Part 2 should be reported in the syntaxError method of csce322Homework01Part02Error.java.

• Naming Conventions

The ANTLR le for the rst part of the assignment should be named csce322Homework01Part01.g4. The ANTLR le for the second part of the assignment should be named csce322Homework01Part02.g4. Both grammars should contain a start rule named dominoes. The Java le for the second part of the assignment should be named csce322Homework01Part02Error.java.

• webgrader

The webgrader is available for this assignment. You can test your submitted les before the deadline by submitting them on webhandin and going to http://cse.unl.edu/~cse322/grade, choosing the correct assignment and entering your cse.unl.edu credentials

The script should take approximately 2 minutes to run and produce a PDF.

4.1 The Use of diff

Because Part 1 of this assignment only depends on the symbols in the le, the order in which they are displayed should not be submission dependent. Therefore, diff will be used to compare the output of a particular submission against the output of the solution implementation. For Part 2, order and repeated output lines will not in uence diff.

• Point Allocation

Component	Points
Part 1	35
Part 2	65
Total	100

6	External Resources
ANTLR
Getting Started with ANTLR v4
ANTLR 4 Documentation
Overview (ANTLR 4 Runtime 4.7 API)
7	Commands of Interest
alias		antlr4 = ‘ java – jar / path / to / antlr -4.7.1 – complete . jar ‘
alias grun =’ java org . antlr . v4 . gui . TestRig ‘
export		C LA SS PA TH =”/ path / to / antlr -4.7.1 – complete . jar : $C L A S S P A T H “
antlr4		/ path / to / c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 #. g4
javac		-d / path / for /. c l a s s f i l e s / path / to / c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 #*. java
java	/ path / of /. c l a s s f i l e s c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 2 D r i v e r / path / to / i np ut fi le
grun	c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 #		dominoes	– gui
grun	c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 #		dominoes	– gui / path / to / i np ut fi le
grun	c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 #		dominoes
grun	c s c e 3 2 2 H o m e w o r k 0 1 P a r t 0 #		dominoes	/ path / to / i np ut fi le

Page 4