Note: this problem is taken from the Programming Languages
subject at Barcelona School of Informatics.
Design a parser to describe heterogeneous lists of numbers. The following
example shows the elements of the language:
L1 = 
L2 = [1,2,3]
L3 = L1#L2
L4 = [[[1,2],3],4]
L5 = lreduce + L4
L6 = lmap - 1 L4
L7 = lfilter > 2 L4
Make the grammar so that the parser generator builds the following AST for the
| | \__[
| | | \__1
| | | \__2
| | \__3
| | \__1
- An identifier is a non-empty sequence of alphanumeric characters, not
starting by a digit.
- A number is a non-empty sequence of digits.
- An identifier cannot appear alone in an expression. Thus,
“L1=L2” is not a valid expression.
- A list literal, i.e., an expression of the form [ ... ] cannot
contain list identifiers nor operations. Just numbers and other list literals.
- The operator # cannot appear more than once in an expression. Thus
“L4 = L1#L2#L3” is not a valid expression. Furthermore, it can only be
applied to identifiers, and not arbitrary expressions.
- The print instruction can only be applied to an identifier, and
not an arbitrary expression.
- lmap, lfilter, and lreduce can only receive an
identifier as last parameter.
- The operators available for lreduce and lmap are +,
-, and *.
- The relational operators available for lfilter are >,
<, ==, and !=.