Esercizi di Linguaggi di Programmazione

Esercizi Avanzati su Scala


Exercise 1: DSL without Parser Combinators.

Define the following DSL in Scala without using the Parser Combinators:

  1. Define a simple calculator DSL that parses (and evaluates) scripts containing several expressions one each line. The admitted operators are: +, -, *, /, ^, sqrt, sin, cos, tan and parentheses with the traditional meanings; all of them can work on integers and reals value. The result for the script evaluation is a printout of the results of the single values.
  2. Extend the DSL developed in the first point and add it the support for variables with assignments. Variables are 1-character long strings that need to be assigned to an expression and later can be used into other expressions; a second assignment will replace the value and an attempt to use an uninitialized variable will raise an error. Basically, the assignment has the traditional behavior, i.e., it is evaluated from right to left whereas all the other expressions are evaluated from left to right, therefore A = B = 5+7 is a correct and admissible instruction in this DSL. Variables are untyped or better all of them are numbers.
Exercise 2: DSL with Parser Combinators but without a Grammar.

Formally describe the grammars for the DSLs described in the first exercise and from such a grammar repeat the exercise with the parser combinators technique.

Exercise 3: Arithmetic operations as in the Primary School.

Let us consider the possibility to parse and evaluate scripts representing additions and subtractions written as in the primary school.



The rules to consider are:

The script includes both the operation and its expected result, the result of parsing/evaluation such a script should be the validation that the written result is the correct one.

Exercise 4: Brainfuck.

The Language

The brainfuck language uses a simple machine model consisting of the program and instruction pointer, as well as an array of at least 30,000 byte cells initialized to zero; a movable data pointer (initialized to point to the leftmost byte of the array); and two streams of bytes for input and output (most often connected to a keyboard and a monitor respectively, and using the ASCII character encoding).

Commands

The eight language commands, each consisting of a single character:

Character Meaning
> increment the data pointer (to point to the next cell to the right).
< decrement the data pointer (to point to the next cell to the left).
+ increment (increase by one) the byte at the data pointer.
- decrement (decrease by one) the byte at the data pointer.
. output a character, the ASCII value of which being the byte at the data pointer.
, accept one byte of input, storing its value in the byte at the data pointer.
[ if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command*.
] if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command*.

any other character contributes to for a spurious string and is ignored.

Grammar

The brainfuck grammar is

Some examples in brainfuck are (respectively, helloworld, extract prime factors from a given integer and a quine):



write a «compiler» by using the parser combinator technique.

Walter Cazzola

Didactics

Publications

Funded Projects

Research Projects

Related Events








Valid XHTML 1.0 Transitional