Homework 01 Solution

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.




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:




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



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



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














































Page 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.













Page 3
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