Your assignment is to write a scanner for the μGo language with lex. This document gives the lexical definition of the language, while the syntactic definition and code generation will follow in subsequent assignments.
Your programming assignments are based around this division and later assignments will use the parts of the system you have built in the earlier assignments. That is, in the first assignment you will implement the scanner using lex, in the second assignment you will implement the syntactic definition in yacc, and in the last assignment you will generate assembly code for the Java Virtual Machine by augmenting your yacc parser.
This definition is subject to modification as the semester progresses. You should take care in implementation that the codes you write are well-structured and able to be revised easily.
1. μGo Language Features
We highlight the features of μGo by comparing it with C language. It is very important to note that μGo is not Go.
μGo is a static type and strong type language.
μGo statements do not end with semicolons ; .
Conditional expression(s) in if and for does not enclosed by parentheses. μGo does not define while in its language.
Simple example [Run online]
/* Example code. */
package main
func main() {
var a int32 = 3
var b int32 = 1
if a < 3 { b =2
}
var sum int32 = 0 var i int32
1/8
2/8
2. Lexical Definitions
Tokens are divided into two classes:
tokens that will be passed to the parser, and
tokens that will be discarded by the scanner (e.g., recognized but not passed to the parser).
2.1 Tokens that will be passed to the parser
The following tokens will be recognized by the scanner and will be eventually passed to the parser.
2.1.1 Delimiters
Each of these delimiters should be passed back to the parser as a token.
Delimiters Symbols
Parentheses (){}[]
Semicolon
Comma
Quotation
Newline
;
,
” ”
\n
2.1.2 Arithmetic, Relational, and Logical Operators
Each of these operators should be passed back to the parser as a token.
Operators
Arithmetic
Relational
Symbols
+ – * / % ++ —
< > <= >= == !=
Assignment = += -= *= /= %=
Logical && || !
for i = 0; i <= 10; i++ { sum += i
}
println(a) // 3 println(b) // 1 println(sum) // 55
}
2.1.3 Keywords
Each of these keywords should be passed back to the parser as a token. The following keywords are reserved words of μC:
Types
Datatype
Variable declaration Functional
2.1.4 Identifiers
keywords
int32 float32 bool string
var
func return package
Conditional if else for
Build-in functions print println
Switch switch case default
Anidentifierisastringofletters(a~z, A~Z, _)anddigits(0~9)anditbeginswith a letter or underscore. Identifiers are case-sensative; for example, ident , Ident , and
IDENT are not the same identifier. Note that keywords are not identifiers.
2.1.5 Integer Literals and Floating-Point Literals
Integer literals: a sequence of one or more digits, such as 1 , 23 , and 666 .
Floating-point literals: numbers that contain floating decimal points, such as 0.2 and 3.141 .
2.1.6 String Literals
A string literal is a sequence of zero or more ASCII characters appearing between double-quote ( ” ) delimiters. A double-quote appearing with a string must be written after a ” , e.g.,
“abc” and “Hello world” .
2.2 Tokens that will be discarded
The following tokens will be recognized by the scanner, but should be discarded, rather than returning to the parser.
2.2.1 Whitespace
A sequence of blanks (spaces), tabs, and newlines.
2.2.2 Comments
Comments can be added in several ways:
C-style is texts surrounded by /* and */ delimiters, which may span more than one line;
3/8
C++-style comments are a text following a // delimiter running up to the end of the line.
Whichever comment style is encountered first remains in effect until the appropriate comment close is encountered. For example,
// this is a comment // line */ /* with /* delimiters */ before the end
and
/* this is a comment // line with some /* and C delimiters */
are both valid comments.
2.2.3 Other characters
The undefined characters or strings should be discarded by your scanner during parsing.
3. What should Your Scanner Do? 3.1 Assignment Requirements
We have prepared 11 μGo programs, which are used to test the functionalities of your scanner.
Each test program is 10pt and the total score is 110pt. You will get 110pt if your scanner successfully generates the answers for all eleven programs. Note that the TA will prepare hidden test cases to verify that your scanner is not hardcoded to the attached inputs and outputs. For the hardcoded case, you will get 0pt.
We use local-judge ( ) to judge your program. You can use the judge program to get the testing score by typing in your terminal.
pip3 install local-judge
judge
4/8
The output messages generated by your scanner must use the given names of token classes listed below.
Symbol
Token Symbol Token
Symbol
if
for
float32
bool
false
var
package
switch
default
Token
IF
FOR
FLOAT
BOOL
FALSE
VAR
PACKAGE
SWITCH
DEFAULT
+ ADD && LAND
– SUB || LOR
println PRINTLN
* MUL !
NOT
LPAREN
RPAREN
LBRACK
RBRACK
LBRACE
RBRACE
SEMICOLON
COMMA
QUOTA
NEWLINE
COLON
INT_LIT
FLOAT_LIT
STRING_LIT
IDENT
COMMENT
/ QUO
% REM
++ INC
— DEC
> GTR
< LSS
>= GEQ
<= LEQ
== EQL
!= NEQ
= ASSIGN
+= ADD_ASSIGN
-= SUB_ASSIGN
*= MUL_ASSIGN
/= QUO_ASSIGN
%= REM_ASSIGN
(
)
[
]
{
}
;
,
”
\n
:
Int Number
Float Number
String Literal
Identifier
Comment
else ELSE
int32 INT
string STRING
true TRUE
func FUNC
return RETURN
case CASE
3.2 Example of Your Scanner Output
The example input code and the corresponding are as follows.
output that we expect your scanner to generate
5/8
Input:
var a int32 = 3
var b int32
println(a) /* print a */ b += 10 // Hello world for a < b {
a++ }
Output:
var VAR a IDENT int32 INT = ASSIGN 3 INT_LIT
NEWLINE var VAR
b IDENT int32 INT
NEWLINE println PRINTLN
( LPAREN a IDENT ) RPAREN /* print a */
NEWLINE b IDENT
C Comment
+= ADD_ASSIGN 10 INT_LIT // Hello world C++ Comment
NEWLINE for FOR
a IDENT
< LSS
b IDENT
{ LBRACE
NEWLINE a IDENT
++ INC
NEWLINE
} RBRACE
Finish scanning, total line: 7 comment line: 2
6/8
3.3 How to debug
Compile source code and feed the input to your program, then compare with the ground truth.
Check the output file char-by-char (Space and Tab are different)
$ make clean && make $ ./myscanner < input/in01_arithmetic.go >| tmp.out $ diff -y tmp.out answer/in01_arithmetic.out
$ od -c answer/in06_if.out
0000000 p ack a ge 0000020 G E \n m a in 0000040 E N T \n
0000060 E W L I N E \n 0000100 \t NE W LI 0000120 \t FU
\t PACKA \t ID \t N
N E \n f u n c N C \n m a i n
4. Environmental Setup
For Linux
Ubuntu 18.04 LTS
For Windows
You may like to install VirtualBox to emulate the Linux environment.
WSL2 with version: Ubuntu-18.04 ( wsl -l -v ) with Linux version 5.4.72-microsoft- standard-WSL2 (oe-user@oe-host) (gcc version 8.2.0 (GCC)) #1 SMP Wed Oct 28 23:40:43 UTC 2020 ( cat /proc/version ) in Windows 10.0.19044.1586 ( ver ) also works.
Install dependencies: $ sudo apt install flex bison git python3 python3-pip
Our grading system uses the Ubuntu environment. We will revise your uploaded code to adapt to our environment. In order to facilitate the automated code revision process, we need your help to arrange your code in the following format as specified in 5. Submission.
