Question

In Exercises \(7.34-7.35,\) we introduced Simpletron Machine Language \((\mathrm{SML}),\) and you implemented a Simpletron computer simulator to execute programs written in SML. In this section, we build a compiler that converts programs written in a high-level programming language to SML. This section "ties" together the entire programming process. You will write programs in this new high-level language, compile them on the compiler you build and run them on the simulator you built in Exercise \(7.35 .\) You should make every effort to implement your compiler in an object-oriented manner. (\text { The Simple Language })\( Before we begin building the compiler, we discuss a simple, yet powerful high-level language similar to early versions of the popular language BASIC. We call the language Simple. Every Simple statement consists of a line number and a Simple instruction. Line numbers must appear in ascending order. Each instruction begins with one of the following Simple commands: rem, input, 1 et, print, goto, if/goto or end (see Fig. 17.22 ). All commands except end can be used repeatedly. Simple evaluates only integer expressions using the \)+,-, *\( and / operators. These operators have the same precedence as in Java. Parentheses can be used to change the order of evaluation of an expression. Our Simple compiler recognizes only lowercase letters. All characters in a Simple file should be lowercase. (Uppercase letters result in a syntax error unless they appear in a rem statement, in which case they are ignored.) A variable name is a single letter. Simple does not allow descriptive variable names, so variables should be explained in remarks to indicate their use in a program. Simple uses only integer variables. Simple does not have variable declarations - merely mentioning a variable name in a program causes the variable to be declared and initialized to zero. The syntax of Simple does not allow string manipulation (reading a string, writing a string, comparing strings, and so on \)) .$ If a string is encountered in a Simple program (after a command other than rem), the compiler generates a syntax error. The first version of our compiler assumes that Simple programs are entered correctly. Exercise 17.29 asks the reader to modify the compiler to perform syntax error checking.

Short answer

Build a compiler that converts Simple programs to SML using a lexer, parser, and code generator within an object-oriented design.

Step-by-step solution

Understand Simple Language

The Simple language is a basic high-level programming language with a syntax similar to BASIC. It contains commands like rem, input, let, print, goto, if/goto, and end. It supports basic arithmetic operations and evaluates expressions with precedence similar to Java's operators. Variables are single lowercase letters; uppercase letters lead to syntax errors unless in rem statements.

Review Requirements for the Compiler

The task is to create a compiler that translates Simple programs into Simpletron Machine Language (SML). Ensure the compiler processes input in lowercase and automatically declares variables when they are first used, initializing them to zero. The final compiler should utilize object-oriented principles.

Define the Basic Compiler Structure

Design the compiler's architecture. Consider including a lexer (to tokenize input), a parser (to structure tokens into commands), a code generator (to convert structured commands into SML), and potentially a syntax checker (to improve flexibility after exercise 17.29).

Design the Lexer

The lexer will scan through the Simple program and convert it into tokens. Tokens are the smallest units like keywords (e.g., rem, input), operator symbols (+, -, *, /), integer literals, and variable identifiers (single lowercase letters). Ensure that the lexer is case-sensitive and only accepts lowercase letters unless they are in a rem statement.

Implement the Parser

Create a parser to analyze the sequence of tokens from the lexer and build a syntactic structure or abstract syntax tree (AST). This step organizes the tokens into understandable patterns corresponding to Simple's syntax, allowing for efficient translation to SML.

Develop the Code Generator

The code generator is the part of the compiler that takes the AST and produces the equivalent SML code. For each tree pattern recognized by the parser, the code generator emits corresponding SML instructions, carefully managing line numbers and logical jumps.

Build Additional Components

Include any additional components such as an error handler for syntax checking post-exercise 17.29 or optimization routines to improve SML performance. Tailor these components to ensure robust execution of Simple programs by managing variables and operator precedence properly.

Compile the Simple Program

Test the entire setup by running input Simple programs through the compiler. Ensure that the produced SML code executes correctly on the pre-built Simpletron simulator, validating both the compiler and the simulation environment.

Key concepts

High-level Programming Languages

High-level programming languages are designed to be easy for humans to read and write. Unlike machine language, which consists of binary code, high-level languages use syntax that resembles human language, making them much more user-friendly. These languages allow programmers to write instructions using easier-to-understand constructs, like loops and conditionals, which are then translated into machine code by a compiler.

• Examples include Python, Java, and C++.
• They often include libraries that simplify complex tasks.
• Languages like Simple, referenced in the exercise, offer basic control flow features and arithmetic operations but are more limited.

These languages abstract away the complexities of the underlying hardware, enabling developers to focus on the problem-solving aspects of programming. This abstraction dramatically enhances productivity and program manageability. However, the tradeoff is typically a loss in the fine-grained control over hardware execution, which is why high-level languages are often converted into machine language for execution via processes like compilation.

Object-oriented Programming

Object-oriented programming (OOP) is a paradigm that organizes software design around data, or objects, rather than functions and logic. The objects can contain data, in the form of fields (often called attributes), and code, in the form of procedures (often known as methods).

• OOP languages include Java, C++, and Python.
• They support concepts such as inheritance, encapsulation, and polymorphism.
• The solution emphasizes using OOP principles to construct the compiler.

In the context of building a compiler, employing OOP helps structure the compiler’s components, such as the lexer, parser, and code generator, into logical units with clear hierarchies and collaborations. This structuring aids in maintaining and extending the compiler by encapsulating functionality and promoting reusability of code across different parts of the compiler.

Simple Language Compilation

Simple language compilation refers to the process of turning code written in the Simple language (a high-level programming language similar to early BASIC) into Simpletron Machine Language (SML). This process involves several key steps that transform human-readable instructions into machine-executable code.

The primary steps in this process include:

• **Lexing**: Breaking down Simple code into tokens, which are the simplest elements like keywords and operators.
• **Parsing**: Organizing these tokens into an abstract syntax tree that mirrors the code's logical structure.
• **Code Generation**: Translating this structure to SML, ensuring instructions follow the Simpletron's machine-level execution format.

Compilation ensures that programs written in an accessible form can be executed by a computer. Each component of the compilation process needs to work seamlessly with the others to produce correct and efficient machine code.

Syntax Error Checking

Syntax error checking is a crucial part of any compiler's functionality. Syntax errors occur when code violates the rules of the programming language, such as having missing parentheses or misspelled commands.

Benefits of syntax error checking include:

• Providing programmers with immediate feedback on what went wrong and where.
• Preventing programs from executing with potentially harmful faults.
• Enhancing the reliability of the final software application by catching mistakes early in the process.

In the case of the Simple language compiler, step-by-step error checking can be enhanced by implementing a special component dedicated to analyzing the correctness of program syntax before translation. This involves designing checks that work efficiently within the compiler's lexer and parser phases, ensuring only syntactically accurate programs proceed to the code generation step.