quetzal

1. Introduction

This document contains the complete technical specification of the Quetzal Dragon programming language.

The Quetzal Dragon is a dragon based on the Aztec culture. Its name and appearance are based on the Aztec God Quetzalcoatl, a flying serpent covered in feathers. Its colors are based on the quetzal bird and it’s also one of the few dragons without legs.
— Dragon City Wiki

This language specification was developed for the 2022 spring semester TC3048 Compiler Design course at the Tecnológico de Monterrey, Campus Estado de Mexico.

2. Lexicon

In the following sections, a letter is any character from the English alphabet from A to Z (both lowercase and uppercase). A digit is any character from 0 to 9.

2.1. Tokens

There are five kinds of tokens: identifiers, keywords, literals, operators, and other separators. Spaces, tabulators, newlines, and comments (collectively, “white space”) are used as delimiters between tokens, but are otherwise ignored.

If the input stream has been separated into tokens up to a given character, the next token is the longest string of characters that could constitute a token.

2.2. Comments

Comments can be either single or multi-line. Single line comments start with two slash symbols (//) and conclude at the end of the line. Multi-line comments start with a slash symbol followed by an asterisk symbol (/*) and end with an asterisk symbol followed by a slash symbol (*/). Comments cannot be placed inside string literals. Multi-line comments cannot nest.

2.3. Identifiers

An identifier is composed of a letter and a sequence of zero or more letters, digits and the underscore character (_). Uppercase and lowercase letters are considered different. Identifiers can be of any length.

An identifier token appears as an ‹id› terminal symbol in the language grammar.

2.4. Keywords

The following fourteen identifiers are reserved for use as keywords with special meanings and may not be used for any other purpose:

and

false

or

break

if

return

dec

inc

true

elif

loop

var

else

not

2.5. Literals

At a lexical level there are four kinds of literals: booleans, integers, characters, and strings.

2.5.1. Booleans

A boolean literal is either the keyword true or the keyword false. These are equal to 1 and 0, respectively.

A boolean literal token appears as a ‹lit-bool› terminal symbol in the language grammar.

2.5.2. Integers

An integer literal is a sequence of one or more digits from 0 to 9. It can optionally start with a minus (−) sign. Only decimal (base 10) numbers are supported. Valid range: −2,147,483,648 to 2,147,483,647 (\(-2^{31}\) to \(2^{31} - 1\)).

An integer literal token appears as a ‹lit-int› terminal symbol in the language grammar.

2.5.3. Characters

A character literal is a Unicode character enclosed in single quotes, as in 'x'. The compiler translates the specified character into its corresponding Unicode integer code point.

Character literals cannot contain the quote character (') or a newline character; in order to represent them, and certain other characters, the following escape sequences may be used:

Name Escape Sequence Code Point

Newline

\(\backslash \texttt{n}\)

10

Carriage Return

\(\backslash \texttt{r}\)

13

Tab

\(\backslash \texttt{t}\)

9

Backslash

\(\backslash \backslash\)

92

Single Quote

\(\backslash \texttt{'}\)

39

Double Quote

\(\backslash \texttt{"}\)

34

Unicode Character

\(\backslash \texttt{u} hhhhhh\)

\(hhhhhh\)

The escape sequence \(\backslash \texttt{u} hhhhhh\) consists of the backslash, followed by the lower case letter “u”, followed by six hexadecimal digits (digits “0” to “9” and the upper or lower case letters “a” to “f”), which are taken to specify the code point in base 16 of the desired character.

A character literal token appears as a ‹lit-char› terminal symbol in the language grammar.

2.5.4. Strings

A string literal is a sequence of zero or more Unicode characters delimited by double quotes, for example: "this is a string". String literals cannot contain newline or double-quote characters. These and other special characters can be represented using the same escape sequences available for character literals.

A string literal is stored in memory as an array (accessible through a 32-bit handle) containing zero or more int32 values. Each value is the code point of the character in the corresponding position of the given string. In other words, a string is stored using the UTF-32 encoding.

A string literal token appears as a ‹lit-str› terminal symbol in the language grammar.

3. Syntax

The following BNF context free grammar defines the syntax of the Quetzal Dragon programming language. The red elements represent explicit terminal symbols (tokens).

‹program›

\(\rightarrow\)

‹def-list›

‹def-list›

\(\rightarrow\)

‹def-list› ‹def›

‹def-list›

\(\rightarrow\)

ε

‹def›

\(\rightarrow\)

‹var-def›

‹def›

\(\rightarrow\)

‹fun-def›

‹var-def›

\(\rightarrow\)

var ‹var-list› ;

‹var-list›

\(\rightarrow\)

‹id-list›

‹id-list›

\(\rightarrow\)

‹id› ‹id-list-cont›

‹id-list-cont›

\(\rightarrow\)

, ‹id› ‹id-list-cont›

‹id-list-cont›

\(\rightarrow\)

ε

‹fun-def›

\(\rightarrow\)

‹id› ( ‹param-list› ) { ‹var-def-list› ‹stmt-list› }

‹param-list›

\(\rightarrow\)

‹id-list›

‹param-list›

\(\rightarrow\)

ε

‹var-def-list›

\(\rightarrow\)

‹var-def-list› ‹var-def›

‹var-def-list›

\(\rightarrow\)

ε

‹stmt-list›

\(\rightarrow\)

‹stmt-list› ‹stmt›

‹stmt-list›

\(\rightarrow\)

ε

‹stmt›

\(\rightarrow\)

‹stmt-assign›

‹stmt›

\(\rightarrow\)

‹stmt-incr›

‹stmt›

\(\rightarrow\)

‹stmt-decr›

‹stmt›

\(\rightarrow\)

‹stmt-fun-call›

‹stmt›

\(\rightarrow\)

‹stmt-if›

‹stmt›

\(\rightarrow\)

‹stmt-loop›

‹stmt›

\(\rightarrow\)

‹stmt-break›

‹stmt›

\(\rightarrow\)

‹stmt-return›

‹stmt›

\(\rightarrow\)

‹stmt-empty›

‹stmt-assign›

\(\rightarrow\)

‹id› = ‹expr› ;

‹stmt-incr›

\(\rightarrow\)

inc ‹id› ;

‹stmt-decr›

\(\rightarrow\)

dec ‹id› ;

‹stmt-fun-call›

\(\rightarrow\)

‹fun-call› ;

‹fun-call›

\(\rightarrow\)

‹id› ( ‹expr-list› )

‹expr-list›

\(\rightarrow\)

‹expr› ‹expr-list-cont›

‹expr-list›

\(\rightarrow\)

ε

‹expr-list-cont›

\(\rightarrow\)

, ‹expr› ‹expr-list-cont›

‹expr-list-cont›

\(\rightarrow\)

ε

‹stmt-if›

\(\rightarrow\)

if ( ‹expr› ) { ‹stmt-list› } ‹else-if-list› ‹else›

‹else-if-list›

\(\rightarrow\)

‹else-if-list› elif ( ‹expr› ) { ‹stmt-list› }

‹else-if-list›

\(\rightarrow\)

ε

‹else›

\(\rightarrow\)

else { ‹stmt-list› }

‹else›

\(\rightarrow\)

ε

‹stmt-loop›

\(\rightarrow\)

loop { ‹stmt-list› }

‹stmt-break›

\(\rightarrow\)

break ;

‹stmt-return›

\(\rightarrow\)

return ‹expr› ;

‹stmt-empty›

\(\rightarrow\)

;

‹expr›

\(\rightarrow\)

‹expr-or›

‹expr-or›

\(\rightarrow\)

‹expr-or› or ‹expr-and›

‹expr-or›

\(\rightarrow\)

‹expr-and›

‹expr-and›

\(\rightarrow\)

‹expr-and› and ‹expr-comp›

‹expr-and›

\(\rightarrow\)

‹expr-comp›

‹expr-comp›

\(\rightarrow\)

‹expr-comp› ‹op-comp› ‹expr-rel›

‹expr-comp›

\(\rightarrow\)

‹expr-rel›

‹op-comp›

\(\rightarrow\)

==

‹op-comp›

\(\rightarrow\)

!=

‹expr-rel›

\(\rightarrow\)

‹expr-rel› ‹op-rel› ‹expr-add›

‹expr-rel›

\(\rightarrow\)

‹expr-add›

‹op-rel›

\(\rightarrow\)

<

‹op-rel›

\(\rightarrow\)

<=

‹op-rel›

\(\rightarrow\)

>

‹op-rel›

\(\rightarrow\)

>=

‹expr-add›

\(\rightarrow\)

‹expr-add› ‹op-add› ‹expr-mul›

‹expr-add›

\(\rightarrow\)

‹expr-mul›

‹op-add›

\(\rightarrow\)

+

‹op-add›

\(\rightarrow\)

−

‹expr-mul›

\(\rightarrow\)

‹expr-mul› ‹op-mul› ‹expr-unary›

‹expr-mul›

\(\rightarrow\)

‹expr-unary›

‹op-mul›

\(\rightarrow\)

*

‹op-mul›

\(\rightarrow\)

/

‹op-mul›

\(\rightarrow\)

%

‹expr-unary›

\(\rightarrow\)

‹op-unary› ‹expr-unary›

‹expr-unary›

\(\rightarrow\)

‹expr-primary›

‹op-unary›

\(\rightarrow\)

+

‹op-unary›

\(\rightarrow\)

−

‹op-unary›

\(\rightarrow\)

not

‹expr-primary›

\(\rightarrow\)

‹id›

‹expr-primary›

\(\rightarrow\)

‹fun-call›

‹expr-primary›

\(\rightarrow\)

‹array›

‹expr-primary›

\(\rightarrow\)

‹lit›

‹expr-primary›

\(\rightarrow\)

( ‹expr› )

‹array›

\(\rightarrow\)

[ ‹expr-list› ]

‹lit›

\(\rightarrow\)

‹lit-bool›

‹lit›

\(\rightarrow\)

‹lit-int›

‹lit›

\(\rightarrow\)

‹lit-char›

‹lit›

\(\rightarrow\)

‹lit-str›

4. Semantics

4.1. Compile Time Validations

  1. The language only supports a 32-bit signed two’s complement integer (int32) data type. This is the data type for every variable, parameter and function return value. This means that a Quetzal Dragon compiler doesn’t need to verify type consistency.

  2. Every program starts its execution in a function called main. It is an error if the program does not contain a function with this name. It is also an error if the main function defines one or more parameters.

  3. Any variable defined outside a function is a global variable. The scope of a global variable is the body of all the functions in the program, even those defined before the variable itself.

  4. Function names and global variables exist in different namespaces. This means that you can have a global variable with the same name as a function and vice versa.

  5. It’s an error to define two global variables with the same name.

  6. It’s an error to define two functions with the same name.

  7. A function definition is visible from the body of all the functions in a program, even from itself. Thus, functions can call themselves recursively directly or indirectly.

  8. In every function call the number of arguments must match the number of parameters contained in the corresponding function definition.

  9. The following names are part of the initial namespace for functions and constitute Quetzal Dragon’s API (the number after the slash symbol (/) is the arity of the given function):

    • printi/1

    • printc/1

    • prints/1

    • println/0

    • readi/0

    • reads/0

    • new/1

    • size/1

    • add/2

    • get/2

    • set/3

  10. Each function has its own independent namespace for its local names. This means that parameter and local variable names have to be unique inside the body of each function. It’s valid to have a parameter or local variable name with the same name as a global variable. In that case the local name shadows the global variable.

  11. It’s an error to refer to a variable, parameter or function not in scope in the current namespace.

  12. The break statement can only be used inside the body of a loop statement.

  13. Values of integer literals should be between -2147483648 and 2147483647 (\(-2^{31}\) and \(2^{31} - 1\), respectively).

4.2. Runtime Behavior

  1. A function returns zero by default, except if it executes an explicit return statement with some other value.

  2. The value returned by the main function must be the exit code returned by the program to the operating system.

  3. For the conditional and loop statements (if and loop) the number 0 is the only value considered false, everything else is considered true.

  4. The assignment, function call, conditional, break, and return statements behave like their C# counterparts. The loop statement is equivalent to while(true) { …​ } in other languages. The increment statement (inc) adds one to the provided variable, while the decrement statement (dec) subtracts one from it.

  5. The Quetzal Dragon syntax supports string and array literals. Both of these are represented in memory as arrays accessible through API managed 32-bit handles.

  6. The following are the supported operators. Precedence and associativity are established in the language grammar.

    Table 1. Arithmetic operators
    Operator Syntax Description

    Unary minus

    − x

    Produces x negated (with its sign changed).

    Unary plus

    + x

    Produces x.

    Multiplication

    x * y

    Produces x times y.

    Division

    x / y

    Produces x divided by y truncating the result towards zero. An exception is thrown if y is zero.

    Remainder

    x % y

    Produces the remainder of dividing x by y. An exception is thrown if y is zero.

    Addition

    x + y

    Produces x plus y.

    Subtraction

    x − y

    Produces x minus y.
    Table 2. Logical operators
    Operator Syntax Description

    Not

    not x

    Evaluates x and produces 1 if its result is equal to 0. Otherwise produces 0.

    And

    x and y

    Produces 1 if both x and y evaluate to non-zero values. Otherwise, produces 0. The operation is short circuited, this means that if x evaluates to 0 then y is not evaluated.

    Or

    x or y

    Produces 1 if either x or y evaluate to a non-zero value. Otherwise, produces 0. The operation is short circuited, this means that if x evaluates to a non-zero value then y is not evaluated.
    Table 3. Comparison and relational operators
    Operator Syntax Description

    Equal to

    x == y

    Produces 1 if x is equal to y, otherwise produces 0.

    Not equal to

    x != y

    Produces 1 if x is not equal to y, otherwise produces 0.

    Greater than

    x > y

    Produces 1 if x is greater than y, otherwise produces 0.

    Less than

    x < y

    Produces 1 if x is less than y, otherwise produces 0.

    Greater than or equal to

    x >= y

    Produces 1 if x is greater than or equal to y, otherwise produces 0.

    Less than or equal to

    x <= y

    Produces 1 if x is less than or equal to y, otherwise produces 0.
    Table 4. Function call
    Operator Syntax Description

    Function call

    f (arg1, arg2, …​, argn)

    Invoke f with the given arguments and return its result. All arguments are fully evaluated before the call.

5. API

This section documents all the functions from the Quetzal Dragon application programming interface (API).

Table 5. Input/Output Operations
Signature Description

printi(i)

Prints i to stdout as a decimal integer. Does not print a new line at the end. Returns 0.

printc(c)

Prints a character to stdout, where c is its Unicode code point. Does not print a new line at the end. Returns 0.

prints(s)

Prints s to stdout as a string. s must be a handle to an array containing zero or more Unicode code points. Does not print a new line at the end. Returns 0.

println()

Prints a newline character to stdout. Returns 0.

readi()

Reads from stdin an optionally signed decimal integer and returns its value. Does not return until a valid integer has been read.

reads()

Reads from stdin a string (until the end of line) and returns a handle to a newly created array containing the Unicode code points of all the characters read.
Table 6. Array List Operations
Signature Description

new(n)

Creates a new array object with n elements and returns its handle. All the elements of the array are set to zero. Throws an exception if n is less than zero.

size(h)

Returns the size (number of elements) of the array referenced by handle h. Throws an exception if h is not a valid handle.

add(h, x)

Adds x at the end of the array referenced by handle h. Returns 0. Throws an exception if h is not a valid handle.

get(h, i)

Returns the value at index i from the array referenced by handle h. Throws an exception if i is out of bounds or if h is not a valid handle.

set(h, i, x)

Sets to x the element at index i of the array referenced by handle h. Returns 0. Throws an exception if i is out of bounds or if h is not a valid handle.

6. Code Examples

Source File Description

001_hello.quetzal

The classical "hello, world" program.

002_binary.quetzal

Converts decimal numbers into binary.

003_palindrome.quetzal

Determines if a string is a palindrome.

004_factorial.quetzal

Computes factorials using iteration and recursion.

005_arrays.quetzal

Implementation of typical array operations.

006_next_day.quetzal

Given the date of a certain day, determines the date of the day after.

007_literals.quetzal

Verifies that the implementation of literal values meet the specified requirements.

008_vars.quetzal

Example using global and local variables.

009_operators.quetzal

Verifies that the implementation of all the operators meet the specified requirements.

010_breaks.quetzal

Verifies that the implementation of the break statement meets the specified requirements.