CS 315
Project 1

Design of a Programming Language for Processing Boolean Data and Its Lexical Analyzer

This semester’s projects focus on the design of a new programming language that is limited to Boolean data types. This newly designed language will be similar to imperative languages. The main difference is that the language is restricted to Boolean data and aggregate structures built from Boolean values. String constants can be used in output operations. The first part of the project is about the design of the language and the implementation of its lexical analyzer.

Part A - Language Design (30 points)

First, you will give a name to your language and design its syntax. Note that the best way to hand in your design is with its grammar in the BNF (not EBNF) form, followed by a description of each language component. The following is a list of features that are required in your language:

• Constant truth values (true, false).
• A data structure to store a collection of Boolean values
• Variables, which may be assigned Boolean values or an aggregate of Boolean values
• Operators (and, or, not, implication, double implication)
• Expressions may contain matching parentheses along with Boolean values, variables, operators, and function calls.
• Conditional statements (e.g., if-then, if-then-else)
• Looping statement(s)
• Input/output statements (string constants can be displayed on the console)
• Function definitions (functions take and return Boolean values)
• Comments.

You are encouraged to use your imagination to extend the list given above.

Discuss any other features of your language that you think are important.

Do not panic! You will have a chance to do minor revisions to your syntax design for Project 2 (later in the semester). Language designs are almost never exactly right in the first iteration. Just try your best to make it as readable, writable, and reliable as you can and keep your eyes open for what does and what does not work :)

Part B - Lexical Analyzer (40 points)

Having designed the language, you will design and implement a lexical analyzer for your language, using the lex tool available on all Unix-style systems. Your scanner should read its input stream and output a sequence of tokens corresponding to the lexemes you will define in your language. Since at this stage, you will not be able to connect the output to a parser, your scanner will print the names of the tokens on the screen. For instance, if we were designing a C-like syntax, for the input

if (p implies q) x gets false ; display "OK" x ;

the lexical analyzer should produce the output

IF LP IDENTIFIER OP IDENTIFIER RP IDENTIFIER ASSIGN CONST SC DISPLAY STR IDENTIFIER SC

Part C - Example Programs (30 points)

Finally, you will prepare three test programs of your choice that exercise all of the language constructs in your language, including the ones that you may have defined in addition to the required list given above. In addition to your test programs, write programs corresponding to the following two pieces of pseudocode:

Program 1:

1. prompt the user to enter the values of x, y, and z 
2. read the value of x, y, and z from the keyboard
3. if all of them are true ask the user to enter at least one false value 
4. keep reading new values until proper values are entered.
5. display the value of the expression (x implies y) and (not x doubly implies z)

Program 2:

1. define a function foo that has 3 parameters p, q, and r, 
   and displays its name, the names and the values of the parameters, then
   if r is true it returns the value of p implies (q or r), otherwise q doubly-implies r.
2. for each value of a in the list of {true, false} // assuming your data structure has such a syntax
2.1.   for each value of b in the list of {true, false}
2.1.1.    c gets foo(a, b, false)
2.1.2     display the values of a, b and c

Make sure your lex implementation correctly identifies all the tokens. The TA will test your lexical analyzer with these example programs along with other programs written in your language. Your grade will primarily depend on internal consistency between grammar, lexical analyzer, and example programs.

Do not panic! You are not required to write an interpreter or compiler for this language. Just write a few programs in the language you designed and make sure that the lexical analyzer produces the right sequence of tokens.

Groups

Submission

• There are several parts that you will hand in.
  1. A project report including the following components:
     • Name, ID, and section for all of the project group members.
     • The name of your programming language.
     • The complete BNF description of your language.
     • A paragraph explanation for each language construct (i.e. variables and terminals) detailing their intended usage and meaning, as well as all of the associated conventions.
     • Descriptions of how nontrivial tokens (comments, identifiers, literals, reserved words, etc) are defined in your language. For all of these, explain what your motivations and constraints were and how they relate to various language criteria such as readability, writability, reliability, etc.
  2. Your lex description file
  3. The example program described above, written in your language
• Make sure your lexical analyzer compiles and runs on dijkstra.cs.bilkent.edu.tr . The TA will test your project on the dijkstra machine, and any project that does not compile or run on this machine will get 0 on Part-B.
• Your password is the same as the one for your @ug.bilkent.edu.tr e-mail account.
• Please upload all of the above items, as a single zip file, to Moodle before the due date. PDF format is preferred for the project reports.
• Late submissions will be accepted, with 20 points (out of 100) deduction for each extra day.

Resources

• Running lex and yacc on Linux systems (accessible in Bilkent Campus)
• John R. Levine, Tony Mason & Doug Brown, "Lex & Yacc"